Update: My calculations were only correct up to a constant. Turns out that Zero-Knowledge Proofs are flawed only on April Fools Days. 364/365 of the time ZK is still as ingenious as it ever was.
I have mixed feelings reporting my last discovery as on one hand it is undoubtedly my greatest discovery but on the other hand it comes at the expense of some of my scientific idols. For years I had the feeling that zero-knowledge proofs are too good to be true, but with so many of the greatest TOC minds working on the subject it seemed bullet proof. But in the last week I’ve been working on a post dedicated to zero-knowledge in celebration of the Turing Award to GM. The more I looked into it the more it became clear: zero-knowledge is not only too good to be true, it is simply is not true!
I am hard at work writing a detailed account of my findings (including a proof of why there is no possible meaningful fix for the notion of zero-knowledge). But I wanted to announce the result as soon as possible. Let me give a sense of where the bug lies. When a proof is zero-knowledge it means that apart from the real protocol (between the Prover and Verifier) we also have a simulator that can create a simulated run a protocol that seems completely real. As the simulator does not interact with the Prover it definitely learns no information, and as the simulated transcript looks real the verifier does not learn anything either. Right? Well not exactly. What GMR failed to take into account is pretty simple in retrospect: In reality nobody uses the simulator and in particular the Verifier *knows* it is interacting with the real Prover. So the indistinguishability from a simulated transcript fails miserably at the presence of this additional (aka. auxiliary) information.
How did nobody catch this bug before? I think the answer for this is pretty simple too. When a concept gets established we rarely question it. This has certainly happened to me in my past work on zero-knowledge. But we should be true to science, so farewell zero-knowledge, it’s both us and you!