Paper 2024/526

Optimizing and Implementing Fischlin's Transform for UC-Secure Zero-Knowledge

Yi-Hsiu Chen, Coinbase, USA
Yehuda Lindell, Coinbase, USA

Fischlin's transform (CRYPTO 2005) is an alternative to the Fiat-Shamir transform that enables straight-line extraction when proving knowledge. In this work we focus on the problem of using the Fischlin transform to construct UC-secure zero-knowledge from Sigma protocols, since UC security -- that guarantees security under general concurrent composition -- requires straight-line (non-rewinding) simulators. We provide a slightly simplified transform that is much easier to understand, and present algorithmic and implementation optimizations that significantly improve the running time. It appears that the main obstacles to the use of Fischlin in practice is its computational cost and implementation complexity (with multiple parameters that need to be chosen). We provide clear guidelines and a simple methodology for choosing parameters, and show that with our optimizations the running-time is far lower than expected. For just one example, on a 2023 MacBook, the cost of proving the knowledge of discrete log with Fischlin is only 0.41ms (on a single core). This is 15 times slower than plain Fiat-Shamir on the same machine, which is a significant multiple but objectively not significant in many applications. We also extend the transform so that it can be applied to batch proofs, and show how this can be much more efficient than individually proving each statement. We hope that this paper will both encourage and help practitioners implement the Fischlin transform where relevant.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CIC 2024
zero-knowledge proofs of knowledgestraight-line extractionUC security
Contact author(s)
yihsiuc @ pm me
yehuda lindell @ gmail com
2024-06-20: revised
2024-04-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yi-Hsiu Chen and Yehuda Lindell},
      title = {Optimizing and Implementing Fischlin's Transform for {UC}-Secure Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2024/526},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.