Skip to content

Act III · Zero-knowledge proofs

Exact change

A zero-knowledge proof lets you convince someone that something is true without revealing anything else. It matters because everyday checks ask for far more than they need. To prove your age, you show a card with your name, address and exact birthday, and small details like these, once combined, can identify you. This page follows the act from that problem to the idea itself, through an auction where you prove you can spot a fake painting without revealing how.

Ordinary details can identify you

In the 1990s, Massachusetts released its state employees' hospital records to researchers, with names, addresses and ID numbers removed. Latanya Sweeney, then a graduate student, bought the Cambridge voter list for $20 and placed it beside the medical data. Six voters shared Governor William Weld's birth date. Three of them were men. Only one lived in his ZIP code. Three ordinary facts linked his name to his medical records, even though the obvious identifiers were gone.

What the 87 percent means

In a separate study in 2000, Sweeney used 1990 US census data to estimate that 87% of Americans were probably the only person with their combination of ZIP code, birth date and sex. It's a historical estimate of how unique those details are, not today's rate of identification, and not proof that anyone can be found in a named database.

Maya's day

Maya, who is made up, goes through five everyday checks: paying for coffee, badging into work, proving her age, applying for a loan and renewing a prescription. Each check needs a single yes. Each one takes far more: her bank, her employer, her exact birthday, her salary, a clue to her medical condition. Linked together, they build a much fuller picture of her than any one check needed.

The second time through, each check gets only its answer, such as "over 21: true", and nothing else, so no copy of her forms. That's what a zero-knowledge proof aims for. The records in Maya's day are the story's assumptions, not a claim about what every café, employer, lender or pharmacy actually collects.

The auction: proving you can spot the fake

The Gallery turns the idea into a game. You own a painting made on one night in February 1987. At an auction, a man brings an almost identical one and says his is real. His was painted years later from the same spot, and he claims no one can tell the two apart. You know one difference. In February 1987, a star exploded and was bright enough to see for a few months before it faded. Your painting shows it. His doesn't.

Telling the auctioneer about the star would convince them once, but the man would hear it and paint the star in. After that, the star could never tell the paintings apart again. So instead, the auctioneer hides the paintings behind a curtain, shuffles them and notes which is which. You point to the fake. The auctioneer can check your answer against their own note, so they learn that you were right without learning how you knew.

Why the test repeats

One correct answer could be luck: a guesser has a one-in-two chance. Assuming each guess is a fair one-in-two choice and every shuffle is independent, the chance of guessing every answer right halves with each test. Someone guessing gets all three right about one time in eight. Getting all 100 right has a chance of about 1 in 1.27 × 10³⁰.

That number describes a guesser's luck. It isn't the chance that you're honest. The computer's 100 answers are also kept separate from your own three, including any mistakes.

What zero knowledge means, precisely

Shafi Goldwasser, Silvio Micali and Charles Rackoff first defined zero-knowledge proofs in 1985. A checker becomes convinced that a statement is true and learns nothing beyond that, under the proof system's assumptions. In the game, the secret stays private because only you have the magnifier. In a real proof, mathematics keeps it private, and the proof must show that the checker learns nothing else. A streak of correct answers on its own can't show that.

Two more limits matter. Picking the fake every time proves you can tell the two paintings apart; it doesn't prove where either painting came from. And a real age check needs a trustworthy link between the hidden birth date and an issued ID. Proving something about a birthday you made up proves nothing.

What you can try

First, watch Maya's day twice: once the usual way, as each check collects more than it needs and a copy of her builds up, then again with zero-knowledge proofs, where each check gets only its yes. Then enter the auction. Use your magnifier to find the missing star, choose whether to reveal it, take three tests yourself, and watch a computer take 100.

Where the model stops

Maya, the paintings and the people at the auction are made up, and the missing star is the story's chosen clue. The game decides who sees what to make the idea clear; it doesn't enforce that with cryptography. Real zero-knowledge systems also need a precise statement of what's being proved and clear security assumptions. And they don't hide everything: accounts, network data or links between visits can still identify someone.

Narration transcript

The narration as spoken in Act III. The explanation above covers what the illustrations leave out.

In the mid-nineteen-nineties, Massachusetts released its state employees' hospital records to researchers.

The governor said there was nothing to worry about.

Names, addresses, identification numbers, all removed. Anonymized.

A graduate student named Latanya Sweeney spent twenty dollars on the Cambridge voter rolls: names, addresses, birthdays.

She placed the public list beside the medical data.

Birth date, ZIP code, sex.

Six people shared the governor's birthday. Three were men. One lived in his ZIP code.

She mailed Governor Weld his own medical file.

Sweeney went on to show that those same three facts could uniquely identify eighty-seven percent of Americans.

Now follow someone we'll call Maya through one ordinary day.

To prove she is old enough, Maya shows an ID. The clerk needs one yes.

The card gives a name, an address, an exact birthday, and a license number that follows her.

Coffee records her morning.

A badge places her at work. A loan exposes her income. Telehealth exposes her prescription.

No service receives Maya's whole identity. The services begin assembling it between them.

What if each learned only the answer it asked for?

Old enough. Allowed inside. Enough income. Each answer true. Nothing else handed over.

A zero-knowledge proof claims it can do exactly that: prove the fact without revealing the person.

You're about to watch Maya either appear or not.

Watch the story →

Sources