Quantum resistant public key cryptography: a survey

ABSTRACT

Public key cryptography is widely used to secure transactions over the Internet. However, advances in quantum computers threaten to undermine the security assumptions upon which currently used public key cryptographic algorithms are based. In this paper, we provide a survey of some of the public key cryptographic algorithms that have been developed that, while not currently in widespread use, are believed to be resistant to quantum computing based attacks and discuss some of the issues that protocol designers may need to consider if there is a need to deploy these algorithms at some point in the future.

References

1. M. Ajtai. The shortest vector problem in L₂ is NP-hard for randomized reductions (extended abstract). In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pages 10--19, 1998.
2. M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. In STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 284--293, 1997.
3. E. Barker, W. Barker, W. Burr, W. Polk, and M. Smid. Recommendation for key management -- part 1: General. NIST special publication 800-57, National Institute of Standards and Technology, Mar. 2007.
4. C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computation. Special Issue on Quantum Computation of the Siam Journal of Computing, Oct. 1997.
5. D. Boneh and M. Franklin. Identity-based encryption from the Weil pairing. SIAM J. of Computing, 32(3):586--615, 2003.
6. D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. In Advances in Cryptology -- ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, pages 514--532, 2001.
7. J. Buchmann, C. Coronado, M. Döring, D. Engelbert, C. Ludwig, R. Overbeck, A. Schmidt, U. Vollmer, and R.-P. Weinmann. Post-quantum signatures. Cryptology ePrint Archive, Report 2004/297, 2004.
8. J. L. Carter and M. N. Wegman. Universal classes of hash functions (extended abstract). In STOC '77: Proceedings of the ninth annual ACM symposium on Theory of computing, pages 106--112, 1977.
9. B. Chor and R. L. Rivest. A knapsack type public key cryptosystem based on arithmetic in finite fields. IEEE Transactions on Information Theory, 34(5):901--909, Sept. 1988.
10. S. Cook. The importance of the P versus NP question. Journal of the ACM, 50(1):27--29, 2003.
11. N. Courtois, M. Finiasz, and N. Sendrier. How to achieve a McEliece-based digital signature scheme. In Advances in Cryptology -- ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, pages 157--174, 2001.
12. N. T. Courtois, L. Goubin, and J. Patarin. SFLASH^v3, a fast asymmetric signature scheme. Cryptology ePrint Archive, Report 2003/211, 2003.
13. D. Deutsch and R. Jozsa. Rapid solution of problems by quantum computation. Proc Roy Soc Lond A, 439:553--558, Oct. 1992.
14. W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644--654, Nov. 1976.
15. V. Dubois, P.-A. Fouque, A. Shamir, and J. Stern. Practical cryptanalysis of SFLASH. In Advances in Cryptology -- CRYPTO 2007, 27th Annual International Cryptology Conference, pages 1--12, 2007.
16. R. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6&7):467--488, 1982.
17. FIPS 186-2. Digital Signature Standard (DSS). National Institute of Standards and Technology, Jan. 2000.
18. N. Gama and P. Q. Nguyen. New chosen-ciphertext attacks on NTRU. In Public Key Cryptography -- PKC 2007, 10th International Conference on Practice and Theory in Public-Key Cryptography, pages 89--106, 2007.
19. T. E. Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Advances in Cryptology, Proceedings of CRYPTO '84, pages 10--18, 1984.
20. L. C. C. García. On the security and the efficiency of the Merkle signature scheme. Cryptology ePrint Archive, Report 2005/192, 2005.
21. C. Gentry. Key recovery and message attacks on NTRU-composite. In Advances in Cryptology -- EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, pages 182--194, 2001.
22. C. Gentry, J. Jonsson, J. Stern, and M. Szydlo. Cryptanalysis of the NTRU signature scheme (NSS) from Eurocrypt 2001. In Advances in Cryptology -- ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, pages 1--20, 2001.
23. O. Goldreich, S. Goldwasser, and S. Halevi. Public-key cryptosystems from lattice reduction problems. In Advances in Cryptology -- CRYPTO '97, 17th Annual International Cryptology Conference, pages 112--131, 1997.
24. L. K. Grover. A fast quantum mechanical algorithm for database search. In STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212--219, 1996.
25. J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. NTRUSign: Digital signatures using the NTRU lattice. In Topics in Cryptology -- CT-RSA 2003, The Cryptographers' Track at the RSA Conference 2003, pages 122--140, 2003.
26. J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. NTRUEncrypt and NTRUSign: efficient public key algorithms for a post-quantum world. In PQCrypto 2006: International Workshop on Post-Quantum Cryptography, pages 141--158, May 2006.
27. J. Hoffstein, J. Pipher, and J. H. Silverman. NTRU: A ring-based public key cryptosystem. In Algorithmic Number Theory (ANTS-III): Proceedings of the Third International Symposium on Algorithmic Number Theory, pages 267--288, June 1998.
28. J. Hoffstein, J. Pipher, and J. H. Silverman. NSS: An NTRU lattice-based signature scheme. In Advances in Cryptology -- EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques, pages 211--228, 2001.
29. N. Howgrave-Graham. A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In Advances in Cryptology -- CRYPTO 2007, 27th Annual International Cryptology Conference, pages 150--169, 2007.
30. N. Howgrave-Graham, J. H. Silverman, A. Singer, and W. Whyte. NAEP: Provable security in the presence of decryption failures.
31. É. Jaulmes and A. Joux. A chosen-ciphertext attack against NTRU. In Advances in Cryptology -- CRYPTO 2000, 20th Annual International Cryptology Conference, pages 20--35, 2000.
32. N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48(177):203--209, 1987.
33. L. Lamport. Constructing digital signatures from a one-way function. Technical Report CSL-98, SRI International, Oct. 1979.
34. R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. Deep Space Network Progress Report 42--44, Jet Propulsion Laboratory, California Institute of Technology, pages 114--116, 1978.
35. R. C. Merkle. Security, Authentication, and Public Key Systems. PhD thesis, Stanford University, June 1979.
36. R. C. Merkle. A certified digital signature. In Advances in Cryptology -- CRYPTO '89, 9th Annual International Cryptology Conference, pages 218--238, 1989.
37. R. C. Merkle and M. E. Hellman. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory, 24(5):525--530, Sept. 1978.
38. T. Meskanen and A. Renvall. A wrap error attack against NTRUEncrypt. Discrete Applied Mathematics, 154(2):382--391, Feb. 2006.
39. D. Micciancio. Improving lattice based cryptosystems using the Hermite normal form. In Cryptography and Lattices Conference --- CaLC 2001, pages 126--145, Mar. 2001.
40. V. S. Miller. Use of elliptic curves in cryptography. In Advances in Cryptology -- CRYPTO '85, pages 417--426, 1986.
41. M. Myers, R. Ankney, A. Malpani, S. Galperin, and C. Adams. X.509 Internet Public Key Infrastructure Online Certificate Status Protocol -- OCSP. RFC 2560 (Proposed Standard), June 1999.
42. P. Q. Nguyen. A note on the security of NTRUsign. Cryptology ePrint Archive, Report 2006/387, 2006.
43. NTRU Announces Signature Algorithm, NTRUSign, viewed November 12, 2008, (http://www.ntru.com/cryptolab/intro_ntrusign.htm).
44. M. O. Rabin. Digitalized signatures and public-key functions as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science, Jan. 1979.
45. O. Regev. New lattice-based cryptographic constructions. Journal of the ACM, 51(6):899--942, Nov. 2004.
46. R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120--126, Feb. 1978.
47. S. Robinson. Emerging insights on limitations of quantum computing shape quest for fast algorithms. SIAM News, 36(1), January/February 2003.
48. C.-P. Schnorr and H. H. Hörner. Attacking the Chor-Rivest cryptosystem by improved lattice reduction. In Advances in Cryptology -- EUROCRYPT '95, International Conference on the Theory and Application of Cryptographic Techniques, pages 1--12, 1995.
49. A. Shamir. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem. In Advances in Cryptology: Proceedings of CRYPTO '82, pages 279--288, 1982.
50. C. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 28(4):656--715, 1949.
51. P. W. Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Symposium on Foundations of Computer Science, pages 124--134, 1994.
52. P. van Emde Boas. Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, University of Amsterdam, Department of Mathematics, Netherlands, 1981.
53. G. S. Vernam. US patent #1,310,719: Secret signaling system, July 1919.
54. W. Whyte. NTRUSign and P1363.1, Apr. 2006. http://grouper.ieee.org/groups/1363/WorkingGroup/presentations/P1363.1-2006-04.ppt.
55. H. C. Williams. A modification of the RSA public-key encryption procedure. IEEE Transactions on Information Theory, IT-26(6):726--729, Nov. 1980.

Index Terms

• Security and privacy

  • Cryptography

    • Public key (asymmetric) techniques

      • Public key encryption