← Hall of Foundations Exhibit 154 · the perfect hash
The Assumption Beneath Fiat–Shamir

The oracle that
can't be predicted

Much of cryptography leans on a fiction so useful it's treated as bedrock: a hash function that behaves like a perfectly random one. Feed it anything, get back noise you could never have guessed — and the same input always returns the same noise. From that single idea, signatures are built.

A model, held on purpose. No real function is a true random oracle. But designing a scheme as if one exists, then instantiating it with a strong hash like SHA-3, is how a huge fraction of deployed cryptography is proven and built. This exhibit shows the two properties that make the fiction hold up.
§1

Two demands on a hash

Preimage resistance asks that finding an input for a specified digest be infeasible; collision resistance asks that finding any two distinct inputs with one digest be infeasible. Neither property follows merely from outputs looking unrelated to their inputs.

pre-image: given h, find m with H(m)=h  ·  collision: find m₁ ≠ m₂ with H(m₁)=H(m₂)
§2

The avalanche

Here's the property you can see. Flip a single input bit and, in a good hash, roughly half the output bits flip — with no pattern linking which. Toggle any input bit below and watch the change cascade through the mixing rounds. A one-bit nudge should scramble the whole output.

—
Click any input bit (top row) to toggle it. The vermilion output bits are the ones that changed versus the previous output. A good mixer changes about half, unpredictably — that's the avalanche.
Necessary, not sufficient. Avalanche is what a broken hash fails to show, so it's a useful first look — but a deliberately weak function can pass this eye test and still be trivial to invert or collide. The toy mixer here is one of them. Seeing the scramble is not evidence of one-wayness; it only tells you the output isn't obviously tracking the input.
Keyboard alternative: enter a bit position 0 to 15 to toggle, then apply.
§3

From random oracle to signature

The Fiat–Shamir transform replaces the verifier's challenge with a hash of the commitment, public statement and required application context; a signature also binds its message. A proof in the random-oracle model treats that hash as an ideal random function. Correct transcript binding and the proof's assumptions matter, and substituting a real hash does not automatically transfer the proof.

Hash the message to get an unforgeable challenge, and an interactive proof becomes a signature anyone can check.
Where this touches your keys

Used by several signature families

Schnorr-style signatures and ML-DSA use Fiat–Shamir ideas. ML-DSA uses SHAKE-based hashing and a construction often described as Fiat–Shamir with aborts. SLH-DSA belongs to a hash-based signature family with different assumptions and tradeoffs. These are distinct constructions, not one security argument applied to every signature.

Related: One-Way Functions (pre-image resistance in general), Reduction & Proof (what a proof in this model claims).

Sources and scope: RFC 8235 (2017); NIST FIPS 204 and FIPS 205 (2024). The interactive 16-bit mixer is an illustration, not a cryptographic hash.