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

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

doi:10.1007/s00145-024-09525-2

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

Chaya Ganesh, Claudio Orlandi, Mahak Rakesh Pancholi, Akira Takahashi, Daniel Tschudi

Department of Computer Science

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaper › Journal article › Research › peer-review

Abstract

Bulletproofs (Bünz et al., in: 2018 IEEE symposium on security and privacy, IEEE Computer Society Press, pp 315–334, 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., in: EUROCRYPT 2022, Part II. LNCS, vol 13276, Springer, Cham, pp 397–426, 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.

Original language	English
Article number	11
Journal	Journal of Cryptology
Volume	38
Issue	1
ISSN	0933-2790
DOIs	https://doi.org/10.1007/s00145-024-09525-2
Publication status	Published - Jan 2025

Keywords

Bulletproofs
Non-interactive zero knowledge proof
Non-malleability
Random oracle model
Simulation-extractability

Access to Document

10.1007/s00145-024-09525-2

https://eprint.iacr.org/2023/147

Cite this

@article{ac74391c15894a36ad142cf36846c86f,

title = "Fiat-Shamir Bulletproofs are Non-Malleable (in the Random Oracle Model)",

abstract = "Bulletproofs (B{\"u}nz et al., in: 2018 IEEE symposium on security and privacy, IEEE Computer Society Press, pp 315–334, 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., in: EUROCRYPT 2022, Part II. LNCS, vol 13276, Springer, Cham, pp 397–426, 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.",

keywords = "Bulletproofs, Non-interactive zero knowledge proof, Non-malleability, Random oracle model, Simulation-extractability",

author = "Chaya Ganesh and Claudio Orlandi and Pancholi, {Mahak Rakesh} and Akira Takahashi and Daniel Tschudi",

year = "2025",

month = jan,

doi = "10.1007/s00145-024-09525-2",

language = "English",

volume = "38",

journal = "Journal of Cryptology",

issn = "0933-2790",

publisher = "Springer",

number = "1",

}

TY - JOUR

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

AU - Ganesh, Chaya

AU - Orlandi, Claudio

AU - Pancholi, Mahak Rakesh

AU - Takahashi, Akira

AU - Tschudi, Daniel

PY - 2025/1

Y1 - 2025/1

N2 - Bulletproofs (Bünz et al., in: 2018 IEEE symposium on security and privacy, IEEE Computer Society Press, pp 315–334, 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., in: EUROCRYPT 2022, Part II. LNCS, vol 13276, Springer, Cham, pp 397–426, 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.

AB - Bulletproofs (Bünz et al., in: 2018 IEEE symposium on security and privacy, IEEE Computer Society Press, pp 315–334, 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., in: EUROCRYPT 2022, Part II. LNCS, vol 13276, Springer, Cham, pp 397–426, 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.

KW - Bulletproofs

KW - Non-interactive zero knowledge proof

KW - Non-malleability

KW - Random oracle model

KW - Simulation-extractability

UR - http://www.scopus.com/inward/record.url?scp=85213006675&partnerID=8YFLogxK

U2 - 10.1007/s00145-024-09525-2

DO - 10.1007/s00145-024-09525-2

M3 - Journal article

SN - 0933-2790

VL - 38

JO - Journal of Cryptology

JF - Journal of Cryptology

IS - 1

M1 - 11

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this