High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems

For the last three decades, public key cryptosystems, as a revolutionary break through in cryptography, have developed into an indispensable element of the modern communication system. For RSA and other number theory based cryptosystems, their security depends on the assumption about the difficulty of certain number theory problems, such as the Integer Prime Factorization Problem or the Discrete Logarithm Problem. However, due to the quantum computer attack by Shor [Sho99] and the demand for more efficient cryptosystems for small devices, there is a great challenge to build new public key cryptosystems, in particular ones that could survive future attacks utilizing quantum computers [PQ].