Cryptology ePrint Archive: Report 2021/1393

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

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

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.

Category / Keywords: Non-interactive Zero-knowledge, Simulation-extractability, Fiat-Shamir, Bulletproofs

Date: received 15 Oct 2021

Contact author: chaya at iisc ac in, orlandi at cs au dk, mahakp at cs au dk, takahashi at cs au dk, dt at concordium com

Available format(s): PDF | BibTeX Citation

Version: 20211015:082750 (All versions of this report)

Short URL: ia.cr/2021/1393


[ Cryptology ePrint archive ]