1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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

0

Reset to default

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.