How can a function be one-way, and does a quantum computer undo it?
Before the part that breaks, the part that does not. A secret needs a key and an open design, a fingerprint needs a one-way function, and both of those, the symmetric cipher and the hash, meet nothing worse than a square root.
A cryptographic hash turns any input, a word or a film, into a fixed-size digest, and it is built to make three things hard. Preimage resistance: given a digest, find any input that produces it. Second-preimage resistance: given an input, find a different one with the same digest. Collision resistance: find any two inputs with the same digest. The last is the easiest to break, because you are free to choose both inputs, and that freedom is the birthday effect: in a room of 23 people, the odds that two share a birthday pass one half, far sooner than most people guess.
Hashes sit inside nearly everything that matters here. A signature signs the hash of a message, not the message. A Merkle tree (topic 09) is built of hashes. A certificate is identified by its hash. Git names every commit by one. Bitcoin's mining is a hash puzzle.
What does a quantum computer do to this? Grover's algorithm turns a search through N possibilities into about the square root of N steps, so a preimage search for a 256-bit digest drops from about 2256 to about 2128 steps, which is still out of reach. Collisions already cost about 2128 on a classical machine for a 256-bit digest. Quantum algorithms for collisions exist on paper, but they need an enormous quantum memory, and Daniel Bernstein argued in 2009 that once memory is priced in they save nothing over the classical attack. That is why the standard advice is short: keep your hashes, and prefer the longer ones.
Avalanche. A good hash behaves as if each output bit flips independently with probability one half when the input changes. For a 256-bit digest the number of flipped bits is then binomial with mean 256 × 1/2 = 128 and standard deviation √(256 × 1/4) = 8. Measured over 4,000 random one-bit input changes for SHA-256 the mean was 127.9 and the spread 8.0, and the single pair above happens to land at 123, about 0.6 of a standard deviation low.
The birthday bound. Hash k inputs to n-bit digests. The chance of at least one collision is approximately
P(collision) ≈ 1 − e−k² / 2n+1 reaches ½ at k ≈ 1.1774 · 2n/2
For a 32-bit digest that is about 77,163 hashes, well under a second on a laptop. For n = 256 it is about 2128. The cost of a collision is the square root of the size of the output space, which is the entire reason digests are chosen twice as long as the security they are meant to give.
Grover on a preimage. Finding an input that hits one target digest among N = 2n candidates takes about (π/4) √N = (π/4) 2n/2 quantum steps, each a full hash evaluation run reversibly, and Bennett, Bernstein, Brassard and Vazirani proved in 1997 that no quantum algorithm can do better than the square root for unstructured search.
Change either text, even by a single letter, and watch how many of the 256 output bits move. The button runs the same experiment a thousand times on random messages and reports the average and the spread; an ideal hash gives 128 and 8.
Everywhere a name must be tied to content SHA-256 and SHA-3 digests identify files, certificates and commits, and are fed into every signature scheme. NIST's post-quantum standards keep them: the hash-based signature in FIPS 205 is built from hashes alone, and the lattice signature in FIPS 204 uses SHAKE internally.
Passwords are a different job A fast hash is the wrong tool for storing passwords, because speed helps the attacker. Password storage uses deliberately slow, memory-hungry functions (Argon2, bcrypt, scrypt). That is about brute force, not about quantum computers.
The ruling A quantum computer does not threaten hashing in the way it threatens public-key cryptography. It halves the exponent of a preimage search. Choosing a 256-bit digest leaves 128 bits, and that is why the next topic and the rest of the course look elsewhere for the damage.
Check yourself
You change one letter of the input to SHA-256. About how many of its 256 output bits will differ?
A good hash flips each output bit with probability one half, so the count is about 128 with a spread of about 8. The dog and cog example differs in 123 bits, and thousands of random trials average 127.9.