PaperlayerView exact revision on arXiv

Source-linked AI summary

Can AI Oversight Be Zero Knowledge?

Alessandro Chiesa, Ziyi Guan, Burcu Yildiz

arXiv:2610.01995v1cs.AIcs.CCcs.CR

TL;DR

AI outputs may depend on confidential records or secret molecules, yet checking them can require external judgments or experiments. This paper shows that general zero-knowledge verification can fail, and constructs efficient zero-knowledge verification when oracle answers are signed, assuming collision-resistant hash functions.

  • Problem

    The paper asks whether AI outputs supported by confidential data can be checked without revealing the underlying records or molecule structure.

    Source: §1 · p. 3

  • Method

    The paper studies zero-knowledge arguments for oracle-aided computations and modifies the oracle interface to return signatures on its answers.

    Source: §1.1 · pp. 4–5

  • Results

    Some oracle-aided computations in the random oracle model have no witness-hiding argument, while signed oracles enable zero-knowledge arguments with efficient proving and succinct verification under collision-resistant hash functions.

    Source: §1.1 · pp. 4–5

  • Takeaways & Limitations

    A physician, laboratory, or digital-resource operator can sign oracle answers, provided the signer signs only genuine answers and keeps the signing key private.

    Source: §1.1 · p. 5

    The signed-oracle construction requires a signer trusted to sign only genuine answers and keep the signing key private.

    Source: §1.1 · p. 5

Abstract

from arXiv · show

AI systems increasingly produce outputs from confidential data, such as a fitness-for-duty assessment from medical records or the predicted properties of a drug candidate from its secret structure. It is important to verify that such outputs are correct without revealing the underlying data. A recent line of work studies verification of AI outputs via interactive proofs and debate for oracle-aided computation, where correctness may depend on an oracle such as human judgment, a physical experiment, or the web. These works focus on verification by a verifier that runs much faster than the computation. However, such efficient verification is impossible for general oracle-aided computation, and these works therefore rely on additional assumptions. We focus instead on privacy: allowing the verifier to run in time polynomial in the computation, we ask whether interactive arguments for oracle-aided computation can be zero knowledge, so that the verifier learns nothing about the confidential data beyond the correctness of the output. We prove that, in general, they cannot. In the random oracle model, there are no zero-knowledge proofs for all oracle-aided computations, even if both the prover and the verifier are allowed to run much longer than the computation itself. The impossibility extends to debate, a canonical model for scalable oversight. On the positive side, we show that if the oracle attaches a cryptographic signature to each of its answers, then every oracle-aided computation can be verified in zero knowledge with an efficient prover and verifier, assuming only collision-resistant hash functions. Beyond privacy, this also gives an alternative approach to scalable oversight that relies neither on an honest opponent, as in debate, nor on the robustness of the computation, as in prior single-prover protocols.

1 Introduction

The introduction asks whether oracle-aided AI outputs can be checked while keeping confidential witnesses hidden, even when checking requires an external judgment or experiment. It answers negatively in general and presents signed oracle answers as a route to zero-knowledge verification.

1 Introduction

  • AI outputs may rely on confidential medical records or secret molecule structures, while verification can require a physician’s judgment or a laboratory assay.Independent assay testing requires a physical sample that can reveal the molecule’s structure.Source: §1 · p. 3
  • The paper asks whether a verifier can check that a confidential witness supports an output without learning more about the witness than the claim reveals.It relaxes succinctness because prior work rules out succinct verification for general oracle-aided computations.Source: §1 · pp. 3–4

1.1 Our results

  • In the random oracle model, some oracle-aided computation has no witness-hiding relativized argument, even without succinct verification [FS90; GMR89].Because zero knowledge implies witness hiding, this rules out zero-knowledge verification as well.Source: §1.1 · p. 4
  • The impossibility also rules out even the weakest stated privacy requirement for debate, where the opponent and verifier follow the protocol but cannot recover the witness [ICA18].If both provers receive the witness, either can reveal it to the verifier.Source: §1.1 · p. 5
  • Assuming collision-resistant hash functions, signed oracle answers enable zero-knowledge arguments with an efficient prover and succinct verification for every oracle-aided computation.The signature certifies an oracle answer to a query and can be checked without querying the oracle.Source: §1.1 · p. 5
  • Signed oracles offer an oversight alternative to debate’s honest-opponent assumption and prior single-prover protocols’ robustness assumption [ICA18; BCIP24; CKX26].This approach instead trusts a signer to provide genuine oracle answers and keep the signing key private.Source: §1.1 · p. 5

1.2 Related work

  • Prior scalable-oversight work principally addresses correctness and oversight cost, while private audits of ordinary computations do not address checks depending on external oracle answers.The paper retains the oracle-aided formulation and asks about simulation-based privacy for a confidential witness.Source: §1.2 · p. 6

2 Technical overview

The overview explains a witness-hiding lower bound for an oracle-aided computation, extends it to debate, and presents signed oracles as a construction for succinct zero-knowledge verification.

2.1 The lower bound

  • In the random-oracle construction, any correct protocol for C⋆ forces the verifier to learn a valid witness, violating witness hiding even without requiring succinctness.The proof compares an honest interaction using an oracle with a zeroed witness row to a cheating interaction using the real oracle, which differs only on that row.Source: §2.1 · pp. 7–8

2.2 Debate

  • When only P1 receives the witness, privacy against cooperating P2 and J still permits a reduction to single-prover witness hiding, so the lower bound rules out such debates.The reduction runs P2 and J internally as the single verifier; the debate lower bound then follows from the single-prover result for C⋆.Source: §2.2 · p. 9

2.3 Construction with signed oracles

  • With signed answers, the prover keeps the witness and query-answer-signature record private and proves it is accepting and signature-valid, yielding sound, zero-knowledge, succinct verification.The statement about the record and signatures is an NP statement; the construction uses a zero-knowledge argument of knowledge, with succinct verification based on collision-resistant hash functions.Source: §2.3 · pp. 9–10

3 Preliminaries

This section establishes the notation and formal framework used in the paper, covering oracle computation, relativized arguments, cryptographic assumptions, and PCPs. It also presents a zero-knowledge PCP for the universal relation and a vector-commitment primitive whose security can be obtained from collision-resistant hashing.

3 Preliminaries

  • The preliminaries encode finite sets as binary strings and use standard notation for sampling from distributions and uniformly from nonempty sets.They also define membership in a distribution’s support as having nonzero sampling probability.Source: §3 · p. 11

3.1 Oracles, languages and relations

  • An oracle is a distribution over functions, and relativized languages and relations index membership and witnesses by oracle functions.The language associated with a relativized relation contains instances for which some witness satisfies the relation.Source: §3.1 · p. 11

3.2 Turing machines and complexity classes with oracles

  • Oracle Turing machines query a black-box function, with each query costing one step and an out-of-domain query receiving an empty answer.The section defines relativized nondeterministic time using oracle nondeterministic machines that decide the indexed relations.Source: §3.2 · pp. 12–13

3.3 Relativized interactive arguments in an oracle model

  • Relativized arguments have prover and verifier share an oracle and require no trusted setup; malicious-verifier zero knowledge implies witness hiding when witnesses are hard to find.The zero-knowledge definition compares simulated and real verifier views, and Lemma 3.19 bounds witness-hiding error by z + εfind.Source: §3.3 · pp. 13–15

3.4 Collision-resistant hash functions

  • A keyed hash family uses a polynomial-time key generator and deterministic λ-bit hash function, with collision resistance defined against oracle-aided adversaries.The relative collision-resistance error is negligible for polynomially bounded instance size, query count, and adversary time.Source: §3.4 · p. 15

3.5 Digital signatures

  • Collision-resistant hash functions relative to an oracle imply an EUF-CMA-secure digital signature scheme relative to that oracle.The section derives this using the OWF-to-signature result and black-box hash-to-OWF constructions.Source: §3.5 · p. 16

3.6 Probabilistically checkable proofs

  • A PCP verifier uses randomness to query selected proof bits, and knowledge soundness requires an extractor to recover a witness from an accepted proof.The section defines proof length, query and randomness complexity, verifier time, completeness error, and extraction time.Source: §3.6 · pp. 16–17
  • The universal relation has a perfect-HVZK PCP with perfect completeness, knowledge soundness error at most 1/2, constant queries, and logarithmic randomness.Its proof length is poly(t), verifier time is poly(|M| + |x| + log t), and prover and extractor time is poly(|M| + |x| + t).Source: §3.6 · p. 17

3.7 Vector commitment schemes

  • A vector commitment commits to a bitstring and lets a verifier check openings for queried positions against the commitment.The interface includes generation, commitment, opening, and checking algorithms; succinctness bounds parameter, commitment, and proof lengths by poly(λ, |Q|, log N).Source: §3.7 · pp. 17–18
  • A keyed hash family collision resistant relative to O yields a succinct vector commitment with perfect completeness, hiding error at most 2^-λ, and position binding relative to O.The theorem states that the resulting scheme is position binding relative to O when the hash family is collision resistant relative to O.Source: §3.7 · p. 18

4 Impossibility of witness hiding in the random oracle model

In the random oracle model, the section proves that some oracle-aided relations have no witness-hiding relativized arguments. Its proof modifies the oracle to insert a witness and analyzes how those modifications affect the verifier’s view and query behavior.

4 Impossibility of witness hiding in the random oracle model

  • Theorem 4.1 establishes that, for a random oracle, some oracle-aided relations have no witness-hiding relativized arguments.The theorem uses a time-constructible function t with t(n) ≥ n.Source: §4 · p. 19

4.1 How to modify the oracle to insert a witness

  • The proof inserts a witness by changing oracle answers at its designated query locations, using the same modification as.The section uses this modification to switch between completeness and soundness cases by changing the oracle at a few locations.Source: §4 · p. 19, §4.1 · p. 20

4.2 Proof of Lemma 4.4

  • The proof tracks verifier queries to locations associated with a witness, because a query there lets an adversary recover a valid witness.The proof also bounds the query and running-time costs of its constructed adversaries.Source: §4.2 · pp. 22, 24, 25

5 Zero-knowledge relativized arguments in the signed oracle model

The section constructs zero-knowledge arguments for oracle-aided computations by authenticating oracle answers and proving the resulting computation trace. Under signature-security and collision-resistant-hash assumptions, the construction provides succinct verification in zero knowledge.

5 Zero-knowledge relativized arguments in the signed oracle model

  • A trusted party signs each oracle query–answer pair, while keeping the signing key and queries private and signing only correct answers.In the described implementation, the party reuses signatures for repeated queries and sees queries that may contain private data.Source: §5 · p. 26
  • With EUF-CMA-secure signatures and collision-resistant hashing relative to the signed oracle, every relativized relation in NTIME^O[T] has a malicious-verifier zero-knowledge argument for its signed-oracle lift.The theorem gives negligible soundness error, 2λ + 1 rounds, polynomial communication in λ and log T(n), and polynomial prover and verifier times in the stated parameters.Source: §5 · pp. 26–27

5.1 A zero-knowledge argument of knowledge for the universal relation

  • If a collision-resistant keyed hash family exists relative to an oracle, the universal relation has a malicious-verifier zero-knowledge argument of knowledge with no oracle queries by honest parties.Its communication is polynomial in λ and log t, while verifier time is polynomial in λ, |M|, |x|, and log t.Source: §5.1 · p. 27

5.2 Proof of Theorem 5.2

  • The reduction encodes the oracle computation and its signed query trace as a universal-relation instance, where the machine checks signatures and simulates the computation without querying the oracle.The witness includes the computation witness and the query, answer, and signature records.Source: §5.2 · p. 28
  • Sequential repetition reduces the construction’s soundness error to negligible while giving malicious-verifier zero-knowledge error at most λ · 2^-λ.The repeated protocol has 2λ + 1 rounds.Source: §5 · pp. 26–27, §5.2 · p. 29

A Impossibility of witness hiding for debate

The section transfers an oracle-model impossibility for witness hiding to debate when the honest opponent is efficient. It does so by simulating that opponent inside a single-prover verifier.

Relativized debates

  • The debate privacy guarantee protects the witness from the honest opponent and verifier jointly, since they may cooperate.The section uses witness hiding, the weakest such guarantee; stronger privacy requirements are also covered by the impossibility.Source: A Impossibility of witness hiding for… · p. 30

Folding the opponent into the verifier

  • When the honest opponent is efficient, a debate can be folded into a single-prover relativized argument while preserving soundness and witness hiding.The resulting verifier incorporates the opponent’s query and time costs; the honest prover’s costs remain unchanged.Source: A Impossibility of witness hiding for… · p. 31

The lower bound for debate

  • The corollary transfers Theorem 4.1’s lower bound to debates with the stated polynomial resource bounds.The transfer follows because an assumed debate would yield a relativized argument contradicting Theorem 4.1.Source: A Impossibility of witness hiding for… · p. 32
  • The transfer requires an efficient honest opponent, so debates whose honest opponent takes more than polynomial time are not covered.The corollary concerns witness hiding; extending it to zero knowledge uses the stated negligible-probability condition for finding a witness from the instance alone.Source: A Impossibility of witness hiding for… · p. 32

AI use statement

The authors describe generative-AI assistance in preparing the paper and state that they reviewed the AI-assisted work and take responsibility for its final content.

AI use statement

  • The introduction and technical overview were written by the authors, with AI assistance for language improvement and grammar checks.Source: AI use statement · p. 33
  • The lower bound and its proof were written entirely by the authors apart from typo and spelling checks.Source: AI use statement · p. 33
  • For the debate extension and signed-oracle construction, authors originated the ideas and revised and checked human-guided AI-generated first drafts of proofs.AI tools also assisted with literature search and summaries, figures, and feedback on drafts; the authors say references identified by an LLM were manually checked.Source: AI use statement · p. 33
Loading 2610.01995v1…