Imagine you hire a locksmith to check whether your safe is secure. You need the answer — yes or no — but you absolutely cannot let the locksmith memorize the combination. Now imagine proving the safe was tested correctly to a third party, without revealing the combination to them either. That's the core tension this paper formalizes: can an AI system prove its output is correct while revealing zero information about the private data it consumed? The committed claim is stark. For general oracle-aided computation — any AI process that depends on external judgment calls like a doctor's assessment, a lab result, or a web lookup — zero-knowledge proofs are impossible. This holds even if you give both prover and verifier unlimited extra time. The impossibility is proven in the random oracle model, which is the standard idealization cryptographers use when they want results to generalize broadly. This isn't a resource constraint; it's a mathematical wall. The result extends directly to debate, the canonical model for scalable AI oversight where two AI agents argue before a human judge. If you want debate to be zero-knowledge — meaning the judge learns only the verdict, not the underlying confidential data — the impossibility theorem says no. This matters because debate is currently one of the leading candidates for oversight of superhuman AI systems, and privacy was an unstated assumption in much of the enthusiasm around it. The positive result is equally clean. If the oracle (the doctor, the experiment, the database) cryptographically signs each answer it gives, then zero-knowledge verification becomes possible with efficient provers and verifiers, assuming only collision-resistant hash functions — a standard, well-understood cryptographic primitive. The signed-oracle model is not exotic; it maps naturally to any setting where authoritative sources already authenticate their outputs (medical records systems, certified lab results, digitally signed API responses). Architecturally, this is pure complexity-theoretic cryptography. The impossibility proof uses a simulation argument in the random oracle model, showing that any simulator attempting to fake a transcript without knowing the oracle's answers must query the oracle in a way that leaks information. The positive construction uses the signed oracle to build a non-interactive zero-knowledge argument via collision-resistant hashing — the signatures serve as unforgeable "receipts" that let the prover demonstrate it consulted the oracle without revealing what it asked or received. The integrity of the result is strong in the way theory papers are strong: the claims are mathematical theorems with proofs, not empirical measurements. There's no benchmark to cherry-pick and no dataset to overfit. The negative result is unconditional within its model (random oracle), and the positive result reduces to a standard assumption (collision-resistant hashing). The main integrity question is ecological: how well does the random oracle model capture real AI oversight scenarios? The practical upshot is a fork in the road. If you want zero-knowledge AI oversight, you need infrastructure that makes oracle signatures available — which means redesigning how AI systems interact with authoritative external sources. Without that infrastructure, privacy and verifiability are provably in tension. This is the kind of result that constrains engineering choices years before the engineering happens.
