Talk:Zero-knowledge proof

From Wikipedia, the free encyclopedia

WikiProject on Cryptography This article is part of WikiProject Cryptography, an attempt to build a comprehensive and detailed guide to cryptography on 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

[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)
It seems that completeness (termed non-triviality by Goldreich wrt PK) is the same for both zero knowledge and proof of knowledge. Is this correct? It seems to me that proof of knowledge is zero knowledge with the additional property of validity (which is a stronger def of ZK soundness). Thus, ZK \subset PK. Am I correct?

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


I'm not sure that I buy this example either. It seems to make a tacit assumption that graph isomorphism is not in P, a statement is yet undecided. Given a deterministic polynomial algorithm for graph isomorphism, it would be feasible for the verifier to simply do the following:

1. Ask the prover for the Hamiltonian cycle

2. Compute the isomorphism from H to G

3. Apply isomorphism to the cycle, recovering Peggy's private information

  • In steps where the prover divulges the cycle, she does *not* divulge H, so the verifier cannot perform step 2. -- Dominus (talk) 20:42, 13 January 2008 (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)
Seems, the last paragraph of the article subsection now explains why Victor cant just wait outside, and make Peggy come out of the other side. The explanation says that by choosing a random, unknown (to Victor) path, it reduces the chance of eaves-dropping by Victor (by following Peggy). However, this is terrible explanantion, as Victor can eavesdrop along a random path and with probability 50% succeed... and since they repeat 20 times, his probability of eaves-dropping goes up tremendously. The correct explanation is the following. The password works in only one direction, and this information should also not be disclosed to Victor. Hence, Peggy must take a random path (unbeknownst to Victor). Ustad NY 14:19, 27 July 2007 (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)


Perhaps a discrete log style ZK protocol would be a good mathematical example. The example at least needs a clearer description of Peggy's bit commitment that happens prior to Victor's challenge. There also isn't a clear exposition of the simulator or why Victor can't impersonate Peggy or go prove to Eve that Peggy knows the secret.

My problem with the Hamiltonian graph problem is that Peggy's preparation is hard to describe clearly in a way that translates to a mathematical application. She must do a random permutation of the graph, then Victor asks either for the cycle or the proof of isomorphism. In the first case, Peggy should not reveal any information about the structure of the graph when she presents the cycle in the permuted form. For example, if the graph has "interesting" edges, these could reveal information about how the cycle fits into the original graph when it is viewed in the permuted graph. I will prepare a discrete logarithm example shortly, and then we can always revert back if there are objections. (Decateron (talk) 18:46, 3 June 2008 (UTC))

The ZK protocol with the Hamiltonian graph is indeed badly described. In fact, Peggy first just commits to a description of H, but does not reveal it. If asked to show an isomorphism she will uncover the full description of H and show the isomorphism. However, when asked to show the Hamiltonian path, she only uncovers the edges of the Hamiltonian graph. The nice thing about this ZK protocol is that it can be performed with pencil and paper only: Peggy writes each edge of H on a small piece of paper and puts them upside down on a table. When asked to prove the isomorphism she turns every piece of paper and proves the isomorphism. Otherwise she only turns those pieces that are part of the Hamiltonian path. 85.2.53.175 (talk) 21:02, 3 June 2008 (UTC)
When you say "writes each edge" do you mean like a random face-down pile of pairs (V1,V2)? I think that makes more sense than the way I always envisioned it: draw the graph where all the vertices are randomly placed in a ring with their original labels, then draw the connections, then put lottery-ticket paint over the vertices, the edges, and the *non* edges, so you have a complete-looking graph. Then for the query "show graph" Peggy scrapes off *all* the paint; for "show cycle" she traces out the cycle edges showing that each vertex (not showing labels!) is contained. Note that here the "show graph" reply gives Victor something really easy to verify since the vertices have their original labeling, but are just moved around in the commitment and only revealed for "show graph." In the paper method, would Peggy also provide Victor with the mapping from G->H? (Decateron (talk) 14:58, 4 June 2008 (UTC))
The description consists of two parts. Part 1 is a mapping from the canonical, standard labels of the vertices to new, ad-hoc labels. Part 2 is a pile of pairs of ad-hoc labels, one pair for each edge of H. For "show graph" Peggy reveals all the pairs and also the mapping. For "show cycle" she reveals the pairs that form the cycle, but not the mapping. See [1] for an example. -- Dominus (talk) 19:32, 4 June 2008 (UTC)
OK, this pieces-of-paper description eliminates the shortcomings I have found with other presentations of this particular example in the past - namely not revealing information about a vertex's order in "show cycle." Thank you for the clarification. -- (Decateron (talk) 23:23, 4 June 2008 (UTC))
It appears that this article became another victim of "Applied cryptography". The version of the graph example before August 16, 2006 was much better than it is now. Maybe we should just revert about 2 years of changes on this section. Btw, I'd also support your suggestion to add a section with a discrete logarithm example. Such an example may be better suited to explain how the protocol can be simulated. 85.0.103.65 (talk) 20:09, 5 June 2008 (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)

[edit] List of proofs

Would it be valuable to establish a list of zero-knowledge proofs (like the List of NP-complete problems)? --Johnruble 15:56, 22 June 2007 (UTC)

I doubt I'll learn enough about this stuff to make the contributions I'm suggesting, but ultimately it'd be swell to subdivide off a section for zero-knowledge identification schemes like the linked Feige-Fiat-Shamir Identification Scheme. Schneier's book follows FFS identification with Guillou-Quisquater and Schnorr. --Johnruble 15:20, 6 July 2007 (UTC)