Fischlin vs. Fiat-Shamir Performance

Atonal

8/9/24, 9:54 PM

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

0 + 3

zero-knowledge-proofs

fiat-shamir

proof-of-work

universal-composability

fgrieu

8/10/24, 11:09 AM

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](https://crypto.stackexchange.com/q/107573/555)), it may help to detail or give a reference. Also the Fischlin transform usually is presented as building a signature, not a NIZK proof.

Atonal

8/10/24, 4:05 PM

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](https://crypto.ethz.ch/publications/files/Fischl05b.pdf)). 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.

fgrieu

8/10/24, 4:42 PM

Very clear. My bad for not reading the original material on the Fischlin transform, and thanks for linking to that.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Fischlin vs. Fiat-Shamir Performance

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.