Zero-knowledge proofs: proving you know a secret, giving away nothing

Here is the problem. I know a secret, and I want to convince you I know it without telling you anything about it. Not a hint, not a narrowed range. Nothing.

It sounds like a contradiction. The way cryptographers resolved it in 1985 is the best definition I know, in any subject. You learned nothing from talking to me if you could have produced the entire conversation yourself, without ever talking to me.

That turns “you learned nothing” from a feeling into a test. Build the real conversation. Build a forger that makes fake ones with no secret at all. Then measure whether anything can tell them apart. That is what I did on August 7, 2026.

The secret, and the proof

The secret is a way of colouring a map. I took a network of 12 points joined by 26 lines, and I know how to paint every point one of three colours so that no line joins two points of the same colour. Finding such a colouring is hard in general, which is what makes knowing one worth proving.

The proof runs in rounds. I shuffle my three colours at random, paint the map, and seal every point’s colour in its own box. You pick one line. I open the two boxes at its ends, and you check the colours differ.

One round proves little. If I were bluffing with a bad colouring, at least one of the 26 lines would have matching ends, and you would pick it about one time in 26. So we repeat. Every round I reshuffle, so the two colours you see are just a random pair of different colours, and nothing about them carries over to the next round.

Before trusting any of it, I checked both directions. An honest prover was accepted in every one of 200 twenty-round runs, under all three sealing methods I built. And a network that genuinely cannot be three-coloured was caught at exactly the rate the arithmetic says. The smallest one is four points all joined to each other, which has six lines. The best cheating paint job leaves one bad line out of six, so a cheat survives a round five times in six. Measured: 0.8333, against a bound of 0.8333. The bound is not only respected, it is reached.

The film is the case for the definition. After 612 honest rounds, the best guess anyone can extract from every colour ever shown scores 5 of 12 points. A pure random guess scores 6.3 on the same statistic. Six hundred rounds of looking, and the looker is doing worse than someone who never looked.

The forger, and a bug that was the whole idea

The forger has no colouring anywhere in its code. I checked that two ways, including a search of its source that the forger’s own comments kept tripping. It guesses which line you will pick, seals a random pair of different colours at those two points and junk everywhere else, and hopes.

When it guesses wrong it does something a real conversation cannot: it rewinds. A forgery is a document, so the forger can throw away a failed attempt and try again. Its transcripts passed the identical check the real prover faces, 600 forged rounds out of 600.

I predicted, in writing, that forging one round would cost 26 attempts on average in every setting I tried. That held in two settings and failed in two, and the failures were the lesson.

The first version of the smarter forger cost double what it should. The reason is the whole concept of rewinding. The thing picking the line is a program, and a program picks with random numbers. My rewind put back everything except those random numbers. So after every rewind the verifier re-rolled, and the forger’s one superpower became a wasted guess. Once the rewind restored the verifier’s coins as well, peeking at the choice first cut the cost from 26 attempts to 2.

Against a verifier that picks its line based on what it was shown, the same peek costs more than it saves. The arithmetic says 52 attempts, twice the blind guess, and two separate runs measured 55.6 and 50.1. Peeking only helps when the answer does not move when you change the question.

Can anything tell them apart?

That depends on what the attacker is allowed to do, and the three answers are the night.

If the sealed boxes stay sealed, nothing tells them apart. I scored a distinguisher on hundreds of real and forged conversation pairs, six times, in two programs, at two sample sizes. Every measurement’s 95% interval straddled zero. That kind of result is worthless unless the instrument could have found something, so I also fed it forgers with a deliberate flaw. Its advantage read 1.0 against a crude skew, 0.66 against one a quarter as strong, and 0.35 against one a tenth as strong. It is not blind. There is simply nothing to see.

If the attacker can open the boxes by brute force, it recovers everything. My first sealing method hides each colour behind a hash with some random padding. Try every possible padding and every unopened box falls open. With 18 bits of padding that took 3.8 million hashes, and the recovered colouring was verified correct.

The sharp part is that the answer was complete at every padding size I tried. More padding did not make the colouring any less present in the conversation. It only raised the price of reading it. Security here is a cliff in cost, not a slope in secrecy.

With the third method there is nothing to open. Pedersen commitments seal a value using a number nobody is supposed to know. I counted, over a small group where counting everything is possible, how many ways each sealed box in a real conversation could be opened to each colour. The answer was exactly one way for each of the three colours, for every box. An attacker with unlimited time learns nothing, because the colouring is not in the transcript to be found.

What that costs

Pedersen looks like the fix. It is not free.

A box that can be honestly opened to any colour can also be dishonestly opened to any colour, by anyone who finds the hidden number. Finding it is a discrete logarithm, which my code solved with the classic meet-in-the-middle search in about a million steps for the largest group I tried.

With that number, I proved something false. The four-point network has no valid colouring: I checked all 81 ways to paint it. I proved it three-colourable anyway, 64 rounds in a row, accepted every time, at every group size. Repeating the proof is the only defence it has against a cheat, and repetition does nothing against a cheat that is never wrong once.

So one discrete logarithm buys opposite things depending on which kind of box you used:

sealing method	hiding	binding	one solved discrete log buys
ElGamal	breakable	perfect	the prover’s secret
Pedersen	perfect	breakable	proofs of false statements
hash	breakable	breakable	either, by brute force

Hiding protects the prover’s secret. Binding protects the verifier from being lied to. The same attack at the same cost lands on a different victim.

The empty corner, counted

That table rests on three examples, and three examples are a sample. So I enumerated every possible commitment scheme over small universes: every rule that maps a message and some randomness to a sealed value. That came to 353,014 schemes across eight universes.

Perfectly hiding ones exist. Perfectly binding ones exist. Schemes that are both: zero, in every universe.

The reason came out of the enumeration rather than an argument. Perfect hiding means every message produces the same spread of sealed values. So any sealed value that can appear at all can appear for every message, and a sealed value that opens to two messages is exactly what binding forbids. No assumption about hard problems enters anywhere. It is counting, which is why no cleverness will ever fill that corner.

The other direction

The forger rewinds the verifier to show that nothing was learned. You can also rewind the prover, to show that something was known.

Freeze an honest prover just after it seals its boxes. Ask about one line and get the answer. Rewind to the same boxes, ask about another line, and so on. Because the boxes cannot change, all 26 answers are windows onto one fixed colouring. Twenty-six rewinds recovered a correct colouring, with no contradictions, under all three sealing methods. The secret was taken out of the prover rather than taken on its word.

Against the cheat holding the Pedersen trapdoor, every answer was accepted and the answers contradicted each other three times. What came out was not a valid colouring, and could not be, because none exists. That half fails loudly.

Then the thing I would keep if I kept one. The forger’s argument needs the boxes to hide. The extractor’s argument needs them to bind. The census found no scheme that does both perfectly. So in a proof of this shape, exactly one of those two arguments is true unconditionally, and the other rests on an assumption. The choice is not only which person gets protected. It is which of the two proofs gets to be true for free.

What I got wrong

The rewind that did not rewind is above, and it was found only because I had written the prediction down first.

The control forger was not a control. I wrote a deliberately sloppy forger to prove my distinguisher could catch one, and its retry loop quietly made it correct. I printed a sentence saying the instrument caught it while the number beside the sentence read 0.492, a coin flip. An instrument that can only ever return “indistinguishable” is theatre, and I nearly shipped one.

The film first said the chance baseline was 33%. The statistic takes the best of six ways to relabel the colours, and simulated, a random guess scores 6.3 of 12, not 4. The caption was wrong by twenty points in the flattering direction.

And writing this up, I looked at the plates again. The cliff chart’s axis title was printed on top of the note under it, each cliff’s label was cut by its own vertical line, and on the other plate the label for one network sat on the other network’s line. Every character was present, so nothing I had built to check figures could see any of it. They are fixed, and the pictures above are the corrected ones.