NIST Post-Quantum Crypto Standardization project round 2

January 30, 2019 at 03:36PM     Research

The United States National Institute of Standards and Technology (NIST) is currently running a multi-year standardization project for post-quantum cryptography. Today, NIST announced the schemes that have made it to round 2 of the competition. Below is my categorization of the round 2 schemes.

Timeline

• December 2016: Formal call for proposals released
• November 30, 2017: Round 1 deadline: 82 submissions received (59 KEMs, 23 signatures)
• December 21, 2017: Round 1 public release: 69 “complete and proper” submissions
• January 30, 2019: Round 2 announcement: 26 accepted to round 2 (17 KEMs, 9 signatures)
• March 15, 2019: Round 2 “tweak” deadline

For a good summary as of August 2018, see the talk by Bernstein, Lange, Panny at the Workshop on Attacks in Cryptography (WAC) co-located with Crypto 2018.

Round 2 key encapsulation mechanisms / public key encryption schemes (17)

Code-based

(17 in Round 1, 7 in Round 2)

• BIKE (some McEliece, some Niederreiter, using quasi-cyclic medium density parity check codes, IND-CPA)
• Classic McEliece (Niederreiter, using binary Goppa codes, IND-CCA directly)
• HQC (Hamming quasi-cyclic codes, IND-CCA using FO transform)
• LEDAcrypt (merger of LEDAkem/LEDApkc) (Niederreiter, using quasi-cyclic low density parity check codes, IND-CCA using Kobara-Imai transform)
• NTS-KEM (Goppa codes, IND-CCA using FO-like transform)
• ROLLO (merger of LAKE/LOCKER/Ouroboros-R) (McEliece, rank metric codes, IND-CPA)
• RQC (rank quasi-cyclic codes, IND-CCA using FO transform)

Structured lattices

(19 in Round 1, 8 in Round 2)

• CRYSTALS-KYBER (module learning with errors, IND-CCA using FO transform) (University of Waterloo connection: John Schanck)
• LAC (ring learning with errors, IND-CCA using FO transform)
• NewHope (ring learning with errors, IND-CCA using FO transform) (University of Waterloo connection: Douglas Stebila)
• NTRU (merger of NTRUEncrypt/NTRU-HRSS-KEM) (NTRU-based, IND-CCA using FO-like transform) (University of Waterloo connection: John Schanck)
• NTRU Prime (NTRU-based, IND-CCA using re-encryption)
• Round5 (merger of Hila5/Round2) (general learning with rounding, IND-CCA using FO transform)
• SABER (module learning with rounding, IND-CCA using FO transform)

Unstructured lattices

(3 in Round 1, 1+1 in Round 2)

• FrodoKEM (learning with errors, IND-CCA using FO transform) (University of Waterloo connection: Douglas Stebila, UW alum Patrick Longa)

Round5 (listed above in “Structured lattices”) also contains a variant based on unstructured lattices.

Isogenies

(1 in Round 1, 1 in Round 2)

• SIKE (supersingular isogenies, IND-CCA using FO transform) (University of Waterloo connection: David Jao, David Urganik, UW alums Patrick Longa, Vladimir Soukharev)

Integer-ring

(3 in Round 1, 1 in Round 2)

• Three Bears (integer module learning with errors, IND-CCA using custom transform)

Multivariate

(3 in Round 1, 0 in Round 2)

Other

(3 in Round 1, 0 in Round 2)

Round 2 digital signature schemes (9)

Structured lattices

(5 in Round 1, 3 in Round 2)

• CRYSTALS-DILITHIUM (module learning with errors / module short integer solutions)
• FALCON (NTRU short integer solutions)
• qTESLA (ring learning with errors) (University of Waterloo connection: Edward Eaton; UW alums Gus Gutoski (ISARA), Patrick Longa)

Multivariate

(8 in Round 1, 4 in Round 2)

• GeMSS (HFEv-)
• LUOV (unbalanced oil and vinegar)
• MQDSS (Fiat-Shamir applied to 5-pass identification scheme)
• Rainbow (generalized oil and vinegar)

Symmetric crypto

(3 in Round 1, 2 in Round 2)

• Picnic (hash functions + block ciphers + ZK proofs) (University of Waterloo connection: UW alum Greg Zaverucha)
• SPHINCS+ (hash based, tree of trees)

Other

(4 in Round 1, 0 in Round 2)