An attack algorithm is proposed on a finite automaton public key cryptosystem.It is proved that this attack can break FAPKCO in polynomial time.The basic idea can be used in principle to attack other FAPKCs.Therefore,...An attack algorithm is proposed on a finite automaton public key cryptosystem.It is proved that this attack can break FAPKCO in polynomial time.The basic idea can be used in principle to attack other FAPKCs.Therefore,while designing an FAPKC,it must be taken into account whether it is secure or not under this kind of attack.展开更多
Multivariate Public Key Cryptography （MPKC） has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally rega...Multivariate Public Key Cryptography （MPKC） has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally regarded as a difficult task to design a secure MPKC foundation scheme, such as an encryption scheme and key exchange scheme. In this work, we investigate the security of a new public key cryptosystem that is based on the Morphism of Polynomials （MP）. The public key cryptosystem proposed by Wang et al. （Wuhan University, China） comprises a key exchange scheme and encryption scheme. Its security can be provably reduced to the hardness of solving a new difficult problem, namely, the Decisional Multivariate Diffie Hellman （DMDH） problem. This problem Js a variant of the MP problem, which is difficult to solve by random systems. We present a proposition that reduces the DMDH problem to an easy example of the MP problem. Then, we propose an efficient algorithm for the Key Recover Attack （KRA） on the schemes of the public key cryptosystem. In practice, we are able to entirely break the cryptosystem＇s claimed parameter of 96 security levels in less than 17.252 s. Furthermore, we show that finding parameters that yield a secure and practical scheme is impossible.展开更多
This paper deals with finite automaton public key cryptosystem and digital signatures. A new system FAPKC3 is proposed which can be used for encryption and implementing digital signatures as well. Some performances o...This paper deals with finite automaton public key cryptosystem and digital signatures. A new system FAPKC3 is proposed which can be used for encryption and implementing digital signatures as well. Some performances of a software implementation of FAPKC3 are presented and its security is discussed.展开更多
FAPKC4, a public key cryptosystem based on automata theory, is generalized so that component automata of compound automata in user’s public key would not be restricted to memory finite automata. The generalized FAPKC...FAPKC4, a public key cryptosystem based on automata theory, is generalized so that component automata of compound automata in user’s public key would not be restricted to memory finite automata. The generalized FAPKCA can be used in encryption and implementing digital signatures as well.展开更多
Finding the solution to a general multivariate modular linear equation plays an important role in cryptanalysis field. Earlier results show that obtaining a relatively short solution is possible in polynomial time. Ho...Finding the solution to a general multivariate modular linear equation plays an important role in cryptanalysis field. Earlier results show that obtaining a relatively short solution is possible in polynomial time. However, one problem arises here that if the equation has a short solution in given bounded range, the results outputted by earlier algorithms are often not the ones we are interested in. In this paper, we present a probability method based on lattice basis reduction to solve the problem. For a general multivariate modular linear equation with short solution in the given bounded range, the new method outputs this short solution in polynomial time, with a high probability. When the number of unknowns is not too large （smaller than 68）, the probability is approximating 1. Experimental results show that Knapsack systems and Lu-Lee type systems are easily broken in polynomial time with this new method.展开更多
Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to ...Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to deal with nonlinear memory finite automata, and gave sufficient conditions for weak inverse andfor weakly invertible memory finite automata and inversion processes concerned;methods by transformation to generate a kind of nonlinear memory finite automatasatisfying one of these sufficient conditions were also given. This paper extends theconcepts, methods and results to general finite automata, in which states consist offinite input history, finite output history and finite 'inner state' history.展开更多
基金Project supported by the National Natural Science Foundation of China.
文摘An attack algorithm is proposed on a finite automaton public key cryptosystem.It is proved that this attack can break FAPKCO in polynomial time.The basic idea can be used in principle to attack other FAPKCs.Therefore,while designing an FAPKC,it must be taken into account whether it is secure or not under this kind of attack.
文摘Multivariate Public Key Cryptography （MPKC） has intensively and rapidly developed during the past three decades. MPKC is a promising candidate for post-quantum cryptography. However, designing it is universally regarded as a difficult task to design a secure MPKC foundation scheme, such as an encryption scheme and key exchange scheme. In this work, we investigate the security of a new public key cryptosystem that is based on the Morphism of Polynomials （MP）. The public key cryptosystem proposed by Wang et al. （Wuhan University, China） comprises a key exchange scheme and encryption scheme. Its security can be provably reduced to the hardness of solving a new difficult problem, namely, the Decisional Multivariate Diffie Hellman （DMDH） problem. This problem Js a variant of the MP problem, which is difficult to solve by random systems. We present a proposition that reduces the DMDH problem to an easy example of the MP problem. Then, we propose an efficient algorithm for the Key Recover Attack （KRA） on the schemes of the public key cryptosystem. In practice, we are able to entirely break the cryptosystem＇s claimed parameter of 96 security levels in less than 17.252 s. Furthermore, we show that finding parameters that yield a secure and practical scheme is impossible.
基金the Chinese Academy of Sciences the National Natural Science Foundationof China
文摘This paper deals with finite automaton public key cryptosystem and digital signatures. A new system FAPKC3 is proposed which can be used for encryption and implementing digital signatures as well. Some performances of a software implementation of FAPKC3 are presented and its security is discussed.
文摘FAPKC4, a public key cryptosystem based on automata theory, is generalized so that component automata of compound automata in user’s public key would not be restricted to memory finite automata. The generalized FAPKCA can be used in encryption and implementing digital signatures as well.
基金Supported by the National Natural Science Foundation of China (Grant Nos. 60873249, 60973142)the National High-Tech Research & Development Program of China (Grant Nos. 2008AA10Z419, 2009AA011906)the Project Funded by Basic Research Foundation of School of Information Science and Technology of Tsinghua University
文摘Finding the solution to a general multivariate modular linear equation plays an important role in cryptanalysis field. Earlier results show that obtaining a relatively short solution is possible in polynomial time. However, one problem arises here that if the equation has a short solution in given bounded range, the results outputted by earlier algorithms are often not the ones we are interested in. In this paper, we present a probability method based on lattice basis reduction to solve the problem. For a general multivariate modular linear equation with short solution in the given bounded range, the new method outputs this short solution in polynomial time, with a high probability. When the number of unknowns is not too large （smaller than 68）, the probability is approximating 1. Experimental results show that Knapsack systems and Lu-Lee type systems are easily broken in polynomial time with this new method.
文摘Ra, Rb transformations were successfully applied to establish invertibility theory for linear and quasi-linear finite automata over finite fields. In aprevious paper, the authors generalized R., Rb transformations to deal with nonlinear memory finite automata, and gave sufficient conditions for weak inverse andfor weakly invertible memory finite automata and inversion processes concerned;methods by transformation to generate a kind of nonlinear memory finite automatasatisfying one of these sufficient conditions were also given. This paper extends theconcepts, methods and results to general finite automata, in which states consist offinite input history, finite output history and finite 'inner state' history.
