Using Fiat-Shamir, an interactive 3-round sigma protocol can be compiled into a non-interactive zero-knowledge proof in the random oracle model.

A NIZK through Fiat-Shamir is not UC-Secure due to rewinding. There are some straight-line-extractable compilation techniques, and to the best of my knowledge, the most efficient one is the proof-of-work-based Fischlin transform.

My question is about the computational performance differences. Specifically, for 128 security, how much slower will it be compared to Fiat-Shamir "in practice" to do a NIZK proof of knowledge of discrete log? Like 20 times slower, or 20000 times slower? Select whatever Fischlin parameters (like the length of the hash, iterations, etc) necessary for optimal results

  • $\begingroup$ Is what the first paragraph describes the building of signature from 3-round sigma protocol using a hash per the Fiat-Shamir heuristic, as e.g. in EdDSA? If so, I doubt "non-interactive zero-knowledge proof" is proper terminology because signature is not zero-knowledge. If indeed it's meant using Fiat-Shamir to build a NIZK proof (as in e.g. this question), it may help to detail or give a reference. Also the Fischlin transform usually is presented as building a signature, not a NIZK proof. $\endgroup$
    – fgrieu
    Aug 10, 2023 at 11:09
  • 1
    $\begingroup$ No. I'm not describing a signature by definition because there's no message. And Fischlin, like FS, is a way to compile some class of ZK protocols into a NIZK (see the zero-knowledge property in the original paper). You can then build a signature scheme out of it, which consequently loses the ZK property. Specifically in your example, Schnorr dlog proof+FS is a NIZKPoK. EdDSA/Schnorr signatures are that, without ZK. $\endgroup$
    – Atonal
    Aug 10, 2023 at 16:05
  • $\begingroup$ Very clear. My bad for not reading the original material on the Fischlin transform, and thanks for linking to that. $\endgroup$
    – fgrieu
    Aug 10, 2023 at 16:42


Your Answer

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