Post-Quantum Security: Origin, Fundamentals, and Adoption
Article Sidebar
Main Article Content
Abstract
Based on Shor’s quantum algorithm for computing discrete logarithms, powerful enough quantum computers will break current cryptographic protocols. While today’s quantum computers are not yet capable enough of running this algorithm successfully, it is expected by many experts that they will be capable enough in the foreseeable future. Thus, actions must be taken to create a new infrastructure that protects society and companies against such attacks. In this contribution, we describe the backgrounds necessary to comprehend these actions.
We first describe the relation between discrete logarithms and two well-known asymmetric security schemes, RSA and Elliptic Curve Cryptography. Next, we present the foundations of lattice-based cryptography which is the basis of schemes that are considered to be safe against attacks by quantum algorithms (as well as by classical algorithms). Then we describe two such quantum-safe algorithms (Kyber and Dilithium) in more detail. Finally, we give a very brief and selective overview of a few actions currently taken by governments and industry as well as standardization in this area. The article has a pedagogical character, not presenting any new research results. Especially it strives towards being self-contained, e.g. the required mathematical foundations to understand post-quantum cryptography are provided and examples are given. Thus, a reader interested in getting a first comprehensive overview of the subject doesn’t have to consult text books or several research papers.
Downloads
Article Details
Copyright (c) 2024 Barzen J, et al.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Licensing and protecting the author rights is the central aim and core of the publishing business. Peertechz dedicates itself in making it easier for people to share and build upon the work of others while maintaining consistency with the rules of copyright. Peertechz licensing terms are formulated to facilitate reuse of the manuscripts published in journals to take maximum advantage of Open Access publication and for the purpose of disseminating knowledge.
We support 'libre' open access, which defines Open Access in true terms as free of charge online access along with usage rights. The usage rights are granted through the use of specific Creative Commons license.
Peertechz accomplice with- [CC BY 4.0]
Explanation
'CC' stands for Creative Commons license. 'BY' symbolizes that users have provided attribution to the creator that the published manuscripts can be used or shared. This license allows for redistribution, commercial and non-commercial, as long as it is passed along unchanged and in whole, with credit to the author.
Please take in notification that Creative Commons user licenses are non-revocable. We recommend authors to check if their funding body requires a specific license.
With this license, the authors are allowed that after publishing with Peertechz, they can share their research by posting a free draft copy of their article to any repository or website.
'CC BY' license observance:
|
License Name |
Permission to read and download |
Permission to display in a repository |
Permission to translate |
Commercial uses of manuscript |
|
CC BY 4.0 |
Yes |
Yes |
Yes |
Yes |
The authors please note that Creative Commons license is focused on making creative works available for discovery and reuse. Creative Commons licenses provide an alternative to standard copyrights, allowing authors to specify ways that their works can be used without having to grant permission for each individual request. Others who want to reserve all of their rights under copyright law should not use CC licenses.
Shor PW. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Sci. Statist. Comput. 1997;26. Available from: https://doi.org/10.1137/S0097539795293172
Rivest R, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Comm. ACM. 1978;21(2):120-126. Available from: https://doi.org/10.1145/359340.359342
Nielsen MA, Chuang IL. Quantum Computation and Quantum Information. Cambridge University Press; 2016.
McLeman C, McNicholas E, Starr C. Explorations in Number Theory. Springer Nature; 2022. Available from: https://books.google.co.in/books/about/Explorations_in_Number_Theory.html?id=G7OiEAAAQBAJ&redir_esc=y
Delfs H, Knebl H. Introduction to cryptography. 2nd ed. Springer; 2015.
Rubinstein-Salzedo S, editor. The Vigenère Cipher. In: Cryptography. Springer Undergraduate Mathematics Series. Springer; 2018;41-54. Available from: https://doi.org/10.1007/978-3-319-94818-8_5
Barzen J, Leymann F. Continued fractions and probability estimations in Shor’s algorithm: A detailed and self-contained treatise. Appl Math. 2022;2(3):393–432. Available from: https://doi.org/10.3390/appliedmath2030023
Gidney C, Ekara M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum. 2021;5:433. Available from: https://doi.org/10.22331/q-2021-04-15-433
Roetteler M, Naehrig M, Svore KM, Lauter K. Quantum resource estimates for computing elliptic curve discrete logarithms. 2017. Available from: https://arxiv.org/abs/1706.06752
Cleland AN. An introduction to the surface code. SciPost Phys Lect Notes. 2022;49:1–34. Available from: https://scipost.org/SciPostPhysLectNotes.49
Bravyi S, Cross AW, Gambetta JM, Maslov D, Rall P, Yoder TJ. High-threshold and low-overhead fault-tolerant quantum memory. arXiv. 2024 Aug 30. Available from: https://arxiv.org/abs/2308.07915
Zu G, Sikander S, Portnoy E, Cross AW, Brown BJ. Non-Clifford and parallelizable fault-tolerant logical gates on constant and almost-constant rate homological quantum LDPC codes via higher symmetries. Available from: https://doi.org/10.48550/arXiv.2310.16982
Leymann F, Barzen F. The bitter truth about gate-based quantum algorithms in the NISQ era. Quantum Sci Technol. 2020;5(1):015010. Available from: https://iopscience.iop.org/article/10.1088/2058-9565/abae7d
Cerezo M, Arrasmith A, Babbush R, Benjamin SC, Endo S, Fujii K, et al. Variational quantum algorithms. Nat Rev Phys. 2021;3(9):625–644. Available from: https://doi.org/10.1038/s42254-021-00348-9
Preskill J. Quantum Computing in the NISQ era and beyond. Quantum. 2018;2:79. Available from: https://doi.org/10.22331/q-2018-08-06-79
Yan B, Tan Z, Wei S, Jiang H, Wang W, Wang H, et al. Factoring integers with sublinear resources on a superconducting quantum processor. Available from: https://doi.org/10.48550/arXiv.2212.12372
Khattar T, Yosri N. A comment on “Factoring integers with sublinear resources on a superconducting quantum processor”. arXiv. 2023 Jul 22. Available from: https://arxiv.org/abs/2307.09651
Bernstein DJ. Understanding brute force. Semantic Scholar. 2005. Available from: https://www.semanticscholar.org/paper/Understanding-brute-force-Bernstein/3bf374700ec98ea5d1b7658ec85c472f2fe4d952
Wang Z, Wei S, Long GL, Hano L. Variational quantum attacks threaten advanced encryption standard based symmetric cryptography. Sci China Inf Sci. 2022;65:200503. Available from: http://dx.doi.org/10.1007/s11432-022-3511-5
Wang Z, Wei S, Long GL. A quantum circuit design of AES requiring fewer quantum qubits and gate operations. Front Phys. 2022;17(4):41501. Available from: https://ui.adsabs.harvard.edu/abs/2022FrPhy..1741501W/abstract
Fluhrer S. Reassessing Grover’s algorithm. Cryptology ePrint Archive, Paper 2017/811. 2017. Available from: https://ia.cr/2017/811
Haase Ch, Nill B, Pfaffenholz A. Lecture notes on lattice polytopes. TU Berlin; 2021. Available from: https://www2.mathematik.tu-darmstadt.de/~paffenholz/daten/preprints/20210628_Lattice_Polytopes.pdf
Peikert Ch. A Decade of Lattice Cryptography. Foundations and Trends in Theoretical Computer Science. 2016;10(4). Available from: https://eprint.iacr.org/2015/939.pdf
Silberman JH. An Introduction to Lattices, Lattice Reduction, and Lattice-Based Cryptography. Brown University; 2020. Available from: https://www.ias.edu/sites/default/files/Silverman_PCMI_Note_DistributionVersion_220705.pdf
Zheng Z. Modern Cryptography - 1. Springer; 2022. Available from: https://link.springer.com/book/10.1007/978-981-19-0920-7
Manohar N. Hardness of lattice problems for use in cryptography. Harvard University, Cambridge, Massachusetts; 2016. Available from: https://www.semanticscholar.org/paper/Hardness-of-Lattice-Problems-for-Use-in-Manohar/ca5adbdefc035619799a2ba05c49be452df60d38
Micciancio D. The hardness of the closest vector problem with preprocessing. IEEE Trans Inf Theory. 2001;47(3):1214–1222. Available from: https://cseweb.ucsd.edu/~daniele/papers/CVPP.pdf
Goldreich O, Goldwasser S, Halevi S. Public-key cryptosystems from lattice reduction problems. In: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO); 1997 Aug 17-21; Santa Barbara, California. 112–131.
Galbraith SD. Mathematics of public key cryptography. Version 2.0. University of Auckland; 2018. Available from: https://www.math.auckland.ac.nz/~sgal018/crypto-book/main.pdf
Babai L. On Lovasz lattice reduction and the nearest lattice point problem. Combinatorica. 1986;6(1):1–13. Available from: https://link.springer.com/article/10.1007/BF02579403
Ajtai M. Generating hard instances of lattice problems. Proc 28th ACM Symposium on Theory of Computing. 1996:99–108. Available from: https://dl.acm.org/doi/pdf/10.1145/237814.237838
Lang S. Algebra. Springer; 2002. Available from: https://link.springer.com/book/10.1007/978-1-4613-0041-0
Regev O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. Journal of the ACM. 2009;56(6). Available from: https://doi.org/10.1145/1568318.1568324
Micciancio D, Regev O. Lattice-based Cryptography. In: Bernstein DJ, Buchmann J, Dahmen E, editors. Post-Quantum Cryptography. Springer; 2009;147–191. Available from: https://link.springer.com/chapter/10.1007/978-3-540-88702-7_5
Regev O. The Learning with Errors Problem. IEEE 25th Annual Conference on Computational Complexity. 2010. Available from: https://cims.nyu.edu/~regev/papers/lwesurvey.pdf
Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: EUROCRYPT 2010: Advances in Cryptology; 2010 May 30-Jun 3; French Riviera, France. 1–23.
Mukherjee A, Aikata A, Mert AC, Lee Y, Kwon S, Deryabin M, Roy SS. ModHE: Modular Homomorphic Encryption Using Module Lattices: Potentials and Limitations. Cryptology ePrint Archive, Paper 2023/895. 2023. Available from: https://eprint.iacr.org/2023/895
Avanzi R, Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, et al. CRYSTALS-Kyber - Algorithm specifications and supporting documentation (version 3.02). 2021. Available from: https://pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf
Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck JM, et al. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. In: IEEE European Symposium on Security and Privacy (EuroS&P); 2018 Apr 2-6; London, UK. p. 1–18. Available from: http://dx.doi.org/10.1109/EuroSP.2018.00032
Bai S, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, et al. CRYSTALS-Dilithium - Algorithm specifications and supporting documentation (version 3.1). 2021. Available from: https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf
Richter M, Bertram M, Seidensticker J, Tschache A. A Mathematical Perspective on Post-Quantum Cryptography. Mathematics. 2022;10(15):2579. Available from: https://ideas.repec.org/a/gam/jmathe/v10y2022i15p2579-d871032.html
Jackson KA, Miller CA, Wang D. Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model. arXiv. 2024 Dec 13. Available from: https://arxiv.org/abs/2312.16619
National Institute of Standards and Technology. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. FIPS PUB 202. 2015. Available from: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schwabe P, Seiler G, et al. CRYSTALS-Dilithium: A lattice-based digital signature scheme. IACR Trans Cryptogr Hardw Embedded Syst. 2018;2018(1):238–268. Available from: https://doi.org/10.13154/tches.v2018.i1.238-268
Bakos-Lang EC. Worst-case to average-case reductions for the SIS problem: Tightness and security. University of Waterloo; 2019. Available from: https://dspacemainprd01.lib.uwaterloo.ca/server/api/core/bitstreams/70e489d8-fb0a-4f9c-a0c2-e6dd2d122bef/content
Scholten TL, William CJ, Moody D, Mosca M, Hurley W, Zeng WJ, et al. Assessing the Benefits and Risks of Quantum Computers. 2024. Available from: https://www.nist.gov/publications/assessing-benefits-and-risks-quantum-computers
Mosca M, Piani M. Quantum Threat Timeline Report. Global Risk Institute. 2023. Available from: https://policycommons.net/artifacts/11327929/quantum-threat-timeline-report-2023-dr/12216736/
US Government. Public Law 117 - 260 - Quantum Computing Cybersecurity Preparedness Act. 2022. Available from: https://www.govinfo.gov/content/pkg/PLAW-117publ260/pdf/PLAW-117publ260.pdf
US Government. Report on Post-Quantum Cryptography. 2024. Available from: https://www.whitehouse.gov/wp-content/uploads/2024/07/REF_PQC-Report_FINAL_Send.pdf
European Commission. Commission Recommendation on a Coordinated Implementation Roadmap for the transition to Post-Quantum Cryptography. 2024. Available from: https://www.europeansources.info/record/commission-recommendation-eu-2024-1101-on-a-coordinated-implementation-roadmap-for-the-transition-to-post-quantum-cryptography/
DigiCert, Ponemon Institute. Preparing for a safe post-quantum computing future: A global study. 2023. Available from: https://www.digicert.com/content/dam/digicert/pdfs/report/ponemon-preparing-safe-post-quantum-future-report-en-v1.pdf
Chen L, Jordan S, Liu Y, Moody D, Peralta R, Perlner R, et al. Report on Post-Quantum Cryptography. NISTIR 8105. 2016. Available from: http://dx.doi.org/10.6028/NIST.IR.8105
National Institute of Standards and Technology. Post-Quantum Cryptography. 2023. Available from: https://csrc.nist.gov/projects/post-quantum-cryptography
National Institute of Standards and Technology. FIPS 203. Module-Lattice-Based Key-Encapsulation Mechanism Standard. 2024. Available from: https://doi.org/10.6028/NIST.FIPS.203
National Institute of Standards and Technology. FIPS 204. Module-Lattice-Based Digital Signature Standard. 2024. Available from: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.pdf
National Institute of Standards and Technology. Internal Report IR 8528. Status Report on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process. 2024. Available from: https://nvlpubs.nist.gov/nistpubs/ir/2024/NIST.IR.8528.pdf
NTRU Prime Risk-Management Team. Risks of lattice KEMs. NTRU Prime. 2021. Available from: https://ntruprime.cr.yp.to/latticerisks-20211031.pdf
Goodin D. Post-quantum encryption contender is taken out by single-core PC and 1 hour. Ars Technica. 2022. Available from: https://arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/
Macaulay T, Henderson R. Cryptographic Agility in Practice. InfoSec Global. 2019.
National Cybersecurity Center of Excellence. Migration to Post-Quantum Cryptography. NIST Special Publication 1800-38A. 2023. Available from: https://www.nccoe.nist.gov/sites/default/files/2023-04/pqc-migration-nist-sp-1800-38a-preliminary-draft.pdf
Post-Quantum Cryptography Alliance. Available from: https://pqca.org/
Open Quantum Safe. Available from: https://openquantumsafe.org
Open Quantum Safe. Applications and protocols. Available from: https://openquantumsafe.org/applications/
liboqs. Available from: https://github.com/open-quantum-safe/liboqs
Post-Quantum Cryptography Coalition. Available from: https://www.mitre.org/news-insights/news-release/post-quantum-cryptography-coalition-launches
Sandwich. Available from: https://sandbox-quantum.github.io/sandwich/