Design And Analysis Of High Order Multivariate Public Key Cryptosystem

Multivariate public key cryptosystem(MPKC) is designed to resist the quantum computer, which has attracted much interests in recent years. The operations of MPKCs are defined in some small finite fields, so there are more efficient and faster than traditional public key cryptosystems, such as RSA and DSA. However, the key sizes of MPKCs are very large, which definitely hinders their applications in practice.Hence, how to reduce the public key sizes is also a hot topic in MPKCs.Currently, almost all the existing MPKCs are quadratic. Most of them are faced with the threat of variety of attacks, such as solving the equations attack, differential cryptanalysis, linearization equations attack and rank attack etc. According to our analysis, if we increase the degree of public key polynomials to three or higher, this could make the scheme be able to avoid the threats above. It may increase the key sizes,but this kind of sacrifice in exchange for high security is feasible. In our thesis, we proposed two high degree schemes, Cubic Unbalanced Oil and Vinegar Signature(CUOV) system and Cubic Multivariate Public Key Cryptosystem(CMPKC). And we broke a New Extended Multivariate Public Key Cryptography(NEMPKC) in whose degree is quartic.There are no cross terms of oil variables in the central map of UOV signature system, so an attacker can easily separate oil and vinegar and break the scheme. We use a special transformation to reconstruct the central map with cubic degree. It is secure against the existing attacks, and its key sizes are reduced by 62% compared with the original UOV.The key idea of CMPKC is to replace the polynomial in small field with a cubic monomial in big field. The public key of new scheme becomes bigger than before, but it’s very effective to against the existing attacks. Then we implement the scheme on the Magma, and analysis its security and efficiency.The nonlinear tame transformation in the NEMPKC can hide the weakness of the original scheme. And the authors indicated that the improved scheme is able to resist the known attacks. But we find that there are many quadratization equations in the central map, which can be used to recover the encrypted message effectively. We did many experiments on Magma to verify it.