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

Yi-Hsiu Chen; Yehuda Lindell

doi:10.62056/a66chey6b

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

Authors

Yi-Hsiu Chen, Yehuda Lindell

Yi-Hsiu Chen

Coinbase, USA
yihsiuc at pm dot me

Yehuda Lindell

Coinbase, USA
yehuda dot lindell at gmail dot com

Abstract

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.

References

[BGR98]

Mihir Bellare, Juan A. Garay, and Tal Rabin. Fast Batch Verification for Modular Exponentiation and Digital Signatures. In Kaisa Nyberg, editor, Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding, volume 1403 of Lecture Notes in Computer Science, pages 236–250. 1998. Springer. DOI: 10.1007/BFB0054130

Google Scholar ePrint

[Can01]

Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 136–145. 2001. IEEE Computer Society. DOI: 10.1109/SFCS.2001.959888

Google Scholar ePrint

[CDS94]

Ronald Cramer, Ivan Damgård, and Berry Schoenmakers. Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols. In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, pages 174–187. 1994. Springer. DOI: 10.1007/3-540-48658-5_19

Google Scholar ePrint

[CGKN21]

Konstantinos Chalkias, François Garillot, Yashvanth Kondi, and Valeria Nikolaenko. Non-interactive Half-Aggregation of EdDSA and Variants of Schnorr Signatures. In Kenneth G. Paterson, editor, Topics in Cryptology - CT-RSA 2021 - Cryptographers' Track at the RSA Conference 2021, Virtual Event, May 17-20, 2021, Proceedings, volume 12704 of Lecture Notes in Computer Science, pages 577–608. 2021. Springer. DOI: 10.1007/978-3-030-75539-3_24

Google Scholar ePrint

[CL24]

Yi-Hsiu Chen and Yehuda Lindell. Feldman's Verifiable Secret Sharing for a Dishonest Majority. IACR Cryptol. ePrint Arch., 2024.

Google Scholar ePrint

[Dam10]

Ivan Damgård. On Sigma protocols.. 2010.

Google Scholar ePrint

[DV14]

Özgür Dagdelen and Daniele Venturi. A Second Look at Fischlin's Transformation. In David Pointcheval and Damien Vergnaud, editors, Progress in Cryptology - AFRICACRYPT 2014 - 7th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 28-30, 2014. Proceedings, volume 8469 of Lecture Notes in Computer Science, pages 356–376. 2014. Springer. DOI: 10.1007/978-3-319-06734-6_22

Google Scholar ePrint

[Fis05]

Marc Fischlin. Communication-Efficient Non-interactive Proofs of Knowledge with Online Extractors. In Victor Shoup, editor, Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, volume 3621 of Lecture Notes in Computer Science, pages 152–168. 2005. Springer. DOI: 10.1007/11535218_10

Google Scholar ePrint

[FS86]

Amos Fiat and Adi Shamir. How to Prove Yourself: Practical Solutions to Identification and Signature Problems. In Andrew M. Odlyzko, editor, Advances in Cryptology - CRYPTO '86, Santa Barbara, California, USA, 1986, Proceedings, volume 263 of Lecture Notes in Computer Science, pages 186–194. 1986. Springer. DOI: 10.1007/3-540-47721-7_12

Google Scholar ePrint

[GLSY04]

Rosario Gennaro, Darren Leigh, Ravi Sundaram, and William S. Yerazunis. Batching Schnorr Identification Scheme with Applications to Privacy-Preserving Authorization and Low-Bandwidth Communication Devices. In Pil Joong Lee, editor, Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings, volume 3329 of Lecture Notes in Computer Science, pages 276–292. 2004. Springer. DOI: 10.1007/978-3-540-30539-2_20

Google Scholar ePrint

[HL10]

Carmit Hazay and Yehuda Lindell. Efficient Secure Two-Party Protocols - Techniques and Constructions. Information Security and Cryptography. Springer 2010. DOI: 10.1007/978-3-642-14303-8

Google Scholar ePrint

[HLNR18]

Iftach Haitner, Yehuda Lindell, Ariel Nof, and Samuel Ranellucci. Fast Secure Multiparty ECDSA with Practical Distributed Key Generation and Applications to Cryptocurrency Custody. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 1837–1854. 2018. DOI: 10.1145/3243734.3243788

Google Scholar ePrint

[Knu97]

Donald E. Knuth. The Art of Computer Programming, Volume 2 (3rd ed.): Seminumerical Algorithms. Addison-Wesley, USA 1997.

Google Scholar ePrint

[KS22]

Yashvanth Kondi and Abhi Shelat. Improved Straight-Line Extraction in the Random Oracle Model with Applications to Signature Aggregation. In Shweta Agrawal and Dongdai Lin, editors, Advances in Cryptology - ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part II, volume 13792 of Lecture Notes in Computer Science, pages 279–309. 2022. Springer. DOI: 10.1007/978-3-031-22966-4_10

Google Scholar ePrint

[PS96]

David Pointcheval and Jacques Stern. Security Proofs for Signature Schemes. In Ueli M. Maurer, editor, Advances in Cryptology - EUROCRYPT '96, International Conference on the Theory and Application of Cryptographic Techniques, Saragossa, Spain, May 12-16, 1996, Proceeding, volume 1070 of Lecture Notes in Computer Science, pages 387–398. 1996. Springer. DOI: 10.1007/3-540-68339-9_33

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a66chey6b

History

Submitted: 2024-04-04
Accepted: 2024-06-03
Published: 2024-07-08

How to cite

Yi-Hsiu Chen and Yehuda Lindell, "Optimizing and Implementing Fischlin's Transform for UC-Secure Zero Knowledge," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/a66chey6b.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-2-11,
    author = "Chen, Yi-Hsiu and Lindell, Yehuda",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Optimizing and Implementing Fischlin's Transform for {UC}-Secure Zero Knowledge",
    volume = "1",
    number = "2",
    date = "2024-07-08",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/a66chey6b"
}

TY - JOUR
AU - Chen, Yi-Hsiu
AU - Lindell, Yehuda
PY - 2024
TI - Optimizing and Implementing Fischlin's Transform for UC-Secure Zero Knowledge
JF - IACR Communications in Cryptology
JA - CIC
VL - 1
IS - 2
DO - 10.62056/a66chey6b
UR - https://doi.org/10.62056/a66chey6b
AB - <p>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. </p>
ER -

Yi-Hsiu Chen and Yehuda Lindell, "Optimizing and Implementing Fischlin's Transform for UC-Secure Zero Knowledge," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/a66chey6b.