Comment by jstanley

Comment by jstanley 4 days ago

> A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key.

I don't think a digital signature is a Zero-Knowledge Proof because someone else could copy and paste the signature and then it would look like they know the key, and because other third parties could check whether the signature was valid or not.

To be a true Zero-Knowledge Proof it needs to:

* show that you know the thing without revealing the thing

* not allow other people to copy your answer

* not allow anyone other than your intended counterparty to even verify the answer

amluto 4 days ago

I think you can make a nice zero-knowledge interactive protocol to prove knowledge of an RSA secret key. First, the prover and the verifier jointly agree on a random number m between 1 and n-1. [0] Then the verifier signs that number, and tells the prover the signature. (The signature is d^m mod n.) The verifier verifies the signature, which, critically, is exactly the same as verifying that the signature encrypts to m.

Why is this zero-knowledge? Because the verifier could invent an entire transcript of the protocol without the prover’s help: choose a random signature and encrypt it to generate the “random message”. So the ability to work with the prover to generate random pairs of (message, signature) accomplishes nothing at all except to convince the verifier that the prover knows the secret key.

This, by the way, is one of many footguns involved in using raw RSA: you cannot assume that a private key was used properly just because someone presents the signature of some message. Better signature schemes built on top of RSA avoid this problem.

[0] This is fairly straightforward using cryptographic hashes. The verifier could instead choose freely, but then the protocol isn’t zero-knowledge.

Reply View 0 replies

phkahler 4 days ago

>> I don't think a digital signature is a Zero-Knowledge Proof because someone else could copy and paste the signature and then it would look like they know the key, and because other third parties could check whether the signature was valid or not.

One of us is confused. You can't copy a digital signature in a useful way. Without the message it doesnt mean anything. With the message its proof that the message was signed by someone with the private key.

To meet your second two (arbitrary) requirements, have the signer encrypt the signed message with your public key before sending it to you.

Reply View 5 replies

jstanley 4 days ago

They're not my arbitrary requirements, see https://en.wikipedia.org/wiki/Zero-knowledge_proof
Specifically:
> In light of the fact that one should be able to generate a proof of some statement only when in possession of certain secret information connected to the statement, the verifier, even after having become convinced of the statement's truth by means of a zero-knowledge proof, should nonetheless remain unable to prove the statement to further third parties.

Reply View | 1 reply
- pastel8739 4 days ago
  
  I’m not sure that requirement is violated here; the interactive nature of a challenge-response protocol is required to prove that someone knows the private key. Without an interactive process, the prover could have just found the signatures lying around somewhere and reused them without knowing the private key at all. This means that the verifier would not be able to prove anything beyond “the private key X signed these messages”.
  
  Reply View | 0 replies
pastel8739 4 days ago

I think it’s the original quote that is unclear:
> a digital signature proves your possession of a private key without revealing that key.
Signatures do not themselves do this; but they can be used to construct a protocol that does (e.g. the provee provides a random challenge that the prover must sign). But still this is not AFAIU a zero-knowledge proof as the signature is itself “knowledge”.

Reply View | 2 replies
- drdeca 4 days ago
  
  I think a definition of the security of a signature scheme is that a computationally limited attacker should not have a non-negligibly better than chance guess of the secret key.
  I think some of the “ZKP” techniques are supposed to only be “ZK” for a computationally limited observer? Though I may be mistaken, and maybe non-interactive ZKP schemes are only assuming that the prover has limited computational resources, not that the observer/attacker hoping to get information from them does?
  
  Reply View | 1 reply
  
  pastel8739 4 days ago
  
  I know very little about ZKPs, but it does indeed sound like there is a notion of “computational zero knowledge”. I don’t know whether digital signatures would meet that definition or not, or if it’s algorithm-dependent.
  
  Reply View | 0 replies

pastel8739 4 days ago

I think even aside from that (which can be solved with challenge-response) digital signatures are typically not ZKPs because the signature itself constitutes information that must be transferred during the proof.

Reply View 0 replies