Cryptanalysis of a Public Key Cryptosystem Based on Data Complexity Under Quantum Environment

Shor presented a quantum algorithm to factor large integers and compute discrete logarithms in polynomial time. As a result, public key cryptosystems, such as RSA, ElGamal and ECC, which are based on these computational assumptions will become insecure with the advent of quantum computers. To construct a secure anti-quantum public-key cryptosystem, Wu et al. introduced the notion of data complexity under quantum environment. Based on the hardness of NP-complete problems and data complexity, they presented a new public key cryptosystem. Using Shor’s quantum algorithm, we break their public key cryptosystem by directly solving the private key from the public key. Therefore, their public key cryptosystem is insecure in a quantum computer.