3
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\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 ♦
    Commented 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
    Commented 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 ♦
    Commented Aug 10, 2023 at 16:42

1 Answer 1

Reset to default
3
$\begingroup$

Please check the work here: https://eprint.iacr.org/2024/526

Just quoting the number there, the running time of generating a single discrete log proof on secp256k1 curve on Apple M3 Pro CPU:

  • Fiat-Shamir: 0.027 ms
  • Fischlin: 0.41 ms

which is ~15x overhead. The ratio will depend on the curve and the platform/machine, since there are two basic operations that contribute most of the running time -- SHA256 and multiplication on the curve. Overall, it is indeed about 20x slower based on the implementation.

More details regarding how the protocols are optimized and parameters are chosen can be found in the paper.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.