Paper 2025/311

Malleable SNARKs and Their Applications

Suvradip Chakraborty, Visa Research
Dennis Hofheinz, ETH Zurich
Roman Langrehr, ETH Zurich
Jesper Buus Nielsen, Aarhus University
Christoph Striecks, Austrian Institute of Technology
Daniele Venturi, Sapienza University of Rome
Abstract

Succinct non-interactive arguments of knowledge (SNARKs) are variants of non-interactive zero-knowledge proofs (NIZKs) in which complex statements can be proven in a compact way. SNARKs have had tremendous impact in several areas of cryptography, including verifiable computing, blockchains, and anonymous communication. A recurring concept in many applications is the concept of recursive SNARKs, in which a proof references a previous proof to show an evolved statement. In this work, we investigate malleable SNARKs, a generalization of this concept of recursion. An adaptation of the existing concept of malleable NIZKs, malleable SNARKs allow to modify SNARK proofs to show related statements, but such that such mauled proofs are indistinguishable from “properly generated” fresh proofs of the related statement. We show how to instantiate malleable SNARKs for universal languages and relations, and give a number of applications: the first post-quantum RCCA-secure rerandomizable and updatable encryption schemes, a generic construction of reverse firewalls, and an unlinkable (i.e., computation-hiding) targeted malleable homomorphic encryption scheme. Technically, our malleable SNARK construction relies on recursive proofs, but with a twist: in order to support the strong indistinguishability properties of mauled and fresh SNARK proofs, we need to allow an unbounded recursion depth. To still allow for a reasonable notion of extractability in this setting (and in particular to guarantee that extraction eventually finishes with a “proper” witness that does not refer to a previous SNARK proof), we rely on a new and generic computational primitive called adversarial one-way function (AOWF) that may be of independent interest. We give an AOWF candidate and prove it secure in the random oracle model.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2025
Keywords
SNARKsmalleabilityhomomorphic encryptionrerandomizable encryptionupdatable encryptionreverse firewalls
Contact author(s)
suvchakr @ visa com
hofheinz @ inf ethz ch
roman langrehr @ inf ethz ch
jbn @ cs au dk
Christoph Striecks @ ait ac at
venturi @ di uniroma1 it
History
2025-02-23: revised
2025-02-20: received
See all versions
Short URL
https://ia.cr/2025/311
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/311,
      author = {Suvradip Chakraborty and Dennis Hofheinz and Roman Langrehr and Jesper Buus Nielsen and Christoph Striecks and Daniele Venturi},
      title = {Malleable {SNARKs} and Their Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/311},
      year = {2025},
      url = {https://eprint.iacr.org/2025/311}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.