Talk:Zero-knowledge proof

Cryptography: Computer science Unassessed

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
???	This article has not yet received a rating on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the importance scale.
	This article is supported by WikiProject Computer science.

Man In the Middle Attack

I think this article should mention the man in the middle attack aginst this protocol.

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)

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]