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 constr...

Full description

Saved in:
Bibliographic Details
Published in:Mobile networks and applications 2021-08, Vol.26 (4), p.1609-1615
Main Authors: Jing, Zhengjun, Gu, Chunsheng, Ge, Chunpeng, Shi, Peizhong
Format: Article
Language:English
Subjects:
Algorithms
Communications Engineering
Complexity
Computer Communication Networks
Computer systems
Computers
Cryptography
Electrical Engineering
Engineering
IT in Business
Logarithms
Networks
Polynomials
Quantum computers
Quantum computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 and a signature scheme. Using Shor’s quantum algorithm, we break their public key cryptosystem and signature scheme by directly solving the private key from the public key. Therefore, their public key cryptosystem and signature scheme are insecure in a quantum computer.
ISSN:1383-469X
1572-8153
DOI:10.1007/s11036-019-01498-y