Paper 2021/1393

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

Chaya Ganesh, Claudio Orlandi, Mahak Pancholi, 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.

Note: Full version

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in Eurocrypt 2022
Keywords
Non-interactive Zero-knowledgeSimulation-extractabilityFiat-ShamirBulletproofs
Contact author(s)
chaya @ iisc ac in
orlandi @ cs au dk
mahakp @ cs au dk
takahashi @ cs au dk
dt @ concordium com
History
2022-03-17: revised
2021-10-15: received
See all versions
Short URL
https://ia.cr/2021/1393
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1393,
      author = {Chaya Ganesh and Claudio Orlandi and Mahak Pancholi and Akira Takahashi and Daniel Tschudi},
      title = {Fiat–Shamir Bulletproofs are Non-Malleable (in the Algebraic Group Model)},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1393},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1393}},
      url = {https://eprint.iacr.org/2021/1393}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.