Talk:Zero-knowledge proof

Cryptography: Computer science Top‑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
Top	This article has been rated as Top-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Top-importance).

Definitions[edit]

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?

--

So, can we simply say that "providing a ZK proof" is equivalent to obtaining a rule (or system) to generate enough statistical simulation evidence for testing a hypothesis about a system's property, without directly observing that property?

For example, I have a coin, and I want to prove that it's biased. I just sample it's landings. I just proved myself that the coin is not unbiased. Inyuki (talk) 18:17, 31 January 2019 (UTC)[reply]

Peggy and Victor Example[edit]

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

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

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

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

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

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"[edit]

(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[edit]

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

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]

The point of signatures is not proving that the signer knows something, the point is authenticating the message. But yes, in essence, a signature is a zero-knowledge proof of the statement “this message was endorsed by someone who knows the private key corresponding to this public key”. And in this sense they are a special case of signatures of knowledge, as introduced by Chase and Lysyanskaya. Kirelagin (talk) 22:02, 23 September 2021 (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"[edit]

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

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]

The same issue (completeness confused with soundness) now appears in the section "two balls and the colour-blind friend". Completeness should say: if the balls are differently colored, "you" (the non-color-blind prover) will be able to correctly determine whether the balls were switched, every single time. 108.217.33.225 (talk) 15:09, 22 November 2023 (UTC)[reply]

Hamilton is confused[edit]

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

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

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?[edit]

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...[edit]

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

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

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

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]

A "zero-knowledge proof protocol" is a way for Peggy to convey something to Victor without leaking any information other than the information she's trying to convey. In the cave example, Peggy is trying to convey (b) to Victor without also conveying (a); therefore she's looking for a zero-knowledge proof of (b). Real systems are actually very analogous to the cave example; typically I know ("a") my password, and I want to prove to the system that ("b") I know my password, without actually revealing anything about ("a") my password to the system. Makes sense, right? —Quuxplusone (talk) 23:32, 5 June 2013 (UTC)[reply]

More on this example of the Cave[edit]

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, unlike 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]

The difference between a zero-knowledge proof and a proof of knowledge is that in a zero-knowledge proof the verifier must not learn any information that he could not generate himself. Since he cannot make a video of someone entering the cave on one side and leaving it on the other side, any protocol that results in such a video would not be zero-knowledge, but of course can be a "proof of knowledge". The "zero-knowledge" property may not be a bit advantage in this example. But it is a huge simplification for showing the security of a complex cryptographic protocol, because frequently in such protocols it is far from obvious that the verifier does not receive information that can help to determine a secret key (unless of course the protocol actually is zero-knowledge). Zero-knowledge protocols give absolut priority to the property that prover does not leak his secret. Hence there is also nothing ironical about the fact that a "proof of knowledge" can have a lower cheating probability. While you can claim that a "proof of knowledge" would be more appropriate in the cave case, you cannot claim that the described "zero-knowledge protocol" is wrong or misleading. 83.77.189.6 (talk) 09:13, 28 March 2013 (UTC)[reply]

Cal-linux: I admit I'm not a professional mathematician, but I did take a course once... ;) I believe the answer to your objection is that you're taking the word "knowledge" too narrowly. Consider the protocol "Enter through A, come back through B". If Victor video-tapes this protocol, you claim he gains no knowledge. But you would agree that he gains an ability, right? Victor now possesses the ability — which he did not possess before — to convince other people that Peggy knows the magic word! Convincing other people is a really powerful ability, and Peggy really doesn't want him to gain it; she just wants him to be convinced himself. I believe a mathematician would claim that "abilities" are just another form of "knowledge", and thus a protocol which allows Victor to gain abilities cannot qualify as "zero-knowledge". (Please ping User talk:Quuxplusone if you respond; I'm terrible at checking talk pages.) —Quuxplusone (talk) 23:45, 5 June 2013 (UTC)[reply]

EDIT: In fact I take that back! Victor totally has data he didn't possess before: he has an unfakeable videotape of a magic trick! (Remember, we're assuming video editing software doesn't exist in Victor's world.) Victor possesses this data now, and he couldn't have possessed it without help from someone magical like Peggy. He could kinda-sorta see in his mind's eye what it would be like, but he couldn't possess the actual data on that tape before he met Peggy and convinced her to help him. —Quuxplusone (talk) 00:02, 6 June 2013 (UTC)[reply]

More on the Cave, part 2[edit]

The part about the video in the above comment is incorrect in the context of the "verifier must not learn any information [ABOUT THE SECRET] that he could not generate himself". Making a video as explained doesn't reveal information about the secret. In the cave example, Peggy is demonstrating with a zero-knowledge proof that she can get through the magic door. The video has no effect on the proof being zero knowledge or not. Peggy is proving to Victor that she knows the secret. Victor proving to anyone else, with a video or what not, is a different problem. Victor COULD generate such a video himself using basic video editing software -- "Ok Peggy, go down path A and stay out of sight for a minute... Cut! Reset, now go down path B and I'll film you coming out of the cave" -- and it would not be a proof of anything, nor leak any knowledge about the secret that Peggy is proving she knows. Peggy could even incorporate a random delay into her appearing at the specified path in order to conceal how long it takes to execute her secret. — Preceding unsigned comment added by 134.134.139.70 (talk) 03:44, 1 May 2013 (UTC)[reply]

Well, in this analogy we're assuming for simplicity that video-editing software of that caliber doesn't exist in Victor's world. :) If such software does exist in analogy-world, then you're absolutely right. (Also, if Victor has friends in the CIA who can help him plant a recording device in the cave before Peggy arrives... but again, for the sake of the analogy we're saying that's off the table.) --Quuxplusone (talk) 23:38, 5 June 2013 (UTC)[reply]

I don't buy this argument about gaining the ability counting as additional gained knowledge; how can one claim that Victor can not have the ability to prove something that he now knows for a fact? Gaining a piece of knowledge automatically involves the possibility of proving that piece of knowledge. Or, looking at it from the other angle: the ability to prove something that you know can not count as something additional to knowing the given something.

Again, I'm convinced that the crucial difference here, the one that implies the requirement of the proof having to be interactive or it can't be zero-knowledge is the distinction between a proof that the prover knows something vs. a proof that a concrete person knows something.

I also have an objection to your comments about the video editing not existing; under that assumption, then the interactive / randomized protocol could also be videotaped, and it will allow Victor to prove to others that Peggy knows the secret (which according to you, would contradict the zero-knowledge nature of the proof); just place the videocamera at a location where Victor is always in sight, and the viewer sees that Victor is waiting and not seeing which path Peggy is entering through. A large number of repeats of the protocol guarantees with arbitrarily high probability that in one of the instances, Victor will ask Peggy to exit through the path other than the one she entered, which now proves to anyone seeing the video that Peggy knows. Cal-linux (talk) 01:18, 6 June 2013 (UTC)[reply]

the interactive / randomized protocol could also be videotaped, and it will allow Victor to prove to others that Peggy knows the secret Not true at all! Suppose I show you a video of my friend Alice going into the cave; and then I go in and shout "Left!" and she comes out the left side; and then Alice goes back in and I shout "Right!" and she comes out the right side; and so on. Would you conclude that Alice knows magic, or is it more likely (really, is it statistically possible at all) that Alice and I just arranged the whole thing ahead of time? The whole point of ZKP is that Peggy can interactively convince Victor of a proposition X, without enabling Victor to use recordings of that protocol to convince anyone else. The reason ZKP works in this case is because in order to be convinced by the protocol, you have to trust that Victor is choosing "Left!" and "Right!" randomly, and the only person who trusts Victor is Victor himself. —Quuxplusone (talk) 18:49, 6 June 2013 (UTC)[reply]

I think you misunderstood what I meant by ″videotape the interactive protocol″ — I meant videotape it such that the viewer (the viewer of the videotape) can see everything (think of it as the camera being really far and capturing everything except what happens inside the cave).

So, the viewer sees Victor standing far away and not seeing Peggy choosing one path to enter; but the viewer does see Peggy entering, then coming out. With probability extremely close to 1, in at least one of the trials, Peggy will enter through one gate and then come out through the other one, which the viewer of the videotape will then see; that, under the assumption (the assumption that I'm questioning) that video editing or video doctoring does not exist in that hypothetical world, means that anyone seeing that recording of the interactive version of the protocol would be convinced. Thus, Victor would be gaining the ability to prove that Peggy knows to others with the interactive protocol as well.

To summarize, just to make sure that we're in sync with what the arguments are: you claim that the non-interactive version can not be ZK since Victor is gaining the ″ability″ to prove Peggy's knowledge to someone else by videotaping the non-interactive, which requires the assumption that video editing does not exist in that hypothetical world. My counter-argument is that these assumptions end up breaking down in that if we need to assume that video editing or video doctoring does not exist in that hypothetical world, then the interactive version of the protocol would not be ZK either.

I will go back to my original point, which has not been directly and explicitly answered: how does the non-interactive version of the protocol break any of the three defining characteristics? In this respect, I insist that for a ZK proof-of-knowledge, the key detail that makes it "non-transferrable" is the subtlety of "proving that the prover knows something" vs. "proving that some actual/concrete person knows something": I prove to you in ZK that I know something; you shall not be able to prove to someone else that you know the something, but if I disclosed (by proving) to you the fact that I know something, why on earth would you (be required to) be unable to prove that fact to someone else? Cal-linux (talk) 19:46, 6 June 2013 (UTC)[reply]

(I re-set the indentation.) if I disclosed to you the fact that I know something, why on earth would you (be required to) be unable to prove that fact to someone else? Because that's part of the definition of ZKP. Peggy doesn't want Victor to be able to prove anything to anyone else; she doesn't want to give Victor that power. (Rename "Victor" to "Geraldo" and imagine that Peggy doesn't want the paparazzi bothering her for the rest of her life; so it's important that nobody but Geraldo be convinced by Geraldo's videotape.) It's definitely time for you to read the original paper; read it in order, but read especially closely when it gets to the section on "The Jealous Reporter." If you still have questions after that, maybe we should try to find an interactive proving tool of our own. Gmail chat? :) —Quuxplusone (talk) 20:01, 6 June 2013 (UTC)[reply]

But there is no such thing as “proof” in nature! It’s utterly unscientific![edit]

As is generally understood in modern science and philosophy, proof can only exist in defined formal systems, and not in nature. The best one can achieve is high statistical probability. Which only guarantees things “on average”. Meaning that it can still have 10 trillion consecutive failures, followed by (10 trillion − 1) trillion successes, to be “a one in a trillion chance”. And those latter ~10 trillion trillion successes can still be outside of one’s personal universe of causality, even if that’s not the case for humanity on average. It’s just very very unlikely. Not impossible.

So this should rather be called “zero-knowledge probability determination”. — Preceding unsigned comment added by 89.0.124.45 (talk) 15:27, 28 October 2014 (UTC)[reply]

This distinction is incorrect. The article describes a zero-knowledge proof in the context of cryptographic systems, which are by construction a formal and rigorous system where the term "proof" can be used exactly correctly. Jrfarah1999 (talk) 22:46, 11 March 2022 (UTC)[reply]

Phone example[edit]

The phone example is not really a ZKP, as there is no simulator. Anyone standing next to Victor while Peggy is unlocking the phone will also be convinced that Peggy knows the phone's code (and thus presumably that the phone is hers). Am I right? If not, it might be better to mention this, or delete the section altogether. Digilus (talk)

I agree. The example is not zero-knowledge for the reason you pointed out. 178.199.25.189 (talk) 18:52, 23 July 2015 (UTC)[reply]

otherwise[edit]

i do not see the logic of this sentence: Jackzhp (talk) 13:45, 9 April 2016 (UTC)[reply]

Notice that the statement being proved must include the assertion that the prover has such knowledge (otherwise, the statement would not be proved in zero-knowledge, since at the end of the protocol the verifier would gain the additional information that the prover has knowledge of the required secret information).

?[edit]

Yes, it is possible to verify that a user knows his password without exchanging secret information and without secret information stored in a central database.

Why we don't just use it? — Preceding unsigned comment added by 84.118.82.226 (talk) 15:25, 15 February 2018 (UTC)[reply]

zero knowledge of what?[edit]

I think there is something missing in the formal definition, zero knowledge of what? The simulation paradigm is missing this part. The simulation part is hard to understand, and I would guess people often get lost on what is being hidden. So the formal definition should stress what is being hidden. Jackzhp (talk) 12:44, 28 October 2018 (UTC)[reply]

External links moved from page[edit]

None of these meet WP:ELNO, but I've put them here so they can be mined for references (if they're up to WP:RS):

SZK in the Complexity Zoo
Applied Kid Cryptography – A simple explanation of zero-knowledge proofs using Where's Waldo? as an example
A gentle introduction to zero-knowledge proofs with applications to cryptography
How to construct zero-knowledge proof systems for NP
An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products
A tutorial by Oded Goldreich on zero knowledge proofs
Salil Vadhan, Vadhan's phd thesis on statistical zero knowledge
Theory of Computing Course, Cornell University 2009, Zero knowledge proofs
Ali Baba's Cave as told by Steve Gibson on TWiT show Security Now Episode 363 Wednesday August 1, 2012
Demonstrate how Zero-Knowledge Proofs work without using maths
The Bitcoin's Zero knowledge proof to binding

- David Gerard (talk) 13:58, 20 April 2019 (UTC)[reply]

Target level[edit]

This article is written as if the reader had a PhD in cryptography. Is this really the intended audience? — Preceding unsigned comment added by 24.241.152.175 (talk) 14:44, 4 August 2020 (UTC)[reply]

Suggestion[edit]

Adding some top Dapps based on Zk proof — Preceding unsigned comment added by Web3 student (talk • contribs) 07:21, 5 May 2022 (UTC)[reply]

Html program[edit]

Program 45.250.47.203 (talk) 03:49, 5 February 2023 (UTC)[reply]

excessive language about replayability[edit]

i have just edited the page; i refactored and removed a number of repetitive and verbose statements around replayabilty. these statements, roughly, insisted repeatedly that the verifier, even after having engaged in a successful proof, should remain unable to replay this proof to third parties. on the one hand, this fact is essentially true, especially for interactive proofs (this is essentially the definition of simulation). even in the (abstract) random oracle model, it may be true under certain definitions—it depends on whether we stipulate that the oracle gets "reset" between the initial proof and the subsequent verification by the recipient of the replay. this is a subtle definitional question, and i don't think there is a clear answer. if the oracle does get reset, then the second verifier has no way of knowing whether the first proof was obtained with the aid of programming (say, by the zero-knowledge simulator), and the replay should fail; if it doesn't get reset, then the second verifier can verify the proof in the usual way, and the replay would "succeed".

on the other hand, this statement is essentially misleading, for the following reason. in the real world, where we use hash functions, we're in something like the second model above: replaying always does work, since the random oracle never gets "reset". yet this isn't a problem; though it might technically contravene zero knowledge, we usually don't care about this kind of replay, since the statement is connected to the prover. (I can always replay someone's signature, but who cares—it's signed under their key, not mine, so this has no use.) this topic is discussed in detail in this paper by Rafael Pass: https://link.springer.com/chapter/10.1007/978-3-540-45146-4_19 Benediamond (talk) 02:09, 28 June 2023 (UTC)[reply]