(2026-04) Mergeable SNARGs for Trapdoor Languages and Their Applications
2026-04-07
We present a new method for merging short computationally sound proofs (SNARGs). Intuitively, this means going from short proofs of two statements to a short proof of a statement that is a ``logical consequence'' of the two.
Our work is the first to handle an unbounded polynomial number of recursive merges with arbitrary topology. Unlike prior works, the running time of our security reduction grows only with the depth of the merging process, and not with the associated ``tree size", which could be exponentially larger.
Our method is only applicable to so-called ``trapdoor languages'', where the validity of a statement can be decided in polynomial time given a trapdoor. Importantly, this trapdoor needs not be known for generating or verifying proofs, and is only used in the security reduction. We present constructions from sub-exponential iO and from LWE, where the former yields fully compact proofs, while in the latter the proof size scales with the depth of the merging process.
We show the usefulness of our method by presenting the first CCA1-secure multi-hop fully homomorphic encryption, from either iO or LWE. We also present the first adaptive multi-hop aggregate signature scheme from LWE.