Quantum-Safe Hash Functions

Quantum-Safe Hash Functions

Hash functions and hash-based signatures are among the most conservative post-quantum constructions. Their security reduces to the collision resistance of the underlying hash function: a property that Grover's algorithm weakens only quadratically, not exponentially. This makes hash-based signatures like SPHINCS+ a trusted fallback even if lattice assumptions break.

Why Hash Functions Are Quantum-Resistant

Grover's algorithm can find a preimage of a hash function in $O(2^{n/2})$ quantum operations, compared to $O(2^n)$ classically: a quadratic speedup. For SHA-256, this reduces effective security from 256 bits to 128 bits. This is manageable: use SHA-256 at 128-bit post-quantum security, or move to SHA3-512 for 256-bit post-quantum security.

For collision resistance (finding two inputs with the same hash), the BHT algorithm gives a cubic speedup: $O(2^{n/3})$ quantum operations. SHA-256 collision resistance drops from 128-bit to ~85-bit security. SHA3-512 retains 170-bit post-quantum collision resistance.

Crucially, hash functions do not rely on factoring, discrete logarithms, or lattice assumptions. Even if Shor's algorithm is improved or lattice algorithms advance, hash-based signatures remain conservative choices.

Lamport One-Time Signatures

The simplest hash-based signature scheme is Lamport's one-time signature (1979):

Security: To forge a signature on a different message, the attacker must find the unrevealed preimage for at least one bit position, finding a SHA-256 preimage requires $2^{128}$ operations even with Grover.

One-time limitation: Revealing preimages for both values of any bit allows signature forgery. Lamport signatures must never be reused. (XMSS and SPHINCS+ use Merkle trees to build multi-time signatures from many Lamport keys.)