Say that I have a signing/verification key pair $(sk,vk)$ and I generate a signature $\sigma$ over a message $m$. Then, I want to prove to someone else of this fact, which can be done in two different manners:

  1. I directly send $(\sigma,m)$.
  2. I compute a non-interactive zero knowledge argument $\pi$ for the statement: "I have a valid signature $\sigma$ for the message $m$". Notice that the argument does not reveal $\sigma$. I send $(\pi, m)$.

The question is: which is the fundamental difference 1 and 2? In 2, the verifiers do not learn the signature itself, but the proof $\pi$ can be used with the same purpose as $\sigma$. Are signatures and non-interactive zero knowledge arguments the very same thing?

Say that I want to prove that I have written the new Game of Thrones book and I want to authenticate it to a designated verifier. I know that 1 will not work, but what about 2?

  • $\begingroup$ Related to Are digital signatures a type of zero-knowledge proof?, and to a lesser extend to Did digital signatures come from Zero Knowledge Proofs?. I have not yet made my mind about what to do about that overlap. $\endgroup$
    – fgrieu
    Sep 29 at 9:12
  • $\begingroup$ Proving I have possession of a signature for a particular public key on a particular message will indirectly act as a signature itself and demonstrate the same knowledge as the signature I have in my possession. So what would be the point - am I missing something? $\endgroup$
    – knaccc
    Sep 29 at 22:37
  • $\begingroup$ @knaccc Yeah, that is exactly what I am asking. If the ZKP is interactive instead of non-interactive then that is not true: the proof becomes "non-reusable". In contrast, if the protocol is rendered non-interactive (via FS) then I want to know if it s really the case that both constructions are equivalent. This in fact would imply that a signature is a better option than a ZKP, since the former requires less computing power than the latter. $\endgroup$
    – Bean Guy
    Sep 30 at 12:46
  • $\begingroup$ I think it would help if you were more specific about what you mean by "ZKP", and how that would be implemented. A very simple signature such as a Schnorr signature is a zero-knowledge proof, and can be interactive or non-interactive. You must mean something different when you say "ZKP". $\endgroup$
    – knaccc
    Sep 30 at 12:58
  • $\begingroup$ @knaccc For instance, you could compute an arithmetic circuit $C$ such that $C(vk,\sigma,m) = 0$ if and only if $\sigma$ is a valid signature on $m$ with respect to $vk$. Then, you could use any SNARK that you wish to prove the correctness of the computation of such circuit $C$. This is totally different from a standard signature scheme. $\endgroup$
    – Bean Guy
    Sep 30 at 17:25


Your Answer

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

Browse other questions tagged or ask your own question.