Table 1.
Security Categories
-
Previous Article
Giophantus distinguishing attack is a low dimensional learning with errors problem
- AMC Home
- This Issue
-
Next Article
Letters for post-quantum cryptography standard evaluation
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 |
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. |
| [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. |
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. |
| [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. |
| 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] |
Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantum-safe identity-based broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022026 |
| [3] |
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 |
| [4] |
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 |
| [5] |
Pedro Branco. A post-quantum UC-commitment scheme in the global random oracle model from code-based assumptions. Advances in Mathematics of Communications, 2021, 15 (1) : 113-130. doi: 10.3934/amc.2020046 |
| [6] |
Javier de la Cruz, Ricardo Villanueva-Polanco. Public key cryptography based on twisted dihedral group algebras. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022031 |
| [7] |
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 |
| [8] |
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 |
| [9] |
Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492 |
| [10] |
Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems and Imaging, 2021, 15 (5) : 893-928. doi: 10.3934/ipi.2021021 |
| [11] |
Weinan E, Jianfeng Lu. Mathematical theory of solids: From quantum mechanics to continuum models. Discrete and Continuous Dynamical Systems, 2014, 34 (12) : 5085-5097. doi: 10.3934/dcds.2014.34.5085 |
| [12] |
Paolo Antonelli, Pierangelo Marcati. Quantum hydrodynamics with nonlinear interactions. Discrete and Continuous Dynamical Systems - S, 2016, 9 (1) : 1-13. doi: 10.3934/dcdss.2016.9.1 |
| [13] |
Luiza H. F. Andrade, Rui F. Vigelis, Charles C. Cavalcante. A generalized quantum relative entropy. Advances in Mathematics of Communications, 2020, 14 (3) : 413-422. doi: 10.3934/amc.2020063 |
| [14] |
Gabriel Rivière. Remarks on quantum ergodicity. Journal of Modern Dynamics, 2013, 7 (1) : 119-133. doi: 10.3934/jmd.2013.7.119 |
| [15] |
Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems and Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1 |
| [16] |
Dmitry Jakobson. On quantum limits on flat tori. Electronic Research Announcements, 1995, 1: 80-86. |
| [17] |
James B. Kennedy, Jonathan Rohleder. On the hot spots of quantum graphs. Communications on Pure and Applied Analysis, 2021, 20 (9) : 3029-3063. doi: 10.3934/cpaa.2021095 |
| [18] |
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 |
| [19] |
Jin-Cheng Jiang, Chi-Kun Lin, Shuanglin Shao. On one dimensional quantum Zakharov system. Discrete and Continuous Dynamical Systems, 2016, 36 (10) : 5445-5475. doi: 10.3934/dcds.2016040 |
| [20] |
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 |
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]