In a sigma protocol, a well known transformation to a signature is Fiat-Shamir, where message derived randomness is mixed into the randomness of the challenge. A natural example is Schnorr signatures. This is also called a Signature of Knowledge.

Suppose you start with a modern, transparent ZK-SNARK to prove knowledge of R1CS or arithmetic circuit satisfiability (such as ligero/aurora/orion). I am interested whether or not it is possible to perform a similar FS-esque (or the IOP generalisation BCS) approach to construct a signature scheme.

This paper seems to indicate the issue relies on proving simulation extractability (SE) of the scheme, which implies the existential unforgeability of the signature requires. Intuitively, I believe this is related to the malleability of the underlying ZK-SNARK, and due to that fact that IOPs can have much richer structure than a sigma protocol. In their paper they discuss some other schemes that satisfy this property but they rely on trusted setup and/or non post-quantum assumptions.

Does anyone know of any major challenges to proving SE of the current state-of-the-art schemes. It seems like this would lead to good optimizations as the current approaches to zk-SNARK based signatures (such as Picnic and Banquet) use a higher level approach, by using a PRF and proving knowledge of computations on the PRF. If you could do a signature of knowledge, an OWF would suffice.

  • $\begingroup$ As an addendum: Picnic and Banquet work roughly like this: the private key corresponds to an instantiation of a PRF $PRF_{sk}$, and public key is an evaluation $PRF_{sk}(0^\lambda)$. A signature of a message $m$ is an evaluation of $PRF_{sk}(m)$ with a zero knowledge proof that the signer knows the private key sk that generates both $PRF_{sk}(m)$ and $PRF_{sk}(0^\lambda)$. $\endgroup$
    – Lev
    Sep 7, 2022 at 3:14
  • $\begingroup$ In the other case, the message is not used an input to the computation but rather as an input to the randomness of the zero knowledge proof protocol. $\endgroup$
    – Lev
    Sep 7, 2022 at 3:17


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.