Adaptive Soundness in Non Interactive Proofs

16 concepts6 papers

In a typical non-interactive proof system, a trusted setup phase generates a set of public parameters, often called the Common Reference String (CRS). In an ideal, static world, we assume that a prover decides what statement they want to prove before this CRS is generated. Under this assumption, standard soundness guarantees that a malicious prover cannot forge a valid proof for a false statement.

However, real-world deployments rarely follow this static sequence. Instead, the public parameters are generated once and published for everyone to see. A malicious prover can study the specific, concrete randomness embedded within the published CRS, identify its unique mathematical quirks or accidental alignments, and then adaptively engineer a false statement tailored to exploit those exact weaknesses. This capability defines the threat model of post-setup adversarial choice, and defending against it requires a robust property known as adaptive soundness.

The Vulnerability of Post-Setup Choice

To understand why adaptive soundness is difficult to achieve, consider how cryptographic proofs are typically verified. In an interactive protocol, a verifier can generate fresh, unpredictable challenges in response to the prover's claims, preventing the prover from planning a trick in advance. In a non-interactive argument system, however, the CRS must act as a standing, static challenge.

As highlighted by Canetti et al., if an adversary can select the statement to be proven after observing the system's public parameters, they can tailor malicious inputs to specific structural holes in the CRS. This flexibility undermines both soundness and zero-knowledge properties. Dachman-Soled et al. similarly note that this post-setup freedom allows the attacker to optimize their strategy against a fixed instance of the proof system, presenting a far steeper security challenge than static models where the input statement is locked in advance.

The Failure of Naive Adaptivity

A simple way to convert a statically sound proof system into an adaptively sound one is a technique called complexity leveraging. If a system is secure for any single fixed statement, a simulator can attempt to guess which statement the adversary will choose.

If there are $N$ possible statements, the security of the system degrades by a factor of $N$. While this approach works if the statement space is small, it completely fails for practical applications like verifiable computation. When delegating the computation of a circuit, the statement space includes every possible input and output combination, which grows exponentially with the input size. Guessing the statement ahead of time incurs an exponential security loss, forcing parameters to become impossibly large and rendering the proof system useless.

Bypassing Exponential Loss via New Primitives

To achieve adaptive soundness without sacrificing efficiency, cryptographers have introduced specialized primitives that inherently resist post-setup manipulation.

Extractable Primitives

One foundational approach involves changing what it means to "prove" something. In Bitansky et al., the authors formalize Succinct Non-interactive Adaptive Arguments of Knowledge (SNARKs). They demonstrate that adaptive soundness can be secured in the standard model by introducing Extractable Collision-Resistant Hash functions (ECRHs). By assuming that any prover capable of generating a valid proof must internally "know" the underlying witness—and that an mathematical extractor can pull this witness out—they bypass the need for multi-round interactive challenges to pin down an adaptive adversary.

Zero-Testable Homomorphic Encryption

For the specific problem of publicly verifiable computation delegation, Paneth et al. introduced a novel primitive called Zero-Testable Homomorphic Encryption (ZTHE). ZTHE extends somewhat homomorphic encryption by incorporating a specialized "weak zero test" capable of identifying ciphertexts that evaluate to a zero polynomial over integers, while strictly preserving semantic security.

The authors demonstrate that ZTHE allows a weak client to verify a powerful server's computation non-interactively. Crucially, this framework achieves adaptive soundness inherently: the proofs remain valid even when the statement to be proven is chosen adaptively, completely avoiding the exponential security loss typical of complexity leveraging. This built on earlier foundations by Rothblum et al., who proved that non-interactive systems for bounded-depth circuits could successfully maintain adaptive soundness against adversaries selecting malicious inputs post-CRS observation.

Extending Adaptivity to Interactive and Composable Settings

The challenge of post-parameter statement selection is not confined to purely non-interactive arguments; it also emerges in interactive protocols where inputs are determined dynamically.

Static Soundness:
[Statement Fixed] ──> [Setup / Parameters Generated] ──> [Proof Generated]

Adaptive Soundness:
[Setup / Parameters Generated] ──> [Adversary Selects Statement] ──> [Proof Generated]

In the domain of interactive proofs, Ciampi et al. addressed this by designing a compiler for delayed-input Sigma protocols. In a standard Sigma protocol, the statement must be known from the start. The compiler presented by the authors strengthens these protocols to achieve adaptive-input special soundness, allowing a prover to postpone learning or choosing the specific statement until the very last stage of the protocol—even after the verifier has sent their challenge—without compromising the system's core security guarantees.

As cryptographic systems are woven into larger, multi-user networks, adaptive soundness must also survive environmental composition and active corruption. Canetti et al. achieved this by constructing the first triply adaptive Universally Composable (UC) Non-Interactive Zero Knowledge (NIZK) argument. Their protocol remains secure under standard, falsifiable assumptions (like LWE or DDH) even when the adversary can adaptively choose statements after seeing the setup and adaptively corrupt participants to expose internal secrets after a proof has already been published.

Key Foundational Work

Publicly Verifiable Non-Interactive Arguments for Delegating Computation (2014) — contributed 2 concept elements to this direction.
Online/Offline OR Composition of Sigma Protocols (2016) — contributed 2 concept elements to this direction.
The Hunting of the SNARK (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adaptive_soundness_8160a410,
  title = {adaptive soundness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-soundness/rdr_8160a410e63648aeba8043cdfe923123},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_adaptive_soundness_8160a410_v1,
  title = {adaptive soundness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-soundness/rdr_8160a410e63648aeba8043cdfe923123/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}

See something wrong? Report a mistake