Post-Quantum Cryptography
Quantum computing has the potential to break all cybersecurity protocols. This will compromise confidentiality and integrity of digital communication.
In 2022, the U.S. Department of Commerce's National Institute of Standards and Technology (NIST) selected the first group of encryption tools designed to withstand quantum computer cyberattacks. The NIST predicted that by the year 2040, quantum computing technology will exist to break all public key schemes currently being used today.
Encryption uses mathematics to protect information using public-key encryption systems. Quantum computers are capable of solving these math problems quickly, compared to the current most advanced classical computers.
There are three core cryptographic functionalities: (1) public key encryption, (2) digital signatures, and (3) key exchange. These are currently implemented using Diffie-Hellman key exchange, RSA cryptosystems, and elliptic curve cryptosystems. Integer Factorization and the Discrete Log Problem are two examples of theoretic problems that determine the security of these techniques.
The NIST commented that Elliptic Curve Cryptography and Finite Field Cryptography are not secure since the introduction of quantum computers. AES requires larger key sizes. SHA-2 and SHA-3 require larger output.
As an example, TLS (Transport Layer Security) uses public key cryptography for passwords and financial data transmitted over https. The corresponding algorithms are based on factoring, discrete logarithms, and/or elliptic curves. All these mathematical problems can be broken by a quantum computer.
Asymmetric encryption and digital signature algorithms based on number theory (RSA, DSA, Diffie-Hellman, EIGamal, and elliptic curve variants) are also at risk.
The NIST suggested that Internet protocols may need to be changed to protect against quantum computers, such as TLS and Internet Key Exchange (IKE).
The NIST stated that cryptosystems offering 80 bits of security were phased out in 2011-2013 and pose the greatest risk. Classical computers can break these cryptosystems for as little as tens of thousands of dollars up to hundreds of millions of dollars.
112 bits of security is capable of being broken by classical computers for $1 billion dollars in 30 to 40 years. NIST recommends phasing out 112 bit security by 2031 and for 80 bit security systems to be considered insecure.
Mathematical techniques that may be viable for quantum-safe cryptosystems are: (1) hash functions and symmetric zero-knowledge proofs; (2) error correcting codes; (3) lattices; (4) multivariate equations; and (5) supersingular elliptic curve isogenies.
NIST selected quantum-resistant algorithms that rely on math problems that both classical and quantum computers may find difficult to solve. These algorithms are designed for general encryption and digital signatures.
General Encryption: CRYSTALS-Kyber algorithm.
Digital Signatures: CRYSTALS-Dilithium, FALCON, and SPHINCS+
NIST recommends CRYSTALS-Dilithium as the primary algorithm. FALCON is for applications that need smaller signatures than Dilithium provides. SPHINCS+ is a backup because it is based on a different math approach than the other three algorithms.
SPHINCS+ uses hash functions while the other three use structural lattices.
NIST recommends that developers take inventory of software that uses public-key cryptography and alert the appropriate I.T. vendors and departments, but not to formally adopt these new algorithms until the final NIST review is complete. Public-key cryptography will need to be replaced before quantum computers become viable.
CRYSTALS-Kyber
IND-CCA2-secure key encapsulation mechanism, based on solving the learning-with-errors (LWE) problem over module lattices.
Kyber-512 security is roughly equivalent to AES-128, Kyber-768 to AES-192, and Kyber-1024 to AES-256.
Kyber-768 is recommended along with using Kyber in hybrid mode, such as in combination with elliptic-curve Diffie-Hellman. Kyber-768 provides more than 128-bits of security against all known classical and quantum attacks.
The algorithm is based on improvements to LWE encryption, square matrix as the public key instead of rectangular, NTRU cryptosystems, and polynomial rings instead of integers.
Module lattices lie between the definitions of the LWE problem and those for the Ring-LWE problem. The lattices used for Kyber and Dilithium (described below) have less algebraic structure than Ring-LWE and are closed to unstructured lattices in LWE. It is proposed that a algebraic attack against Ring-LWE would be less effective against Kyber and Dilithium.
CRYSTALS refers to "Cryptographic Suite for Algebraic Lattices".
CRYSTALS-Dilithium
Digital signature scheme based on lattice problems over module lattices.
Recommendation is to use Dilithium in hybrid mode in combination with a pre-quantum signature scheme.
Dilithium3 parameter set achieves more than 128 bits of security.
Based on "Fiat-Shamir with Aborts" technique using rejection sampling. The smallest signature size scheme is based on NTRU assumption and Gaussian sampling (uniform distribution).
A new technique is used to shrink the public key by more than a factor of 2.
FALCON
Cryptographic signature algorithm using lattice-based signature schemes over NTRU lattices and a trapdoor sampler "fast Fourier sampling". The underlying hard problem is the short integer solution problem (SIS) over NTRU lattices.
Acronym for Fast Fourier lattice-based compact signatures over NTRU.
Negligible leakage of information on secret key based on a true Gaussian sampler.
NTRU lattices allow substantially shorter signatures than other lattice-based schemes.
The key generation algorithm uses less than 30 KB of RAM for compatibility with memory-constrained embedded devices.
FALCON-512 is roughly equivalent to RSA-2048.
SPHINCS+
Stateless hash-based signature scheme.
Multi-target attack protection uses a different hash function for each call, keyed with a different key and bitmasks. These keys and bitmasks are pseudorandomly generated from an address specifying the context of the call and a public seed.
Tree-less WOTS+ public key compression uses a single tweakable hash function call.
Each message that an adversary tries becomes directly linked to a FORS (Forest of Random Subsets) instance and is unusable for any other instance.
Open Quantum Safe (OQS) Project
OQS is an open-source project to develop and prototype quantum-resistant cryptography.
There are two main tools: (1) liboqs is an open-source C library, and (2) Prototype integrations for protocols and applications, such as OpenSSL.
References:
[1] NIST Announces First Four Quantum-Resistant Cryptographic Algorithms. NIST. https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms [Accessed 10/25/2023]
[2] Post-Quantum Cryptography Standardization. NIST. https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization [Accessed 10/25/2023]
[3] Report on Post-Quantum Cryptography. NIST. https://csrc.nist.gov/pubs/ir/8105/final [Accessed 10/25/2023]
[4] CRYSTALS - Cryptographic Suite for Algebraic Lattices. https://pq-crystals.org/index.shtml [Accessed 10/25/2023]
[5] Dilithium. https://pq-crystals.org/dilithium/index.shtml [Accessed 10/25/2023]
[6] Falcon. https://falcon-sign.info/ [Accessed 10/25/2023]
[7] SPHINCS+ Stateless hash-based signatures. https://sphincs.org/ [Accessed 10/25/2023]
[8] Open Quantum Safe. https://openquantumsafe.org/ [Accessed 10/25/2023]
Quantum Computing Technology
Overview |
Patents |
Patent Search |
Trademarks |
Copyrights |
Videos