- 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
-
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.
-
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
-
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.
-
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
-
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 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.
-
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.
We made minor updates to the submission in response to the reviewer’s comments. Below, we answer the reviewer’s questions in more detail.
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 λ and n in our answer for simplicity and assume logλ=o(t(n)); we use “polynomial” to mean poly(λ,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 be WH adversaries, where A2 makes at most aq queries and runs in time at, and let A’ be the composed adversary: A’f(x) computes (ρ,tr) by running the zero-knowledge simulator Sf,V(x) and outputs w←A2f(x,ρ,tr). If both A2 and the zero-knowledge simulator are polynomially bounded, then A’ is polynomially bounded: A’ takes time O(st+at) to run S and A2. Since A’ queries the oracle only if S or A2 queries, A’ has query complexity sq+aq. We note that the simulator’s time and query bounds already account for the time it takes to run V and V’s oracle queries.
We lower bound the probability that A’ outputs a valid witness by Pr[(A1,A2) wins the WH game]−z(vq,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) for a q-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) constructed in the proof of Lemma D.2, we have 2t(n)sq+O(vq⋅t(n))+1≥Pr[A’ outputs a valid witness]≥ω−α−β−z, where ω→1/e. Under α,β,z≤1/10, the right-hand side is eventually bounded below by a positive constant, since 1/e−3/10>0, whereas the left-hand side tends to zero under our parameter assumption. This gives the contradiction.
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.