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

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 directly)
  • 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)