.png){kind=icon}
.png){kind=icon}
Return
A public key cryptosystem based on data complexity under quantum environment
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-015-5408-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Since the Shor algorithm showed that a quantum algorithm can efficiently calculate discrete logarithms and factorize integers, it has been used to break the RSA, EIGamal, and ECC classical public key cryptosystems. This is therefore a significant issue in the context of ensuring communication security over insecure channels. In this paper, we prove that there are no polynomial-size quantum circuits that can compute all Boolean functions (of which there are 2(2n) cases) in the standard quantum oracle model. Based on this, we propose the notion of data complexity under a quantum environment and suggest that it can be used as a condition for post-quantum computation. It is generally believed that NP-complete problems cannot be solved in polynomial time even with quantum computers. Therefore, a public key cryptosystem and signature scheme based on the difficulty of NP-complete problems and the notion of data complexity are presented here. Finally, we analyze the security of the proposed encryption and signature schemes.
Keywords:
public key cryptography
information security
NP-complete problem
complexity theory
quantum computation
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K