Skip to content

Zero-Knowledge Proofs – Inherently Flawed

April 1, 2013

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!

11 Comments leave one →
  1. April 1, 2013 6:22 pm

    Knowledge is pure. It is real. It cannot be simulated by any Turing Machine, classical or quantum. Merely postulating that an efficient simulator produce transcripts that mimic the actual conversation was flawed from the beginning. What is surprising is that it took the TCS community to *first* award a big prize to the inventors of such specious claims before someone like Dr. Reingold to point out what should have been obvious thirty years ago! The purity of knowledge is what makes humans special, and even if we can create chess-playing machines and Jeopardy!-winning machines, we can never simulate (in probabilistic polynomial time) the conversations which reflect the **real** minds of an omnipresent, omniscient Prover (which can only mean one thing, all the major religions agree on this) and a human verifier. The all-powerful Prover doesn’t play captchas, let’s get over it.

    • April 1, 2013 6:32 pm

      This is deep and true, I couldnt have said it better myself.

      • Ross Snider permalink
        April 1, 2013 9:21 pm

        This is one of my favorite posts from today. Keep up the good work! 🙂

      • April 2, 2013 3:40 pm

        much obliged 🙂

    • jku permalink
      April 1, 2013 9:00 pm

      “Knowledge is pure. It is real. It cannot be simulated…”

      I think I’d need precise definitions of what you mean by “pure” vs. “simulated” knowledge to discern whether the above statement is accurate, inaccurate, or simply vacuous. However, a statement like “purity of knowledge is what makes humans special” is clearly in the latter category and contributes nothing to the discussion.

  2. anonymous permalink
    April 2, 2013 2:45 pm

    Good catch. I knew it. If it was true they would have made their own proof ZK!

  3. April 2, 2013 3:41 pm

    Thanks for all of the brilliant comments!

    When I was looking for a fake GM bug for this post, I remembered a story that happened way back when I was is graduate school. I gave a talk in a crypto/security workshop on pseudorandom permutations (one’s that are indistinguishable from truly random permutations). Following me, in the same session came a respectable researcher that claimed (absolutely seriously) that block-ciphers should not be analyzed as pseudorandom permutations because in real life the attacker knows that it is a block-cipher rather than a pseudorandom permutation. One would imagine that he would then move to suggest an even stronger notion, but instead he used for his analysis the much weaker (and undoubtedly much too weak) notion of key-recovery (where the challenge is to recover the key of the block cipher). I was too shy to react at the time, but I’m happy to have had the chance to recycle this infuriating experience into something better. 🙂

  4. Dominique Unruh permalink
    April 2, 2013 4:17 pm

    Dear Omer,

    as much as I appreciate your nice exposition on the subject, I believe that this result hat already been known for a number of years. See for example SSTW 2007, or BCC 2009. It is also well-known that quantum zero-knowledge proofs allow us to circumvent the issue — one simply runs the simulator with a low (but non-zero) amplitude. Nevertheless, I think it is beneficial that the problem is finally brought to the awareness of a wider audience.

    • April 2, 2013 5:05 pm

      Dear Dominique,
      Now that it is April 2nd, I’m not sure how to read your comment. Just so this post does not have a life of its own, I posted an update.
      Thanks,
      Omer

      • Dominique Unruh permalink
        April 2, 2013 8:16 pm

        Don’t be too hard on a late-comer… Feel free to read the relevant prior work in 364 days.

      • April 2, 2013 8:21 pm

        Not at all, and sorry if I sounded hard. Your comment was too convincing and I was afraid that I have created a monster ..

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: