February  2020, 14(1): 161-169. doi: 10.3934/amc.2020013

New mission and opportunity for mathematics researchers: Cryptography in the quantum era

Computer Security Division, National Institute of Standards and Technology, Gaithersburg, MD 20899, USA

*Corresponding author

Received  February 2019 Published  August 2019

This article introduces the NIST post-quantum cryptography standardization process. We highlight the challenges, discuss the mathematical problems in the proposed post-quantum cryptographic algorithms and the opportunities for mathematics researchers to contribute.

Citation: Lidong Chen, Dustin Moody. New mission and opportunity for mathematics researchers: Cryptography in the quantum era. Advances in Mathematics of Communications, 2020, 14 (1) : 161-169. doi: 10.3934/amc.2020013
References:
[1]

S. Aaronson, The limits of quantum computers, Scientific American, 4649 (2007), 4-4.  doi: 10.1007/978-3-540-74510-5_2.  Google Scholar

[2]

L. Adleman, On breaking the titrated Merkle-Hellman public-key cryptosystem, in Advances in Cryptology: Crypto '82, Springer, (1982), 303–308. Google Scholar

[3]

Announcing request for nominations for public-key post-quantum cryptographic algorithms, Federal Register, 81 (2016), 92787–92788, Available at https://federalregister.gov/a/2016-30615. Google Scholar

[4]

E. Barker, L. Chen, A. Roginsky, A. Vassilev and R. Davis, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, NIST Special Publication (SP) 800-56A Revision 3, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2018,141 pp. Available from: https://doi.org/10.6028/NIST.SP.800-56Ar3 Google Scholar

[5]

E. Barker, L. Chen, A. Roginsky, A. Vassilev, R. Davis, S. Simon, Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography, NIST Special Publication (SP) 800-56B Revision 1, National Institute of Standards and Technology, Gaithersburg, Maryland, September 2014,121 pp. Available from: https://doi.org/10.6028/NIST.SP.800-56Br1 Google Scholar

[6]

E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.  Google Scholar

[7]

J. Buchmann, E. Dahmen and M. Szydlo, Hash-based digital signature schemes, in: Post-Quantum Cryptography (eds. D.J. Bernstein, J. Buchmann, E. Dahmen), Springer, Heidelberg, (2009), 35–93. doi: 10.1007/978-3-540-88702-7_3.  Google Scholar

[8]

C. Gentry and M. Szydlo, Cryptanalysis of the revised NTRU signature scheme, in Proceedings of Eurocrypt 2002, Lect. Notes in Comput. Sci., Springer, 2332 (2002), 299–320. doi: 10.1007/3-540-46035-7_20.  Google Scholar

[9]

L. K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on Theory of Computation, (1996), 212–219. doi: 10.1145/237814.237866.  Google Scholar

[10]

J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, in Proceedings of ANTS '98 (ed. J. Buhler), Lect. Notes in Comput. Sci. Springer, 1423 (1998), 267–288. doi: 10.1007/BFb0054868.  Google Scholar

[11]

R. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report, Jet Propulsion Laboratory, Pasadena, (1978), 42–44. Available at https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF. Google Scholar

[12]

D. Moody, Post-Quantum Cryptography Standardization: Announcement and outline of NIST's Call for Submissions, PQCrypto 2016, Fukuoka, Japan, February, (2016), 24–26, Available at https://csrc.nist.gov/Presentations/2016/Announcement-and-outline-of-NIST-s-Call-for-Submis. Google Scholar

[13]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26 (1997), 1484–1509, Available at: http://dx.doi.org/10.1137/s0036144598347011. doi: 10.1137/S0097539795293172.  Google Scholar

[14]

U. S. Department of Commerce, Data Encryption Standard (DSS), Federal Information Processing Standards (FIPS) Publication 46–3, October 1999, 22 pp. Available from: https://csrc.nist.gov/CSRC/media/Publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf. Google Scholar

[15]

U. S. Department of Commerce, Secure Hash Standard (SHS), Federal Information Processing Standards (FIPS) Publication 180–4, August 2015, 31 pp. Available from: https://doi.org/10.6028/NIST.FIPS.180-4. Google Scholar

[16]

U. S. Department of Commerce, Digital Signature Standard (DSS), Federal Information Processing Standards (FIPS) Publication 186–4, July 2003,121 pp. Available from: https://doi.org/10.6028/NIST.FIPS.186-4. Google Scholar

[17]

U. S. Department of Commerce, Advanced Encryption Standard (AES), Federal Information Processing Standards (FIPS) Publication 197, November 2001, 47 pp. Available from: https://doi.org/10.6028/NIST.FIPS.197. Google Scholar

[18]

U. S. Department of Commerce, The Keyed-Hash Message Authentication Code (HMAC), Federal Information Processing Standards (FIPS) Publication 198–1, July 2008, 7 pp. Available from: https://doi.org/10.6028/NIST.FIPS.198-1. Google Scholar

[19]

U. S. Department of Commerce, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, Federal Information Processing Standards (FIPS) Publication 202, August 2015, 29 pp. Available from: https://doi.org/10.6028/NIST.FIPS.202. Google Scholar

[20]

First PQC Standardization Conference, Ft. Lauderdale, FL, April 11-13, 2018, Available at https://csrc.nist.gov/Events/2018/First-PQC-Standardization-Conference. Google Scholar

show all references

References:
[1]

S. Aaronson, The limits of quantum computers, Scientific American, 4649 (2007), 4-4.  doi: 10.1007/978-3-540-74510-5_2.  Google Scholar

[2]

L. Adleman, On breaking the titrated Merkle-Hellman public-key cryptosystem, in Advances in Cryptology: Crypto '82, Springer, (1982), 303–308. Google Scholar

[3]

Announcing request for nominations for public-key post-quantum cryptographic algorithms, Federal Register, 81 (2016), 92787–92788, Available at https://federalregister.gov/a/2016-30615. Google Scholar

[4]

E. Barker, L. Chen, A. Roginsky, A. Vassilev and R. Davis, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, NIST Special Publication (SP) 800-56A Revision 3, National Institute of Standards and Technology, Gaithersburg, Maryland, April 2018,141 pp. Available from: https://doi.org/10.6028/NIST.SP.800-56Ar3 Google Scholar

[5]

E. Barker, L. Chen, A. Roginsky, A. Vassilev, R. Davis, S. Simon, Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization Cryptography, NIST Special Publication (SP) 800-56B Revision 1, National Institute of Standards and Technology, Gaithersburg, Maryland, September 2014,121 pp. Available from: https://doi.org/10.6028/NIST.SP.800-56Br1 Google Scholar

[6]

E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. of Cryptology, 4 (1991), 3-72.  doi: 10.1007/BF00630563.  Google Scholar

[7]

J. Buchmann, E. Dahmen and M. Szydlo, Hash-based digital signature schemes, in: Post-Quantum Cryptography (eds. D.J. Bernstein, J. Buchmann, E. Dahmen), Springer, Heidelberg, (2009), 35–93. doi: 10.1007/978-3-540-88702-7_3.  Google Scholar

[8]

C. Gentry and M. Szydlo, Cryptanalysis of the revised NTRU signature scheme, in Proceedings of Eurocrypt 2002, Lect. Notes in Comput. Sci., Springer, 2332 (2002), 299–320. doi: 10.1007/3-540-46035-7_20.  Google Scholar

[9]

L. K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on Theory of Computation, (1996), 212–219. doi: 10.1145/237814.237866.  Google Scholar

[10]

J. Hoffstein, J. Pipher and J. H. Silverman, NTRU: A ring-based public key cryptosystem, in Proceedings of ANTS '98 (ed. J. Buhler), Lect. Notes in Comput. Sci. Springer, 1423 (1998), 267–288. doi: 10.1007/BFb0054868.  Google Scholar

[11]

R. McEliece, A public-key cryptosystem based on algebraic coding theory, DSN Progress Report, Jet Propulsion Laboratory, Pasadena, (1978), 42–44. Available at https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF. Google Scholar

[12]

D. Moody, Post-Quantum Cryptography Standardization: Announcement and outline of NIST's Call for Submissions, PQCrypto 2016, Fukuoka, Japan, February, (2016), 24–26, Available at https://csrc.nist.gov/Presentations/2016/Announcement-and-outline-of-NIST-s-Call-for-Submis. Google Scholar

[13]

P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 26 (1997), 1484–1509, Available at: http://dx.doi.org/10.1137/s0036144598347011. doi: 10.1137/S0097539795293172.  Google Scholar

[14]

U. S. Department of Commerce, Data Encryption Standard (DSS), Federal Information Processing Standards (FIPS) Publication 46–3, October 1999, 22 pp. Available from: https://csrc.nist.gov/CSRC/media/Publications/fips/46/3/archive/1999-10-25/documents/fips46-3.pdf. Google Scholar

[15]

U. S. Department of Commerce, Secure Hash Standard (SHS), Federal Information Processing Standards (FIPS) Publication 180–4, August 2015, 31 pp. Available from: https://doi.org/10.6028/NIST.FIPS.180-4. Google Scholar

[16]

U. S. Department of Commerce, Digital Signature Standard (DSS), Federal Information Processing Standards (FIPS) Publication 186–4, July 2003,121 pp. Available from: https://doi.org/10.6028/NIST.FIPS.186-4. Google Scholar

[17]

U. S. Department of Commerce, Advanced Encryption Standard (AES), Federal Information Processing Standards (FIPS) Publication 197, November 2001, 47 pp. Available from: https://doi.org/10.6028/NIST.FIPS.197. Google Scholar

[18]

U. S. Department of Commerce, The Keyed-Hash Message Authentication Code (HMAC), Federal Information Processing Standards (FIPS) Publication 198–1, July 2008, 7 pp. Available from: https://doi.org/10.6028/NIST.FIPS.198-1. Google Scholar

[19]

U. S. Department of Commerce, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, Federal Information Processing Standards (FIPS) Publication 202, August 2015, 29 pp. Available from: https://doi.org/10.6028/NIST.FIPS.202. Google Scholar

[20]

First PQC Standardization Conference, Ft. Lauderdale, FL, April 11-13, 2018, Available at https://csrc.nist.gov/Events/2018/First-PQC-Standardization-Conference. Google Scholar

Table 1.  Security Categories
Categories Security Description
At least as hard to break as AES128 (exhaustive key search)
At least as hard to break as SHA256 (collision search)
At least as hard to break as AES192 (exhaustive key search)
At least as hard to break as SHA384 (collision search)
At least as hard to break as AES256 (exhaustive key search)
Categories Security Description
At least as hard to break as AES128 (exhaustive key search)
At least as hard to break as SHA256 (collision search)
At least as hard to break as AES192 (exhaustive key search)
At least as hard to break as SHA384 (collision search)
At least as hard to break as AES256 (exhaustive key search)
Table 2.  Distribution of First Round Candidates
Signature Encryption/KEM Overall
Lattice-based 5 21 26
Code-based 2 17 19
Multivariate 7 2 9
Symmetric/Hash-based 3 0 3
Other 2 5 7
Total 19 45 64
Signature Encryption/KEM Overall
Lattice-based 5 21 26
Code-based 2 17 19
Multivariate 7 2 9
Symmetric/Hash-based 3 0 3
Other 2 5 7
Total 19 45 64
Table 3.  Distribution of Second Round Candidates
Signature Encryption/KEM Overall
Lattice-based 3 9 12
Code-based 0 7 7
Multivariate 4 0 4
Symmetric/Hash-based 2 0 2
Other 0 1 1
Total 9 17 26
Signature Encryption/KEM Overall
Lattice-based 3 9 12
Code-based 0 7 7
Multivariate 4 0 4
Symmetric/Hash-based 2 0 2
Other 0 1 1
Total 9 17 26
[1]

Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021021

[2]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451

[3]

Sergei Avdonin, Julian Edward. An inverse problem for quantum trees with observations at interior vertices. Networks & Heterogeneous Media, 2021, 16 (2) : 317-339. doi: 10.3934/nhm.2021008

[4]

Fang Li, Jie Pan. On inner Poisson structures of a quantum cluster algebra without coefficients. Electronic Research Archive, , () : -. doi: 10.3934/era.2021021

[5]

Yongming Luo, Athanasios Stylianou. On 3d dipolar Bose-Einstein condensates involving quantum fluctuations and three-body interactions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3455-3477. doi: 10.3934/dcdsb.2020239

[6]

José Luis López. A quantum approach to Keller-Segel dynamics via a dissipative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2601-2617. doi: 10.3934/dcds.2020376

[7]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[8]

Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells. Ironwood meta key agreement and authentication protocol. Advances in Mathematics of Communications, 2021, 15 (3) : 397-413. doi: 10.3934/amc.2020073

[9]

Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2020159

[10]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070

[11]

Xianjun Wang, Huaguang Gu, Bo Lu. Big homoclinic orbit bifurcation underlying post-inhibitory rebound spike and a novel threshold curve of a neuron. Electronic Research Archive, , () : -. doi: 10.3934/era.2021023

[12]

Chiara Spadafora, Riccardo Longo, Massimiliano Sala. A coercion-resistant blockchain-based E-voting protocol with receipts. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021005

[13]

Baba Issa Camara, Houda Mokrani, Evans K. Afenya. Mathematical modeling of glioma therapy using oncolytic viruses. Mathematical Biosciences & Engineering, 2013, 10 (3) : 565-578. doi: 10.3934/mbe.2013.10.565

[14]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446

[15]

Luigi Barletti, Giovanni Nastasi, Claudia Negulescu, Vittorio Romano. Mathematical modelling of charge transport in graphene heterojunctions. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021010

[16]

A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909

[17]

Pankaj Kumar Tiwari, Rajesh Kumar Singh, Subhas Khajanchi, Yun Kang, Arvind Kumar Misra. A mathematical model to restore water quality in urban lakes using Phoslock. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3143-3175. doi: 10.3934/dcdsb.2020223

[18]

José Antonio Carrillo, Martin Parisot, Zuzanna Szymańska. Mathematical modelling of collagen fibres rearrangement during the tendon healing process. Kinetic & Related Models, 2021, 14 (2) : 283-301. doi: 10.3934/krm.2021005

[19]

Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021017

[20]

Alexander Dabrowski, Ahcene Ghandriche, Mourad Sini. Mathematical analysis of the acoustic imaging modality using bubbles as contrast agents at nearly resonating frequencies. Inverse Problems & Imaging, 2021, 15 (3) : 555-597. doi: 10.3934/ipi.2021005

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (693)
  • HTML views (1069)
  • Cited by (0)

Other articles
by authors

[Back to Top]