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]

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

[2]

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

[3]

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

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (673)
  • HTML views (1060)
  • Cited by (0)

Other articles
by authors

[Back to Top]