NIST selected the post-quantum cryptosystems

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.

OpenSSH prepares post-quantum

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. 

NIST reduced the number of candidates for post-quantum cryptography

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-basedLatticeIsogeny
BIKEX
Classic McElieceX
CRYSTALS-KYBERX
FrodoKEMX
HQCX
NTRUX
NTRU primeX
SABERX
SIKEX
Table 1: NIST candidates for encryption
Hash-basedLatticeMQE
CRYSTALS-DILITHIUMX
FALCONX
GeMSSX
Picnic
Rainbow
SPHINCS+X
Table 2: NIST candidates for digital signature

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 what?

Quantum what?

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.

  • Hash-based signatures; It uses the current hash algorithms, and its security is well understood. The size of the public key is far larger and usable only once. 
  • Code-based encryption;  It uses sophisticated error-correcting codes.  The McEliece’s scheme was first proposed in 1978 [3] and has not been broken since. 
  • Lattice-based encryption is the most efficient and promising solution.  It allows encryption, digital signatures, and fully homomorphic encryption.
  • Multi-variate Quadratic Equations seem the less promising path.  All proposed schemes are currently broken. 

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.

References

[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.