← 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

A cryptographic hash must be one-way — given an output, you cannot find an input that produces it — and collision-resistant — you cannot find two inputs that produce the same output. Both reduce to one visible behavior: the output must look utterly unrelated to the input.

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 random-oracle model is the engine of the Fiat–Shamir heuristic: it turns an interactive proof — where a verifier sends random challenges — into a non-interactive signature, by replacing the verifier's coins with a hash of the message. If the hash behaves like a random oracle, the challenge is unpredictable, and the proof stays sound.

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

Under most deployed signatures

Fiat–Shamir is everywhere in deployed cryptography: ML-DSA and Schnorr-style signatures convert an interactive identification proof into a signature by hashing — with SHA-256-class functions playing the oracle. ML-DSA is literally "Fiat–Shamir with aborts" over the polynomial ring. The random-oracle assumption is the ground all of that stands on — though not every signature needs it. SLH-DSA, the hash-based standard, is built to rest on concrete properties of its hash function rather than on an idealized oracle, which is exactly why it exists as a conservative backup.

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