Post-Quantum Cryptography and Multivariate Public Key Cryptosystem

Abstract

The emergence of quantum computer is now becoming a threat to current cryptosystem. Earlier, Shor proved that widely used RSA public key cryptosystem can be solved in polynomial time by quantum computation algorithm, which makes us consider the safety of other existing cryptosystems known to be safe for classical computer algorithm. This paper presents mathematical and systematic explanations of the relation between quantum computation and cryptographic security, briefly examines the safety of existing cryptosystems and reviews the efficiency and security of several multivariate polynomial-based cryptosystems(MPKC) with implementation of Matsumoto-Imai Cryptosystem on computer. As a result, it has been shown that MPKC is efficient under limited computing power. However, it has been also found that the research on the compatibility as a post-quantum cryptosystem and the security against the other threats are still insufficient. Therefore we conclude that MPKC should be studied with persistent interest.