17
$\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?

Improve this question
$\endgroup$
3
  • 3
    $\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, 2016 at 14:58
  • 1
    $\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, 2018 at 13:54
  • 1
    $\begingroup$ So why not add the time to data that is signed? Then the signature should only be considered valid for a certain interval. A new person will need to get a new signature with a new time stamp. $\endgroup$
    – NickJ
    Feb 18 at 21:46

2 Answers 2

Reset to default
17
$\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.

Improve this answer
$\endgroup$
3
  • 4
    $\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, 2016 at 18:37
  • 3
    $\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, 2016 at 18:39
  • 1
    $\begingroup$ So why not just force some custom data to be included in the data that needs to be signed each time? Then the signature would be useless for someone who added new custom data. $\endgroup$
    – NickJ
    Feb 18 at 21:48
3
$\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

Improve this answer
$\endgroup$

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.