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, 2022 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, 2022 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, 2022 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, 2022 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, 2022 at 17:25


Your Answer

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

Browse other questions tagged or ask your own question.