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]

Jintai Ding, Sihem Mesnager, Lih-Chung Wang. Letters for post-quantum cryptography standard evaluation. Advances in Mathematics of Communications, 2020, 14 (1) : i-i. doi: 10.3934/amc.2020012

[2]

Gerhard Frey. Relations between arithmetic geometry and public key cryptography. Advances in Mathematics of Communications, 2010, 4 (2) : 281-305. doi: 10.3934/amc.2010.4.281

[3]

Gérard Maze, Chris Monico, Joachim Rosenthal. Public key cryptography based on semigroup actions. Advances in Mathematics of Communications, 2007, 1 (4) : 489-507. doi: 10.3934/amc.2007.1.489

[4]

Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020046

[5]

Felipe Cabarcas, Daniel Cabarcas, John Baena. Efficient public-key operation in multivariate schemes. Advances in Mathematics of Communications, 2019, 13 (2) : 343-371. doi: 10.3934/amc.2019023

[6]

Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492

[7]

Roderick Melnik, B. Lassen, L. C Lew Yan Voon, M. Willatzen, C. Galeriu. Accounting for nonlinearities in mathematical modelling of quantum dot molecules. Conference Publications, 2005, 2005 (Special) : 642-651. doi: 10.3934/proc.2005.2005.642

[8]

Weinan E, Jianfeng Lu. Mathematical theory of solids: From quantum mechanics to continuum models. Discrete & Continuous Dynamical Systems - A, 2014, 34 (12) : 5085-5097. doi: 10.3934/dcds.2014.34.5085

[9]

Paolo Antonelli, Pierangelo Marcati. Quantum hydrodynamics with nonlinear interactions. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 1-13. doi: 10.3934/dcdss.2016.9.1

[10]

Gabriel Rivière. Remarks on quantum ergodicity. Journal of Modern Dynamics, 2013, 7 (1) : 119-133. doi: 10.3934/jmd.2013.7.119

[11]

Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems & Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1

[12]

Dmitry Jakobson. On quantum limits on flat tori. Electronic Research Announcements, 1995, 1: 80-86.

[13]

Jin-Cheng Jiang, Chi-Kun Lin, Shuanglin Shao. On one dimensional quantum Zakharov system. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5445-5475. doi: 10.3934/dcds.2016040

[14]

Dubi Kelmer. Quantum ergodicity for products of hyperbolic planes. Journal of Modern Dynamics, 2008, 2 (2) : 287-313. doi: 10.3934/jmd.2008.2.287

[15]

Mason A. Porter, Richard L. Liboff. The radially vibrating spherical quantum billiard. Conference Publications, 2001, 2001 (Special) : 310-318. doi: 10.3934/proc.2001.2001.310

[16]

Jianhong (Jackie) Shen, Sung Ha Kang. Quantum TV and applications in image processing. Inverse Problems & Imaging, 2007, 1 (3) : 557-575. doi: 10.3934/ipi.2007.1.557

[17]

Huai-Dong Cao and Jian Zhou. On quantum de Rham cohomology theory. Electronic Research Announcements, 1999, 5: 24-34.

[18]

Philipp Fuchs, Ansgar Jüngel, Max von Renesse. On the Lagrangian structure of quantum fluid models. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1375-1396. doi: 10.3934/dcds.2014.34.1375

[19]

Ruikuan Liu, Tian Ma, Shouhong Wang, Jiayan Yang. Thermodynamical potentials of classical and quantum systems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1411-1448. doi: 10.3934/dcdsb.2018214

[20]

Anton Stolbunov. Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves. Advances in Mathematics of Communications, 2010, 4 (2) : 215-235. doi: 10.3934/amc.2010.4.215

2018 Impact Factor: 0.879

Article outline

Figures and Tables

[Back to Top]