Fiat–Shamir Bulletproofs are Non-Malleable (in the Algebraic Group Model)

Chaya Ganesh, Claudio Orlandi, Mahak Pancholi, Akira Takahashi, Daniel Tschudi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Bulletproofs (Bünz et al. IEEE S&P 2018) are a celebrated ZK proof system that allows for short and efficient proofs, and have been implemented and deployed in several real-world systems.
In practice, they are most often implemented in their non-interactive version obtained using the Fiat-Shamir transform, despite the lack of a formal proof of security for this setting.
Prior to this work, there was no evidence that malleability attacks were not possible against Fiat-Shamir Bulletproofs. Malleability attacks can lead to very severe vulnerabilities, as they allow an adversary to forge proofs re-using or modifying parts of the proofs provided by the honest parties.
In this paper, we show for the first time that Bulletproofs (or any other similar multi-round proof system satisfying some form of weak unique response property) achieve simulation-extractability in the algebraic group model.
This implies that Fiat-Shamir Bulletproofs are non-malleable.
Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim, Norway, May 30 – June 3, 2022, Proceedings, Part II
EditorsOrr Dunkelman, Stefan Dziembowski
PublisherSpringer
Pages397-426
Number of pages30
ISBN (Electronic)978-3-031-07085-3
ISBN (Print)978-3-031-07084-6
DOIs
Publication statusPublished - 25 May 2022
Event41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway
Duration: 30 May 20223 Jun 2022

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
Volume13276
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022
Country/TerritoryNorway
CityTrondheim
Period30/05/223/06/22

Keywords / Materials (for Non-textual outputs)

  • Non-interactive zero-knowledge
  • Simulation-extractability
  • Fiat-Shamir

Fingerprint

Dive into the research topics of 'Fiat–Shamir Bulletproofs are Non-Malleable (in the Algebraic Group Model)'. Together they form a unique fingerprint.

Cite this