Research Article
Cryptanalysis of a Public Key Cryptosystem Based on Data Complexity Under Quantum Environment
@INPROCEEDINGS{10.1007/978-3-030-21373-2_32, author={Zhengjun Jing and Chunsheng Gu and Peizhong Shi}, title={Cryptanalysis of a Public Key Cryptosystem Based on Data Complexity Under Quantum Environment}, proceedings={Security and Privacy in New Computing Environments. Second EAI International Conference, SPNCE 2019, Tianjin, China, April 13--14, 2019, Proceedings}, proceedings_a={SPNCE}, year={2019}, month={6}, keywords={Public-key cryptosystem Data complexity Quantum algorithm Discrete logarithm Integer factorization}, doi={10.1007/978-3-030-21373-2_32} }- Zhengjun Jing
Chunsheng Gu
Peizhong Shi
Year: 2019
Cryptanalysis of a Public Key Cryptosystem Based on Data Complexity Under Quantum Environment
SPNCE
Springer
DOI: 10.1007/978-3-030-21373-2_32
Abstract
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.
