Talk:Zero-knowledge proof

From Wikipedia, the free encyclopedia

This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography in the Wikipedia. If you would like to participate, you can choose to edit the article attached to this page, or visit the project page, where you can join the project and see a list of open tasks.

Contents 1 Definitions 2 Peggy and Victor Example 3 Images todo 4 Question 5 Man In the Middle Attack 6 Broken Link 7 A slightly different example section 8 I changed "NP" to "NP-complete"

[edit] Definitions

The article starts off with some confusion between zero-knowledge proofs and zero-knowledge proofs of knowledge, which have extra properties.

I've attempted to correct this, by describing ZKPs in terms of proving validity of statements, instead of proving that a party "knows something."

Thanks. Would it be useful to add a definition of zero-knowledge proofs of knowledge, too? — Matt 17:54, 16 Nov 2004 (UTC)

Yep, undoubtedly. However, the definition of PoK is pretty complicated (when done formally). Of course, it can be said "in words"...

I tend to think that Wikipedia should include both technical definitions and informal descriptions, so that it's of use to a large group of people. One strategy is to "hide" the harder, more formal stuff later on in the article, and present only the hand-wavy stuff at first. — Matt 10:19, 17 Nov 2004 (UTC)

[edit] Peggy and Victor Example

I'm new to ZKN, so with that disclaimer, I was initially confused about how Victor is not able to impersonate Peggy after learning, with high probability, both the graph G and the Hamiltonian cycle. I think I see it, and believe that the wording could be augmented for clarity. Original augmented with italics of my own adding:

"The information revealed by Peggy does not give Victor any information at all about the Hamiltonian cycle of G.

In each round, Victor receives a fresh vertex-label randomization of the graph, encrypted with unique keys that only Peggy knows; further, he receives an answer to exactly one question, which is either "reveal the graph" or "reveal the Hamiltonian cycle," but not both.

If he requests the graph, Peggy "reveals" (gives him keys enabling him to decrypt) all edges and gives him a mapping of the random vertices to the true vertices. From there, he can easily verify that the graph he has is identical to the published graph G. In this case, Victor knows the graph, but not the cycle.

If he requests the cycle, Peggy reveals the cycle, but keeps the vertex mapping a secret, such that he can verify that what he has is a cycle with the same number of vertices as published graph G. By doing this, Peggy is revealing a subgraph that is isomorphic to the real Hamiltonian cycle that only she knows. In this case, Victor knows the cycle, but not how it maps onto the published graph.

In subsequent cycles, Peggy issues a fresh randomization and encryption of her graph to Victor, and allows him to ask only one question.

If Victor were to try to impersonate Peggy, it would be impossible for him without knowing the Hamiltonian cycle for G to create a randomized, encrypted graph that both maps to the original graph G and has a valid Hamiltonian cycle for the graph. The impersonator does not get to choose which question to answer - thus, the impersonator's encrypted graph would have to successfully stand up to both questions, which we said is NP-hard to do.

Another point worth knowing is that

... Victor can manufacture a transcript of the game without talking to Peggy at all. He can select a sequence of heads and tails, and then prepare hypothetical replies from Peggy, without ever knowing the Hamiltonian cycle himself, by following the appropriate impostor strategy in each round. The transcript itself, and the information it contains,

does not provide proof of possessing Peggy's ability to identify the Hamiltonian cycle in G: Zero Knowledge Proofs require interaction on the part of the verifier.

[DELETE: has no clue about the legitimacy of Peggy's identity.]

... Peggy proves her identity not because she can give the right answers, but because she can give the right answers without knowing what the questions will be."

Please be bold and just change it. It's a lot easier to review changes in the article itself. Deco 22:19, 13 February 2006 (UTC)

[edit] Images todo

User:Dake has authored these fine diagrams on Commons:

Todo: Add these to the article (with a text description of the cave thing). — Matt Crypto 12:11, 20 September 2005 (UTC)

Done. I don't remember the exact details, so I made up some stuff. Also, I don't remember what the original source is - could you add a citation? Feel free to edit in any other way. Deco 22:48, 13 February 2006 (UTC)

[edit] Question

This isn't really a question about the article's content, but more about zero-knowledge proofs. In the cave story, why bother with randomly choosing paths? Why can't they just go to the fork in the path, and Victor watches as Peggy goes down path A and re-emerges from path B? Isn't that sufficient to prove that Peggy knows how to open the door, and doesn't it not give Victor any information about the word? Decrypt3 04:00, 3 April 2006 (UTC)

You're pushing the analogy too far. You might as well ask why we need zero-knowledge proofs at all, since there is no such thing as a cave with a magic door. -- Dominus 15:18, 3 April 2006 (UTC)

Or perhaps the analogy is inappropriate? As another casual reader, I think Decrypt3 pose a very legitimate question. Why choose probalistic testing when the analogy suggest that deterministic testing can be achieved? --AndersFeder 01:41, 13 May 2006 (UTC)

Perhaps, but a brief explanation of that wierdness does help. The basic idea is that randomising as much of the information in the exchange reduces the probability that more than the desired fact leaks. If Victor knew the path, she took, he could follow her and eavesdrop on the actual password. By randomising her initial path, the odds of that happening are reduced by 50%. Every little bit helps, this is an exercise in probabilities remember. Danpat 14:52, 4 May 2006 (UTC)

[edit] Man In the Middle Attack

I think this article should mention the man in the middle attack aginst this protocol. —The preceding unsigned comment was added by Yongqli (talk • contribs) 01:22, 17 April 2006 (UTC)

[edit] Broken Link

The link to "How to Explain Zero-Knowledge Protocols to Your Children" (ref #1) appears broken. I'll fix it later when I'm not in a hurry, but I figured I'd write this here until someone gets around to it first. wdaher 01:59, 13 May 2006 (UTC)

[edit] A slightly different example section

I just redid the example section quite a bit and changed the type of zero knowledge proof described. I find this example with isomorphic graphs to be more intuitive than the previous encrypted graph example. Any problems with the Peggy/Victor scenario I outlined? Disclosure: I am pretty sure I got it straight out of the book Applied Cryptography.

Also, I changed the focus of the example from specifically party identification to a more general proof-of-knowledge, so all different applications are covered.

One more thing: I am a bit new to editing wikipedia articles, so what is the best way to consolidated external links? Should I use footnotes or the external links section instead of "(see $REF)"? --Ec- 17:25, 16 August 2006 (UTC)

[edit] I changed "NP" to "NP-complete"

(see comment) and then I realized I should have checked here first. The 'owner' should change it back if (s)he feels it's not correct or appropriate, but a discussion would be valid. Andrei r 20:22, 12 March 2007 (UTC)