Why is the current month decisive for PQC?

✍️ Written on 2022-01-28 in 698 words.
Part of cs IT-security pqcrypto

Update 2022-02-09: NIST announced a delay. “We hope to be able to announce the results and report not later than the end of March”.
Update 2022-07-02: NIST announced that intellectual property issue prevented them for their publication. They plan to release the results on Tuesday.
Update 2022-07-09: A new post covers the decision.

Motivation

PQC is currently at its peak. Whereas the German BSI decided in favor of Classic McEliece and FrodoKEM as recommended schemes in 2020-01 (warning: German text behind hyperlink), most academics look towards the NIST decision. NIST asked the cryptographic community for final comments until end of October 2021. And NIST announced to decide “in December 2021 or January 2022” at the Third Standardization Conference in June 2021.

Now’s the time.

On cryptographic competitions

The selection of cryptographic primitives is organized in a competition by NIST. I enjoyed the paper “Cryptographic competitions” by Daniel J. Bernstein (2020) w.r.t this topic. He revised similar competitions (SHA-3, CAESAR, NISTLWC, …) and discusses their problems. One basic question is: which communication happens between the provably malicious NSA and NIST. A transparent decision is desired, but this is non-trivial because the ultimate decision is usually a tradeoff and includes subjective components. For the previous round, the round 3 selection was accompanied by NIST-IR 8309 which provides some pro/contra arguments per candidate and thus makes the decision more transparent.

Reminder: timeline

2016-02

Announcement of “Post-Quantum Cryptography Standardization Effort”

2017-11

Deadline for submissions

2017-12

Round 1 algorithms announced (69 submissions)

2019-01

Round 2 algorithms announced (26 submissions left)

2020-07

Round 3 algorithms announced (7 finalists left, alternate track not mentioned here)

2021-12/2022-01

Schemes to standardize to be announced

2024

Expected end of standardization

Fun fact: “Guess Again” was a candidate in round 1 which was broken by Lorenz Panny 3 hours after publication.

Reminder: cryptographic primitives

Fundamentally, cryptographic primitives are designed for the following two interfaces:

Key Encapsulation Mechanism (KEM):

  1. KeyGen() → (pk, sk)

  2. Encapsulate(pk) → (ct, ss)

  3. Decapsulate(pk, sk, ct) → (ss)

sk stands for secret key and pk stands for public key. Thus they are Steps 1 and 3 are done by one party and step 2 by another. Encapsulation means that no message is encrypted, but a shared secret (ss) negotiated. Thus the message originates from some random number generator and is not user-supplied.

Digital signatures (sig):

  1. KeyGen() → (pk, sk)

  2. Sign(sk, msg) → (sig)

  3. Verify(sig, msg, pk) → (msg)

NIST mentioned that it considers to extend the digital signature track beyond the current deadline (thus a round 4 including new submissions). I think their argument was that the digital signature track is dominated by lattice-based schemes (Rainbow is the only non-lattice finalist) even though I don’t see such a difference to the KEM track.

Reminder: finalists

NIST lists the following Round 3 finalists:

  1. Classic McEliece (KEM, code)

  2. CRYSTALS-KYBER (KEM, lattice, MLWE)

  3. NTRU (KEM, lattice, NTRU)

  4. SABER (KEM, lattice, MLWR)

  5. CRYSTALS-DILITHIUM (sig, lattice, Fiat-Shamir)

  6. FALCON (sig, lattice, NTRU)

  7. Rainbow (sig, multi-variate, Oil-Vinegar)

Conclusion

I just wanted to raise attention to this current deadline. PQC is the topic I studied for about 2 years during my aborted PhD studies. I was always looking forward to this deadline and the decision is expected every day at the pqc-forum mailing list.