Fiat-Shamir Bulletproofs are Non-Malleable (in the Random Oracle Model)

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

Paper 2023/147

Fiat-Shamir Bulletproofs are Non-Malleable (in the Random Oracle Model)

Chaya Ganesh

, Indian Institute of Science Bangalore

Claudio Orlandi

, Aarhus University

Mahak Pancholi, IMDEA Software

Akira Takahashi

, J.P.Morgan AI Research & AlgoCRYPT CoE

Daniel Tschudi

, Concordium, Institute for Network and Security, Eastern Switzerland University of Applied Sciences (OST)

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. A security proof for this setting is necessary for ruling out malleability attacks. These 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. An earlier version of this work (Ganesh et al. EUROCRYPT 2022) provided evidence for non-malleability of Fiat-Shamir Bulletproofs. This was done by proving simulation-extractability, which implies non-malleability, in the algebraic group model. In this work, we generalize the former result and prove simulation extractability in the programmable random oracle model, removing the need for the algebraic group model. Along the way, we establish a generic chain of reductions for Fiat-Shamir-transformed multi-round public-coin proofs to be simulation-extractable in the (programmable) random oracle model, which may be of independent interest.

Note: Preliminary version appeared at EUROCRYPT 2022. This is a full version of EC:GOPTT22 with improved results and supersedes ePrint 2021/1393. - 04.13.2023 Added a concurrent work section - 10.10.2024 Uploaded a version accepted at the Journal of Cryptology

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published by the IACR in JOC 2025
Keywords: zero knowledge Fiat-Shamir non-malleability simulation-extractability Bulletproofs
Contact author(s): chaya @ iisc ac in
orlandi @ cs au dk
mahak pancholi @ imdea org
takahashi akira 58s @ gmail com
dt @ concordium com
History: 2024-10-10: last of 3 revisions; 2023-02-08: received; See all versions
Short URL: https://ia.cr/2023/147
License: CC BY

BibTeX

@misc{cryptoeprint:2023/147,
      author = {Chaya Ganesh and Claudio Orlandi and Mahak Pancholi and Akira Takahashi and Daniel Tschudi},
      title = {Fiat-Shamir Bulletproofs are Non-Malleable (in the Random Oracle Model)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/147},
      year = {2023},
      url = {https://eprint.iacr.org/2023/147}
}