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.
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 language | English |
---|---|
Title of host publication | Advances 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 |
Editors | Orr Dunkelman, Stefan Dziembowski |
Publisher | Springer |
Pages | 397-426 |
Number of pages | 30 |
ISBN (Electronic) | 978-3-031-07085-3 |
ISBN (Print) | 978-3-031-07084-6 |
DOIs | |
Publication status | Published - 25 May 2022 |
Event | 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway Duration: 30 May 2022 → 3 Jun 2022 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer Cham |
Volume | 13276 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 |
---|---|
Country/Territory | Norway |
City | Trondheim |
Period | 30/05/22 → 3/06/22 |
Keywords / Materials (for Non-textual outputs)
- Non-interactive zero-knowledge
- Simulation-extractability
- Fiat-Shamir