Post-quantum signature schemes

tl;dr: Some notes on post-quantum (PQ) signature schemes.

Notes

This is a research blog post on the state-of-the-art PQ signature schemes.

Steps:

• Surveyed NIST’s Round 2 additonal candidates¹
  • Filtered after Round 1. (See status report².)
  • See all schemes here, with the advanced ones marked in $\textcolor{blue}{\text{blue}}$
    • A criticism: The MPC-in-the-Head schemes actually rely on all sorts of exotic assuptions. The caption makes it seem like they do not, which is confusing.
• Looked at FAEST
  • Not as fast to verify as SPHINCS+
  • Better if faster signing is desired (e.g., consensus signatures)
• Looked at SLH-DSA (SPHINCS+)
  • This is ideal for the blockchain setting: minimal assumptions (just hashing), verification time descreases with signature size (by trading off signing time), standardized, sufficiently-succinct (e.g., 7.67 KiB)
• Found all FIPS standards³; not that many, hm.

FAEST

See FAEST website for a full list of resources.

Notes:

• introduced in 2023⁴
• based on AES128/192/256 and Vector Oblivious Linear Evaluation (VOLE) in the head (VOLEiTH)
  • VOLEitH is constructed only from symmetric-key primitives
• NIST cites it as “somewhat complex” and says “the security proof is very technical.”²

Construction

\begin{align} \pk &= (x,y)\\
\sk &= k \end{align} such that: \begin{align} E_k(x) = y,\ \text{where}\ E\ \text{is a block cipher} \end{align}

Signing works by doing a ZKPoK of $k$ using VOLEitH and the QuickSilver information-theoretic proof system⁵ (under the Fiat-Shamir transform).

Sizes

Secret and public keys are small: 32 bytes at 128-bit security.

Signature sizes are described below.

Performance

Benchmarked on:

“a single core of a consumer notebook with an AMD Ryzen 7 5800H processor, with a base clock speed of 3.2 GHz and 16 GiB memory.” “Simultaneous Multi-Threading was enabled.” The computer was running Linux 6.1.30, and the implementations were built with GCC 12.2.1.”

Unoptimized reference implementation is too slow (tens of milliseconds to verify):

But x86-64 AVX2 implementation could be practical at 128-bit security level (0.87 ms to verify 6,336-byte signatures):

These numbers are multi-threaded!

Perhaps this recent QuickSilver improvement⁶ will help? I quote: “For a circuit of size $\sizeof{C} = 2^{27}$, it shows up to 83.6× improvement on communication, compared to the general VOLE-ZK Quicksilver. In terms of running time, it is 70% faster when bandwidth is 10Mbps”.

Pratik Sarkar suggests it likely does not. And even if it does, it would require additively-homomorphic encryption like BGV, which would introduce additional assumptions.

SLH-DSA (SPHINCS+)

See SPHINCS website for a full list of resources.

• FIPS-standardized⁷
• stateless, hash-based (hence the “SLH” acronym?)
• “an SLH-DSA key pair contains $2^{63}, 2^{64}, 2^{66}$, or $2^{68}$ forest of random subsets (FORS) keys”
• “FORS allows each key pair to safely sign a small number of messages”
• “An XMSS key consists of $2^{h’}$ WOTS$^+$ keys and can sign $2^{h’}$ messages”
• a rather-involved construction; would need to dig deeper to see if there’s a simple design underneath
• “The SHA2-based parameter sets are 2x slower than the SHAKE-based ones”

Sizes

Key and signature sizes from FIPS-205⁷:

sphincs-shake-128f benchmarks

16.69 KiB signature size, signing time is 17 ms and verification is 1.1 ms!

Benchmarking the reference implementation in C⁸ on my Apple Macbook Pro, M1 Max below. They only provide an ARM implementation for the SHAKE variant $\Rightarrow$ not sure what the SHA2 numbers would look like on ARM.

Are these numbers single-threaded?

Got this kpc_get_thread_counters failed, run as sudo? error (I think) during the thash benchmarks.

Building this variant on ARM via:

git clone https://github.com/sphincs/sphincsplus/
cd shake-a64/
make clean
make benchmark

The results, edited for clarity of exposition:

cc -Wall -Wextra -Wpedantic -Wmissing-prototypes -O3 -std=c99 -fomit-frame-pointer -flto -DPARAMS=sphincs-shake-128f  -o test/benchmark test/cycles.c hash_shake.c hash_shakex2.c thash_shake_robustx2.c address.c randombytes.c merkle.c wots.c utils.c utilsx2.c fors.c sign.c fips202.c fips202x2.c f1600x2_const.c f1600x2.s test/benchmark.c
wrong fixed counters count

Parameters: n = 16, h = 66, d = 22, b = 6, k = 33, w = 16

Running 10 iterations.

thash                avg.        0.53 us
f1600x2              avg.        0.28 us
thashx2              avg.        0.58 us

Generating keypair.. avg.     1,294.10 us
  - WOTS pk gen 2x.. avg.       294.70 us
Signing..            avg.    17,255.30 us --> 17 ms
  - FORS signing..   avg.       853.00 us
  - WOTS pk gen x2.. avg.       176.80 us
Verifying..          avg.     1,096.50 us --> 1.1 ms

Signature size: 17,088 bytes (16.69 KiB)

Public key size: 32 bytes (0.03 KiB)
Secret key size: 64 bytes (0.06 KiB)

sphincs-shake-128s benchmarks

Clear winner: hash-based, 7.67 KiB signatures created in 336 ms that verify in 0.4 ms!

Building this variant on ARM by via:

git clone https://github.com/sphincs/sphincsplus/
cd shake-a64/
gsed -i 's/shake-128f/shake-128s/g' Makefile
make clean
make benchmark

Note that the Makefile was modified to build the shorter s-variant of SPHINCS+.

The results for sphincs-shake-128s, edited for clarity of exposition:

cc -Wall -Wextra -Wpedantic -Wmissing-prototypes -O3 -std=c99 -fomit-frame-pointer -flto -DPARAMS=sphincs-shake-128s  -o test/benchmark test/cycles.c hash_shake.c hash_shakex2.c thash_shake_robustx2.c address.c randombytes.c merkle.c wots.c utils.c utilsx2.c fors.c sign.c fips202.c fips202x2.c f1600x2_const.c f1600x2.s test/benchmark.c
wrong fixed counters count
Parameters: n = 16, h = 63, d = 7, b = 12, k = 14, w = 16

Running 10 iterations.

thash                avg.        0.94 us
f1600x2              avg.        0.38 us
thashx2              avg.        0.66 us

Generating keypair.. avg.    46,510.80 us
  - WOTS pk gen 2x.. avg.       178.80 us
Signing..            avg.   336,702.20 us --> 336.7 ms
  - FORS signing..   avg.    22,816.50 us
  - WOTS pk gen x2.. avg.       176.40 us
Verifying..          avg.       396.10 us --> 0.396 ms

Signature size: 7,856 bytes (7.67 KiB)

Public key size: 32 bytes (0.03 KiB)
Secret key size: 64 bytes (0.06 KiB)

Performance of RustCrypto/signatures

Seems like a single-threaded implementation.

Bechmarked via:

git clone https://github.com/RustCrypto/signatures
cd slh-dsa/
cargo bench

SHA2 variants are faster. It may be because they leverage native SHA2 instructions.

TODO

SIS-based schemes

GPV hash-and-sign signatures and their plain-lattice descendants⁹. (Also see this.) “Fiat-Shamir with Aborts” signatures¹⁰$,$¹¹. Squirrels. HuFu. (Also see this survey.)

ML-DSA

Investigate ML-DSA, based on MLWE.

References

For cited works, see below 👇👇