-
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
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.
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. 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. |
[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. 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. |
[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. |
[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. |
[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. 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. |
[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 |
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) |
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 |
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] |
Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021021 |
[2] |
Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451 |
[3] |
Sergei Avdonin, Julian Edward. An inverse problem for quantum trees with observations at interior vertices. Networks & Heterogeneous Media, 2021, 16 (2) : 317-339. doi: 10.3934/nhm.2021008 |
[4] |
Fang Li, Jie Pan. On inner Poisson structures of a quantum cluster algebra without coefficients. Electronic Research Archive, , () : -. doi: 10.3934/era.2021021 |
[5] |
Yongming Luo, Athanasios Stylianou. On 3d dipolar Bose-Einstein condensates involving quantum fluctuations and three-body interactions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3455-3477. doi: 10.3934/dcdsb.2020239 |
[6] |
José Luis López. A quantum approach to Keller-Segel dynamics via a dissipative nonlinear Schrödinger equation. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2601-2617. doi: 10.3934/dcds.2020376 |
[7] |
Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145. |
[8] |
Iris Anshel, Derek Atkins, Dorian Goldfeld, Paul E. Gunnells. Ironwood meta key agreement and authentication protocol. Advances in Mathematics of Communications, 2021, 15 (3) : 397-413. doi: 10.3934/amc.2020073 |
[9] |
Jingni Guo, Junxiang Xu, Zhenggang He, Wei Liao. Research on cascading failure modes and attack strategies of multimodal transport network. Journal of Industrial & Management Optimization, 2021 doi: 10.3934/jimo.2020159 |
[10] |
Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021070 |
[11] |
Xianjun Wang, Huaguang Gu, Bo Lu. Big homoclinic orbit bifurcation underlying post-inhibitory rebound spike and a novel threshold curve of a neuron. Electronic Research Archive, , () : -. doi: 10.3934/era.2021023 |
[12] |
Chiara Spadafora, Riccardo Longo, Massimiliano Sala. A coercion-resistant blockchain-based E-voting protocol with receipts. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021005 |
[13] |
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 |
[14] |
Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446 |
[15] |
Luigi Barletti, Giovanni Nastasi, Claudia Negulescu, Vittorio Romano. Mathematical modelling of charge transport in graphene heterojunctions. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021010 |
[16] |
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 |
[17] |
Pankaj Kumar Tiwari, Rajesh Kumar Singh, Subhas Khajanchi, Yun Kang, Arvind Kumar Misra. A mathematical model to restore water quality in urban lakes using Phoslock. Discrete & Continuous Dynamical Systems - B, 2021, 26 (6) : 3143-3175. doi: 10.3934/dcdsb.2020223 |
[18] |
José Antonio Carrillo, Martin Parisot, Zuzanna Szymańska. Mathematical modelling of collagen fibres rearrangement during the tendon healing process. Kinetic & Related Models, 2021, 14 (2) : 283-301. doi: 10.3934/krm.2021005 |
[19] |
Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021017 |
[20] |
Alexander Dabrowski, Ahcene Ghandriche, Mourad Sini. Mathematical analysis of the acoustic imaging modality using bubbles as contrast agents at nearly resonating frequencies. Inverse Problems & Imaging, 2021, 15 (3) : 555-597. doi: 10.3934/ipi.2021005 |
2019 Impact Factor: 0.734
Tools
Metrics
Other articles
by authors
[Back to Top]