acceptodds
Under review as a conference paper at ICLR 2027

Can AI Oversight Be Zero-Knowledge?

Abstract

AI systems increasingly produce outputs from confidential data: a fitness-for-duty assessment from an employee's medical records, or the predicted properties of a drug candidate from its molecular structure, a trade secret. It is important to verify that such outputs are correct without revealing the data on which they are based. 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 an external database such as the web. These works focus on efficient verification, which was shown to be impossible for general oracle-aided computation and so requires additional assumptions on the model. In this work, we focus instead on privacy. To sidestep the impossibility, we allow the verifier to run in time polynomial in the computation, and we ask whether interactive arguments for oracle-aided computation can be zero-knowledge: 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 is 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. 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, assuming only collision-resistant hash functions.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
AI safety, privacy, zero-knowledge, cryptography, scalable oversight, complexity theory

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_wGY9OpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies whether oracle-aided computations can be verified without revealing a confidential witness. In the random oracle model, it establishes a tradeoff between completeness, computational soundness, and witness recovery, even when the honest prover and verifier have polynomial overhead relative to the computation being checked. The lower bound extends to a private-witness debate model by combining the honest opponent and verifier.

On the positive side, the paper introduces signed oracle responses and proves knowledge of an accepting, authenticated execution trace using a zero-knowledge argument of knowledge. Under cryptographic assumptions that remain secure relative to the oracle, this provides statistical zero knowledge against malicious verifiers and computational soundness. The construction requires a signer trusted to authenticate genuine answers and protect the sensitive queries. The contributions are theoretical and supported by formal arguments.

Critical strengths
  1. The lower bound isolates a meaningful privacy obstruction beyond verification efficiency. Theorem 3.3 rules out even witness hiding while allowing polynomial overhead in the underlying computation. The quantitative tradeoff in Lemma D.2 makes the conflict between correctness and privacy precise. This is the strongest contribution and the main reason I support acceptance.

  2. The positive result provides a coherent counterpart to the lower bound. Signed responses let the verifier authenticate oracle-dependent computation without repeating queries that expose the witness; a zero-knowledge argument then hides the authenticated trace. The paper clearly acknowledges that this protects privacy from the verifier while introducing trust in the signer. This makes the change in assumptions understandable rather than presenting the construction as an unconditional solution.

Critical weaknesses
  1. The reduction from the witness-hiding lower bound to the headline zero-knowledge conclusion would benefit from explicit resource accounting. Applying the standard implication from zero knowledge to witness hiding requires spelling out the composition of the simulator and the recovery algorithm, including their time and oracle-query bounds and the effect of simulation error. Section 2.1 provides the relevant search-hardness intuition, but the single-prover parameter accounting is not stated explicitly. This seems like a fixable clarification rather than evidence of a counterexample, but it concerns a central claim.

  2. The additional contribution of the positive construction could be positioned more precisely. The construction combines signed-oracle authentication with established zero-knowledge arguments of knowledge. The paper explains the mechanism well, but it is less explicit about which guarantees or technical steps are new relative to the cited signature-card approach. This affects how much independent weight to assign to the positive result, although it does not diminish the main privacy lower bound.

Questions for authors
  1. Could you make the reduction from Theorem 3.3 to zero-knowledge impossibility explicit for the constructed random-oracle relation? In particular, please bound the success probability of the composed adversary (the simulator followed by the recovery algorithm) when it has access to the instance and oracle, but not the protocol transcript. Please also give the time and oracle-query bounds for this composition and explain why they fall within the poly(λ,t(n))\mathrm{poly}(\lambda,t(n)) regime of Theorem 3.3, accounting for simulation error. Does the required search bound follow from the row-search analysis in Section 2.1, or does it need a further argument? Please state the parameter regime under which the corollary holds.

  2. Which guarantees or proof steps in the signed-oracle result go beyond the cited signature-card construction combined with an ordinary zero-knowledge argument of knowledge? A concise explanation of the additional work needed for the stated malicious-verifier statistical zero-knowledge and oracle-relative security guarantees would help assess this contribution.

1 comment

We made minor updates to the submission in response to the reviewer’s comments. Below, we answer the reviewer’s questions in more detail.

  1. We added Lemmas A.20 (lines 954-976) and B.10 (lines 166-1278) and Remark D.3 (lines 1612-1619) to make the reduction from zero knowledge to witness hiding and its parameter regime explicit. Next, we summarize the additions. We suppress λ\lambda and nn in our answer for simplicity and assume log⁡λ=o(t(n))\log \lambda=o(t(n)); we use “polynomial” to mean poly(λ,t(n))poly(\lambda,t(n)).

    In Remark D.3, we argue that Theorem 3.3 extends to a zero-knowledge lower bound with the same parameters and the additional conditions that the zero-knowledge error is at most 1/10 and the simulator runs in polynomial time. Remark D.3 relies on analyzing the composed adversary described by the reviewer.

    Let A1,A2\mathcal{A}_1,\mathcal{A}_2 be WH adversaries, where A2\mathcal{A}_2 makes at most aq\mathsf{aq} queries and runs in time at\mathsf{at}, and let A’\mathcal{A}’ be the composed adversary: A’f(x)\mathcal{A}’^f(\mathbb{x}) computes (ρ,tr)(\rho,\mathsf{tr}) by running the zero-knowledge simulator Sf,V(x)\mathcal{S}^{f,\mathcal{V}}(\mathbb{x}) and outputs w←A2f(x,ρ,tr)\mathbb{w}\gets \mathcal{A}_2^f(\mathbb{x},\rho,\mathsf{tr}). If both A2\mathcal{A}_2 and the zero-knowledge simulator are polynomially bounded, then A’\mathcal{A}’ is polynomially bounded: A’\mathcal{A}’ takes time O(st+at)O(\mathsf{st}+\mathsf{at}) to run S\mathcal{S} and A2\mathcal{A}_2. Since A’\mathcal{A}’ queries the oracle only if S\mathcal{S} or A2\mathcal{A}_2 queries, A’\mathcal{A}’ has query complexity sq+aq\mathsf{sq}+\mathsf{aq}. We note that the simulator’s time and query bounds already account for the time it takes to run V\mathcal{V} and V\mathcal{V}’s oracle queries.

    We lower bound the probability that A’\mathcal{A}’ outputs a valid witness by Pr[(A1,A2) wins the WH game]−z(vq,vt)\mathrm{Pr}[(\mathcal{A}_1,\mathcal{A}_2) \text{ wins the WH game}]-z(\mathsf{vq},\mathsf{vt}) in the proof of Lemma A.20. Then, in Lemma B.10, we show that an adversary with polynomial query bound has negligible probability of finding a valid witness for our relation, following the row-search analysis closely. Even with adaptive queries, each previously unqueried row is independent of the observations so far; a union bound over the queried rows, plus a possible final guess at an unqueried row, gives the bound (q+1)/2t(n)(q+1)/2^{t(n)} for a qq-query adversary. Combining these two lemmas with Lemma D.2 gives us the desired lower bound for relativized zero-knowledge arguments. In particular, for (A1,A2)(\mathcal{A}_1,\mathcal{A}_2) constructed in the proof of Lemma D.2, we have sq+O(vq⋅t(n))+12t(n)≥Pr[A’ outputs a valid witness]≥ω−α−β−z,\frac{\mathsf{sq}+O(\mathsf{vq}\cdot t(n))+1}{2^{t(n)}}\geq \mathrm{Pr}[\mathcal{A}’\text{ outputs a valid witness}]\geq \omega - \alpha -\beta-z, where ω→1/e\omega\to1/e. Under α,β,z≤1/10\alpha,\beta,z\leq1/10, the right-hand side is eventually bounded below by a positive constant, since 1/e−3/10>01/e-3/10>0, whereas the left-hand side tends to zero under our parameter assumption. This gives the contradiction.

  2. The signed-oracle idea originates from CT10 (https://people.eecs.berkeley.edu/~alexch/docs/CT10.pdf), which constructs relativized succinct arguments in the signed random-oracle model. Our construction follows the same approach. The conceptual contribution is to use signed answers from an application oracle to obtain zero-knowledge verification of oracle-aided computations.

    The underlying argument of knowledge uses standard techniques, but we need to establish its security against parties with access to the application oracle. In particular, extraction and statistical zero knowledge must hold against oracle-aided malicious provers and verifiers, respectively. We prove these guarantees under collision resistance relative to the oracle (Theorem F.6, lines 1977–1990).

    We then use the signed query-answer pairs in the witness for the underlying argument. Knowledge extraction and signature security ensure that an accepting proof corresponds to a computation using authenticated oracle answers. Zero-knowledge follows from the underlying simulator.

Reviewer_ynfkOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies AI oversight with zero knowledge (ZK), which verifies an oracle-aided computation without learning anything about the witness, where the oracle-aided computation relies on an external oracle for the correctness of the AI output. Unlike prior work on scalable oversight, this work focuses on ZK instead of verifier efficiency. This paper's contribution consists of three parts. (1) The authors show the existence of a computation that cannot be verified with witness hiding (WH), which is weaker than ZK, in the random oracle model, even when efficient verification is not required. (2) This impossibility can be extended to the debate model. (3) Assuming collision-resistant hash functions, the authors prove that in the signed oracle model, every oracle-aided computation can be verified efficiently in ZK.

Critical strengths

To my knowledge, this is the first work to cover ZK in scalable oversight. Even though the motivation is achieving ZK, the impossibility holds even for the weaker notion of WH. The result is extended to the debate model, another major model in AI oversight. A clear positive result is also presented via a construction in the signed-oracle model.

Critical weaknesses

I don't think there is a major concern.

  • Although the impossibility results are new for ZK, it seems that much of the proof strategy comes from the lower-bound proof of Barbara et al. for succinct arguments. It would be better to clearly explain which parts of the proof are difficult when moving from the non-ZK impossibility result to the ZK one without the succinctness requirement.
  • The construction in the signed oracle model combines signed oracle answers with a standard zero-knowledge argument of knowledge, so its additional technical contribution seems limited.
Questions for authors

Could you add some comments on the technical novelty of the impossibility result over Barbara et al.? Which proof ingredients are inherited from Barbara et al. and which additional arguments are needed to establish the WH impossibility without a succinctness requirement?

1 comment

Our proof techniques are very close to those used in BCG25 (https://eprint.iacr.org/2024/728), which themselves originate from Fortnow and Sipser (https://lance.fortnow.com/papers/files/conpipl.pdf). However, one cannot apply BCG25’s main theorem in a black-box way to obtain our impossibility result. In particular, BCG25 rules out succinct arguments, whereas we allow verification time polynomial in the original computation, so its theorem does not apply directly.

Establishing the witness-hiding impossibility requires additional lemmas. Lemma C.5 (lines 1526–1534) gives a lower bound on the probability that the verifier queries a location encoding the prover’s witness, without assuming succinctness. Lemma D.2 (lines 1597–1601) then uses these queries to construct an efficient witness-recovery procedure (lines 1637–1664), contradicting witness hiding.

Reviewer_shAiOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper suggests that it is generally impossible to create a protocol that would verify the correctness of a result requiring confidential input without revealing the latter to the verifier, even under a reasonable complexity assumptions. Additionally, it provides a solution to this problem using a cryptographic signature. This result is said to have potential applications in medical assessment, drug design and AI oversight.

Critical strengths
  • The verification literature for oracle-aided computation (e.g., [1,2]) has mostly focused on efficiency. Asking whether verification can also be private is a natural and useful question.

  • The tradeoff ϵcomplete+ϵsound+ϵhide≥1/e−o(1)\epsilon_{complete}+ \epsilon_{sound} + \epsilon_{hide} \geq 1/e - o(1) is nice: it says completeness, soundness and privacy compete for a fixed budget, so making verification more reliable makes the leak more likely.

Critical weaknesses
  • While the lower bound seems correct within the paper’s definitions, I am wondering how much it goes beyond the result in [1]. It looks like the main technical details from [1] are reused without saying it explicitly.

  • The title suggests a general treatment of AI oversight, but the results focus on relativized arguments and debate for oracle-aided computation. I felt tricked by the title, and think a more specific title would better set expectations. To this point, although the motivation by applications in health assessment, drug design and AI oversight is stated, it appears quite far from the content of the paper. Specifically, the implications regarding scalable oversight are not discussed explicitly, although the topic is mentioned in "relevant work".


References

[1] Barbara, Chiesa, Guan, "Relativized Succinct Arguments in the ROM Do Not Exist", TCC 2025

[2] Chen, Kalai, Xi, "How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs", ICML 2026

Questions for authors
  1. Could the authors describe a concrete scalable oversight application in which the zero-knowledge verification problem studied here arises?
  2. The model here already assumes a party that sees the confidential witness and is trusted to answer correctly and keep everything secret, so this party could simply evaluate the public computation and sign the final conclusion. This baseline gives the verifier the same privacy and requires essentially the same trust as the paper’s protocol, while being far cheaper to verify (one signature check instead of a zero-knowledge argument). Can the authors describe a concrete setting where per-query signatures plus a zero-knowledge argument are strictly better than having the trusted signer attest the final output? And could the authors elaborate on how practical the proposed approach is?
2 comments

We made minor updates to the submission in response to the reviewer’s comments. We revised the abstract for clarity and added lines 159–173 to better reflect our contribution to both privacy and scalability in oversight.

Our focus on relativized arguments comes from the oracle-aided formulation of scalable oversight, where checking an AI’s output may require external judgments or resources. Relativization is believed to be necessary to capture this dependence, as discussed here: https://www.alignmentforum.org/posts/XycoFucvxAPhcgJQa/the-need-to-relativise-in-debate-1. In this setting, our work shows that scalable oversight can be made zero-knowledge using succinct arguments, provided that the oracle can sign its answers. We added lines 167–173 to explain this connection and our contribution to scalable oversight.

  1. Concrete examples where zero knowledge arises: Two notable applications where an AI’s conclusion must be verified without revealing its confidential inputs are occupational health and drug discovery (see lines 051–062 for the examples and lines 078–091 for the roles of the parties and the privacy requirement). Drug discovery has also been discussed as a motivating application for scalable oversight, for example in Sam Bowman’s talk: https://www.far.ai/event-recordings/sam-bowman-adversarial-scalable-oversight-for-truthfulness-work-in-progr

    In the occupational-health example, the AI (prover), given the medical records (witness) and conclusion (instance), proves to the employer or licensing body (verifier) that the conclusion is correct without revealing the medical records. Both the AI and the employer or licensing body may ask the physician (oracle) the medical questions needed to check the assessment.

    In the drug-discovery example, the AI (prover) proves to a prospective partner (verifier) that a molecule (witness) has the claimed properties (instance), without revealing the molecule’s formula. Both the AI and the partner may check measurements from the laboratory assay (oracle). Independently repeating the assay may require a physical sample, which could be analyzed to recover the molecule’s confidential structure.

  2. Usability of our model: Our approach is useful in two settings: when signing individual oracle answers is cheaper than evaluating the full computation, and when the oracle is a static source that can authenticate information but cannot evaluate the computation. We consider three examples: a human, the web, and a database.

    A human oracle can answer questions about human preferences. For example, scalable oversight has considered a human providing feedback on a long legal contract by inspecting only a few sentences (https://proceedings.mlr.press/v235/brown-cohen24a.html). For sufficiently complicated computations, stating and signing individual judgments can be significantly cheaper than evaluating the full computation. The prover can carry out the expensive computation and prove its correctness, while the human only needs to answer and sign the individual queries.

    For a web oracle, one way to authenticate answers is TLS notarization. For example, TLSNotary allows a notary to sign a commitment to an authenticated TLS transcript, which can later be used to prove what a web server returned (https://tlsnotary.org/docs/protocol/notarization/). The prover can use the authenticated response in a computation and prove that the conclusion is correct, without requiring the web server to evaluate the full computation.

    Similarly, a database oracle can authenticate its records without evaluating a computation that relies on them. The prover can then use the authenticated records in the computation and prove that the conclusion is correct. For example, prior work on scalable oversight considers verifying a computation over a large public dataset while making only a few queries to it (https://arxiv.org/html/2607.03561v1#S1). See lines 159–166 for the discussion of the signer.

  3. Practicality (part of reviewer’s question 2): Our construction is designed to be concretely efficient and compatible with practical deployments. In particular, it is a compiler that allows existing zero-knowledge proof systems to be adapted to oracle-aided computations. Our approach allows us to use any known construction of ZK-SNARGs, such as FlashProve (https://www.anthropic.com/research/provable-inference), and off-the-shelf implementations because we present our construction as a compiler. This makes our approach extremely practical.

Dear authors,

Thank you for the detailed response. Most of my concerns have been addressed and I will raise my rating to 3.

Best wishes, Reviewer shAi

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.