[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

  • Review Article
  • Published:

Post-quantum cryptography

Nature volume 549, pages 188–194 (2017)Cite this article

Subjects

Abstract

Cryptography is essential for the security of online communication, cars and implanted medical devices. However, many commonly used cryptosystems will be completely broken once large quantum computers exist. Post-quantum cryptography is cryptography under the assumption that the attacker has a large quantum computer; post-quantum cryptosystems strive to remain secure even in this scenario. This relatively young research area has seen some successes in identifying mathematical operations for which quantum algorithms offer little advantage in speed, and then building cryptographic systems around those. The central challenge in post-quantum cryptography is to meet demands for cryptographic usability and flexibility without sacrificing confidence.

Access through your institution
Buy or subscribe

This is a preview of subscription content, access via your institution

Access options

Access through your institution

Buy this article

  • Purchase on SpringerLink
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

Figure 1: Perspective view of a 9 × 9 × 9 subset of a non-orthogonal three-dimensional lattice.
Figure 2: Merkle tree with public key Y15 to sign eight messages.

Similar content being viewed by others

References

  1. Rivest, R. L., Shamir, A. & Adleman, L. M. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21, 120–126 (1978)

    Article  MathSciNet  Google Scholar 

  2. Shor, P. W. Algorithms for quantum computation: discrete logarithms and factoring. In Proc. 35th Ann. Symp. on Foundations of Computer Science (FOCS ’94) 124–134 (IEEE, 1994)

  3. Beauregard, S. Circuit for Shor’s algorithm using 2n + 3 qubits. Quantum Inf. Comput. 3, 175–185 (2003)

    MathSciNet  MATH  Google Scholar 

  4. Miller, V. S. Use of elliptic curves in cryptography. In Advances in Cryptology, Proc. CRYPTO ’85 (ed. Williams, H. C.) 417–426 (Springer, 1985)

  5. Koblitz, N. Elliptic curve cryptosystems. Math. Comput. 48, 203–209 (1987)

    Article  MathSciNet  Google Scholar 

  6. Campbell, E. T., Terhal, B. M. & Vuillot, C. Roads towards fault-tolerant universal quantum computation. Nature http://dx.doi.org/10.1038/nature23460 (2017)

  7. Grover, L. K. A fast quantum mechanical algorithm for database search. In Proc. 28th Ann. ACM Symp. on Theory of Computing (ed. Miller, G. L. ) 212–219 (ACM, 1996)

  8. Daemen, J. & Rijmen, V. The Design of Rijndael: AES—The Advanced Encryption Standard (Springer, 2002)

  9. Grassl, M., Langenberg, B., Roetteler, M. & Steinwandt, R. Applying Grover’s algorithm to AES: quantum resource estimates. In Post-Quantum Cryptography, Proc. 7th International Workshop (PQCRYPTO 2016) (ed. Takagi, T. ) 29–43 (Springer, 2016)

  10. Rostovtsev, A. & Stolbunov, A. Public-key cryptosystem based on isogenies. Preprint at https://eprint.iacr.org/2006/145 (2006)

  11. Couveignes, J.-M. Hard homogeneous spaces (2006). Preprint at https://eprint.iacr.org/2006/291

  12. Jao, D. & de Feo, L. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In Post-Quantum Cryptography, Proc. 4th International Workshop (PQCRYPTO 2011) (ed. Yang, B.-Y. ) 19–34 (Springer, 2011)

  13. Kuperberg, G. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM J. Comput. 35, 170–188 (2005)

    Article  MathSciNet  Google Scholar 

  14. McEliece, R. J. A Public-Key Cryptosystem based on Algebraic Coding Theory. Deep Space Network Progress Report 42–44 http://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF (1978)

  15. Bernstein, D. J., Lange, T. & Peters, C. Attacking and defending the McEliece cryptosystem. In Post-Quantum Cryptography, Proc. 2nd International Workshop (PQCRYPTO 2008) (eds Buchmann, J. A. & Ding, J. ) 31–46 (Springer, 2008)

  16. Bernstein, D. J. Grover vs. McEliece. In Post-Quantum Cryptography, Proc. 3rd International Workshop (PQCRYPTO 2010) (ed. Sendrier, N. ) 73–80 (Springer, 2010)

  17. Niederreiter, H. Knapsack-type cryptosystems and algebraic coding theory. Probl. Control Inform. 15, 159–166 (1986)

    MathSciNet  MATH  Google Scholar 

  18. Hoffstein, J., Pipher, J. & Silverman, J. H. NTRU: a ring-based public key cryptosystem. In Algorithmic Number Theory, Proc. 3rd International Symp. (ANTS-III) (ed. Buhler, J. ) 267–288 (Springer, 1998)

  19. Lyubashevsky, V., Peikert, C. & Regev, O. On ideal lattices and learning with errors over rings. J. ACM 60, 43:1–43:35 (2013)

    Article  MathSciNet  Google Scholar 

  20. Campbell, P., Groves, M. & Shepherd, D. Soliloquy: a cautionary tale. http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Systems_and_Attacks/S07_Groves_Annex.pdf (2014)

  21. Biasse, J.-F. & Song, F. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In Proc. 27th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA 2016) (ed. Krauthgamer, R. ) 893–902 (SIAM, 2016). An extension of Shor’s algorithm breaks some lattice-based systems

  22. Cramer, R., Ducas, L. & Wesolowski, B. Short Stickelberger class relations and application to Ideal-SVP. In Advances in Cryptology, Proc. Ann. International Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2017) 324–348 (Springer, 2017)

  23. Bernstein, D. J. A subfield-logarithm attack against ideal lattices. The cr.yp.to blog https://blog.cr.yp.to/20140213-ideal.html (2014)

  24. Bernstein, D. J., Chuengsatiansup, C., Lange, T. & van Vredendaal, C. NTRU Prime. Preprint at https://eprint.iacr.org/2016/461 (2016)

  25. Laarhoven, T. Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In Advances in Cryptology, Proc. 35th Ann. Cryptology Conf. (CRYPTO 2015) (eds Gennaro, R. & Robshaw, M. ) 3–22 (Springer, 2015)

  26. Laarhoven, T. & de Weger, B. Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. In Progress in Cryptology, Proc. 4th International Conf. on Cryptology and Information Security in Latin America (LATINCRYPT 2015) (eds Lauter, K. E. & Rodríguez-Henríquez, F. ) 101–118 (Springer, 2015)

  27. Becker, A., Ducas, L., Gama, N. & Laarhoven, T. New directions in nearest neighbor searching with applications to lattice sieving. In Proc. 27th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA 2016) (ed. Krauthgamer, R. ) 10–24 (SIAM, 2016)

  28. Regev, O. On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56, 34:1–34:40 (2009)

    Article  MathSciNet  Google Scholar 

  29. Goldreich, O., Goldwasser, S. & Halevi, S. Public-key cryptosystems from lattice reduction problems. In Advances in Cryptology, Proc. 17th Ann. International Cryptology Conf. (CRYPTO’97) (ed. Kaliski, B. S. Jr ) 112–131 (Springer, 1997)

  30. Hoffstein, J., Pipher, J. & Silverman, J. H. NSS: an NTRU lattice-based signature scheme. In Advances in Cryptology, Proc. International Conf. on the Theory and Application of Cryptographic Techniques (EUROCRYPT 2001) (ed. Pfitzmann, B. ) 211–228 (Springer, 2001)

  31. Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J. H. & Whyte, W. NTRUSIGN: digital signatures using the NTRU lattice. In Topics in Cryptology, Proc. Cryptographers’ Track at the RSA Conf. 2003 (CT-RSA 2003) (ed. Joye, M. ) 122–140 (Springer, 2003)

  32. Nguyen, P. Q. & Regev, O. Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures. In Advances in Cryptology, Proc. 25th Ann. International Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2006) (ed. Vaudenay, S. ) 271–288 (Springer, 2006)

  33. Ducas, L. & Nguyen, P. Q. Learning a zonotope and more: cryptanalysis of NTRUSign countermeasures. In Advances in Cryptology, Proc. 18th International Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2012) (eds Wang, X. & Sako, K. ) 433–450 (Springer, 2012)

  34. Lyubashevsky, V. Lattice signatures without trapdoors. In Advances in Cryptology, Proc. 31st Ann. International Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2012) (eds Pointcheval, D. & Johansson, T. ) 738–755 (Springer, 2012)

  35. Ducas, L., Durmus, A., Lepoint, T. & Lyubashevsky, V. Lattice signatures and bimodal Gaussians. In Advances in Cryptology, Proc. 33rd Ann. Cryptology Conf. (CRYPTO 2013) (eds Canetti, R. & Garay, J. A. ) 40–56 (Springer, 2013)

  36. Groot Bruinderink, L., Hülsing, A., Lange, T. & Yarom, Y. Flush, Gauss, and reload: a cache attack on the BLISS lattice-based signature scheme. In Cryptographic Hardware and Embedded Systems, Proc. 18th International Conf. (CHES 2016) (eds Gierlichs, B. & Poschmann, A. Y. ) 323–345 (Springer, 2016). First successful side-channel attacks against lattice-based signatures

  37. Matsumoto, T. & Imai, H. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In Advances in Cryptology, Proc. Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT’88) (ed. Günther, C. G. ) 419–453 (Springer, 1988)

  38. Patarin, J. Cryptanalysis of the Matsumoto and Imai public key scheme of Eurocrypt’88. In Advances in Cryptology, Proc. 15th Ann. International Cryptology Conf. (CRYPTO’95) (ed. Coppersmith, D. ) 248–261 (Springer, 1995)

    Chapter  Google Scholar 

  39. Patarin, J. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In Advances in Cryptology, Proc. International Conf. on the Theory and Application of Cryptographic Techniques (EUROCRYPT’96) (ed. Maurer, U. M. ) 33–48 (Springer, 1996)

  40. Petzoldt, A., Chen, M.-S., Yang, B.-Y., Tao, C. & Ding, J. Design principles for HFEv-based multivariate signature schemes. In Advances in Cryptology, Proc. 21st International Conf. on the Theory and Application of Cryptology and Information Security (ASIACRYPT 2015) (eds Iwata, T. & Cheon, J. H.) 311–334 (Springer, 2015).Optimizes conservative multivariate-quadratic signatures

  41. Lamport, L. Constructing Digital Signatures from a One Way Function. Technical Report No. SRI-CSL-98 (SRI International Computer Science Laboratory, 1979); available at http://lamport.azurewebsites.net/pubs/pubs.html#dig-sig

  42. Diffie, W. & Hellman, M. E. New directions in cryptography. IEEE Trans. Inf. Theory 22, 644–654 (1976)

    Article  MathSciNet  Google Scholar 

  43. Merkle, R. C. Secrecy, Authentication, and Public Key Systems. PhD thesis, Stanford Univ., http://www.merkle.com/papers/Thesis1979.pdf (1979)

  44. Merkle, R. C. A certified digital signature. In Advances in Cryptology, Proc. 9th Ann. International Cryptology Conf. (CRYPTO ’89) (ed. Brassard, G. ) 218–238 (Springer, 1989)

  45. Dods, C., Smart, N. P. & Stam, M. Hash based digital signature schemes. In Cryptography and Coding, Proc. 10th IMA International Conf. (ed. Smart, N. P. ) 96–115 (Springer, 2005)

  46. Hülsing, A. W-OTS+—shorter signatures for hash-based signature schemes. In Progress in Cryptology, Proc. 6th International Conf. on Cryptology in Africa (AFRICACRYPT 2013) (eds Youssef, A., Nitaj, A. & Hassanien, A. E. ) 173–188 (Springer, 2013)

  47. Buchmann, J. A., Dahmen, E. & Hülsing, A. XMSS—a practical forward secure signature scheme based on minimal security assumptions. In Post-Quantum Cryptography, Proc. 4th International Workshop (PQCRYPTO 2011) (ed. Yang, B.-Y. ) 117–129 (Springer, 2011).Conservative stateful hash-based signatures are small and fast

  48. Hülsing, A., Rausch, L. & Buchmann, J. A. Optimal parameters for XMSSMT. In Security Engineering and Intelligence Informatics, Proc. CD-ARES 2013 Workshops: MoCrySEn and SeCIHD (eds Cuzzocrea, A. et al.) 194–208 (Springer, 2013)

  49. Langley, A. Hash based signatures. Imperial Violethttps://www.imperialviolet.org/2013/07/18/hashsig.html (2013)

  50. Bernstein, D. J. et al. SPHINCS: practical stateless hash-based signatures. In Advances in Cryptology, Proc. 34th Ann. International Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2015) (eds Oswald, E. & Fischlin, M.) 368–397 (Springer, 2015). Conservative stateless hash-based signatures are practical

  51. Kocher, P. C. Timing attacks on implementations of Diffie–Hellman, RSA, DSS, and other systems. In Advances in Cryptology, Proc. 16th Ann. International Cryptology Conf. (CRYPTO ’96) (ed. Koblitz, N. ) 104–113 (Springer, 1996)

    Chapter  Google Scholar 

  52. Kocher, P. C., Jaffe, J. & Jun, B. Differential power analysis. In Advances in Cryptology, Proc. 19th Ann. International Cryptology Conf. (CRYPTO ’99) (ed. Wiener, M. J. ) 388–397 (Springer, 1999)

  53. Bernstein, D. J., Chou, T. & Schwabe, P. McBits: fast constant-time code-based cryptography. In Cryptographic Hardware and Embedded Systems, Proc. 15th International Workshop (CHES 2013) (eds Bertoni, G. & Coron, J.-S. ) 250–272 (Springer, 2013). Conservative code-based encryption is faster than ECC

  54. PQCRYPTO Project. Initial Recommendations of Long-Term Secure Post-Quantum Systems. https://pqcrypto.eu.org/docs/initial-recommendations.pdf (2015)

  55. Braithwaite, M. Experimenting with post-quantum cryptography. Google Security Blog. https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html (2016)

  56. Alkim, E., Ducas, L., Pöppelmann, T. & Schwabe, P. Post-quantum key exchange—a new hope. In 25th USENIX Security Symp. (USENIX Security 16) (eds Holz, T. & Savage, S.) 327–343 (USENIX Association, 2016)

  57. Langley, A. CECPQ1 results. Imperial Violethttps://www.imperialviolet.org/2016/11/28/cecpq1.html (2016)

  58. Bernstein, D. J. The Salsa20 family of stream ciphers. In New Stream Cipher Designs: The eSTREAM Finalists (eds Robshaw, M. J. B. & Billet, O. ) 84–97 (Springer, 2008)

  59. McGrew, D. A. & Viega, J. The security and performance of the Galois/counter mode (GCM) of operation. In Progress in Cryptology, Proc. 5th International Conf. on Cryptology in India (INDOCRYPT 2004) (eds Canteaut, A. & Viswanathan, K. ) 343–355 (Springer, 2004)

  60. Bernstein, D. J. The Poly1305-AES message-authentication code. In Fast Software Encryption, Proc. 12th International Workshop (FSE 2005) (eds Gilbert, H. & Handschuh, H. ) 32–49 (Springer, 2005)

  61. NIST Information Technology Laboratory. Secure Hash Standard (SHS). Federal Information Processing Standards Publication 180-4, http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180–4.pdf (NIST, 2012)

  62. Bertoni, G., Daemen, J., Peeters, M. & Assche, G. V. Keccak. In Advances in Cryptology, Proc. 32nd Ann. International Conf. on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2013) (eds Johansson, T. & Nguyen, P. Q. ) 313–314 (Springer, 2013)

  63. ElGamal, T. A public key cryptosystem and a signature scheme based on discrete logarithms. In Advances in Cryptology, Proc. CRYPTO ’84 (eds Blakley, G. R. & Chaum, D. ) 10–18 (Springer, 1984)

  64. Schnorr, C.-P. Efficient identification and signatures for smart cards. In Advances in Cryptology, Proc. 9th Ann. International Cryptology Conf. (CRYPTO ’89) (ed. Brassard, G. ) 239–252 (Springer, 1989)

  65. Bernstein, D. J. Curve25519: new Diffie–Hellman speed records. In Public Key Cryptography, Proc. 9th International Conf. on Theory and Practice of Public-Key Cryptography (PKC 2006) (eds Yung, M. et al.) 207–228 (Springer, 2006)

  66. Johnson, D., Menezes, A. & Vanstone, S. A. The elliptic curve digital signature algorithm (ECDSA). Int. J. Inf. Sec. 1, 36–63 (2001)

    Article  Google Scholar 

  67. Bernstein, D. J., Duif, N., Lange, T., Schwabe, P. & Yang, B.-Y. High-speed high-security signatures. J. Cryptographic Eng. 2, 77–89 (2012)

    Article  Google Scholar 

Download references

Acknowledgements

We thank A. Hülsing and B.-Y. Yang for their comments. Author list is in alphabetical order; see https://www.ams.org/profession/leaders/culture/CultureStatement04.pdf. This work was supported by the European Commission under Contract ICT-645622 PQCRYPTO; by the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005; and by the US National Science Foundation under grant 1314919. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (or other funding agencies).

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Illinois at Chicago, Chicago, 60607-7045, Illinois, USA

    Daniel J. Bernstein

  2. Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, Eindhoven, 5612 AZ, The Netherlands

    Tanja Lange

Authors
  1. Daniel J. Bernstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tanja Lange
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

D.J.B. and T.L. jointly inventoried the space of cryptographic systems, selected specific systems and quantum algorithms to cover, decided on the organization, and wrote text. No new experiments were performed.

Corresponding author

Correspondence to Tanja Lange.

Ethics declarations

Competing interests

The authors declare no competing financial interests.

Additional information

Publisher's note: Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

PowerPoint slides

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bernstein, D., Lange, T. Post-quantum cryptography. Nature 549, 188–194 (2017). https://doi.org/10.1038/nature23461

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1038/nature23461

This article is cited by

Search

Advanced search

Quick links

Nature Briefing AI and Robotics

Sign up for the Nature Briefing: AI and Robotics newsletter — what matters in AI and robotics research, free to your inbox weekly.

Get the most important science stories of the day, free in your inbox. Sign up for Nature Briefing: AI and Robotics