10
$\begingroup$

In the classic description of Zero Knowledge Proof of Knowledge, Victor must wait outside the entrance to the cave while Peggy goes to the fork and choose a side. It's only once Peggy has entered a tunnel and is out of view that Victor comes at the fork and shout the side he wants her to come out from.

I am wondering why this setup is necessary for the proof to really be Zero Knowledge.

Let's try a much simpler experiment. Victor and Peggy walk together down the primary tunnel until the fork. Peggy goes alone in one side and come out the other. Victor did not hear the secret to open the door, but he is now convinced that she knows it. Peggy presented a proof of her knowledge without Victor learning anything apart the fact that Peggy has this knowledge.

Why is this simple setup not enough to model ZKPK?

Here are some hypotheses that I'm working with:

  1. The analogy is crafted this way to model the fact that the attacker would always have a probability of $p=0.5$ to guess the correct answer during the interactive proof. If Victor sees Mallory enter the tunnel and not come out the other side he will instantly know that Mallory does not know the secret. To model a setup closer to reality, the indirection is added so that Mallory can fake knowledge half the time.

  2. The analogy is crafted this way to make a point that Victor does not know some part of the mechanism. In our case, the door in fact only opens in one way, and once Peggy is at the door, she only uses her knowledge half the time. Maybe this is to model a mathematical aspect of the proof. I am dissing this one out but I've seen mentioned.

  3. Victor must not be able to convince anyone else that Peggy has the knowledge she claims. This is often presented with the extra story where Victor taped the whole thing while still not being able to convince a third party because he could have conspired with Peggy and staged the experiment.

I feel this third point is the crucial part.

However, it departs from the usual description of simply proving you know something without revealing it.

  • Hey, I'm Peggy and I can prove to you that I know a secret without telling it to you!
  • Oh, and by the way, in addition to not knowing the secret you won't be able to even tell anyone else the simple fact that I know the secret, booya.

Is the concealment of this meta information about the relationship between Peggy and the secret what really makes it Zero Knowledge?

Are there practical consequences of having a scheme that discloses it? (If the proof is interactive Victor wouldn't be able to impersonate Peggy anyway, right?).

To make the point more practical and concrete, let's consider the following simple protocols:

  1. Victor sends a plaintext to Peggy and ask her to send it back signed with her secret key. He verifies the result with Peggy's public key. Proof that Peggy has the private key.

  2. Victor encrypts a piece of data with Peggy's public key and asks Peggy to send back the hash of the data. If the hash match, he has a proof that Peggy knows the private key.

Why are these Protocols not Zero Knowledge proof of knowledge? (or are they?)

Improve this question
$\endgroup$
2
  • $\begingroup$ In addition to not necessarily being zero knowledge, "the following simple protocols" are not necessarily proofs of knowledge either, since, for example, a cheating prover could know enough to be able to sign half of all possible messages or decrypt half of all possible plaintexts without having a private key that is compatible with the public key. $\;$ $\endgroup$
    – user991
    Mar 9, 2014 at 19:10
  • $\begingroup$ Matthew Green's post give another example, closer to real use cases: blog.cryptographyengineering.com/2014/11/… $\endgroup$
    – Cédric Van Rompay
    Jan 14, 2015 at 13:00

2 Answers 2

Reset to default
6
$\begingroup$

The description of this "kid zero knowledge" example follows the strucure of how interactive proofs that are zero-knowledge usually work:

  1. The prover sends a commitment (walks into one of the two sides)
  2. The verifier challenges the prover (tosses the coin to decide which side the prover should walk out)
  3. The prover gives a response (walks out the side the verifier has told him).

An essential part of interactive proofs that are zero-knowledge which seems to be the source of your misunderstanding is the zero-knowledge property. This means (informally) that a verifier can efficiently simulate a transcript of a proof without having access to the prover (and thus only knows the statement to be proven but not the information the prover has) and such a transcript cannot be distinguished from a real transcript from a real proof run.

Note that this fact that an interactive proof is efficiently simulatable without having access to the prover, nicely captures the fact that the proof can not leak any information beyond the validity of the statement to be proven. In a real interaction, the verifier can be convinced that the prover knows what he wants to prove, but the transcript can not leak any further information since it can be efficiently simulated. So this idea of indistinguishability of real and simulated transcripts is a nice way of formally modeling the zero-knowledge property.

So now lets look at your example:

Let's try a much simpler experiment. Victor and Peggy walk together down the primary tunnel until the fork. Peggy goes alone in one side and come out the other. Victor did not hear the secret to open the door, but he is now convinced that she knows it. Peggy presented a proof of her knowledge without Victor learning anything apart the fact that Peggy has this knowledge.

In this example you CAN NOT simulate such a protocol without having access to the prover. You will never succeed in producing such a transcript without having access to the party knowing the secret (PIN).

However, in the original example you can just throw away all the runs of the protocol where the verifier wants the prover to come out the other tunnel (where the coin toss does not yield the same choice as Peggies choice for the tunnel to walk in) and only keep those where Victors coin toss says that Peggy has to come out the same tunnel she went in (and thus does not have to know the secret).

Your other approaches

Victor sends a plaintext to Peggy and ask her to send it back signed with her secret key. He verifies the result with Peggy's public key. Proof that Peggy has the private key.

As in your modified Alibaba example, you cannot simulate a transcript without having access to the prover (who knows the signing key - assuming that you work with a secure signature scheme).

Victor encrypts a piece of data with Peggy's public key and asks Peggy to send back the hash of the data. If the hash match, he has a proof that Peggy knows the private key.

This protocol is efficiently simulatable, but you would have to prove all properties required by zero-knowledge proofs to hold that you can show that it is an interactive proof that is also zero-knowledge.

Improve this answer
$\endgroup$
9
  • $\begingroup$ The "simulatable" property is what, to me, sounds like an extra requirement over my intuitive notion of zero knowledge. What is the benefit of having the proof simulatable if a fake simulation can not be distinguished from a real proof? $\endgroup$
    – Yolanda Ruiz
    Mar 9, 2014 at 12:27
  • $\begingroup$ @Yolanda Ruiz If a simulated proof is indistinguishable from a real one such interactive proof cannot leak any information about the provers knowledge, since the simulated transcript has been computed without the information only available to the prover since the simulation does not require the prover. $\endgroup$
    – DrLecter
    Mar 9, 2014 at 12:49
  • $\begingroup$ Sorry, I guess what I'm trying to say is that a non-simulatable proof cannot leak any information either. $\endgroup$
    – Yolanda Ruiz
    Mar 9, 2014 at 13:57
  • $\begingroup$ Really? How do you proof this? Simulatability is a nice way of capturing that fact and I can not think of a simpler and more meaningful way of modeling zero knowledge. $\endgroup$
    – DrLecter
    Mar 9, 2014 at 14:15
  • 2
    $\begingroup$ The "simulatability" is not an extra requirement. It is the very core of zero knowledge. If any kind of task is only possible with the secret, then it's most likely that the task relies on the secret and can possibly leak some information about the secret. There are a couple of unvertainties (if, can, ...), which are hard to contradict. The simulator catches all of that with not knowing the secret but only requiring polynomial (mostly linear) overhead for the transcript or any other advantage you grant the simulator $\endgroup$
    – tylo
    Mar 10, 2014 at 10:04
2
$\begingroup$

In addition to what DrLecter said:

Victor sends a plaintext to Peggy and ask her to send it back signed with her secret key. He verifies the result with Peggy's public key. Proof that Peggy has the private key.

Peggy will not want to sign something she did not write. Even if the text is not as blatant as "Peggy certifies she owes Victor one million dollars," this is a bad idea.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, I know she could be tricked with a blind signature scheme, but it was for illustration purposes. $\endgroup$
    – Yolanda Ruiz
    Mar 9, 2014 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.