Abstract
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^{{2^n}}}\) 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Deutsch D, Jozsa R. Rapid solution of problems by quantum computation. Math Phys Sci, 1992, 439: 553–558
Bernstein E, Vazirani U. Quantum complexity theory. SIAM J Comput, 1997, 26: 1411–1473
Simon D R. On the power of quantum computation. SIAM J Comput, 1997, 26: 1474–1483
Grover L K. Quantum mechanics helps in searching for a needle in haystack. Phys Rev Lett, 1997, 79: 325–328
Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput, 1997, 26: 1484–1509
Mosca M, Ekert A. The hidden subgroup problem and eigenvalue estimation on a quantum computer. In: Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communication. Berlin: Springer, 1999
Hallgren S, Russell A, Ta-Shma A. The hidden subgroup problem and quantum computation using group representations. SIAM J Comput, 2003, 32: 916–934
Bennett C H, Brassard G. Quantum cryptography:public key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalor, 1984. 10–12
Bennett C H, Brassard G, Crépeau C, et al. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Phys Rev Lett, 1993, 70: 1895–1899
Bennett C H, DiVincenzo D P, Smolin J A, et al. Mixed-state entanglement and quantum error correction. Phys Rev A, 1996, 54: 3824–3851
Leung D W. Quantum vernam cipher. Quantum Inf Comput, 2002, 2: 14–34
Shi J J, Shi R H, Guo Y, et al. Batch proxy quantum blind signature scheme. Sci China Inf Sci, 2013, 56: 052115
Xiao F Y, Chen H W. Construction of minimal trellises for quantum stabilizer codes. Sci China Inf Sci, 2013, 56: 012306
Gehani A, Labean T H, Reif J H. DNA-based cryptography. In: Proceedings of the 5th Annual Meeting on DNA Based Computers, Cambridge, 2003. 233–249
Lu M X, Lai X J, Xiao G Z, et al. A symmetric key cryptography with DNA technology. Sci China Ser F-Inf Sci, 2007, 50: 324–333
Lai X J, Lu M X, Qin L, et al. Asymmetric encryption and signature method with DNA technology. Sci China Inf Sci, 2010, 53: 506–514
Okamoto T, Tanaka K, Uchiyama S. Quantum public-key cryptosystems. In: Proceedings of 20th Annual International Cryptology Conference, Santa Barbara, 2000. 147–165
Bernstein D J, Buchmann J, Dahmen E. Post-quantum Cryptography. Berlin: Springer, 2000
Wang H Z, Zhang H G, Wang Z Y, et al. Extended multivariate public key cryptosystems with secure encryption function. Sci China Inf Sci, 2011, 54: 1161–1171
Mu L W, Liu X C, Liang C L. Improved construction of LDPC convolutional codes with semi-random parity-check matrices. Sci China Inf Sci, 2014, 57: 022304
Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems. J Cryptol, 1991, 4: 3–72
Biham E, Shamir A. Differential cryptanalysis of the full 16-round DES. In: Proceedings of the 12th Annual International Cryptology Conference, Santa Barbara, 1993. 487–496
Feng D G. Cryptanalysis (in Chinese). Beijing: Tsinghua University Press, 2000
Bennett C H, Brassard G, Vazirani U, et al. Strengths and weaknesses of quantum computing. SIAM J Comput, 1997, 26: 1510–1523
Sleator T, Weinfurter H. Realizable universal quantum logic gates. Phys Rev Lett, 1995, 74: 4087–4090
Barenco A, Deutsch D, Ekert A, et al. Conditional quantum dynamics and logic gates. Phys Rev Lett, 1995, 74: 4083–4086
Monroe C, Meekhof D M, King B E, et al. Demonstration of a fundamental quantum logic gate. Phys Rev Lett, 1995, 75: 4714–4717
Vedral V V, Barenco A, Ekert A. Quantum networks for elementary arithmetic operations. Phys Rev A, 1996, 54: 147–153
Beckman D, Chari A N, Devabhaktuni S, et al. Efficient networks for quantum factoring. Phys Rev A, 1996, 54: 1034–1063
Christof Z. Fast versions of Shor’s quantum factoring algorithm. arXiv: quant-ph/9806084
Parker S, Plenio M B. Efficient factorization with a single pure qubit and logN mixed qubits. Phys Rev Lett, 2000, 85: 3049–3052
Susan L. Protecting Information: from Classical Error Correction to Quantum Cryptograph. Cambridge: Cambridge University Press, 2006
de Riedmatten H, Afzelius M, Staudt M U, et al. A solid-state light-matter interface at the single-photon level. Nature, 2008, 456: 773–777
Mariantoni M, Wang H, Yamamoto T, et al. Implementing the quantum von Neumann architecture with superconducting circuits. Science, 2011, 334: 61–65
Kashefi E, Kent A, Vedral V, et al. Comparison of quantum oracles. Phys Rev A, 2002, 65: 050304
Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010
Hastad J. Tensor rank is NP-complete. J Algorithms, 1990, 11: 644–654
Hillar C J, Lim L-H. Most tensor problems are NP hard. J ACM, 2013, 60: 45
Mao S, Zhang H G, Wu W Q, et al. A resistant quantum key exchange protocol and its corresponding encryption scheme. China Commun, 2014, 11: 124–134
Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: Wiley, 1996
Wu W Q, Zhang H G, Mao S W, et al. Quantum algorithm to find invariant linear structure of MD hash functions. Quantum Inf Process, 2015, 14: 813–829
Wu W Q, Zhang H G, Wang H Z, et al. Polynomial-time quantum algorithms for finding the linear structures of Boolean function. Quantum Inf Process, 2015, 14: 1215–1226
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wu, W., Zhang, H., Wang, H. et al. A public key cryptosystem based on data complexity under quantum environment. Sci. China Inf. Sci. 58, 1–11 (2015). https://doi.org/10.1007/s11432-015-5408-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-015-5408-5