If yes, is there any paper that proves it? Unifying Zero-Knowledge Proofs of Knowledge, by Ueli Maurer, argues that Schnorr's interactive protocol is zero-knowledge. If this is true, using the Fiat-Shamir transform, can we convert Schnorr's protocol into a NIZK proof?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Yes, and in fact, Schnorr's signature scheme was originally described as a non-interactive protocol. I think the confusion around interactivity comes from the fact that the same paper first described a interactive identification scheme, which can be viewed as a specialization of the signature scheme for empty messages.
In both schemes, challenges can be generated either interactively or using hashes. The non-interactive variant can be viewed as an application of the Fiat-Shamir transform, although Schnorr did not describe it as such.
Note that while more general formulations of the Fiat-Shamir transform involve a random oracle assumption, the Schnorr signature scheme in particular has weaker requirements -- see Navel et al. and Chen et al.
$\begingroup$
$\endgroup$
The proof is better done other way round – from NIZK to Schnorr Digital signature.
It goes like this. Fiat-Shamir NIZK Heuristic requires the Prover to use a hash of transcript/timestamp/last-message as the input to the algorithm. Schnorr went one step ahead and allowed the prover to include any bit of information as the input. This not only works as a signature scheme, but also proves that the party knows some witness w.
PS: Not sure if this was ever penned down in a paper, but here is something you might find useful: See §3.2 in [0]
