Talk:Zero-knowledge proof

Cryptography: Computer science C‑class High‑importance

	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
C	This article has been rated as C-class on Wikipedia's content assessment scale.
High	This article has been rated as High-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as High-importance).

Definitions

Disclaimer: I am new at this "talk pages", so please forgive me if I'm adding the entry by editing the wrong way.

With that said --- my entry to the discussion: I am fairly certain that the definition given is incorrect. From Goldwasser/Micali/Rackoff paper itself, the definition given talks about proving a statement without conveying any additional knowledge other than the correctness of the proposition being proved. And I don't think one implies the other one; maybe in the context of a zero-knowledge proof of knowledge this is implied by information theoretical arguments?

Either way, I think the definition should be the "obvious" one (obvious in the sense of what the term zero-knowledge directly says). I will change it some time in the next few days, unless I see some convincing arguments in favor of the way it shows now (as in, why this definition is correct and if so, why it would be preferred to the "obvious" definition as given by G/M/R) --- Cal-linux (talk) 22:19, 26 March 2013 (UTC)[reply]

---

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

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

computational indistinguishable should be computationally indistinguishable

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]

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

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

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

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

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

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

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

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 signals on the other line"; 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 Decateron's directionality fix, but there's a complication that Peggy can learn the direction on the first trial. Maybe claim that the direction is varying and she knows the pattern... (The password is irrelevant.) 87.110.161.64 (talk) 10:02, 1 September 2009 (UTC)[reply]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Hamilton is confused

The Hamiltonian path example is confusing, at least, if not confused. It is not clear why an ignorant Peggy cannot generate, on each round, a valid H and also a random J together with a Ham-path on it. How would Victor be assured that H and J were identical?

Mind, I don't doubt that the mechanics envisioned expressly forbid this strategy. I just say that the description given does not make this clear; for that matter, very little of it is clear; and I have considerable background in graph theory. I understand what is being said and don't feel that my objection is, per se, valid; but a reasonable person might raise it. It took me several readings to grasp what it is that Peggy commits to, what Victor sees prior to his demand, what he sees subsequently, and so forth. The mechanics are strained and artificial.

Since graph theory is basically not taught at the high school level and it's not immediately clear to the untrained how any of it works, I'd suggest a much simpler example. Part of the confusion here is that the game depends heavily on probability. (For example, if G is small, the game is trivial.) Asking the reader to wrap his head around both probability and graph theory is too much.

I'd incline to a game based on balls in bags. Sorry. — Xiong 熊 talk * 10:39, 21 January 2010 (UTC)[reply]

Balls

A little thought suggests an approach. This is not my field, so let's have the comments.

This game involves a large quantity of lettered bags, in each of which is a quantity of numbered balls. Peggy claims to know which balls are in each bag. Victor knows nothing except the constraints: bags are lettered, balls are numbered, and each bag holds balls of only a single number.

Prior to each round, Peggy removes one ball, individually, from each bag and puts it into one of another set of small bags, which she has marked previously by colored dots visible only to her. This removal is performed in front of Victor and with a closed hand; that is, Victor can see that Peggy cannot see the balls during the trip from the letter-bags to the colored-dot-bags. Peggy shuffles the colored-dot-bags.

Now Victor demands to see, for instance, a ball numbered 42. Peggy then opens the appropriate colored-dot-bag and reveals the correct ball. At no time does she expose the colored dots to Victor; she alone can see them.

The round ends when Peggy dumps all the colored-dot bags out, discarding their contents.

Completeness: Peggy can only retrieve, on demand, a ball of a given number if she knows the number-ball to letter-bag and the letter-bag to colored-dot-bag mappings. (She might get lucky a few times but over a large number of trials, etc.) Therefore she supports her claim to know the number-ball to letter-bag mapping.

Soundness: The chance of Peggy producing the right ball on demand (if ignorant) is ${\frac {1}{N}}$ ; the chance of doing so through $T$ trials is $\left({\frac {1}{N}}\right)^{T}$ , which quickly vanishes as a realistic probability (for some value of "realistic").

Knowledge: Peggy establishes the letter-bag to colored-dot-bag mapping in Victor's sight (she is seen not to discover, in the process, the number-ball to letter-bag mapping); but since the colored dots are never seen by Victor, he learns nothing from the game about the prize in question. The colored-dot-bags having been shuffled, when Victor sees the ball he demands, he has no idea which letter-bag it came from.

Again, this is not my field but it seems obvious that, if Victor is given the number-ball to letter-bag mapping, he can simulate the exchange without Peggy's help.

So. A few things about this game remain uncertain to me; I have suspicions but no proof:

Is it permissible for Victor to demand more than one ball per round?

Could Victor simply demand of Peggy that she order the colored-dot-bags (by number), then reveal all of their contents?

If so, I lean toward eliminating the colored-dot bags and having Peggy simply order the balls while blindfolded behind a screen that prevents Victor from seeing exactly what she's doing but lets him see she's not peeking.

Does anybody want to make a fuss about Victor knowing beforehand how many bags there are, or the range of the numbers, etc.? (If he already knows, he learns nothing of this nature during the game.)

It would undoubtedly be more elegant (and concise) to have only one ball per bag but I don't like the idea of Peggy putting the tainted balls back. Any way around this?

Ground rules (do as you like, of course; these are mine): Since I don't know anything, I won't argue about the merits of the game. I'll help if in any way I've been unclear. If you feel this example is equally strained, sorry; I certainly won't try to argue that subjective point. I welcome any attempt to improve.

Oh, and if consensus emerges to support this game, I will be happy to contribute appropriate graphics.

— Xiong 熊 talk * 11:55, 21 January 2010 (UTC)[reply]

Commitment scheme

In the Hamiltonian cycle example, why is a commitment scheme needed? ie what advantage would a cheating verifier gain by knowing H before deciding what to ask for (under the assumption that finding cycles and isomorphisms are computationally impractical)? Also as Icmpecho pointed out above, the claim that a cheating prover would (with high probability) be found out belongs under soundness, not completeness; I'll go ahead and be bold on that one. Stewbasic (talk) 21:58, 19 September 2011 (UTC)[reply]

Actually on further thought I think I understand; this version only assumes that the Hamiltonian path problem is hard, not the graph isomorphism problem. Even if Victor can find graph isomorphisms, when he asks for the cycle Peggy only reveals the cycle edges, so Victor does not see a graph isomorphic to G. Perhaps this could be made clearer in the zero-knowledge section. Stewbasic (talk) 22:16, 19 September 2011 (UTC)[reply]

WPA2?

I'm thinking that WPA2 (and WEP, WPA) must use a kind of zero-knowledge proof authentication. Right? Because what they do is that they both prove that they know the preshared key, but in a way where they don't reveal the pre-shared key to the other part (because he could be an impostor). I have been looking for information about this, but when I google zero-knowledge wpa2, not much legit comes up.

I must admit that I do not understand all of this article, since it is quite theoretical. Have I misunderstood this, or is it fair to say that the WEP/WPA/WPA2 use zero-knowledge proof systems? Thanks

85.97.254.28 (talk) 16:29, 4 May 2012 (UTC)[reply]

Peggy and Victor, don't get it...

I told it to my son and he asked me: Why doesn't Victor simply send Peggy through A and sees if she appears at B? She'd prove that she knows the password without revealing it! João Pimentel Ferreira 16:46, 24 January 2013 (UTC)

"Cheating" Verifier and the existence of a simulator

The article talks about a "cheating" verifier, and that a "simulator" is needed to ensure the "Zero-Knowledge" property.

Here's some of what I do understand:

The existence of the simulator means that any third party who eavesdrops the exchange between Pat and Victor cannot know if Pat really knows the secret, because the questions might have been rigged.
Thus, a simple digital signature cannot serve as a ZKP of public-key knowledge, because a witness could validate the signature and see that the digital signature is correct or not.
At first, I thought that an HMAC with a random key would work, but a witness who knows the secret password could validate or reject the hash.

Some particular points I don't understand:

What exactly is a "cheating" verifier?
What benefit could a verifier gain by cheating (with or without ZK)?
What are the benefits of this particular design?

I mean, it's obvious to me how helpful it would be if I can prove that I know a password without having to tell that password to a remote system. But I don't see how the existence of a simulator aids in that.

Stevie-O (talk) 17:47, 28 January 2013 (UTC)[reply]

Peggy and Victor and the cave

The "children's example" given, with the magic word in the cave, doesn't actually explain why Victor wouldn't just send Alice down Fork A and watch her come back along Fork B. But the original paper does explain it, remarkably well; the problem has to do with making sure that a recording of the protocol wouldn't convince anyone else. Which is the fundamental rule of a ZKP, as I vaguely remember it: it's not merely that Peggy (or Mick Ali, in the paper) guards her secret magic word; it's that Victor (or the TV reporter), although 99.999% convinced himself, is 100% unable to convince anybody else that Peggy (or Mick Ali) has any special knowledge at all. Only the people who were party to the original experiment are convinced; everyone else is justifiably skeptical. --Quuxplusone (talk) 19:17, 8 February 2013 (UTC)[reply]

But if all we want to do is preserve Peggy's secret, and don't specifically care about Victor's inability to persuade anyone else, here's a much better variant of the parable:

There's a long U-shaped hallway with two exits (call them "west" and "east"). At the bottom of the U the passage is blocked by a solid steel door. Both sides of the doorknob have keyholes, but (unconventionally) the keyholes are different shapes, so that you need a different key to unlock the door from the east than you do from the west. Call these two keys Key EW and Key WE, respectively.

Peggy possesses one of these keys — either Key EW or Key WE — but she really doesn't want Victor to know which of the two keys she possesses. However, she *does* want to prove to Victor that she has (at least) one of the two keys.

Victor says: "Prove to me that you have a key to that door!" Now, Peggy could just enter the hallway at entrance "west", unlock the door, and come back out via entrance "east"; but that would indicate to Victor that Peggy definitely had Key WE, and she doesn't want to give away that information.

Peggy could instead tell Victor, "Give me some prep time." While Victor promises not to peek, Peggy goes to the door by her preferred side, opens it, and props it open with a brick. Then, with Victor watching, Peggy enters by the east entrance, goes through the propped-open door, and exits by the west entrance. This proves that the door was opened, while concealing the identity of her key. In fact, Victor can watch the whole process, as long as Peggy goes down each side of the hallway in turn during the setup and Victor can't see what she's doing down there. (He won't know on which trip she opened the door and which trip was just a red herring.)

But what if Peggy doesn't have a brick to prop the door with? Or Peggy is sufficiently security-conscious that she'd never prop a lockable door open for any amount of time? Well, we can still salvage the zero-knowledge proof, by turning it probabilistic. This time Victor really does need to close his eyes and turn around. Peggy goes down the branch of the hallway corresponding to her key. Victor opens his eyes and shouts, "Come out of the ____ entrance!" Well, if Peggy originally went down that branch, no problem. If Peggy went down the other branch, then she's got to use her key to get through the door, and then she can still satisfy Victor's demand.

But of course if Peggy doesn't have a key (i.e. if she's lying to Victor), then she'll be incapable of satisfying his demand approximately half the time, because she can't get through the door.

One iteration of this protocol won't satisfy Victor, since Peggy could have just guessed what he'd demand with 50% probability. But if Victor and Peggy repeat the protocol a dozen times, the odds go down to 1 in 4096 that Peggy is just doing this by chance. Clearly Peggy does have a key (although because he doesn't get to watch the setup Victor can't tell which key). ...Or else she's psychic, or else she knows a back door that Victor doesn't. But Victor presumably assigns those options really low prior probabilities, so he concludes: "With very high probability, Peggy must have either Key EW or Key WE... but I don't know which."

Q.E.D.!

The probabilistic proof protocol in this case coincidentally turns out to also be a zero-knowledge proof protocol, but that is not the motivation for turning the proof probabilistic. The motivation in this case is that Peggy doesn't have a brick to prop open the door with (i.e., our attempt at constructing a non-probabilistic proof protocol was foiled). For this reason, I wouldn't actually recommend inserting this example into the article; it would just confuse the issue even further, by muddying the distinction between "zero-knowledge" (i.e., recording-proof) and "probabilistic". --Quuxplusone (talk) 19:17, 8 February 2013 (UTC)[reply]

...And I have now updated the example on the page to emphasize the zero-knowledge-ness of the protocol, rather than the irrelevant fact that Peggy's magic word remains secret. Obviously Peggy wants to keep the actual word secret, but the really important thing from a ZKP point of view is that she won't be inundated with paparazzi and autograph seekers. Her real goal is just to convince Victor, not to become world-famous. (And fortunately nobody will just take Victor's word for it that Peggy knows magic. Nobody trusts Victor, nor Peggy either for that matter. In fact they're totally willing to believe that Victor and Peggy are in cahoots, rather than to believe that Peggy knows magic.) --Quuxplusone (talk) 19:48, 8 February 2013 (UTC)[reply]

Another question

Sorry if I am asking you to do my laundry, but I noticed two distinct pieces of knowledge with the systems described: a) the secret itself (magic word, hamiltonian path), b) knowledge that Peggie possesses this secret. Do both or only one of them have to be kept secret for the system to be characterized as zero-knowledge? In the cave example, Victor can acquire the magic word without a proof that Peggie knows it and, conversely, he can acquire a proof that Peggie knows the word without the word itself (recording with random coin tosses). I understand this is only an analogy, but what about real systems? — Preceding unsigned comment added by 94.66.70.215 (talk) 11:15, 25 February 2013 (UTC)[reply]

More on this example of the Cave

I'm really unconvinced by this example/analogy; I believe that we should add to the article a comment that the example illustrates the elements that are typically present in a ZKP, but does not constitute an example of where such steps are needed.

In response to Quuxplusone comment at the beginning of the section "Peggy and Victor and the cave" (two sections above); I did not read the original paper where you say they explain remarkably well why not just go through A and come back through B. But assuming that what you tell us is accurately their explanation, I object to that — a recording of the protocol simply IS NOT a valid zero-knowledge proof; it's not even a valid proof; and if someone else chooses to accept it and be convinced by it, that is their problem; and there is nothing that we can do (or should do) to prevent them from accepting such an invalid proof. For that matter, Victor could simple go and tell someone else that he saw Peggy enter through path A and come back through path B, and that someone else could accept that statement as a valid proof and be convinced that the statement is true.

On the other hand, where does this idea of a ZKP having the requirement that the verifier must not be able to convince anyone about the statement? Notice, BTW, the subtlety here: Peggy is executing a proof-of-knowledge (she's proving the statement "I have knowledge of the secret magic word", where "I" acts as a variable referring to "self", to the entity proving the statement, and not to the actual concrete person that it represents); that, by definition, can not be transferrable. But now Victor would be proving a different statement; he's not proving knowledge of the secret magic word; if anything, he would be proving the statement "Peggy has knowledge of the secret magic word". Again, emphasis on the subtlety: in this context, Peggy stating "I know X" is a different thing from someone else stating "Peggy knows X".

Back to why the non-random protocol of just enter through A and come back through B is not wrong: if we look at the definitions and the three conditions for ZKP, please someone tell me how does the protocol "Enter through A, come back through B" violate any one of those three?

Completeness: If Peggy indeed knows the magic secret word, she will be able come back through path B, and Victor will necessarily be convinced about the truth of the statement (since by assumption there is no alternative way to pass from A to B).

Soundness: If Peggy does not know the magic secret word, there is no possible cheating strategy — she will simply be unable to come back through path B, so there is no possible strategy that any cheating prover could use to convince Victor.

(this uses the same assumptions as in the randomized solution — for example, Peggy could be colluding with someone that does know the magic secret word and is waiting inside and never shows himself; if this was a possibility, then the randomized proof would be equally invalid)

Zero-knowledge: There really is nothing that Victor learns from the proof, other than the fact that Peggy does know the magic secret word; he most certainly does not learn the secret word, and, well, there simply is nothing more occuring in the protocol other than knowledge about the steps of the protocol (which is not knowledge that Victor is acquiring as the result of the proof)

Ironically, in terms of soundness, the non-random version is actually superior: the probability of a cheating prover to succeed is zero, unline in the randomized case, where the probability can not reach 0 (it can be arbitrarily low, but always > 0)

Although published by a quite reputable cryptographer, I think the example is actually "wrong" and misleading; however, since it does illustrate the elements normally present in a ZKP, I would vote for adding a short sentence or short paragraph to make this clear. Cal-linux (talk) 18:53, 27 March 2013 (UTC)[reply]

---