American Institute of Mathematical Sciences

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

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

Lidong Chen , and  Dustin Moody

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.

Keywords: Post-quantum cryptography, public-key cryptography, mathematical research, standarization, quantum-safe, quantum resistant.
Mathematics Subject Classification: Primary: 11T71, 14G50; Secondary: 94A60.
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)
Table Options

Download as excel

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
Table Options

Download as excel

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
Table Options

Download as excel

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]

Luiza H. F. Andrade, Rui F. Vigelis, Charles C. Cavalcante. A generalized quantum relative entropy. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020063
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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

[20]

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

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (329)
  • HTML views (903)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences