This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||
|
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)
---
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."
--
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)
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."
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
computational indistinguishable should be computationally indistinguishable
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)
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)
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)
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)
The link to "How to Explain Zero-Knowledge Protocols to Your Children" (ref #1) appears broken. I'll fix it later when I'm not in a hurry, but I figured I'd write this here until someone gets around to it first. wdaher 01:59, 13 May 2006 (UTC)
I 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))
(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)
Would it be valuable to establish a list of zero-knowledge proofs (like the List of NP-complete problems)? -- Johnruble 15:56, 22 June 2007 (UTC)
I doubt I'll learn enough about this stuff to make the contributions I'm suggesting, but ultimately it'd be swell to subdivide off a section for zero-knowledge identification schemes like the linked Feige-Fiat-Shamir Identification Scheme. Schneier's book follows FFS identification with Guillou-Quisquater and Schnorr. -- Johnruble 15:20, 6 July 2007 (UTC)
While studying the Direct anonymous attestation protocol, I've seen usage of a digital signature algorithm (in this case, the Schnorr's algorithm, or a slight variant) as a zero-knowledge proof. Indeed, a digital signature proves that the signer knows the private key without disclosing any part of it to the verifier, and seems to be a zero-knowledge proof. Shouldn't this be discussed in the article? Googling around found a technical confirmation of this, under some hypothesis: [2] (also here), i.e. "Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract)" by Shafi Goldwasser and Rafail Ostrovsky; but the article warrants at least a mention of the comparison, and that the fact that there may be some difference (if any, I've just read through the abstract).
-- Blaisorblade ( talk) 14:14, 9 July 2008 (UTC)
Schnorr signature is a non-interactive variant of a protocol, however zero-knowledge property is missing (that is, no simulator). It is still witness hiding. User credentials with Direct Anonymous Attestation is a data signed with Camenisch-Lysyanskaya scheme.
195.238.92.2 ( talk) 17:48, 26 December 2008 (UTC)
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)
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)
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)
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 ; the chance of doing so through trials is , 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:
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)
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)
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)
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)
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:
Some particular points I don't understand:
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)
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)
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:
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)
...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)
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)
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)
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)
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 do not see the logic of this sentence: Jackzhp ( talk) 13:45, 9 April 2016 (UTC)
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.
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)
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):
- David Gerard ( talk) 13:58, 20 April 2019 (UTC)
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)
Adding some top Dapps based on Zk proof — Preceding unsigned comment added by Web3 student ( talk • contribs) 07:21, 5 May 2022 (UTC)
Program 45.250.47.203 ( talk) 03:49, 5 February 2023 (UTC)
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)
I am unsure about the correctness of the following excerpt:
Further, if Victor chooses his A's and B's by flipping a coin on-camera, this protocol loses its zero-knowledge property; the on-camera coin flip would probably be convincing to any person watching the recording later. Thus, although this does not reveal the secret word to Victor, it does make it possible for Victor to convince the world in general that Peggy has that knowledge—counter to Peggy's stated wishes.
I do not think that a third party could be convinced by a recording of the coin flip followed by Peggy correctly emerging out of the announced side, for the following reason: imagine Peggy also (secretly) selects at random a side to go through. The probability that the random choices "align" (i.e., Victor and Peggy's coin outcomes both mean A or both mean B) for a single attempt is 1/4. Now, by repeating this over and over again, we are sure to have arbitrarily long "runs" of consecutive alignments. All Victor and Peggy would have to do in order to obtain a N consecutive successes is to record a sufficient number of attempts, then trim the video to some long run of coincidences. Tassion ( talk) 13:29, 23 April 2024 (UTC)
This article is rated C-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||
|
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)
---
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."
--
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)
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."
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
computational indistinguishable should be computationally indistinguishable
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)
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)
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)
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)
The link to "How to Explain Zero-Knowledge Protocols to Your Children" (ref #1) appears broken. I'll fix it later when I'm not in a hurry, but I figured I'd write this here until someone gets around to it first. wdaher 01:59, 13 May 2006 (UTC)
I 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))
(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)
Would it be valuable to establish a list of zero-knowledge proofs (like the List of NP-complete problems)? -- Johnruble 15:56, 22 June 2007 (UTC)
I doubt I'll learn enough about this stuff to make the contributions I'm suggesting, but ultimately it'd be swell to subdivide off a section for zero-knowledge identification schemes like the linked Feige-Fiat-Shamir Identification Scheme. Schneier's book follows FFS identification with Guillou-Quisquater and Schnorr. -- Johnruble 15:20, 6 July 2007 (UTC)
While studying the Direct anonymous attestation protocol, I've seen usage of a digital signature algorithm (in this case, the Schnorr's algorithm, or a slight variant) as a zero-knowledge proof. Indeed, a digital signature proves that the signer knows the private key without disclosing any part of it to the verifier, and seems to be a zero-knowledge proof. Shouldn't this be discussed in the article? Googling around found a technical confirmation of this, under some hypothesis: [2] (also here), i.e. "Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract)" by Shafi Goldwasser and Rafail Ostrovsky; but the article warrants at least a mention of the comparison, and that the fact that there may be some difference (if any, I've just read through the abstract).
-- Blaisorblade ( talk) 14:14, 9 July 2008 (UTC)
Schnorr signature is a non-interactive variant of a protocol, however zero-knowledge property is missing (that is, no simulator). It is still witness hiding. User credentials with Direct Anonymous Attestation is a data signed with Camenisch-Lysyanskaya scheme.
195.238.92.2 ( talk) 17:48, 26 December 2008 (UTC)
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)
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)
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)
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 ; the chance of doing so through trials is , 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:
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)
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)
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)
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)
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:
Some particular points I don't understand:
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)
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)
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:
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)
...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)
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)
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)
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)
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 do not see the logic of this sentence: Jackzhp ( talk) 13:45, 9 April 2016 (UTC)
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.
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)
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):
- David Gerard ( talk) 13:58, 20 April 2019 (UTC)
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)
Adding some top Dapps based on Zk proof — Preceding unsigned comment added by Web3 student ( talk • contribs) 07:21, 5 May 2022 (UTC)
Program 45.250.47.203 ( talk) 03:49, 5 February 2023 (UTC)
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)
I am unsure about the correctness of the following excerpt:
Further, if Victor chooses his A's and B's by flipping a coin on-camera, this protocol loses its zero-knowledge property; the on-camera coin flip would probably be convincing to any person watching the recording later. Thus, although this does not reveal the secret word to Victor, it does make it possible for Victor to convince the world in general that Peggy has that knowledge—counter to Peggy's stated wishes.
I do not think that a third party could be convinced by a recording of the coin flip followed by Peggy correctly emerging out of the announced side, for the following reason: imagine Peggy also (secretly) selects at random a side to go through. The probability that the random choices "align" (i.e., Victor and Peggy's coin outcomes both mean A or both mean B) for a single attempt is 1/4. Now, by repeating this over and over again, we are sure to have arbitrarily long "runs" of consecutive alignments. All Victor and Peggy would have to do in order to obtain a N consecutive successes is to record a sufficient number of attempts, then trim the video to some long run of coincidences. Tassion ( talk) 13:29, 23 April 2024 (UTC)