19
$\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
    Commented 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
    Commented 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
    Commented Feb 18, 2023 at 21:46

3 Answers 3

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
  • 5
    $\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
    Commented 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
    Commented 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
    Commented Feb 18, 2023 at 21:48
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

Improve this answer
$\endgroup$
-4
$\begingroup$

I dare disagreeing with the approved answer.

Semantics makes the question difficult to answer.

Cryptographic signatures are absolutely forms of zk-proofs.

Why?

Because by providing a signature, the signer reveals absolutely nothing, not a pico part of clue, of what it knows. Yet absolutely proved, without a pico chance of error, that he knows.

Granted the scheme is secure. But it is implied in the question. Plus, zk-proof systens could as easily have flaws that reveal what is known if exploited, so the "private key could be reconstructed by other parties" argument is moot. And granted that we accept all messsages can only be of the size and format of a private key. And granted we assume that such constraints giving away the size of the secret doesn't qualify as giving away information about the message. That is all messages shared using the system are always ever and forever of the same length.

Cryptographic signing is however an incomplete and unwise illustration of zk proof. Serves different purpose. Designed to guarantee entirely different properties.

Are cars forms of trains? Yes they are. Because they can be. If they can fit on rails they would accomplish about the same thing. They are a sort of train, and poor at that. But they aren't trains.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ You know that zero-knowledge proof is not just a vague concept, but something with a formal definition, right? If so, do you claim that using a signature yields something that satisfies the formal definition of zero-knowledge? If yes, you are wrong. If no, what do you claim? $\endgroup$
    – Geoffroy Couteau
    Commented Dec 17, 2023 at 20:08
  • $\begingroup$ And I absolutely didn't claim that. My answer even took care to clarify this somewhere near the end. $\endgroup$
    – Hirako
    Commented Dec 21, 2023 at 5:43
  • $\begingroup$ If it didn't move your perspective and made you realise as a concept, digital signing isn't a zk-proof system, which you agree with, but that digital signing is absolutely a form of zero knowledge proof, which you disagree with, it's OK. Thanks for commenting I appreciate it more than critique-less down votes. $\endgroup$
    – Hirako
    Commented Dec 21, 2023 at 5:51
  • $\begingroup$ But where did the original OP used the terminology "a form of ZK proof"? And though I understand the point you are trying to make, I disagree with the fact that you can call something "a form of ZK proof" if it does not satisfy the formal definition of a ZK proof - but other terminologies, like "something in the spirit of a ZK proof" which indicate more clearly that this is still not a ZK proof would work better (but then, I still don't really see the point of the answer, this is not what OP asked and this is more misleading than anything else). $\endgroup$
    – Geoffroy Couteau
    Commented Dec 21, 2023 at 8:12
  • $\begingroup$ That is how i read OP's question: are Cryptographic digital signatures zero knowledge proofs. Not: is Cryptographic digital signing a zk proof method / protocol. $\endgroup$
    – Hirako
    Commented Dec 30, 2023 at 11:48

Your Answer

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

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