Talk:Zero-knowledge proof

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?

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)

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)

Example with a cave is nice, still it only shows 'interactive proof' part. It may be reasonable to extend it with 'zero-knowledge' by describing a simulator, a transcript and deciding on protocol transcript, which are alternative news story scenario, tapes submitted as evidence to a court, and court ruling in the original article.

195.238.92.2 (talk) 17:56, 26 December 2008 (UTC)

Actually I think the cave example does a good job of demonstrating zero knowledge; Victor learns only that Peggy knows the magic word and nothing else in this scenario. Dcoetzee 02:33, 27 December 2008 (UTC)

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)

Also, when we extend this to a less-visual, computerized interaction with things like bit commitments and exponents, the idea of following Peggy to see which tunnel she "commits" to does not translate well. Decateron (talk) 22:53, 11 July 2008 (UTC)

Watching Peggy walk down path A and coming back path B would be a proof of knowledge, but not a zero-knowledge proof. The difference is that a zero-knowledge proof needs a simulator. Assume that Victor has a video camera and is recording the rounds of the zero-knowledge proof including him throwing a coin to show that he is randomly choosing his questions. Assume that Eve and Mallory want to make a similar video but they don't know the password. They can do so by guessing the coin throw having Eve walk down the guessed path, recording her coming back the right path if they guessed right and rewinding the video if they guessed wrong. Given the videos by Victor/Peggy and Eve/Mallory it should not be possible to tell which one is the video with the person who knows the password. It may seem strange at first to ask for this possiblity to simulate the proof. The point is that if there is a simulator then this should imply that Victor really didn't learn anything from the protocol since all he did see could also have been played out in a simulation. 85.2.48.226 (talk) 05:34, 5 August 2008 (UTC)

You can concoct a recording of "Peggy walking down path A and coming back path B" just as well, can't you? (Formally that would be just the matter of simulating "prover commits to 0 and outputs 1"; you seem to be assuming irrelevant details from physical videos and/or physical caves.) Decrypt3's and Decateron's points are valid; the current presentation works in principle but it is simplifiable in a pitiful manner. I would propose to apply (or at least mention) Decateron's directionality fix. 87.110.161.64 (talk) 09:25, 1 September 2009 (UTC)

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)

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)

I've checked and it was already fixed. --Blaisorblade (talk) 17:05, 16 July 2008 (UTC)

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)

Is there a preference for DL as an additional example or DL in place of the graph isomorphism example? (Decateron (talk) 22:45, 11 July 2008 (UTC))

An example based on DL would certainly be informative. Why does it have to replace one of the existing examples? I.e., the graph isomorphism is quite good to show the commitment phase (at least if it is presented correctly.) 81.62.44.149 (talk) 11:02, 27 December 2008 (UTC)

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)

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)

Digital signatures as zero-knowledge proof of knowledge of private key

While studying the Direct anonymous attestation protocol, I've seen usage of a digital signature algorithm (in this case, the Schnorr's algorithm, or a slight variant) as a zero-knowledge proof. Indeed, a digital signature proves that the signer knows the private key without disclosing any part of it to the verifier, and seems to be a zero-knowledge proof. Shouldn't this be discussed in the article? Googling around found a technical confirmation of this, under some hypothesis: [2] (also here), i.e. "Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract)" by Shafi Goldwasser and Rafail Ostrovsky; but the article warrants at least a mention of the comparison, and that the fact that there may be some difference (if any, I've just read through the abstract).

--Blaisorblade (talk) 14:14, 9 July 2008 (UTC)

Schnorr signature is a non-interactive variant of a protocol, however zero-knowledge property is missing (that is, no simulator). It is still witness hiding. User credentials with Direct Anonymous Attestation is a data signed with Camenisch-Lysyanskaya scheme.

195.238.92.2 (talk) 17:48, 26 December 2008 (UTC)

"unpublished manuscript"

Why is such a source cited? It is valueless. —Preceding unsigned comment added by 129.132.45.22 (talk) 17:24, 3 August 2008 (UTC)

Corrections

Correct me if I am wrong, but completeness for knowledge of Hamiltonian cycle problem, is confused with soundness.

During each round, Peggy does not know which question she will be asked until after giving Victor H. Therefore, in order to be able to answer both, H must be isomorphic to G and she must have a Hamiltonian cycle in H. Because only someone who knows a Hamiltonian cycle in G would always be able to answer both questions, Victor (after a sufficient number of rounds) becomes convinced that Peggy does know this information.

Shouldn't completeness just say that Victor always accepts if G contains a Hamiltonian cycle and Peggy follows the protocol?

Also, it seems a committment scheme is necessary for this example, wouldn't plain Graph Isomorphism, be an easier example? Couldn't we use Protocol 2 in "Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems"? Icmpecho (talk) 11:38, 4 April 2009 (UTC)