Post Quantum Cryptography is a complex topic. Finding reliable information is crucial for building an informed opinion. Selecting the sources you trust is fundamental. Luckily, AUMASSON J.P. and a few contributors have started a GitHub repository: https://github.com/veorq/awesome-post-quantum.
J.P. is a respected cryptographer that I trust. His book, Serious Cryptography: A Practical Introduction to Modern Encryption, is a must-read.
Recently, an academic paper from a large team of Chinese researchers made the headlines of the specialized press [1]. Reporters claimed that “small” quantum computers may break RSA2048. Breaking RSA2048 may need only 372 qubits. Qubits are similar to bits in the quantum domain. IBM already proposes Osprey: a 433-qubit chip. So, is RSA2048 dead?
The security of RSA relies on the assumption that factorizing the product of two large prime numbers is extremely difficult. It is assumed currently that conventional computers cannot solve this problem. Recent studies showed that, in theory, quantum computers may succeed.
The paper is not for the faint heart. Its summary is as follows:
Shor’s algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. Here, we report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm (QAOA). The number of qubits required is O(logN/loglog N), which is sublinear in the bit length of the integer $N$, making it the most qubit-saving factorization algorithm to date. We demonstrate the algorithm experimentally by factoring integers up to 48 bits with 10 superconducting qubits, the largest integer factored on a quantum device. We estimate that a quantum circuit with 372 physical qubits and a depth of thousands is necessary to challenge RSA-2048 using our algorithm. Our study shows great promise in expediting the application of current noisy quantum computers, and paves the way to factor large integers of realistic cryptographic significance.
As mentioned, RSA’s security assumes it is tough to factorize the product of two very large prime numbers. The researchers use Schnorr’s algorithm [2] to factor these large numbers rather than the Schor one. On the one hand, the Schor algorithm requires millions of qubits, but it is a theoretically proven solution. Unfortunately, it is out of the current feasibility realm. On the other hand, Schnorr’s algorithm seems not yet to be a proven solution at a large scale. The expected speed-up using quantum computing is highly controversial and not demonstrated. The paper stays in the realm of unproven expectations.
The consensus seems to be that the threat is not yet here. Following is a list of posts of people who know far better than me:
Keep calm. RSA 2048 is still safe for many years. Nevertheless, it is key to be aware of the latest progress of post-quantum cryptography. Do we have to switch to post-quantum cryptography? Not right now, especially if you do not handle secrets that have to last for many decades.
[1] B. Yan et al., “Factoring integers with sublinear resources on a superconducting quantum processor.” arXiv, Dec. 23, 2022. Available: http://arxiv.org/abs/2212.12372
[2] C. P. Schnorr, “Fast Factoring Integers by SVP Algorithms, corrected.” 2021. Available: https://eprint.iacr.org/2021/933
[3] S. Aaronson, “Cargo Cult Quantum Factoring,” Shtetl-Optimized, Jan. 04, 2023. https://scottaaronson.blog/?p=6957
[4] “Paper claims to break RSA-2048 with only 372 physical quibits.” https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/AkfdRQS4yoY/m/3plDftUEAgAJ .
[5] “Breaking RSA with a Quantum Computer – Schneier on Security.” https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html
[6] dougfinke, “Quantum Experts Debunk China Quantum Factoring Claims,” Quantum Computing Report, Jan. 06, 2023. https://quantumcomputingreport.com/quantum-experts-debunk-china-quantum-factoring-claims
Post-quantum cryptography encompasses the algorithms that are allegedly immune to quantum computing. In 2017, NIST initiated the process of selecting and standardizing a set of post-quantum cryptosystems. In 2020, NIST started the third round with 15 remaining candidates.
NIST announced the four winners. CRYSTALS-KYBER is the new key establishment protocol for post-quantum.
“Among its advantages are comparatively small encryption keys that two parties can exchange easily, as well as its speed of operation. ”
CRYSTALS-DILITHIUM, Falcon, and SPHINCS+ are the new digital signature systems.
“ Reviewers noted the high efficiency of the first two, and NIST recommends CRYSTALS-Dilithium as the primary algorithm, with FALCON for applications that need smaller signatures than Dilithium can provide. The third, SPHINCS+, is somewhat larger and slower than the other two, but it is valuable as a backup for one chief reason: It is based on a different math approach than all three of NIST’s other selections.”
Interestingly, version 9.0 of OpenSSH proposes a post-quantum algorithm. It is NTRU prime and not CRYSTALS-KYBER.
For several years, cryptography has studied the implication of the rise of quantum computation. Once fully operational, with enough qubits, error-free, and keeping quantum states long enough, quantum computing will break prime number factor-based cryptosystems (such as RSA) and Elliptic Curve Cryptography by quickly finding the private keys.
Thus, in 2017, NIST initiated selecting and standardizing a set of post-quantum cryptosystems.
OpenSSH just released version 9.0. And it adds the support of a post-quantum cryptosystem. To be precise:
Quoting
use the hybrid Streamlined NTRU Prime + x25519 key exchange method by default (“sntrup761x25519-sha512@openssh.com”). The NTRU algorithm is believed to resist attacks enabled by future quantum computers and is paired with the X25519 ECDH key exchange (the previous default) as a backstop against any weaknesses in NTRU Prime that may be discovered in the future. The combination ensures that the hybrid exchange offers at least as good security as the status quo.
NTRU Prime is one of the nine remaining candidates in the NIST selection process. OpenSSH chose one without waiting for the NIST final selection.
Post-quantum cryptography encompasses the algorithms that are allegedly immune against quantum computing. There are five categories that seem suitable for post-quantum cryptography. See previous post.
In 2017, NIST initiated the process to select and standardize a set of post-quantum cryptosystems. In 2019, the second round selected 26 candidates. The third round started in 2020. Last month, NIST published an intermediary analysis of these candidates. As a result, NIST selected seven serious candidates and eight potential but unlikely contenders. The draft standards should be available by 2024. Table 1 lists the nine candidates for encryption. The predominance of lattice-based and code-based solutions is visible. Table 2 lists the six selected candidates for digital signatures. The more likely candidates are highlighted.
| Code-based | Lattice | Isogeny | ||
| BIKE | X | |||
| Classic McEliece | X | |||
| CRYSTALS-KYBER | X | |||
| FrodoKEM | X | |||
| HQC | X | |||
| NTRU | X | |||
| NTRU prime | X | |||
| SABER | X | |||
| SIKE | X |
| Hash-based | Lattice | MQE | ||
| CRYSTALS-DILITHIUM | X | |||
| FALCON | X | |||
| GeMSS | X | |||
| Picnic | ||||
| Rainbow | ||||
| SPHINCS+ | X | |||
Lattice seems to be the big runner for post-quantum. A future post will attempt to give a hint on lattice-based cryptography.
The report is available at https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf
Quantum computing, quantum cryptography, and post-quantum cryptography: these terms are confusing. This post attempts to clarify them and draws the relationship between them.
Quantum computing is the set of technologies that use quantum-mechanical phenomena to perform computing. Quantum computing uses qubits rather than bits. Where one bit of conventional computing has one of the two possible states “0” or “1”, a qubit has a set of independent states simultaneously via superposition. Furthermore, entangled qubits behave together in non-conventional ways (for instance, immediate synchronization independent from the distance separating the two qubits).
These properties allow solving some classes of problems, many orders faster than conventional computing. In 1994, Peter Shor published “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” [1]. His algorithm solves the prime factorization and discrete logarithm hard problems. Prime factorization is the foundation of cryptosystems such as Diffie Hellman (DH) and RSA. Discrete logarithms are the foundation of elliptic curve cryptosystems (ECC). In 1996, Lov Grover published “A fast quantum mechanical algorithm for database search” [2]. His algorithm inverts one-way functions in time. It applies to symmetric ciphers and cryptographic hashes.
Whenever quantum computing is operational, accurate, and with enough qubits, these algorithms and their enhancements will impact traditional cryptography. To mitigate Grover’s algorithm, the size of symmetric keys and hashes has to increase. For instance, AES will need at least 256-bit keys. Shor’s algorithm annihilates the security of prime factorization or discrete logarithm-based cryptosystems. In other words, DH, RSA, and ECC will not be secure anymore.
Post-quantum cryptography encompasses the algorithms that are allegedly immune against quantum computing. There are mainly four categories of algorithms.
It is wise to strengthen post-quantum cryptography to be ready whenever this threat is active. NIST estimates that a 1 billion $ quantum computer may break RSA 2048 keys in a matter of hours. A future post will explore more in detail post-quantum cryptography.
Quantum cryptography or Quantum Key Distribution (QKD) sends over information, including a secret key, using photons over a line between Alice and Bob. Once Bob received the secret key, Alice and Bob use it to encrypt and decrypt via traditional symmetric cryptosystems their messages. This key distribution is very similar to many current systems. Nevertheless, due to the Heisenberg’s principle, if Eve eavesdrops the QKD, she alters the secret key. Thus, Alice and Bob know they are eavesdropped, offering higher security. The obvious limitation is that it can only be used in point to point communications. The first QKDs were designed in the 80s.
Hoping that this post shed some light, I wish you a happy new year.
[1] P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM J. Comput., vol. 26, no. 5, pp. 1484–1509, Oct. 1997, doi: 10.1137/S0097539795293172.
[2] L. K. Grover, “A fast quantum mechanical algorithm for database search,” ArXivquant-Ph9605043, Nov. 1996.
[3] R. McEliece, “A public-key cryptosystem based on algebraic coding theory,” NASA, DSN 42-44, 1978.