SHRINCS: 324-byte stateful post-quantum signatures with static backups

128 bit corresponds to “security level 1” as defined in NIST’s PQC evaluation criteria. We have a section in the report arguing that Level 1 already provides considerable security. In summary, “64 bits against Grover’s” does not take into account the hash function circuit evaluation required in each Grover iteration. The current best circuit for SHA-256 has a depth of 2^{14} gates. Moreover, Grover’s algorithm doesn’t parallelize well: running it on k machines only gives a \sqrt{k} speedup. If you assume quantum computers can evaluate 2^{64} gates in a decade (roughly matching the number of cycles my laptop can perform), you’d need 268 million quantum computers running Grover’s algorithm for a decade.

That said, SHRINCS at NIST security level 3 (192-bit classical / 96-bit quantum) would have signature size of \min(612 + q \cdot 24, s_l) + 24 bytes, so 660 bytes for q = 1: with Winternitz parameter w = 256, we get l = 192/8 = 24 chains, each with 24-byte output. Including 32-byte randomness and 4-byte counter, WOTS+C’s signature size is 24 \times 24 + 32 + 4 = 612 bytes.

1 Like