Study On Multivariate Public Key Cryptosystems

The 21 st century is the era of information. With the rapid development of electronic information science and technology, information security has become so important. After electronic information science and technology, quantum and other new information science are building up and developing. But quantum computers will pose a threat to the widely-used public key cryptosystems, which are based on discrete logarithm problem(including discrete logarithm problem on Elliptic Curve Cryptosystem) and large integer factorization problem. As a consequence, public key cryptography based on post-quantum cryptography becomes a hot topic and key point. As a post-quantum public key cryptography, Multivariate Public Key Cryptosystems(MPKCs) have received more and more attention during the last twenty years.MPKC is considered to be a candidate of secure post-quantum cryptosystems, whose potential is not allowed to ignore. But the whole system of MPKC is not yet complete. As different kinds of attacks are put forward, most of MPKCs are under attack on different levels. Therefore,constructing a new and secure MPKC and improving the existing algorithms remain valuable research topics. We lay emphasis on study on MPKCs in the paper, the main achievements are as follows:1. To resist linearization attack and differential attack effectively, based on the ideas: “tame transformation” and “special oil and vinegar”, two different nonlinear invertible transformations were constructed separately. Then making use of the idea of the extended multivariate quadratic public key cryptosystem, and combining the nonlinear invertible transformations above with Matsumoto-Imai(MI) scheme, extended multivariate public key cryptosystems were proposed. Next the corresponding encryption and signature algorithms were given. Analysis results demonstrate that the extended cryptosystems inherit the merit of MI scheme, i.e., efficient computation. Meanwhile, the new extended cryptosystems can also resist the linearization attack, differential attack and algebraic attack.2. On the base of the MFE signature scheme with external perturbation, an optimized medium-field signature scheme with external perturbation was constructed by designing new external perturbations. The optimized scheme can guarantee the security, and reduce the space for the public and secret key greatly; next, considering that the original MFE encryption scheme cannot be resistant against high order linear equation attack, a new central map was redesigned by utilizing the external perturbations above, and an improved signature scheme based on external perturbation was proposed. The new signature scheme can not only keep a simple structure and an easy inversion of the original version, but also have better security.3. Considering the oil and vinegar signature cryptosystem cannot be resistant against KipnisShamir attack, by incorporate a nonlinear invertible transformation based on tame transformation with the oil and vinegar signature scheme, an improved oil and vinegar signature scheme-L-OV scheme was proposed. The L-OV scheme has small public and secret key space, and it can also resist the exhaustive attack, Kipnis-Shamir attack, and algebraic attack. Meanwhile, the L-OV scheme can satisfy the requirements of digital signature.4. By combining the Square scheme and tame transformation method, a new central map was redesigned, and a hybrid multivariate public key signature scheme-Tri-Square scheme was proposed. Analysis results show that the Tri-Square signature scheme overcomes the drawbacks of the Square scheme and tame transformation method. Meanwhile, it can also resist linearization attack, differential attack, the minrank attack and algebraic attack.