10
$\begingroup$

Suppose Alice publishes a book with a public key in it, and later wants to prove that she wrote the book. She could sign challenge messages with her private key, and others could verify those signed messages. Alice is proving she knows a private key without revealing anything about it.

Is this an example of an interactive zero knowledge proof?

Or does this example somehow not apply to zero knowledge proofs?

$\endgroup$
  • 2
    $\begingroup$ In the intuitive sense of "zero-knowledge proof", yes, this protocol qualifies. However, the technical definition of zero-knowledge requires that it must be possible to generate transcripts of the protocol without knowledge of the secret key. That is clearly not the case here, as in order to generate the response, the simulator must have the secret key. $\endgroup$ – Alan May 9 '16 at 14:58
  • $\begingroup$ This protocol would be vulnerable to man-in-the-middle, and that disqualifies for zero knowledge: A transcript of the protocol has to be worthless to anyone who didn't flip the coins themselves. The definition of ZK is that the verifier does not learn anything about the secret, which isn't revealed by the functionality anyway. A signature on a challenge chosen by the verifier doesn't fit. $\endgroup$ – tylo Jul 19 '18 at 13:54
12
$\begingroup$

This is not zero knowledge. In particular, you give away information in the form of signatures on challenges. This is something that the verifier doesn't have and so it is something that is "learned".

This can be meaningful for two reasons. Let's say that I want to prove to YOU that I wrote the book, but I don't want you to be able to convince anyone else that you interacted with the person who wrote the book. With this protocol, it's possible to prove that you interacted with the book author, but this isn't possible with real ZK. Another issue is that the challenge may actually be generated maliciously so that it provides a meaningful signature.

$\endgroup$
  • 1
    $\begingroup$ But if we take the philosophical meaning of 'knowledge' as being something that allows an adversary to accomplish a task, is it true that having a strongly unforgeable signature on a random challenge is gaining 'knowledge'? Unless the adversary can break some hard computational problem, it can't use this signature to generate further signatures on new messages, or even a different signature on the same challenge. It seems like it can't accomplish any task it couldn't have accomplished before having the signature on the challenge. $\endgroup$ – pg1989 May 9 '16 at 18:37
  • 1
    $\begingroup$ You are making assumptions about what a signature can be used for. However, this may not be the case. ZK guarantees that nothing can be used since nothing is learned (formally). $\endgroup$ – Yehuda Lindell May 9 '16 at 18:39
2
$\begingroup$

Your digital signature method is not zero knowledge because Alice just revealed that she knows the private key. Even if she didn't reveal what the private key is.

A common explanation of zero knowledge is the story of the Ali Baba cave. The paper goes in depth, starting in the "Jealous Reporter" section, to highlight that not only is the secret hidden, but also the knowledge that someone could have the secret is also hidden.

Responding to @pg1989, this has a practical implication. If you know a valuable secret like the key to unlock 100 BTC, you don't want anyone to know you have that key. If people find out, then a malicious actor may put you in a hostage / ransom situation to force you to reveal the key.

http://pages.cs.wisc.edu/~mkowalcz/628.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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