International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Chaya Ganesh , Indian Institute of Science
Claudio Orlandi , Aarhus University
Mahak Pancholi , Aarhus University
Akira Takahashi , Aarhus University
Daniel Tschudi , Concordium
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: Bulletproofs (B{\"u}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 \emph{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 \emph{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 \emph{weak unique response} property) achieve \emph{simulation-extractability} in the \emph{algebraic group model}. This implies that Fiat-Shamir Bulletproofs are \emph{non-malleable}.
Video from EUROCRYPT 2022
  title={Fiat-Shamir Bulletproofs are Non-Malleable (in the Algebraic Group Model)},
  author={Chaya Ganesh and Claudio Orlandi and Mahak Pancholi and Akira Takahashi and Daniel Tschudi},