Post-quantum primitives#

NIST announced the Post-Quantum Cryptography Standardization at PQCrypto 2016, as an effort to standardize algorithms resistant to attacks that make use of quantum-computers.

Out of 69 candidates that were considered for the first round of the competition, 4 algorithms were selected at the end of the third round for standardization. There are 3 digital signature schemes, CRYSTALS-Dilithium, Falcon, and SPHINCS+, and one KEM[1], CRYSTALS-Kyber. NIST plans to recommend Kyber and Dilithium, while standardizing Falcon for cases where Dilithium’s signatures may be too large, and SPHINCS+ to avoid relying only on lattice-based signature schemes. This guide has entries for each:

Besides these algorithms, 4 other KEM candidates are going through a fourth round of analysis in order to standardize a KEM alternative to Kyber. These are BIKE, Classic McEliece, HQC, and SIKE, though last year an attack on SIKE has been published and the team acknowledges SIKE should not be used.

And a new call for proposals for signature schemes with “short signatures and fast verification” is ongoing. For a list of all signature scheme candidates, see Post-Quantum signatures zoo.

A quick comparison of signature schemes#

While only one KEM algorithm has been selected at the end of Round 3, we have three different signatures schemes to compare.

Dilithium

Falcon

SPHINCS+

Based on

(Module) lattices

NTRU lattices

Hash functions

Security based on

SVP

SIS, Floating-point arithmetic, and Gaussian sampling

Second-preimage resistance of the hash function

NIST security levels

2, 3, and 5

1 and 5

1, 3, and 5

Pros

  • Has the fastest signature generation without additional requirements.

  • It’s easy to implement safely.

  • Has the smallest \(|\text{pk}| + |\text{sig}|\).

  • Has a security proof for ROM and QROM.

  • Is modular: the class of lattices and the trapdoor sampler can be changed easily.

  • There are possible instantiations with message-recovery or key-recovery modes.

  • Its security is based on the security of the underlying hash function.

  • Has different parameter sets with different tradeoffs.

  • Has the smallest public key.

Cons

  • Has relatively large signatures and public keys.

  • Delicate implementation: the key generation and fast Fourier sampler are non-trivial to understand.

  • Requires fast constant-time double-precision floating-point arithmetic, which currently requires workarounds.

  • Has the largest signatures.

  • Has the slowest signature generation.