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

Lidong Chen; Dustin Moody

doi:10.3934/amc.2020013

Article Contents

2020, Volume 14, Issue 1: 161-169. Doi: 10.3934/amc.2020013

This issue Previous Article Letters for post-quantum cryptography standard evaluation Next Article Giophantus distinguishing attack is a low dimensional learning with errors problem

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
^*Corresponding author

Received: February 2019

Published: August 2019

Abstract Full Text(HTML) Figure(0) / Table(3) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 11T71, 14G50; Secondary: 94A60.

Citation:

Full Text(HTML)

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)

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Aaronson, The limits of quantum computers, Scientific American, 4649 (2007), 4-4. doi: 10.1007/978-3-540-74510-5_2.
[2]	L. Adleman, On breaking the titrated Merkle-Hellman public-key cryptosystem, in Advances in Cryptology: Crypto '82, Springer, (1982), 303–308.
[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.
[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
[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
[6]	E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, J. of Cryptology, 4 (1991), 3-72. doi: 10.1007/BF00630563.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[20]	First PQC Standardization Conference, Ft. Lauderdale, FL, April 11-13, 2018, Available at https://csrc.nist.gov/Events/2018/First-PQC-Standardization-Conference.