Publicly-Verifiable Certificates for Statistical Algorithms

# Publicly-Verifiable Certificates for Statistical Algorithms
Source: [https://arxiv.org/html/2607.15528](https://arxiv.org/html/2607.15528)
Michael Ngo MIT mingo@mit\.eduResearch completed while at Cornell University, supported by the Bowers Undergraduate Research Experience \(BURE\) and the Dean Archer Undergraduate Research Program\. This research was supported by a gift from Google\.Michael P\. Kim Cornell University mpk@cs\.cornell\.edu

\(1 April 2026\)

###### Abstract

Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41)\], we initiate the study of non\-interactive proofs of learning\. We define and study a new notion:*Publicly\-Verifiable Certificates of Statistical Validity*\(pvCSVs\), which allow for public, distributionally\-robust certification that the result of a learning algorithm is valid\. In a pvCSV, a learner publishes a hypothesishhand corresponding certificateπ\\pi; then,*any*user, who holds a user\-specific distribution, can read the pair\(h,π\)\(h,\\pi\)and determine efficiently whether the hypothesis is valid*according to the user\-specific distribution*\.

We construct pvCSVs in the context of Adaptive Statistical Query \(SQ\) Algorithms\. To certify SQ algorithms that makeskkadaptive queries, we construct pvCSVs where the sample complexity scales withO​\(log⁡k\)O\(\\log k\), whereas the sample complexity of the best learning algorithms scale withO~​\(k\)\\tilde\{O\}\(\\sqrt\{k\}\)\. More generally, we study proof systems for learning in the SQ model, demonstrating the model’s strengths as well as its limitations\.

## 1Introduction

Training large\-scale AI models using statistical machine learning is notoriously costly\. Due to the resource demands of running ML algorithms, AI users rely upon pre\-trained models from a handful of tech companies\. These companies hold enough data—so they claim—to train general\-purpose models that are effective across a wide range of settings\. In this setup, however, users receive no guarantee that the AI models were trained appropriately\. If users fear that the training data does not adequately reflect their setting, they must investigate, for themselves, whether the model produces errors \(or worse, harms\) within their application\.

Inspired by these issues, Goldwasser, Shafer, Rothblum, and Yehudayoff\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41)\]introduced and studied the problem of delegating machine learning, through the PAC Verification framework\. Building on the classic model of interactive proofs\[[GMR85](https://arxiv.org/html/2607.15528#bib.bib1),[BAB85](https://arxiv.org/html/2607.15528#bib.bib34)\], PAC Verification formalizes the problem: a statistically\-limited user \(the*verifier*\) interacts with a powerful, but untrusted learner \(the*prover*\), who aims to convince the user that a given model \(the*hypothesis*\) is valid\. As in cryptographic proof systems, PAC Verification requires that protocols for delegating learning satisfy formal notions of*completeness*and*soundness*\. To date, results in the area focus on developing protocols for verifying Agnostic PAC Learning\[[VAL84](https://arxiv.org/html/2607.15528#bib.bib6),[HAU92](https://arxiv.org/html/2607.15528#bib.bib7),[KSS94](https://arxiv.org/html/2607.15528#bib.bib8)\]for specific concept classes\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41),[MS23](https://arxiv.org/html/2607.15528#bib.bib42),[GJK\+24](https://arxiv.org/html/2607.15528#bib.bib44)\]\. As a notable exception, Mutreja and Shafer\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]also introduce a notion of delegation of Statistical Query \(SQ\) algorithms for loss minimization\.

An essential element of prior works on delegation of learning is*interaction*\. To establish whether a given hypothesis is valid, the prover and verifier exchange a sequence of messages in an online fashion, after which the verifier chooses to accept or reject the prover’s hypothesis\. As a concrete example, the original work on PAC verification shows how to delegate the Goldreich\-Levin algorithm\[[GL89](https://arxiv.org/html/2607.15528#bib.bib5)\]\(which requires point query access to the unknown function\), when the verifier only has i\.i\.d\. labeled samples\. In this proof system, the verifier uses its interactions with the prover to label the point queries, while cleverly hiding some points whose labels are known to the verifier to ensure soundness\. The early works on PAC verification have demonstrated that interactive proof systems provide a powerful tool for efficiently checking the results of an expensive ML computation\.111In these works, and in our paper, “efficiency” primarily focuses on statistical resources, rather than computation\.

Interaction, however, also presents challenges\. Most immediately, running an interactive proof requires the verifier and prover to be online at the same time to execute the protocol\. Additionally, each execution of the interactive proof may require the prover to answer execution\-specific challenges, including re\-running the original ML computation\. Given the immense cost of training ML models in the first place, providers may be unwilling to participate in the interactive proof more than once \(if at all\)\. In such a setting, where the interactive proof is executed once—between the learner and a single verifier—many users would have to place their trust in a single entity\. Even if users agree that the verifier is generally trustworthy, as before, individual users may worry that the verifier’s data does not represent their setting and applications\.

#### This Work\.

We initiate the study of non\-interactive proofs of learning\. Our study leads us to a new notion:*Publicly\-Verifiable Certificates of Statistical Validity \(pvCSVs\)*\. pvCSVs allow for public, distributionally\-robust certification that the result of a learning algorithm is valid\. In particular, a pvCSV allows a learner to publish a hypothesishhand certificate of validityπ\\pithat allows*any*downstream user to subsequently verify that the hypothesis is statistically valid on a*user\-specified*distribution\.

We can understand the semantics of a pvCSV by imagining two worlds\.

- •In the first world, a user collects a huge amount of data from a distribution𝒟\\mathcal\{D\}, relevant to their setting and application\. Then, they correctly execute a statistical learning algorithm𝒜\\mathcal\{A\}on top of this data to obtain a hypothesishidealh\_\{\\mathrm\{ideal\}\}\.
- •In the second world, a centralized, well\-resourced learner publishes a pvCSV\(hreal,π\)\(h\_\{\\mathrm\{real\}\},\\pi\)for the algorithm𝒜\\mathcal\{A\}; the same user from before collects a much more modest amount of data from𝒟\\mathcal\{D\}, then reads and verifies\(hreal,π\)\(h\_\{\\mathrm\{real\}\},\\pi\), using the small amount of user\-specific data\.

A pvCSV guarantees that if\(hreal,π\)\(h\_\{\\mathrm\{real\}\},\\pi\)passes verification, the two worlds produced equally\-valid hypotheseshideal≈𝒟,𝒜hrealh\_\{\\mathrm\{ideal\}\}\\approx\_\{\\mathcal\{D\},\\mathcal\{A\}\}h\_\{\\mathrm\{real\}\}according to the user\-specific data distribution and the learning algorithm𝒜\\mathcal\{A\}\. This guarantee must hold even though the user has no knowledge of the data distribution used to produce the pvCSV\. As such, pvCSVs resolve the key shortcomings of interactive proofs for delegation of learning: the learner can execute the expensive training algorithm once and \(with little overhead\) generate a corresponding pvCSV certificate that any user can subsequently verify\.

#### Certification of Adaptive Data Analysis\.

We make our study of pvCSVs concrete by revisiting the question of Adaptive Data Analysis\[[DFH\+15b](https://arxiv.org/html/2607.15528#bib.bib17)\]in the Statistical Query Model\[[KEA98](https://arxiv.org/html/2607.15528#bib.bib40)\]\. Many tools for learning from data—including workhorse ML algorithms like gradient descent—can be framed as adaptive statistical algorithms\. In such an algorithm, the learner is allowed to ask a sequence of queries of the data distribution \(e\.g\.,*What is the gradient of the expected loss over𝒟\\mathcal\{D\}?*\), where each query may depend on the results from prior queries\.

Formally, we consider learning algorithms𝒜\\mathcal\{A\}that interact with a Statistical Query \(SQ\) oracle𝒪\\mathcal\{O\}: given a toleranceτ\\tauand a queryqq,𝒪​\(q\)\\mathcal\{O\}\(q\)responds with aτ\\tau\-accurate estimate of the expectation of the predicateqqover the data distribution\. Critical to our investigation, the algorithm may select its sequence of queries*adaptively*based on the prior responses\. That is, the algorithm’s choice of theii\-th queryqiq\_\{i\}may depend arbitrarily on prior queriesq1,…,qi−1q\_\{1\},\\ldots,q\_\{i\-1\}and responses𝒪​\(q1\),…,𝒪​\(qi−1\)\\mathcal\{O\}\(q\_\{1\}\),\\ldots,\\mathcal\{O\}\(q\_\{i\-1\}\), \(e\.g\.,*What is the gradient at theii\-th iterate, after takingi−1i\-1gradient descent steps?*\)\.

While the paradigm of adaptive data analysis is a versatile and powerful tool for learning, such algorithms are known to be statistically expensive\. About a decade ago,\[[DFH\+15b](https://arxiv.org/html/2607.15528#bib.bib17)\]identified adaptivity as a key issue in statistical algorithms\. To maintain the statistical validity of an adaptive analysis requires the learner to either resample fresh data to support every new query, or to employ sophisticated \(differentially\-private\) algorithms for answering queries in a way to prevent overfitting to the data set\[[DFH\+15b](https://arxiv.org/html/2607.15528#bib.bib17),[DFH\+15a](https://arxiv.org/html/2607.15528#bib.bib18),[DFH\+15c](https://arxiv.org/html/2607.15528#bib.bib19),[BNS\+16](https://arxiv.org/html/2607.15528#bib.bib21),[FS18](https://arxiv.org/html/2607.15528#bib.bib24),[JLN\+19](https://arxiv.org/html/2607.15528#bib.bib22),[DK22](https://arxiv.org/html/2607.15528#bib.bib25),[BLA25](https://arxiv.org/html/2607.15528#bib.bib26)\]\. To answerkkadaptively selected statistical queries, the best algorithms use a number of samples scaling \(roughly\) withk\\sqrt\{k\}, and in fact, this dependence is essentially tight\[[HU14](https://arxiv.org/html/2607.15528#bib.bib23),[SU15](https://arxiv.org/html/2607.15528#bib.bib20)\]\.

In other words, no matter what techniques are employed, adaptive statistical algorithms require*exponentially*more data than non\-adaptive \(batch\) statistical analyses of similar size\. In this work, we ask when we can certify the results of adaptive data analysis more efficiently than learning\.

### 1\.1Our Contributions

We develop proof systems for delegating*arbitrarily\-adaptive*statistical algorithms where the verifier requires samples scaling only with the*non\-adaptive*complexity\. In doing so, we realize an*exponential*gap, between the sample complexity required for executing SQ algorithms versus verifying them\. Moving beyond prior work on*interactive*proofs for learning, we build novel*non\-interactive*proof systems—namely,*publicly\-verifiable Certificates of Statistical Validity*—that enable a new form of distributionally\-robust validation of statistical learning\. Along the way, we develop a number of extensions to earlier models of proof systems for delegation of learning\.

#### Publicly\-Verifiable Certificates of Statistical Validity\.

In Section[3](https://arxiv.org/html/2607.15528#S3), we introduce our primary contribution: a new notion of proof that allows for public, distributionally\-robust certification of learning\. A*publicly\-verifiable Certificate of Statistical Validity*\(pvCSV\) is a non\-interactive proof system that allows any verifier to certify the results of a statistical computation*with respect to the verifier’s own distribution*\. A pvCSV allows a single, well\-resourced learner—the prover—to publish the results of a statistical algorithm in a way that can be checked efficiently \(with less resources\) by any downstream verifier; in particular, the verifiers need not hold the same distribution as the prover\. Instead, the proof system guarantees a*universal soundness*property such that if the verifier accepts the proof, then the results of the statistical algorithm are valid on the verifier’s distribution—even if the algorithm was executed using samples from a different distribution\.

###### Definition 1\(pvCSV, informal\)\.

Apublicly\-verifiable Certificate of Statistical Validityis a non\-interactive proof system, where a proverPPwith distribution𝒟P\\mathcal\{D\}\_\{P\}publishes a hypothesishhpaired with certificateπ\\pi\. Any verifierVVwith distribution𝒟V\\mathcal\{D\}\_\{V\}can read the pair\(h,π\)\(h,\\pi\)and accept or reject where the following guarantees hold with high probability\.

- •Completeness: if𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}, there exists an honest prover pair\(h,π\)\(h,\\pi\)such thathhis valid for𝒟V\\mathcal\{D\}\_\{V\}andVVaccepts\.
- •Universal Soundness: for any verifierVVwith distribution𝒟V\\mathcal\{D\}\_\{V\}, for any \(possibly\-cheating\) prover pair\(h~,π~\)\(\\tilde\{h\},\\tilde\{\\pi\}\), ifVVaccepts, thenh~\\tilde\{h\}is actually valid for𝒟V\\mathcal\{D\}\_\{V\}\.

One way to understand the guarantee of pvCSVs is as a robust proof of statistical validity,*without an explicit assumption about distributional shifts*\. Rather than positing some known relationship between the prover and verifier distributions, the verification procedure works for any𝒟P\\mathcal\{D\}\_\{P\}and𝒟V\\mathcal\{D\}\_\{V\}and results in acceptance whenever the published certificate—derived from the execution of a learning algorithm𝒜\\mathcal\{A\}using the prover’s distribution—reflects some legitimate execution on the verifier’s distribution\. While our notion of completeness assumes that𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}, the guarantee is more subtle than this equality would suggest\. The distributions𝒟P\\mathcal\{D\}\_\{P\}and𝒟V\\mathcal\{D\}\_\{V\}may differ significantly in composition, but if the verifier accepts, then \(by universal soundness\) the hypothesishhis valid for𝒟V\\mathcal\{D\}\_\{V\}\(because the distributions are indistinguishable according to some invocation of𝒜\\mathcal\{A\}\)\. The careful reader will note that this “universal soundness” condition is actually implied by standard soundness for delegation of learning,222The honest prover using𝒟P\\mathcal\{D\}\_\{P\}may be viewed as a cheating prover with respect to the verifier holding𝒟V\\mathcal\{D\}\_\{V\}\.but holds new significance in the context of non\-interactive proofs\. Our view on soundness, paired with a non\-interactive proof system, allows us to realize certificates of learning that can be verified publicly by any user\.

We can use various measures of complexity to evaluate the quality of a pvCSV construction\. Principle to our work is sample complexity: we aim for pvCSVs where the verifier saves considerably in the number of samples needed from𝒟V\\mathcal\{D\}\_\{V\}compared to the number of samples required for learning \(or proving\)\. Further, we can track other measures like time complexity \(of both the verifier and the honest prover\) and proof length as well\. We define pvCSVs formally in Section[3](https://arxiv.org/html/2607.15528#S3)and provide a thorough discussion of the notion and its properties \(like validity and universal soundness\) therein\.

With this key definition in place, the main technical contributions of this work are to construct pvCSVs for adaptive statistical algorithms within the SQ learning framework\. Our pvCSVs achieve an*exponential*gap in the sample complexity between SQ verification and SQ learning\. While the core idea of each of our constructions is similar, the resulting protocols differ in important ways based on properties of the original SQ algorithm\. As we show, the way that the algorithm uses randomness and the way the SQ oracle is allowed to adapt to the algorithm’s internal state are key factors in building universally\-sound pvCSVs\.

#### pvCSVs for Deterministic SQ Algorithms\.

In Section[3\.1](https://arxiv.org/html/2607.15528#S3.SS1), we consider SQ algorithms that do not use internal randomness\. These “deterministic” SQ algorithms are considerably simpler to reason about, and as such, we obtain strong, statistically\-sound pvCSVs for all such algorithms\.333We note that such “deterministic” algorithms may still have non\-deterministic behavior, due to the algorithm’s adaptivity to the responses from the SQ oracle, which is assumed to beτ\\tau\-accurate, but otherwise, adversarial\.

###### Theorem 2\.

Let𝒜\\mathcal\{A\}be a deterministic SQ algorithm that learns a concept𝒢\\mathcal\{G\}\. Suppose𝒜\\mathcal\{A\}makeskkadaptive queries to aτ\\tau\-accurate SQ oracle𝒪\\mathcal\{O\}\. There exists a pvCSV scheme for certifying𝒢\\mathcal\{G\}\(with constant failure probability\) achievable in the following complexities\.

- •Honest prover sample complexity:mP≤O~​\(k/τ2\)m\_\{P\}\\leq\\tilde\{O\}\(\\sqrt\{k\}/\\tau^\{2\}\)
- •Verifier sample complexity:mV≤O​\(log⁡\(k\)/τ2\)m\_\{V\}\\leq O\(\\log\(k\)/\\tau^\{2\}\)
- •Certificate size:\|π\|≤O​\(k⋅log⁡\(1/τ\)\)\\left\|\\pi\\right\|\\leq O\(k\\cdot\\log\(1/\\tau\)\)

In other words, even though the best learning algorithms useO~​\(k\)\\tilde\{O\}\(\\sqrt\{k\}\)samples to supportkkadaptively\-chosen queries, there is a short certificate \(namely, the results of the queries\) that convinces a verifier with considerably less information about the distribution inO​\(log⁡\(k\)\)O\(\\log\(k\)\)samples\. The bounds of Theorem[2](https://arxiv.org/html/2607.15528#Thmresult2)follow from the prover and verifier collectively executing a direct simulation of the original SQ algorithm with no overhead for the honest prover; in this sense, the delegation scheme can be thought of as*doubly\-efficient*in its statistical complexity, à la\[[GKR08](https://arxiv.org/html/2607.15528#bib.bib2)\]\. Computationally, both the prover and the verifier need to simulate the execution of the underlying SQ algorithm, so the time\-complexity scales roughly linearly in the running time of the original algorithm\.

#### pvCSVs for Randomized SQ Algorithms and SQ Protocols\.

In Section[4](https://arxiv.org/html/2607.15528#S4), we investigate how to build pvCSVs for SQ algorithms that use randomness\. Randomness introduces significant technicality in the resulting proof systems\. Here, we give an informal description of our results, including various definitions we develop to obtain the results\.

Towards a pvCSV for randomized SQ algorithms, we need to reason about how the algorithm—and the \(possibly\-adversarial\) SQ oracle—may act adaptively to the randomness\. First, we say that a randomized SQ algorithm operates inℓ\\ell“epochs” if it can be broken down into a series ofℓ\\elldeterministic SQ algorithms, which each take a fresh random string as an input\. Next, we say that an SQ oracle is “public\-state” if it may choose its query responses as a function of the SQ algorithm’s internal randomness \(in contrast to an “oblivious” oracle, which has no knowledge of the algorithm’s randomness\)\. We construct pvCSVs in the Random Oracle Model \(ROM\)\[[BR93](https://arxiv.org/html/2607.15528#bib.bib36)\]for all constant\-epoch randomized SQ algorithms that are correct using a public\-state SQ oracle\.

###### Theorem 3\.

Let𝒜\\mathcal\{A\}be a randomized SQ algorithm that learns a goal𝒢\\mathcal\{G\}with high probability\. Suppose𝒜\\mathcal\{A\}makeskkadaptive queries to aτ\\tau\-accurate public\-state SQ oracle𝒪\\mathcal\{O\}, over an execution ofO​\(1\)O\(1\)epochs\. There exists a computationally\-sound pvCSV scheme in the ROM for certifying𝒢\\mathcal\{G\}\(with constant failure probability\) achievable in the following complexities\.

- •Honest prover sample complexity:mP≤O~​\(k/τ2\)m\_\{P\}\\leq\\tilde\{O\}\(\\sqrt\{k\}/\\tau^\{2\}\)
- •Verifier sample complexity:mV≤O​\(log⁡\(k\)/τ2\)m\_\{V\}\\leq O\(\\log\(k\)/\\tau^\{2\}\)
- •Certificate size:π≤O​\(k⋅log⁡\(1/τ\)\)\\pi\\leq O\(k\\cdot\\log\(1/\\tau\)\)

In fact, Theorem[3](https://arxiv.org/html/2607.15528#Thmresult3)follows from a much more general result\. We start by adapting the definition of delegation of learning\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41)\]to the statistical query setting, yielding a format for interactive learning which we call*SQ protocols*\. We show that a large class of interactive SQ protocols \(of which randomized SQ algorithms are a special case\) can be compiled into a*canonical SQ protocol*with desirable properties\. The class consists of SQ protocols where the verifier may send random and non\-random challenges to the prover and may make private statistical queries \(not sent to the prover\) to its public\-state oracle; we call these protocols “mixed\-message, private\-query” SQ protocols\. After compilation, we obtain a canonical SQ protocol with the same completeness and soundness guarantees as the original, but which is public\-coin \(verifier only sends random challenges\) and public\-query \(verifier reveals all SQs to the prover\)\. Importantly, the canonical verifier still only makes a single batch of statistical queries\.

###### Lemma 4\.

Suppose\(P,V\)\(P,V\)is a mixed\-message, private\-query SQ protocol where the verifier makeskkadaptive queries to aτ\\tau\-accurate public\-state SQ oracle and verifies concept𝒢\\mathcal\{G\}\. There exists a canonical public\-coin, public\-query SQ protocol\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)that verifies𝒢\\mathcal\{G\}with the same completeness/soundness as\(P,V\)\(P,V\), with the following properties\.

- •𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}makes at mostkkadditional statistical queries compared toPP;
- •𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}makes a single, non\-adaptive batch ofkkstatistical queries\.

This canonical SQ protocol can then be compiled into a pvCSV via a Fiat\-Shamir transformation\[[FS86](https://arxiv.org/html/2607.15528#bib.bib35)\], whose blow\-up in soundness scales exponentially with the “epoch complexity” of the original protocol\. The sample complexities claimed in Theorem[3](https://arxiv.org/html/2607.15528#Thmresult3)follow by giving sample\-based implementations of an adaptive SQ oracle \(for the prover\) and non\-adaptive SQ oracle \(for the verifier\)\. As a consequence, we obtain computationally\-sound pvCSVs for a much broader class of learning goals—those that can be solved by an interactive SQ protocol according to Lemma[4](https://arxiv.org/html/2607.15528#Thmresult4)\.

As may be evident, to appropriately reason about delegation of learning in this context, we need to reason about a number of novel concepts \(e\.g\., SQ protocols, public\-coin, public\-query, epoch complexity, etc\.\)\. An additional key contribution of our work is laying out precise definitions for these notions that arise in the study of proof systems for learning, presented formally in Section[4\.1](https://arxiv.org/html/2607.15528#S4.SS1)\. We discuss our construction of pvCSVs for randomized algoirthms/SQ protocols in greater detail within the Technical Overview\.

#### Beyond pvCSVs: The Limits of SQ Protocols\.

Building pvCSVs, particularly for randomized SQ algorithms, required investigating aspects of more general interactive protocols for statistical query learning\. We complement our constructions of pvCSVs with a few results about the strengths and limitations of SQ protocols\.

We show that, quite generically, verification of SQ protocols can be made statistically non\-adaptive, in the sense that the verifier issues a single batch of statistical queries, and thus, has sample complexity scaling logarithmically in the number of queries\. The exact class of protocols which we can delegate soundly in this manner is a bit technical, but it consists of a large class of “public\-query” SQ protocols\. In particular, the class of protocols includes private\-coin protocols, where the verifier maintains secret randomness from the prover, but allows the prover to know which statistical queries the verifier issues\.

###### Proposition 5\(Informal\)\.

For every public\-query SQ protocol where the verifier makeskkadaptive queries to aτ\\tau\-accurate public\-state SQ oracle, there is an equivalent SQ protocol where the verifierVVmakes a single, non\-adaptive batch of queries; that is,VVhas sample complexitymV≤O​\(log⁡\(k\)/τ2\)m\_\{V\}\\leq O\(\\log\(k\)/\\tau^\{2\}\)\.

This result shows that statistical validation of a large class of SQ protocols can be done in non\-adaptive sample complexity\. A natural question, then, is whether this statistically\-efficient verification scheme can be made computationally\-efficient\. Unfortunately, we show a barrier to generic computational savings in the SQ model\. Piggybacking off of a sample complexity lower bound given by\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]for PAC Verfication, we obtain a lower bound on the verifier’s*query complexity*for the same class of SQ protocols from Proposition[5](https://arxiv.org/html/2607.15528#Thmresult5)\.

###### Corollary 6\(Informal\)\.

For every hypothesis classℋ\\mathcal\{H\}of VC dimensiondd, in any SQ protocol \(as in Proposition[5](https://arxiv.org/html/2607.15528#Thmresult5)\) thatε\\varepsilon\-PAC Verifiesℋ\\mathcal\{H\}using aτ\\tau\-accurate SQ oracle forτ≈ε\\tau\\approx\\varepsilon, the verifier makes2Ω​\(d\)2^\{\\Omega\(\\sqrt\{d\}\)\}statistical queries\.

#### SQ Verification under Differential Privacy\.

Finally, we show that the verifiers of all of our pvCSVs and interactive SQ protocols can be implemented under Differential Privacy\[[DMN\+06](https://arxiv.org/html/2607.15528#bib.bib9)\]\. Differential Privacy \(DP\) is the de facto notion to protect individuals’ data in statistical analyses, but it can be statistically costly: implementing SQ algorithms under DP requires sample complexity akin to adaptive data analysis\. This result shows that a verifier can validate the results of a statistical analysis much more efficiently, while still maintaining privacy over their own data set\.

The new private verifiers use essentially the same number of samples as the non\-private verifiers\. Concretely, we state the result for the pvCSV verifiers\.

###### Proposition 7\(Informal\)\.

Consider the pvCSV verifier from either Theorem[2](https://arxiv.org/html/2607.15528#Thmresult2)or Theorem[3](https://arxiv.org/html/2607.15528#Thmresult3)\. There exists anε\\varepsilon\-DP implementation of the verifier over the samples from𝒟V\\mathcal\{D\}\_\{V\}\(with constant failure probability\) whose sample complexity scales asO​\(log⁡\(k\)/τ2\+log⁡\(k\)/τ​ε\)O\(\\log\(k\)/\\tau^\{2\}\+\\log\(k\)/\\tau\\varepsilon\)\.

### 1\.2Technical Overview and Discussion of Results

In the remainder of the introduction, we give a more detailed overview of our models and results\. Throughout, we aim to provide pointers into the main text for formal presentation\. We include discussion of the significance of the results, connections to prior works, as well as possible extensions\.

The primary goal of our work is to take an arbitrarily\-adaptive SQ algorithm𝒜\\mathcal\{A\}and turn it into a pvCSV that can be verified efficiently\. At a high\-level our approach is simple: require the prover to run a direct simulation of𝒜\\mathcal\{A\}; then, check the prover’s work\. In particular, the statistically\-expensive aspect of adaptive data analysis is generating the sequence of queriesq1,…,qkq\_\{1\},\\ldots,q\_\{k\}\. Once the sequence has been generated, however, the answers to the queriesq1,…,qkq\_\{1\},\\ldots,q\_\{k\}can be checked in a single, non\-adaptive batch ofkkstatistical queries\.

This observation immediately suggests a non\-interactive proof system for delegating “deterministic” SQ algorithms that do not use any internal randomness, which is the focus of Section[3\.1](https://arxiv.org/html/2607.15528#S3.SS1)\.

- •The honest proverPPexecutes𝒜\\mathcal\{A\}using their own SQ oracle𝒪P\\mathcal\{O\}\_\{P\}to answer any necessary queries\. Along the way, the prover records the queries and results, and at the end, when𝒜\\mathcal\{A\}outputs some hypothesishh,PPsendshhandπ=⟨q1,𝒪P​\(q1\),…,qk,𝒪P​\(qk\)⟩\\pi=\\langle q\_\{1\},\\mathcal\{O\}\_\{P\}\(q\_\{1\}\),\\ldots,q\_\{k\},\\mathcal\{O\}\_\{P\}\(q\_\{k\}\)\\rangleto the verifierVV\.
- •To certify thathhis valid, the verifier must re\-run𝒜\\mathcal\{A\}, but rather than using its own oracle, it will answer any statistical queries using the answers fromπ\\pi\. If at any point, the verifier’s execution𝒜\\mathcal\{A\}requires a queryqqthat is not provided inπ\\pi, thenVVrejects immediately, since the transcript sent by the prover was not consistent with the execution of𝒜\\mathcal\{A\}\. If the transcript is consistent, then the verifier concludes the protocol by issuing the batch of statistical queries fromπ\\pito its own oracle𝒪V\\mathcal\{O\}\_\{V\}, and checks that𝒪V​\(qi\)\\mathcal\{O\}\_\{V\}\(q\_\{i\}\)is sufficiently close to the reported𝒪P​\(qi\)\\mathcal\{O\}\_\{P\}\(q\_\{i\}\)for each query\.

Note that even though we think of𝒜\\mathcal\{A\}as deterministic since it does not use randomness, its adaptivity to the SQ oracle responses introduces non\-determinism, so verifying the consistency of the transcript is a non\-trivial aspect of the verifier’s check\.

Given the simplicity of this delegation scheme, both the honest prover and verifier can be implemented very efficiently\. The only overhead of the honest prover is to record the results of their statistical queries to be sent to the verifier \(or posted for public verification\), so the sample and time complexities scale precisely with the original complexities of the SQ algorithm𝒜\\mathcal\{A\}\. To answer a sequence of adaptive queries toτ\\tau\-accuracy, the prover can be implemented inO~​\(k/τ2\)\\tilde\{O\}\(\\sqrt\{k\}/\\tau^\{2\}\)samples\[[BNS\+16](https://arxiv.org/html/2607.15528#bib.bib21),[DK22](https://arxiv.org/html/2607.15528#bib.bib25),[BLA25](https://arxiv.org/html/2607.15528#bib.bib26)\]\. The verifier also has to execute the algorithm𝒜\\mathcal\{A\}, so there is no computational savings, but the statistical savings are exponential\. By concentration bounds, checking a batch ofkkstatistical queries toτ\\tau\-accuracy can be achieved fromO​\(log⁡\(k\)/τ2\)O\(\\log\(k\)/\\tau^\{2\}\)samples\.

#### Understanding Universal Soundness\.

One of the key selling points of pvCSVs is the universal soundness condition: that any verifier holding𝒟V\\mathcal\{D\}\_\{V\}which may differ significantly from the prover’s distribution𝒟P\\mathcal\{D\}\_\{P\}can check the certificate while maintaining soundness\. As described above, our pvCSV construction does not explicitly distinguish between the prover’s distribution𝒟P\\mathcal\{D\}\_\{P\}and the verifier’s𝒟V\\mathcal\{D\}\_\{V\}\. But in a sense that can be made formal, to obtain universal soundness, we only need for standard soundness to hold from the verifier’s perspective\. Specifically, even if the pvCSV\(h,π\)\(h,\\pi\)was generated honestly by a proverPPholding𝒟P\\mathcal\{D\}\_\{P\}, to the verifer holding𝒟V\\mathcal\{D\}\_\{V\}, we can imaginePPto be a potential cheating prover\. In this case, the verifier may reject outright, or may accept ifhhactually satisfies the learning goal over𝒟V\\mathcal\{D\}\_\{V\}\. The verifier’s final statistical validation—paired with the correctness guarantee of SQ algorithms—ensures that if the reported query responses fromπ\\piare sufficiently close to the expectations on the verifier’s distribution𝒟V\\mathcal\{D\}\_\{V\}, thenhhis the result of some valid invocation of the SQ algorithm𝒜\\mathcal\{A\}over𝒟V\\mathcal\{D\}\_\{V\}\.

#### Handling Randomness\.

For algorithms that use randomness, we cannot simply trust the prover to report a direct simulation of the execution of𝒜\\mathcal\{A\}, using untrusted randomness\. Instead, a natural idea for a pvCSV is to convert the randomized algorithm into a public\-coin protocol, then apply a Fiat\-Shamir transformation\[[FS86](https://arxiv.org/html/2607.15528#bib.bib35)\], to obtain a non\-interactive proof\. In Section[4](https://arxiv.org/html/2607.15528#S4), we show that this approach works to yield pvCSVs, but we need to be careful in how we reason about the algorithm’s use of randomness, as well as how the SQ oracle affects the proof of soundness\.

Starting from a randomized SQ algorithm𝒜\\mathcal\{A\}, we imagine breaking the algorithm into a series of “epochs” where in theii\-th epoch, the algorithm samples fresh randomnessrir\_\{i\}, and then executes a deterministic SQ algorithm𝒜i\\mathcal\{A\}\_\{i\}until the end of the epoch\. Every randomized algorithm can be broken into epochs, but different algorithms require more or fewer epochs\. At the low extreme, an algorithm that uses a random initialization, then executes deterministically, would have epoch complexity11; at the other extreme, a stochastic optimization algorithm that makes random choices at every iteration based on fresh independent coins will have high epoch complexity\. The epoch complexity of the algorithm𝒜\\mathcal\{A\}controls the complexity of the resulting proof system\.

In particular, we can turn any SQ algorithm of epoch complexityℓ\\ellinto a public\-coin interactive proof in the SQ model of round complexityℓ\\ell\. At the start of each epochii, the verifierVVsends randomnessrir\_\{i\}to the proverPP\. Then, the honest proverPPsimulates the deterministic algorithm𝒜i​\(ri\)\\mathcal\{A\}\_\{i\}\(r\_\{i\}\)using its own oracle𝒪P\\mathcal\{O\}\_\{P\}to answer any statistical queries\. At the end of the epoch, the prover can return a transcript, similar to in the deterministic case, that summarizes the statistical queries and oracle responses\. At the end of all epochs, the verifier can issue a non\-adaptive batch of queries to𝒪V\\mathcal\{O\}\_\{V\}to ensure that the responses were all sufficiently accurate\.

As described, the SQ protocol is complete, but has a subtle issue with soundness without further assumptions\. In the original algorithm,𝒜\\mathcal\{A\}issues its queries to an SQ oracle𝒪\\mathcal\{O\}, whereas in the protocol, the verifierVVsimulates𝒜\\mathcal\{A\}but delegates the SQs to the prover\. The key distinction between these two setups is that the prover also receives the internal randomness of the algorithmrir\_\{i\}, as the public\-coin message at the start of each epoch\. In other words, to ensure soundness, the original randomized algorithm𝒜\\mathcal\{A\}must be correct even for SQ oracles that have full knowledge of the state of𝒜\\mathcal\{A\}\. Algorithms whose correctness hinges on the obliviousness of𝒪\\mathcal\{O\}to the randomness of𝒜\\mathcal\{A\}cannot be delegated in this way while maintaining soundness\. Formally, we define “public\-state” SQ oracles in Section[4\.1](https://arxiv.org/html/2607.15528#S4.SS1), along with the corresponding correctness notion for SQ algorithms\.

Once we restrict our delegation to randomized SQ algorithms which are correct under this more powerful SQ oracle, then we obtain a sound public\-coin protocol\. To obtain pvCSVs, we appeal to the Random Oracle Model \(ROM\), and show how to apply the Fiat\-Shamir transform to our protocol\. There is some subtlety in defining the notion of universal soundness for pvCSVs in the ROM and then subsequently arguing that Fiat\-Shamir applied to our protocol obtains such soundness\. With the appropriate definitions in place, the soundness proof follows by following the state restoration approach of\[[BCS16](https://arxiv.org/html/2607.15528#bib.bib12),[CY24](https://arxiv.org/html/2607.15528#bib.bib51)\]\.

#### Beyond SQ Algorithms\.

Building pvCSVs for randomized SQ algorithms required us to define and investigate a number of more general models of proof systems in the SQ model\. A key result we show in Section[4\.2](https://arxiv.org/html/2607.15528#S4.SS2)is that a diverse class of interactive SQ protocols can be compiled into a canonical public\-coin SQ protocol\. In a sense, this result is an analogue of the established understanding of public\-coin protocols for delegation of computation\. We show that, quite generically, if an SQ protocol consists of a verifier that reveals its randomness to the prover, there is a canonical version of the protocol where the only messages the verifier sends to the prover are its randomness\. Further, the verifier need not maintain any private statistical queries, but can delegate all of its queries to the prover, then execute one final non\-adaptive validation\. This result holds in the same model of public\-state SQ oracle, which may adapt to the state of the verifier\. With this canonical compiler for SQ protocols, we can similarly obtain computationally\-sound pvCSVs in the ROM, by applying Fiat\-Shamir to the canonical protocol\.

#### Towards Computationally\-Efficient Certification of Learning\.

In this work, our focus is on developing statistically\-efficient proofs of learning\. We make no effort to optimize the verifier’s running time\. Our pvCSV verifier for an SQ algorithm𝒜\\mathcal\{A\}runs in time proportional to the running time of𝒜\\mathcal\{A\}\. A natural question in the study of proof systems is whether we can save on computation time during verification\.

In Section[5](https://arxiv.org/html/2607.15528#S5), we show some barrier to generic speed\-ups \(at least within the SQ framework\)\. In particular, Corollary[6](https://arxiv.org/html/2607.15528#Thmresult6)shows that there are statistically learnable VC classes, for which there is no computationally\-efficient SQ verification scheme, even if we allow for interaction\. Our SQ lower bound is actually a consequence of the*efficiency*of our verification schemes \(in terms of the number of statistical queries\) and an existing lower bound on the samples required for verification from\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]in terms of the VC dimension\. In other words, a fast SQ verification scheme \(which doesn’t make many SQ queries\) would imply an impossibly\-statistically\-efficient verification scheme for the VC class studied by\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]\.

Nevertheless, in some sense, our exploration of pvCSVs and SQ protocols provides new design principles for simultaneously statistically and computationally efficient verification\. Recall that the canonical protocol of Lemma[4](https://arxiv.org/html/2607.15528#Thmresult4), which compiles into a pvCSV as in Theorem[3](https://arxiv.org/html/2607.15528#Thmresult3), applies not just to randomized algorithms but to a broad class of SQ protocols\. Further, the verifier in the resulting pvCSV runs in time proportional to \(or less than\) the verifier in the original protocol—not the full simulation of\(P,V\)\(P,V\)\. In other words, if we can design SQ protocols that reduce verification time, then we may get simultaneous statistical and computational efficiency for free \(provided the protocol is covered by Lemma[4](https://arxiv.org/html/2607.15528#Thmresult4)\)\.

Concretely, our results show that minimizing the epoch complexity of a learning procedure—even if that entails designing an interactive proof system—may actually lead to more efficient pvCSVs than simply focusing on delegating algorithms for learning\. Such observations may also motivate a deeper study of pseudorandomness in machine learning; for instance, if a randomized SQ algorithm can actually be proved correct under a weaker source of randomness, it may reduce the epoch complexity and improve efficiency\.

#### Publicly\-Verifiable End\-to\-End DP\.

Finally, in Section[6](https://arxiv.org/html/2607.15528#S6), we show Proposition[7](https://arxiv.org/html/2607.15528#Thmresult7), which implies a mechanism for verifying pvCSVs statistically efficiently under Differential Privacy with respect to the verifier’s samples\. Given such a verifier, it’s tempting to wonder whether we can achieve End\-to\-End DP over both the prover’s samples from𝒟P\\mathcal\{D\}\_\{P\}and the verifier’s from𝒟V\\mathcal\{D\}\_\{V\}\. The existence of a DP verifier implies an honest prover strategy to achieve such a goal\. Due to the connections between adaptive data analysis and DP, this honest prover strategy is no more expensive than accounting for adaptivity\.

That said, in our setting, we’d have no guarantees about the behavior of the cheating prover, who might violate DP arbitrarily\. To handle the possibility of a cheating prover, we could employ a scheme for Certified DP of\[[BGK\+24](https://arxiv.org/html/2607.15528#bib.bib16)\]\. Certified DP ensures that a prover’s release of statistical queries follows a DP mechanism with respect to some committed\-to, but untrusted databaseX∼𝒟PX\\sim\\mathcal\{D\}\_\{P\}, in a manner that can be verified publicly\. In this sense, adding our DP statistical validation scheme as post\-processing to the output of a Certified DP mechanism would allow the verifier to be convinced of End\-to\-End DP, while also ensuring statistical accuracy of queries from the untrusted databaseXXunder the verifier’s distribution𝒟V\\mathcal\{D\}\_\{V\}\.

### 1\.3Related Works

Our study of pvCSVs and SQ protocols lives in the intersection of learning theory and cryptographic proof systems\. We highlight some of the most relevant related lines of work\.

#### Proof Systems for Learning and Statistics\.

Proof systems for statistical algorithms grew out of the literature on interactive \(cryptographic\) proof systems\[[GMR85](https://arxiv.org/html/2607.15528#bib.bib1),[BAB85](https://arxiv.org/html/2607.15528#bib.bib34)\]\. The PAC Verification, introduced in\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41)\], led to a number of results about strengths and limitations of interactive proofs of learning\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42),[GJK\+24](https://arxiv.org/html/2607.15528#bib.bib44)\]\. Most related to our work is the work of Mutreja and Shafer\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\], who also thought about the issue of delegating SQ algorithms in the context of loss minimization\. In fact, in a subsequent journal version\[[MS26](https://arxiv.org/html/2607.15528#bib.bib43)\], the authors independently include a result analogous to Proposition[5](https://arxiv.org/html/2607.15528#Thmresult5), on the interactive delegation of adaptive SQ algorithms\.

Other works have investigated certifying properties of learning algorithms\.\[[BGK\+24](https://arxiv.org/html/2607.15528#bib.bib16)\]recently designed mechanisms for public cerification of differential privacy \(and other private probabilistic mechanisms\) in the release of statistical queries\. Following this work,\[[BTF\+25](https://arxiv.org/html/2607.15528#bib.bib29)\]extended the techniques to give a publicly\-verifiable implementation of DP Stochastic Gradient Descent, without appealing to heavy\-handed cryptographic primitives for certifying generic computations\.

Beyond proofs for learning algorithms, there has been significant work investigating proof systems for properties of distributions\. Initiated by\[[CG18](https://arxiv.org/html/2607.15528#bib.bib49)\], a sequence of works\[[HR22](https://arxiv.org/html/2607.15528#bib.bib48),[HR23](https://arxiv.org/html/2607.15528#bib.bib47),[HR24b](https://arxiv.org/html/2607.15528#bib.bib46),[HR24a](https://arxiv.org/html/2607.15528#bib.bib45)\]has established doubly\-efficient proof systems for distribution testing\.

#### Adaptive Data Analysis\.

Since its identification as a key algorithmic challenge\[[DFH\+15c](https://arxiv.org/html/2607.15528#bib.bib19),[DFH\+15a](https://arxiv.org/html/2607.15528#bib.bib18),[DFH\+15b](https://arxiv.org/html/2607.15528#bib.bib17)\], Adaptive Data Analysis has seen significant developments, in line with the developments of sophisticated tools for Differential Privacy\[[DMN\+06](https://arxiv.org/html/2607.15528#bib.bib9)\]\. The majority of work studying adaptive data analysis focuses on the problem of answering statistical queries\.\[[BNS\+16](https://arxiv.org/html/2607.15528#bib.bib21)\]first showed near\-optimalO~​\(k\)\\tilde\{O\}\(\\sqrt\{k\}\)dependence on the number of adaptively chosen queries\. Subsequently, a sequence of papers has simplified their analysis and techniques and improved their bounds\[[FS18](https://arxiv.org/html/2607.15528#bib.bib24),[JLN\+19](https://arxiv.org/html/2607.15528#bib.bib22),[DK22](https://arxiv.org/html/2607.15528#bib.bib25)\]\. Recently,\[[BLA25](https://arxiv.org/html/2607.15528#bib.bib26)\]showed that a much simpler subsampling mechanism actually suffices for optimal adaptive data analysis—despite the fact that it does not suffice for DP\. Indeed, the analysis of\[[BLA25](https://arxiv.org/html/2607.15528#bib.bib26)\]does not go through the standard “transfer theorem” that DP implies adaptive generalization, but rather analyzes the effects of subsampling directly\.

## 2Preliminaries

We give formal definitions of the statistical query model of learning\[[KEA98](https://arxiv.org/html/2607.15528#bib.bib40)\]that we adopt, as well as proof systems developed in the context of verifying machine learning\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41),[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]\. We start with background on the SQ Model\. Then, we discuss our formalisms for algorithms and proof systems that use SQ oracles\. We defer some technical aspects of our learning model \(particularly those related to algorithms’ use of randomness\) to the relevant technical section \(Section[4\.1](https://arxiv.org/html/2607.15528#S4.SS1)\)\. Finally, we review background on adaptive data analysis and the complexity of implementing SQ algorithms from samples\[[DFH\+15a](https://arxiv.org/html/2607.15528#bib.bib18)\]\.

### 2\.1The Statistical Query Model

The Statistical Query \(SQ\) Model\[[KEA98](https://arxiv.org/html/2607.15528#bib.bib40)\]abstracts away the notion of learning from samples to the notion of learning from approximate statistics\. In this model, the learning algorithm is allowed to specify predicatesq:𝒳→\{0,1\}q:\\mathcal\{X\}\\to\\\{0,1\\\}from a collection444In our work, we take𝒬=\{0,1\}𝒳\\mathcal\{Q\}=\\\{0,1\\\}^\{\\mathcal\{X\}\}to be the set of all boolean functions, so often drop explicit reference to𝒬\\mathcal\{Q\}\. In this work, we will not consider the computational complexity of evaluating functionsq∈Qq\\in Q, and instead, measure the complexity of learning in terms of the total number/sequence of queries issued\.𝒬⊆\{0,1\}𝒳\\mathcal\{Q\}\\subseteq\\\{0,1\\\}^\{\\mathcal\{X\}\}and receive—from the*statistical query oracle*—the \(rough\) expectation of the queried predicate on the distribution of interest𝒟\\mathcal\{D\}\.

###### Definition 2\.1\(SQ Oracle, idealized\)\.

AStatistical Query \(SQ\) Oracleis a stateful algorithm𝒪:𝒬→\[0,1\]\\mathcal\{O\}:\\mathcal\{Q\}\\to\[0,1\]that takes input queriesq∈𝒬q\\in\\mathcal\{Q\}and responds with evaluations𝒪​\(q\)∈\[0,1\]\\mathcal\{O\}\(q\)\\in\[0,1\]\. Forτ\>0\\tau\>0, the oracle𝒪\\mathcal\{O\}isτ\\tau\-accurate over𝒟\\mathcal\{D\}if for any finite sequence ofk∈ℕk\\in\\mathbb\{N\}\(adaptively\-selected\) queriesq1,q2,…,qkq\_\{1\},q\_\{2\},\\ldots,q\_\{k\}, for alli∈\[k\]i\\in\[k\]

\|𝒪​\(qi\)−EX∼𝒟⁡\[qi​\(X\)\]\|≤τ\.\\displaystyle\\left\|\\mathcal\{O\}\(q\_\{i\}\)\-\\operatorname\*\{\\textnormal\{\\bf E\}\}\_\{X\\sim\\mathcal\{D\}\}\[q\_\{i\}\(X\)\]\\right\|\\leq\\tau\.

Many notable learning algorithms can be described in the SQ Model, including most \(Agnostic\) PAC Learning algorithms555Learning Parities is the most notable example of a task that is PAC learnable, but not SQ learnable\.\[[KEA98](https://arxiv.org/html/2607.15528#bib.bib40)\]as well as more modern ML algorithms like Gradient Descent\.

We remark that, per the definition, the SQ oracle𝒪\\mathcal\{O\}withτ\\tau\-accuracy must always report approximate expectations withinτ\\tauof the true expectation\. As such, given access to an SQ oracle, we can hope to design algorithms that always succeed\. In Section[2\.3](https://arxiv.org/html/2607.15528#S2.SS3), we discuss concrete, sample\-based implementations of the SQ oracle abstraction, which necessarily introduce a failure probability\.

#### Learning Goal\.

We consider an abstract setting of learning over distributions𝒟\\mathcal\{D\}supported on a domain𝒳\\mathcal\{X\}, such as𝒳=\{0,1\}d\\mathcal\{X\}=\\\{0,1\\\}^\{d\}for some finite dimensiond∈ℕd\\in\\mathbb\{N\}\. Additionally, we consider an abstract collection of hypothesesℋ\\mathcal\{H\}\. We define the goal of learning in terms of identifying a hypothesis within some “good” set of hypotheses𝒢​\(𝒟\)⊆ℋ\\mathcal\{G\}\(\\mathcal\{D\}\)\\subseteq\\mathcal\{H\}, parameterized by the distribution𝒟\\mathcal\{D\}\.

###### Definition 2\.2\(Learning goal, abstract\)\.

Fix a class of hypothesesℋ\\mathcal\{H\}and a learning goal𝒢⊆ℋ\\mathcal\{G\}\\subseteq\\mathcal\{H\}\. For a distribution𝒟\\mathcal\{D\}, we say an algorithm𝒜\\mathcal\{A\}learns𝒢\\mathcal\{G\}if𝒜\\mathcal\{A\}outputs someg∈𝒢​\(𝒟\)g\\in\\mathcal\{G\}\(\\mathcal\{D\}\)in the target set of hypotheses\.

For instance, in the context of Agnostic PAC learning, we can takeℋ\\mathcal\{H\}to be the concept classℋ⊆\{h:\{0,1\}d→\{0,1\}\}\\mathcal\{H\}\\subseteq\\\{h:\\\{0,1\\\}^\{d\}\\to\\\{0,1\\\}\\\}, and the good subset𝒢​\(𝒟\)⊆ℋ\\mathcal\{G\}\(\\mathcal\{D\}\)\\subseteq\\mathcal\{H\}to be all hypotheses achieving classification errorPr⁡\[g​\(x\)≠y\]≤Pr⁡\[h∗​\(x\)≠y\]\+ε\\operatorname\*\{\\textnormal\{\\bf Pr\}\}\[g\(x\)\\neq y\]\\leq\\operatorname\*\{\\textnormal\{\\bf Pr\}\}\[h^\{\*\}\(x\)\\neq y\]\+\\varepsiloncompetitive with the besth∗∈ℋh^\{\*\}\\in\\mathcal\{H\}over𝒟\\mathcal\{D\}\. We adopt this abstract notion of learning, rather than a concrete notion like the PAC framework, in order to emphasize the generality of our approach\. At the extreme, we may take the hypothesesℋ\\mathcal\{H\}to be the collection of sequences of statistical queries and expectations, and the good set𝒢​\(𝒟\)\\mathcal\{G\}\(\\mathcal\{D\}\)to be sequences that arise as a valid execution of a statistical algorithm on𝒟\\mathcal\{D\}\. \(We comment further on our choice of abstract Learning Goal after Definition[2\.7](https://arxiv.org/html/2607.15528#S2.Thmtheorem7)of protocols for delegating SQ learning\.\)

#### Statistical Query Algorithms\.

Naturally, we define SQ algorithms as algorithms that may make calls to an SQ oracle\. For SQ algorithms that solve a learning goal, we need to specify the approximation parameterτ\>0\\tau\>0necessary to guarantee correctness\. Formally, we distinguish between deterministic and randomized SQ algorithms\.

###### Definition 2\.3\(SQ Learning, deterministic\)\.

Fix a learning goal𝒢\\mathcal\{G\}andτ\>0\\tau\>0\. A deterministic algorithm𝒜\\mathcal\{A\}τ\\tau\-SQ learns𝒢\\mathcal\{G\}if, for any distribution𝒟\\mathcal\{D\}andτ\\tau\-accurate SQ oracle𝒪\\mathcal\{O\}for𝒟\\mathcal\{D\},𝒜𝒪\\mathcal\{A\}^\{\\mathcal\{O\}\}outputs a hypothesisg∈𝒢​\(𝒟\)g\\in\\mathcal\{G\}\(\\mathcal\{D\}\)\.

When𝒜\\mathcal\{A\}is deterministic, without loss of generality, we can think of the SQ oracle𝒪\\mathcal\{O\}as a pre\-specified function where𝒪​\(q\)\\mathcal\{O\}\(q\)is defined for allq∈𝒬q\\in\\mathcal\{Q\}up front, rather than a stateful algorithm responding sequentially\. Specifically, if the queries that𝒜\\mathcal\{A\}issues are a deterministic function of the input to𝒜\\mathcal\{A\}and the responses given by𝒪\\mathcal\{O\}so far, then a pre\-specified function can simulate any stateful oracle, by simply running𝒜\\mathcal\{A\}ahead of time\. Note the output of running𝒜\\mathcal\{A\}withτ\\tau\-accurate oracle𝒪\\mathcal\{O\}may still be nondeterministic based on the choice of𝒪\\mathcal\{O\}, even if𝒜\\mathcal\{A\}doesn’t flip coins\. That said, we insist that given aτ\\tau\-accurate \(idealized\) oracle𝒪\\mathcal\{O\}, the algorithm𝒜\\mathcal\{A\}always succeeds\.

#### Randomized SQ Algorithms\.

In our study of SQ proof systems, the distinction between deterministic and randomized algorithms is significant\. In contrast to deterministic algorithms, when𝒜\\mathcal\{A\}is randomized, it becomes important to think of the SQ oracle𝒪\\mathcal\{O\}as a stateful adversary, who responds with knowledge of prior queries/responses, subject toτ\\tau\-accuracy\. That is, for a sequence of queriesq1,q2,…,qkq\_\{1\},q\_\{2\},\\ldots,q\_\{k\}, the responseai=𝒪​\(qi\)a\_\{i\}=\\mathcal\{O\}\(q\_\{i\}\)may depend on⟨q1,a1,q2,a2,…,qi−1,ai−1,qi⟩\\langle q\_\{1\},a\_\{1\},q\_\{2\},a\_\{2\},\\ldots,q\_\{i\-1\},a\_\{i\-1\},q\_\{i\}\\rangle\. An SQ algorithm that learns𝒢\\mathcal\{G\}must output a good hypothesis with high probability, no matter what decisions the oracle makes in response to the sequence of queries\.

###### Definition 2\.4\(SQ Learning, randomized\)\.

Fix a learning goal𝒢\\mathcal\{G\}andτ\>0\\tau\>0,γ\>0\\gamma\>0\. A randomized algorithm𝒜\\mathcal\{A\}\(τ,γ\)\(\\tau,\\gamma\)\-SQ learns𝒢\\mathcal\{G\}if for any distribution𝒟\\mathcal\{D\}, and anyτ\\tau\-accurate SQ oracle𝒪\\mathcal\{O\}for𝒟\\mathcal\{D\},𝒜𝒪\\mathcal\{A\}^\{\\mathcal\{O\}\}outputs a hypothesisg∈𝒢​\(𝒟\)g\\in\\mathcal\{G\}\(\\mathcal\{D\}\)with probability at least1−γ1\-\\gammaover the random coins of𝒜\\mathcal\{A\}\.

With this high\-level definition in place, we defer significant details and definitions about randomized SQ algorithms to Section[4\.1](https://arxiv.org/html/2607.15528#S4.SS1), which are essential to understanding our pvCSVs for randomized SQ algorithms and SQ protocols\. In particular, we consider two flavors of SQ oracles for randomized algorithms, “oblivious” oracles \(as in Definition[2\.1](https://arxiv.org/html/2607.15528#S2.Thmtheorem1)\) and “public\-state” oracles \(see Definition[4\.3](https://arxiv.org/html/2607.15528#S4.Thmtheorem3)\)\.

#### Complexity Measures for SQ algorithms\.

An important complexity measure of SQ algorithms is the number of statistical queries the algorithm makesBB, as well as the*adaptivity*to prior query responseskk\. The adaptivity of an SQ algorithm𝒜\\mathcal\{A\}is the number of rounds in which batches of queries are issued to𝒪\\mathcal\{O\}\. At the extremes of adaptivity,k=Bk=Bis a fully\-adaptive algorithm, where the choice of each queryqiq\_\{i\}is determined as an arbitrary function of the prior queries and responses⟨q1,𝒪​\(q1\),q2,𝒪​\(q2\),…,qi−1,𝒪​\(qi−1\)⟩\\langle q\_\{1\},\\mathcal\{O\}\(q\_\{1\}\),q\_\{2\},\\mathcal\{O\}\(q\_\{2\}\),\\ldots,q\_\{i\-1\},\\mathcal\{O\}\(q\_\{i\-1\}\)\\rangle; whereask=1k=1is a*non\-adaptive*SQ algorithm and all of the queries are issued in a single batch\. As we discuss in Section[2\.3](https://arxiv.org/html/2607.15528#S2.SS3), the adaptive query complexity determines how efficiently we can implement the SQ oracle from samples\.

###### Definition 2\.5\(Query Complexity\)\.

Fixτ\>0\\tau\>0\. An SQ algorithm hasτ\\tau\-query complexity\(k,B\)\(k,B\)if for all distributions𝒟\\mathcal\{D\}andτ\\tau\-accurate SQ oracles𝒪\\mathcal\{O\}, the execution of𝒜𝒪\\mathcal\{A\}^\{\\mathcal\{O\}\}issues at mostBBqueries overkkrounds of adaptivity\.

Additionally, we will informally track the running time of SQ algorithms \(eliding details of computation over real\-valued responses from the SQ oracle\)\.

###### Definition 2\.6\(Running Time\)\.

Fixτ\>0\\tau\>0\. An SQ algorithm hasrunning timeT​\(τ\)T\(\\tau\)if over all𝒟\\mathcal\{D\}and allτ\\tau\-accurate SQ oracles𝒪\\mathcal\{O\}, the execution of𝒜𝒪\\mathcal\{A\}^\{\\mathcal\{O\}\}runs in at mostT​\(τ\)T\(\\tau\)steps\.

For simplicity’s sake, in both query and time complexity, we assume that randomized SQ algoirthms provide a deterministic guarantee on the complexity \(that is, a BPP\-style guarantee\)\.

### 2\.2Proof Systems for Statistical Learning

We consider proof systems for statistical learning based off of the classic notions from complexity theory and cryptography\[[GMR85](https://arxiv.org/html/2607.15528#bib.bib1),[BAB85](https://arxiv.org/html/2607.15528#bib.bib34)\], and more recently the notion of PAC Verification\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41)\]\. In this setting, a proverPPand a verifierVVinteract in order for the verifier to be convinced that a given hypothesisg∈𝒢​\(𝒟\)g\\in\\mathcal\{G\}\(\\mathcal\{D\}\)is good for a learning goal\. We modelPPandVVas randomized algorithms and denote their interaction as\(P,V\)\(P,V\)\. We adapt the notions from recent works on PAC Verification to define a model of interactive proof system where the parties have access to SQ oracles as follows\.

###### Definition 2\.7\(SQ Protocol, adapted from\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41),[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]\)\.

AStatistical Query protocolis given by the interaction of two randomized SQ algorithms, the honest proverPPand the verifierVV, denoted\(P,V\)\(P,V\)\.

Fix a learning goal𝒢\\mathcal\{G\},τP,τV\>0\\tau\_\{P\},\\tau\_\{V\}\>0, andγ\>0\\gamma\>0\. An SQ protocol\(P,V\)\(P,V\)\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-SQ\-verifies𝒢\\mathcal\{G\}if for any distribution𝒟\\mathcal\{D\}andτP\\tau\_\{P\}\-accurate SQ oracle𝒪P\\mathcal\{O\}\_\{P\}andτV\\tau\_\{V\}\-accurate SQ oracle𝒪V\\mathcal\{O\}\_\{V\}, the following conditions hold:

- •Completeness: the honest protocol\(P𝒪P,V𝒪V\)\(P^\{\\mathcal\{O\}\_\{P\}\},V^\{\\mathcal\{O\}\_\{V\}\}\)outputsg∈𝒢​\(𝒟\)g\\in\\mathcal\{G\}\(\\mathcal\{D\}\)with probability at least1−γ1\-\\gammaover the random coins ofPPandVV\.
- •Soundness: for any cheating prover strategyP~\\tilde\{P\}, with probability at least1−γ1\-\\gammaover the random coins ofVV, the protocol\(P~𝒪V,V𝒪V\)\(\\tilde\{P\}^\{\\mathcal\{O\}\_\{V\}\},V^\{\\mathcal\{O\}\_\{V\}\}\)outputsg∈𝒢​\(𝒟\)g\\in\\mathcal\{G\}\(\\mathcal\{D\}\)orVVrejects\.

Forfailure probabilityδ\\delta\>0\>0, the SQ protocol hassample complexity\(mP,mV\)\(m\_\{P\},m\_\{V\}\)if the honest prover’s oracle𝒪P\\mathcal\{O\}\_\{P\}can be implemented from at mostmPm\_\{P\}samples and the verifier’s oracle𝒪V\\mathcal\{O\}\_\{V\}can be implemented from at mostmVm\_\{V\}samples, with probability at least1−δ1\-\\deltaover i\.i\.d\. samples from𝒟\\mathcal\{D\}\.

In other words, in an SQ protocol, there exists an honest prover strategy that allows the verifier to accept a good hypothesisg∈𝒢​\(𝒟\)g\\in\\mathcal\{G\}\(\\mathcal\{D\}\)with high probability, and conversely, if the verifier accepts a hypothesisg~\\tilde\{g\}, then with high probability,666For simplicity, we use a single parameterγ\\gammafor the completeness and soundness error\. Of course, it may also be interesting to consider protocols that achieve different completeness and soundness parameters\. In fact, all of our protocols achieve completeness11in the SQ oracle model\.the hypothesisg~∈𝒢​\(𝒟\)\\tilde\{g\}\\in\\mathcal\{G\}\(\\mathcal\{D\}\), even if it was generated through an interaction with a different prover\.

Note that, as is standard, we imagine the cheating proverP~\\tilde\{P\}is all\-powerful and may have arbitrary knowledge of the distribution𝒟\\mathcal\{D\}\. Additionally, we equip the cheating prover*with the verifier’s oracle*𝒪V\\mathcal\{O\}\_\{V\}; that is, for any query that the verifier asksq∈𝒬q\\in\\mathcal\{Q\}, the precise valuea=𝒪V​\(q\)a=\\mathcal\{O\}\_\{V\}\(q\)is known to bothVVandP~\\tilde\{P\}\. \(That said, the verifier may choose to keep queries private from the prover\.\)

There are many properties of SQ protocols that may be of interest\. For instance, we consider both private\- and public\-coin protocols \(or, as hinted above,*private\-*and*public\-query*protocols\)\. We defer these definitions—particularly those related to our construction of pvCSVs—to Section[4\.1](https://arxiv.org/html/2607.15528#S4.SS1)\.

Implementing the oracles from samples will necessarily incur some additional failure probabilityδ\>0\\delta\>0, distinguished from soundness errorγ\\gammaof the original protocol\. Accounting for the failure probabilityγ\\gammaof the oracle\-based protocol separately from the failure probabilityδ\\deltathat arises from sampling actually leads to improved analysis of the soundness of some of our protocols\. We discuss background on the sample complexity of adaptive SQ algorithms in Section[2\.3](https://arxiv.org/html/2607.15528#S2.SS3)\.

#### Comparison to PAC Verification\.

Definition[2\.7](https://arxiv.org/html/2607.15528#S2.Thmtheorem7)is directly inspired by the notion of PAC Verification of statistical algorithms\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41),[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\], but departs in a few key ways\.

First off, our notion of learning is not tied directly to Agnostic PAC learning \(or loss minimization as in\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]\)\. Instead, we elect to use our abstract learning goal \(Definition[2\.2](https://arxiv.org/html/2607.15528#S2.Thmtheorem2)\) as the basis for SQ Protocols\. We make this choice because the protocols we design are not actually tied to any properties of loss minimization, but instead run a direct simulation of a given SQ algorithm\. So, provided we start with a learning algorithm𝒜\\mathcal\{A\}that achieves its learning goal with good probability, we can turn it into a SQ protocol that also learns𝒢\\mathcal\{G\}\.777One may even be inclined to define delegation of learning as a distributional simulation of a given algorithm𝒜\\mathcal\{A\}\. In fact, once formalized, many of our protocols would satisfy such a notion, but we encounter issues with soundness when we want to achieve non\-interactive protocols \(i\.e\., pvCSVs\) for randomized SQ algorithms in Section[4](https://arxiv.org/html/2607.15528#S4)\.

Second, we define SQ protocols in the SQ oracle model, rather than in terms of direct samples from the distribution\. In reality, we will be interested in understanding the statistical resources \(i\.e\., samples\) necessary to implement the verifier and honest prover strategies\. As in the earlier works on PAC verification, the goal is to design SQ protocols where the verifier’s oracle𝒪V\\mathcal\{O\}\_\{V\}can be implemented more efficiently than the honest prover’s𝒪P\\mathcal\{O\}\_\{P\}\. For instance, quantitatively, perhapsPPrequies an oracle with much tighter tolerance thanVV,τP<τV\\tau\_\{P\}<\\tau\_\{V\}; or as in our work, qualitatively,PPmay require an adaptive oracle, whereasVVuses a non\-adaptive oracle\. That said, nothing precludes a hybrid definition, where the verifier only has SQ oracle\-access to𝒟\\mathcal\{D\}, but the prover has more refined access through samples or point evaluations\.\.

#### Computational Soundness and The Random Oracle Model\.

Definition[2\.7](https://arxiv.org/html/2607.15528#S2.Thmtheorem7)assumes that cheating provers are computationally\-unbounded\. We refer to this property as*statistical soundness*\. In contrast, we say that*computational soundness*holds when we prove soundness against probabilistic polynomial\-time cheating proversP~\\tilde\{P\}\. When we consider computational soundness, we will still assume thatP~\\tilde\{P\}may hold prior, detailed knowledge of𝒟\\mathcal\{D\}\(so need not be given an SQ oracle\), but does not have the computational resources to break cryptographic primitives\.

We will be particularly interested in computational soundness when designing pvCSVs for randomized SQ algorithms\. To do so, we leverage a key cryptographic paradigm: The Fiat\-Shamir Transformation\[[FS86](https://arxiv.org/html/2607.15528#bib.bib35)\]\. The heuristic takes a public\-coin interactive protocol and removes interaction by emulating the verifier’s random messages with calls to a cryptographic hash function\. Classically, the soundness of Fiat\-Shamir is proved in the Random Oracle Model \(ROM\)\[[BR93](https://arxiv.org/html/2607.15528#bib.bib36)\], which models public access to an \(idealized\) hash function\.

###### Definition 2\.8\(Random Oracle Model\)\.

For output sizem∈ℕm\\in\\mathbb\{N\}, theRandom Oracle Modelaugments the base computational model by assuming that all parties have access to a public, uniformly\-random functionf:\{0,1\}∗→\{0,1\}mf:\\\{0,1\\\}^\{\*\}\\to\\\{0,1\\\}^\{m\}that can be evaluated at unit cost\.

Note that when we consider protocols that operate in the ROM, the probability of violating computational soundness is over the verifier’s random coins as well as the draw of the random oracle\.

While, in full generality, soundness does not transfer from the ROM to realizable models of computation\[[BAR01](https://arxiv.org/html/2607.15528#bib.bib37),[GK03](https://arxiv.org/html/2607.15528#bib.bib38)\], proofs of soundness in the ROM are generally considered as strong evidence of security and sufficient for many practical applications\. Our pvCSVs for randomized SQ algorithms will be proved computationally\-sound in the ROM\.

### 2\.3Sample\-Based Implementation of SQ Oracles

To run SQ learning algorithms/protocols, we need a concrete implementation of the SQ oracle abstraction based on samples drawn from𝒟\\mathcal\{D\}\. The number of samples required to guarantee statistical validity of the oracle’s responses depends on features of the SQ algorithm𝒜\\mathcal\{A\}\.

In particular, the sample complexity depends on the number of queries issuedBB, the desired accuracyτ\\tau, as well as the*adaptivity*kk\. The adaptivity of an SQ algorithm𝒜\\mathcal\{A\}is the number of rounds in which batches of queries are issued to𝒪\\mathcal\{O\}\. At the extremes of adaptivity,k=Bk=Bis a completely adaptive algorithm, where the choice of each queryqiq\_\{i\}is determined as an arbitrary function of the prior queries and responses⟨q1,𝒪​\(q1\),q2,𝒪​\(q2\),…,qi−1,𝒪​\(qi−1\)⟩\\langle q\_\{1\},\\mathcal\{O\}\(q\_\{1\}\),q\_\{2\},\\mathcal\{O\}\(q\_\{2\}\),\\ldots,q\_\{i\-1\},\\mathcal\{O\}\(q\_\{i\-1\}\)\\rangle; whereask=1k=1is a*non\-adaptive*SQ algorithm and all of the queries are issued in a single batch\. The following definition captures these dependencies\.

###### Definition 2\.9\(SQ Oracle implementation\)\.

An algorithm𝒪\\mathcal\{O\}is a\(k,B,τ,δ\)\(k,B,\\tau,\\delta\)\-implementation of an SQ oracle for a distribution𝒟\\mathcal\{D\}, if𝒪\\mathcal\{O\}can support any sequence of queriesq1,q2,…,qBq\_\{1\},q\_\{2\},\\ldots,q\_\{B\}satisfying the following properties:

- •Rounds of adaptivitykk: the sequence of queries is issued in at mostkkbatches; queries selected in theiith batch may depend arbitrarily on the queries and responses of the firsti−1i\-1batches
- •Query budgetBB: the total number of queries in the sequence is upper bounded byBB
- •Accuracyτ\\tau: for every queryqqin the sequence, the response𝒪​\(q\)\\mathcal\{O\}\(q\)isτ\\tau\-accurate on𝒟\\mathcal\{D\}\.
- •Failure probabilityδ\\delta: for all such query sequences of complexity\(k,B\)\(k,B\), with probability at least1−δ1\-\\delta, all queries are answeredτ\\tau\-accurately\.

Thesample complexityof an SQ oracle implementation is the numberm∈ℕm\\in\\mathbb\{N\}of i\.i\.d\. samples from𝒟\\mathcal\{D\}required to guarantee\(k,B,τ,δ\)\(k,B,\\tau,\\delta\)\-implementation\.

We define the notion of an SQ Oracle implementation in terms of the rounds of adaptivity and the total number of queries, because certain mechanisms are able to exploit limited adaptivity to achieve better sample complexity\[[HR10](https://arxiv.org/html/2607.15528#bib.bib28),[DFH\+15b](https://arxiv.org/html/2607.15528#bib.bib17)\]\. Note that, in order to guaranteeτ\\tau\-accurate queries, we can assume that our implementation returns values usingO​\(log⁡\(1/τ\)\)O\(\\log\(1/\\tau\)\)bits of precision\.

Crucially for our work, the sample complexity required to answer a non\-adaptive batch of queries is an exponential improvement over the complexity required to answer an adaptively\-selected sequence of queries\. For a non\-adaptive batch of queries, the empirical SQ oracle that takesmmsamplesx1,…,xm∼𝒟x\_\{1\},\\ldots,x\_\{m\}\\sim\\mathcal\{D\}and reports𝒪​\(q\)=1m​∑i=1mq​\(xi\)\\mathcal\{O\}\(q\)=\\frac\{1\}\{m\}\\sum\_\{i=1\}^\{m\}q\(x\_\{i\}\)achieves logarithmic dependence on the number of queries\.

###### Proposition 2\.10\(Non\-adaptive Sample Complexity\)\.

For anyτ,δ\>0\\tau,\\delta\>0, the empirical oracle is a\(1,B,τ,δ\)\(1,B,\\tau,\\delta\)\-implementation of an SQ oracle for𝒟\\mathcal\{D\}with sample complexity

m≤O​\(log⁡\(B/δ\)τ2\)\.m\\leq O\\left\(\\frac\{\\log\(B/\\delta\)\}\{\\tau^\{2\}\}\\right\)\.

Proposition[2\.10](https://arxiv.org/html/2607.15528#S2.Thmtheorem10)follows by a standard application of Hoeffding’s inequality\. The sample complexity for answering an adaptively\-selected sequence of statistical queries, however, requires much more sophisticated analysis\. The complexity was only established in the past decade, after connecting the problem of adaptive data analysis with the technique of Differential Privacy\[[DMN\+06](https://arxiv.org/html/2607.15528#bib.bib9)\]\.

In the case of fully\-adaptive algorithms, wherek=Bk=Bstatistical queries are issued adaptively, the \(roughly\) optimal sample complexity scales withk\\sqrt\{k\}, rather thanlog⁡\(k\)\\log\(k\)\. Initially, the upper bounds followed by leveraging the stability properties of differentially\-private query release\[[BNS\+16](https://arxiv.org/html/2607.15528#bib.bib21),[DK22](https://arxiv.org/html/2607.15528#bib.bib25)\], but the most recent result of\[[BLA25](https://arxiv.org/html/2607.15528#bib.bib26)\]leverages a subsampling technique without DP\.888Note that the bounds achieved by\[[DK22](https://arxiv.org/html/2607.15528#bib.bib25)\]and\[[BLA25](https://arxiv.org/html/2607.15528#bib.bib26)\]are technically incomparable, but differ only in poly\-logarithmic factors inkkandτ\\tau\. Either mechanism could be used to implement our honest prover’s SQ oracle\.

###### Proposition 2\.11\(Theorem 3 of\[[BLA25](https://arxiv.org/html/2607.15528#bib.bib26)\], Adaptive Sample Complexity Upper Bound\)\.

For anyτ,δ\>0\\tau,\\delta\>0, there exists a mechanism that is a\(k,k,τ,δ\)\(k,k,\\tau,\\delta\)\-implementation of an SQ oracle for𝒟\\mathcal\{D\}with sample complexity

m≤O​\(k⋅log⁡\(k/δ\)⋅log⁡\(1/δ\)τ2\)\\displaystyle m\\leq O\\left\(\\frac\{\\sqrt\{k\\cdot\\log\(k/\\delta\)\\cdot\\log\(1/\\delta\)\}\}\{\\tau^\{2\}\}\\right\)

The lower bound holds based on the construction of \(interactive\) fingerprinting codes\[[HU14](https://arxiv.org/html/2607.15528#bib.bib23),[SU15](https://arxiv.org/html/2607.15528#bib.bib20)\], and holds unconditionally in large\-domain settings and assuming the existence of one\-way functions in all settings\.

###### Proposition 2\.12\(Theorems 1 & 2 of\[[SU15](https://arxiv.org/html/2607.15528#bib.bib20)\], Adaptive Sample Complexity Lower Bound\)\.

For anyτ∈\(0,0\.49\)\\tau\\in\(0,0\.49\), any mechanism which is a\(k,k,τ,1/2\)\(k,k,\\tau,1/2\)\-implementation of an SQ oracle for𝒟\\mathcal\{D\}has sample complexity

m≥Ω​\(k\)m\\geq\\Omega\(\\sqrt\{k\}\)if either of the following assumptions hold: one\-way functions exist, and the mechanism is computationally bounded; or the space of samples𝒳\\mathcal\{X\}is sufficiently large:\|𝒳\|≥2O​\(k\)\|\\mathcal\{X\}\|\\geq 2^\{O\(k\)\}\.

In other words, there is a*provable*exponential gap in the sample complexity required to answerkkqueries adaptively versus non\-adaptively\.

## 3Publicly\-Verifiable Certificates of Statistical Validity

In this section, we introduce the main conceptual contribution of this work—*publicly\-verifiable Certificates of Statistical Validity*—which allows a prover to publish a digest from the execution of a learning algorithm that*any*verifier can subsequently test for statistical validity\. Importantly, the verifier of a publicly\-verifiable Certificate of Statistical Validity \(pvCSV\) need not hold the same distribution as the prover\. Instead, the verifier can test for statistical validity with respect to their own distribution𝒟V\\mathcal\{D\}\_\{V\}, through an SQ oracle or samples\.

To formalize pvCSVs, we must first introduce the notion of soudness that makes proofs “publicly\-verifiable\.” We define*universal soundness*to ensure soundness holds no matter what distribution the verifier holds\.

###### Definition 3\.1\(Universal Soundness for SQ protocols\)\.

Fix a learning goal𝒢\\mathcal\{G\},τV\>0\\tau\_\{V\}\>0, andγ\>0\\gamma\>0\. An SQ protocol\(P,V\)\(P,V\)hasγ\\gamma\-universal soundnessif for any verifier distribution𝒟V\\mathcal\{D\}\_\{V\}andτV\\tau\_\{V\}\-accurate SQ oracle𝒪V\\mathcal\{O\}\_\{V\}for𝒟V\\mathcal\{D\}\_\{V\}, and for any proverP~\\tilde\{P\}, with probability at least1−γ1\-\\gamma,\(P~𝒪V,V𝒪V\)\(\\tilde\{P\}^\{\\mathcal\{O\}\_\{V\}\},V^\{\\mathcal\{O\}\_\{V\}\}\)outputsg∈𝒢​\(𝒟V\)g\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)orVVrejects\.

It is easy to see that universal soundness of SQ Protocols is actually just a restatement of standard soundness; syntactically, our definition simply renames the distribution𝒟\\mathcal\{D\}to be in terms of𝒟V\\mathcal\{D\}\_\{V\}\. But importantly, the restatement of the property allows us to reason rigorously about proof systems when the prover and verifier hold different distributions\. Under universal soundness, when the verifier has access to𝒟V\\mathcal\{D\}\_\{V\}, running the protocol results inVVrejecting orVVaccepting a hypothesis that is good for the verifier’s distribution, regardless of the prover’s distribution𝒟P\\mathcal\{D\}\_\{P\}\.

In a bit more detail, we can imagine an honest prover with oracle access to𝒪P\\mathcal\{O\}\_\{P\}for a distribution𝒟P\\mathcal\{D\}\_\{P\}, while a verifier has access to an oracleOVO\_\{V\}for a completely different distribution𝒟V\\mathcal\{D\}\_\{V\}\. In effect, we can view the honest proverP𝒪PP^\{\\mathcal\{O\}\_\{P\}\}, as a possible cheating prover for any downstream verifierV𝒪VV^\{\\mathcal\{O\}\_\{V\}\}\. Still, if the verifier accepts the proof of some non\-⊥\\bothypothesis, then universal soundness guarantees thath∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)\. The appeal of universal soundness shows itself when we consider non\-interactive proofs, where a prover wants to publish a fixed certificate, which any verifier \(holding any𝒟V\\mathcal\{D\}\_\{V\}\) can verify for themselves\. In this context, we can define pvCSVs as a non\-interactive SQ protocol satisfying universal soundness\.

###### Definition 3\.2\(pvCSV\)\.

Fix a learning goal𝒢\\mathcal\{G\},τP,τV\>0\\tau\_\{P\},\\tau\_\{V\}\>0, andγ\>0\\gamma\>0\. Apublicly\-verifiable Certificate of Statistical Validity \(pvCSV\) schemeis a non\-interactive SQ protocol, where a proverPPwithτP\\tau\_\{P\}\-accurate SQ oracle for distribution𝒟P\\mathcal\{D\}\_\{P\}publishes a hypothesish∈ℋh\\in\\mathcal\{H\}with certificateπ\\pi\. The pvCSV\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-certifies𝒢\\mathcal\{G\}if any verifierVVwithτV\\tau\_\{V\}\-accurate SQ oracle𝒪V\\mathcal\{O\}\_\{V\}for distribution𝒟V\\mathcal\{D\}\_\{V\}can read\(h,π\)\(h,\\pi\)and accept or reject with the following guarantees:

- •Completeness: if𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}, the honest prover, withτP\\tau\_\{P\}\-accurate SQ oracle for𝒟P\\mathcal\{D\}\_\{P\}, can generate a hypothesis\-certificate pair\(h,π\)←P𝒪P\(h,\\pi\)\\leftarrow P^\{\\mathcal\{O\}\_\{P\}\}such thatV𝒪VV^\{\\mathcal\{O\}\_\{V\}\}accepts andh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at least1−γ1\-\\gamma, over the random coins ofPPandVV\.
- •Universal Soundness: for any verifier distribution𝒟V\\mathcal\{D\}\_\{V\}, for any prover strategy\(h,π\)←P~𝒪V\(h,\\pi\)\\leftarrow\\tilde\{P\}^\{\\mathcal\{O\}\_\{V\}\},V𝒪VV^\{\\mathcal\{O\}\_\{V\}\}rejects orh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at least1−γ1\-\\gammaover the random coins ofVV\.

The construction of a pvCSV allows a prover with access to a distribution𝒟P\\mathcal\{D\}\_\{P\}to execute an algorithm𝒜\\mathcal\{A\}that learns𝒢\\mathcal\{G\}once and publish the results\(h,π\)\(h,\\pi\)\. Then, any party who is interested in running𝒜\\mathcal\{A\}on their own distribution𝒟V\\mathcal\{D\}\_\{V\}can, instead, run the verification algorithmVVon\(h,π\)\(h,\\pi\)\. If\(h,π\)\(h,\\pi\)is accepted, then by universal soundness,h∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)is guaranteed to be valid for the verifier’s distribution\.

#### Remarks\.

A few remarks about the definition of pvCSVs are in order\.

- •*Distributional Access:*We describe our pvCSVs as SQ protocols, then give sample\-based implementations\. That said, pvCSVs could equally encompass non\-interactive protocols for verification of learning, with more general distributional access, provided we define a more general notion of universal soundness\. As in\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41)\], the type of statistical access available may serve as a qualitative difference in the complexity of the prover and verifier\.
- •*Complexity Measures:*Quantitatively, there are many measures of complexity one could track for pvCSVs\. We will be most interested in the sample complexity \(using i\.i\.d\. random draws\) of the honest prover and verifier from𝒟P\\mathcal\{D\}\_\{P\}and𝒟V\\mathcal\{D\}\_\{V\}, respectively\. In general, we may also track other natural complexity measures, such as the time complexity or size of the certificate\.
- •*Computational Soundness:*Definition[3\.2](https://arxiv.org/html/2607.15528#S3.Thmtheorem2)considers universal soundness with respect to computationally\-unbounded provers\. We also consider computationally\-sound pvCSVs, where soundness only holds with respect to PPT algorithms\. Concretely, we will prove soundness in the Random Oracle Model, where the failure probability is taken over the random draw of random oracle \(in addition to the verifier’s coins\)\.
- •*On Robust Completeness?*Note that in our notion of completeness, we assume that the honest prover and verifier have access to exactly the same distribution𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}\. Given the motivating perspective on pvCSVs, we might hope for a weaker notion of distributional closeness required for completeness\. Such a guarantee may be formally defined in future work\. We remark that—paired with universal soundness—we still get some notion of robustness\. If the verifier accepts\(h,π\)\(h,\\pi\)then the distributions are indistinguishable, according to the queries asked by \(a specific execution of\)𝒜\\mathcal\{A\}, regardless of how close they are in any standard notion of statistical/computational indistinguishability\.

### 3\.1A pvCSV for Every Deterministic SQ Algorithm

Our first construction establishes that every deterministic SQ algorithm has a statistically\-sound pvCSV where the verifier answerskkqueries non\-adaptively and has sample complexityO​\(log⁡\(k\)\)O\(\\log\(k\)\), whereas the best known, efficient prover must answerkkpossibly adaptive queries with sample complexity scaling withO~​\(k\)\\tilde\{O\}\(\\sqrt\{k\}\)\. We present the pvCSV scheme as a non\-interactive SQ protocol, Protocol[1](https://arxiv.org/html/2607.15528#algorithm1)\. To generate the certificate, the honest prover first simulates the execution of𝒜\\mathcal\{A\}using the prover’s SQ oracle𝒪P\\mathcal\{O\}\_\{P\}, returning a hypothesishh\. Along the way, the prover writes down the list of queries𝒒\\bm\{q\}and answers𝒪P​\(𝒒\)\\mathcal\{O\}\_\{P\}\(\\bm\{q\}\)provided by the oracle as the certificate\. Then, the verifier also simulates the execution of𝒜\\mathcal\{A\}, but uses the digest of query\-answer pairs\(𝒒,𝒪P​\(𝒒\)\)\(\\bm\{q\},\\mathcal\{O\}\_\{P\}\(\\bm\{q\}\)\)provided by the certificate,*rather than making any adaptive statistical queries*\. Finally, the verifier runs a*batch*statistical validation of the answers provided in the certificate using its oracle𝒪V\\mathcal\{O\}\_\{V\}for𝒟V\\mathcal\{D\}\_\{V\}\. The key insight is that the verifier can non\-adaptively check every \(adaptively\-chosen\) query produced during the execution of𝒜\\mathcal\{A\}\.

Setup:Let

𝒢,τ\\mathcal\{G\},\\tau,

γ\\gammaand

𝒜\\mathcal\{A\}be as described in Theorem[3\.4](https://arxiv.org/html/2607.15528#S3.Thmtheorem4)\.

Let

𝒪P\\mathcal\{O\}\_\{P\}be a

τ/3\\tau/3\-accurate SQ oracle for

𝒟P\\mathcal\{D\}\_\{P\}\.

Let

𝒪V\\mathcal\{O\}\_\{V\}be a

τ/3\\tau/3\-accurate SQ oracle for

𝒟V\\mathcal\{D\}\_\{V\}\.

1ex

1ex

*Simulation of SQ algorithm𝒜\\mathcal\{A\}*

ProverPP:

Initialize an empty transcript

π=⟨⟩\\pi=\\langle\\rangle
Simulate

𝒜\\mathcal\{A\}by executing

𝒜𝒪P\\mathcal\{A\}^\{\\mathcal\{O\}\_\{P\}\}; specifically:

- •whenever𝒜\\mathcal\{A\}issues an SQqq,PPqueries𝒪P​\(q\)\\mathcal\{O\}\_\{P\}\(q\)and updatesπ←⟨π,q,𝒪P​\(q\)⟩\\pi\\leftarrow\\langle\\pi,q,\\mathcal\{O\}\_\{P\}\(q\)\\rangle

if*simulation of𝒜\\mathcal\{A\}returnshh*then

PPsends

\(h,π\)\(h,\\pi\)to

VV
1ex

*Verification of transcript*

VerifierVV:

Read and typecheck

\(h,π\)\(h,\\pi\)\. Parse

π\\piinto

\(𝒒,𝒂\)\(\\bm\{q\},\\bm\{a\}\)as follows:

- •𝒒:=\(q1,q2,…,qBV\)\\bm\{q\}:=\(q\_\{1\},q\_\{2\},\\ldots,q\_\{B\_\{V\}\}\), the list of SQs issued during simulation of𝒜\\mathcal\{A\}
- •𝒂:=\(a1,a2,…,aBV\)\\bm\{a\}:=\(a\_\{1\},a\_\{2\},\\ldots,a\_\{B\_\{V\}\}\), the answers to𝒒\\bm\{q\}, whereaja\_\{j\}should equal𝒪P​\(qj\)\\mathcal\{O\}\_\{P\}\(q\_\{j\}\)

Check that

π\\piis consistent with

𝒜\\mathcal\{A\}outputting

hh; that is,

- •Simulate𝒜\\mathcal\{A\}using𝒂\\bm\{a\}to answer SQs
- •Check that𝒜\\mathcal\{A\}returnsh≠⊥h\\neq\\bot

if*π\\piis NOT consistent with𝒜\\mathcal\{A\}*then

Reject and output

⊥\\bot
1ex

*Statistical Validation of simulated oracle queries*

if*NOT𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾​\(𝐪,𝐚,τ/3,τ\)\\mathsf\{Validate\}\(\\bm\{q\},\\bm\{a\},\\tau/3,\\tau\)*then

Reject and output

⊥\\bot
Accept and output

hh

Protocol 1pvCSV for Determinstic SQ AlgorithmInput :Batch of statistical queries

𝒒\\bm\{q\};

List of candidate answers to queries

𝒂\\bm\{a\};

Candidate accuracy

τP\>0\\tau\_\{P\}\>0and final accuraccy

τ\>0\\tau\>0
Setup :Non\-adaptive

τV\\tau\_\{V\}\-accurate SQ oracle

𝒪V\\mathcal\{O\}\_\{V\}s\.t\.

τP\+2​τV≤τ\\tau\_\{P\}\+2\\tau\_\{V\}\\leq\\tau
Issue batch of queries

𝒒\\bm\{q\}to

𝒪V\\mathcal\{O\}\_\{V\}; let

a^j:=𝒪V​\(qj\)\\hat\{a\}\_\{j\}:=\\mathcal\{O\}\_\{V\}\(q\_\{j\}\)for all

1≤j≤B1\\leq j\\leq B
for*j=1,…,Bj=1,\\ldots,B*do

if*\|a^j−aj\|\>τV\+τP\|\\hat\{a\}\_\{j\}\-a\_\{j\}\|\>\\tau\_\{V\}\+\\tau\_\{P\}*then

returnFalse

end for

returnTrue

Algorithm 2𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾​\(𝒒,𝒂,τP,τ\)\\mathsf\{Validate\}\(\\bm\{q\},\\bm\{a\},\\tau\_\{P\},\\tau\)i\.e\., Non\-adaptive Statistical ValidationWe prove that Protocol[1](https://arxiv.org/html/2607.15528#algorithm1)is a pvCSV where the verifier’s sample complexity scales “non\-adaptively” even when an adaptive algorithm is necessary for learning\. We start with the following lemma\.

###### Lemma 3\.3\.

Fix a learning goal𝒢\\mathcal\{G\},τ\>0\\tau\>0\. Suppose𝒜\\mathcal\{A\}is a deterministic algorithm thatτ\\tau\-SQ learns𝒢\\mathcal\{G\}\. There is an SQ protocol\(P,V\)\(P,V\), described in Protocol[1](https://arxiv.org/html/2607.15528#algorithm1), with the following properties:

1. \(a\)\(P,V\)\(P,V\)is a non\-interactive SQ protocol that\(τ/3,τ/3,0\)\(\\tau/3,\\tau/3,0\)\-SQ verifiers𝒢\\mathcal\{G\}
2. \(b\)VVuses a non\-adaptive SQ oracle, regardless of the SQ adaptivity of𝒜\\mathcal\{A\}\. That is, suppose𝒜\\mathcal\{A\}hasτ\\tau\-query complexity\(k,B\)\(k,B\); then, - •PPhasτ/3\\tau/3\-query complexity\(1,B\)\(1,B\); - •VVhasτ/3\\tau/3\-query complexity\(k,B\)\(k,B\)
3. \(c\)VVandPPrun in linear time in the original algorithm\. That is, suppose𝒜\\mathcal\{A\}runs in timeT𝒜​\(τ\)T\_\{\\mathcal\{A\}\}\(\\tau\); then bothPPandVVrun in timeO​\(T𝒜​\(τ\)\)O\(T\_\{\\mathcal\{A\}\}\(\\tau\)\)

###### Proof\.

First, we analyze the prover and verifier’s query complexities\. Observe thatPPruns a direct simulation of the queries issued by𝒜\\mathcal\{A\}, supported by𝒪P\\mathcal\{O\}\_\{P\}\. Since𝒪P\\mathcal\{O\}\_\{P\}isτ/3\\tau/3\-accurate, thenPPhasτ/3\\tau/3\-query complexity\(k,B\)\(k,B\)\. In contrast,VVcalls𝒪V\\mathcal\{O\}\_\{V\}once on allBBqueries through the𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾\\mathsf\{Validate\}subroutine\. Since𝒪V\\mathcal\{O\}\_\{V\}isτ/3\\tau/3\-accurate,VVhasτ/3\\tau/3\-query complexity\(1,B\)\(1,B\)\. So part \(b\) holds\.

Next, we analyze run time\. Observe that bothPPandVVsimulate an execution of𝒜\\mathcal\{A\}\. While the oracles𝒪P\\mathcal\{O\}\_\{P\}and𝒪V\\mathcal\{O\}\_\{V\}are bothτ/3\\tau/3\-accurate, the simulations of𝒜\\mathcal\{A\}can assumeτ\\tau\-accuracy, so the simulations take timeO​\(T𝒜​\(τ\)\)O\(T\_\{\\mathcal\{A\}\}\(\\tau\)\)\.VValso runs a statistical valdiation that checks the statistical closeness of theBBqueries, each of which takes constant time to evaluate in the query model, which is also linear in the run time of𝒜\\mathcal\{A\}\. Thus, part \(c\) holds\.

To complete the lemma, we show that\(P,V\)\(P,V\)is a non\-interactive SQ protocol that\(τ/3,τ/3,0\)\(\\tau/3,\\tau/3,0\)\-SQ verifies𝒢\\mathcal\{G\}\.999The failure probability of the pvCSV will arise when we implement the protocol’s oracles using samples\.Observe by construction\(P,V\)\(P,V\)is non\-interactive:PPsends one message\(h,π\)\(h,\\pi\)toVV\. Next, we show\(P,V\)\(P,V\)satisfies perfect completenees and universal soundness for𝒢\\mathcal\{G\}

*Completeness:*We consider the honest protocol\(P,V\)\(P,V\)where𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}\. First, we show thatVValways accepts the honestly generated certificate\(h,π\)\(h,\\pi\)\. Since\(h,π\)\(h,\\pi\)is honestly generated,VVcan parseπ\\piinto queries𝒒\\bm\{q\}and answers𝒂\\bm\{a\}\. Then it is sufficient to show thatπ\\piis consistent with an execution of𝒜\\mathcal\{A\}that results in the outputhh\. Consider the sequence of queries𝒒=\(q1,q2,…,qB\)\\bm\{q\}=\(q\_\{1\},q\_\{2\},\\ldots,q\_\{B\}\)listed in the certificate\. We claim this is exactly the same sequence of queries thatVVwill produce when simulating𝒜\\mathcal\{A\}\. This claim follows \(formally by induction on the sequence of queries\) because𝒜\\mathcal\{A\}is deterministic and the verifier’s simulation of𝒜\\mathcal\{A\}uses the same query responses𝒂=\(𝒪P​\(q1\),𝒪P​\(q2\),…,𝒪P​\(qB\)\)\\bm\{a\}=\(\\mathcal\{O\}\_\{P\}\(q\_\{1\}\),\\mathcal\{O\}\_\{P\}\(q\_\{2\}\),\\ldots,\\mathcal\{O\}\_\{P\}\(q\_\{B\}\)\)as the prover’s execution\. By the same argument, the outputhhof the prover and verifier’s execution of𝒜\\mathcal\{A\}will be the same \(since𝒜\\mathcal\{A\}is deterministic and operates on the same input sequence\)\.

Second, we show thatπ\\pipasses the verifier’s statistical validation𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾​\(𝒒,𝒂,τ/3,τ\)\\mathsf\{Validate\}\(\\bm\{q\},\\bm\{a\},\\tau/3,\\tau\), according to𝒪V\\mathcal\{O\}\_\{V\}\. Recall that𝒪P\\mathcal\{O\}\_\{P\}and𝒪V\\mathcal\{O\}\_\{V\}are bothτ3\\frac\{\\tau\}\{3\}\-accurate oracles for𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}, by assumption\. Since the verifier issues the same queriesq1,q2,…,qBq\_\{1\},q\_\{2\},\\ldots,q\_\{B\}to𝒪V\\mathcal\{O\}\_\{V\}, we see that, for each1≤j≤B1\\leq j\\leq B, the comparison looks at the difference between𝒪P​\(qj\)\\mathcal\{O\}\_\{P\}\(q\_\{j\}\)and𝒪V​\(qj\)\\mathcal\{O\}\_\{V\}\(q\_\{j\}\)\. Both queries are withinτ/3\{\\tau\}/\{3\}of the true expectationEx∼𝒟⁡\[qj​\(x\)\]\\operatorname\*\{\\textnormal\{\\bf E\}\}\_\{x\\sim\\mathcal\{D\}\}\[q\_\{j\}\(x\)\], so by the triangle inequality\|a^j−aj\|≤2​τ/3\|\\hat\{a\}\_\{j\}\-a\_\{j\}\|\\leq\{2\\tau\}/\{3\}\. Therefore,𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾\\mathsf\{Validate\}always returns true, andVValways accepts the honestly generated\(h,π\)\(h,\\pi\)\.

So it is sufficient to show thath∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)\. Recall thathhis the output of running𝒜\\mathcal\{A\}using aτ/3\{\\tau\}/\{3\}\-accurate oracle for𝒟P\\mathcal\{D\}\_\{P\}\. Because𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}\(andτ/3≤τ\{\\tau\}/\{3\}\\leq\\tau\), this execution is also the result of running𝒜\\mathcal\{A\}using*some*τ\\tau\-accurate oracle for𝒟V\\mathcal\{D\}\_\{V\}\. Thus, by the assumption that𝒜\\mathcal\{A\}τ\\tau\-SQ learns𝒢\\mathcal\{G\}, thenh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)\. So,\(P,V\)\(P,V\)achieves completeness11\.

*Universal Soundness:*Let𝒟V\\mathcal\{D\}\_\{V\}be any distribution, and𝒪V\\mathcal\{O\}\_\{V\}be anyτ/3\\tau/3\-accurate SQ oracle for𝒟V\\mathcal\{D\}\_\{V\}\. Take any cheating prover strategyP~\\tilde\{P\}, and consider the interaction\(P~𝒪V,V𝒪V\)\(\\tilde\{P\}^\{\\mathcal\{O\}\_\{V\}\},V^\{\\mathcal\{O\}\_\{V\}\}\)\. It suffices to argue, as in the above argument for completeness, that ifVVaccepts, thenh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)\. IfVVaccepts, then it must be the case thatπ\\piis consistent with some execution of𝒜\\mathcal\{A\}that results in outputtinghh\. Further,𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾​\(𝒒,𝒂,τ/3,τ\)\\mathsf\{Validate\}\(\\bm\{q\},\\bm\{a\},\\tau/3,\\tau\)passes, which implies the answers𝒂\\bm\{a\}are within2​τ/3\{2\\tau\}/\{3\}of the responses from the verifier’s non\-adaptive oracle query𝒂^=𝒪V​\(𝒒\)\\hat\{\\bm\{a\}\}=\\mathcal\{O\}\_\{V\}\(\\bm\{q\}\)\. Since𝒪V\\mathcal\{O\}\_\{V\}isτ/3\\tau/3\-accurate with respect to𝒟V\\mathcal\{D\}\_\{V\}, by the triangle inequality,\|aj−Ex∼𝒟V⁡\[qj​\(x\)\]\|≤τ\|a\_\{j\}\-\\operatorname\*\{\\textnormal\{\\bf E\}\}\_\{x\\sim\\mathcal\{D\}\_\{V\}\}\[q\_\{j\}\(x\)\]\|\\leq\\taufor all1≤j≤B1\\leq j\\leq B\.

In combination,π\\pigives the verifier a way to simulate𝒜\\mathcal\{A\}usingτ\\tau\-accurate answers its queries over𝒟V\\mathcal\{D\}\_\{V\}\. The learning guarantee of𝒜\\mathcal\{A\}implies that the returned hypothesish∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)must be valid\. Thus under interaction with any prover cheater, the verifierVVeither rejects or accepts and outputsh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\), and\(P,V\)\(P,V\)satisfies universal soundness0\. ∎

With this lemma in place, establishing our main theorem of this section is straightforward\. To achieve an improved bound on the size of the certificate, we make the following optimization\. Notice that our proof of correctness does not actually use the fact that the queries𝒒\\bm\{q\}used by the prover are the same as the queries derived by the verifier’s simulation of𝒜\\mathcal\{A\}; instead, we only need that the answers in the certificate,𝒂\\bm\{a\}are valid for the verifier’s queries\. Thus, we do not need to include queries in the certificate at all: we need only the certificate be the list of answers, that is,π:=𝒂\\pi:=\\bm\{a\}\. While including the names of the queries improves the clarity of the proof system, we derive an equally\-valid SQ protocol whereπ:=𝒂\\pi:=\\bm\{a\}in the following theorem\.

###### Theorem 3\.4\(Formal Statement of Theorem[2](https://arxiv.org/html/2607.15528#Thmresult2)\)\.

Fix a learning goal𝒢\\mathcal\{G\}andτ\>0\\tau\>0\. Suppose𝒜\\mathcal\{A\}is a deterministic SQ algorithm thatτ\\tau\-SQ learns𝒢\\mathcal\{G\}, which makeskkadaptive queries to aτ\\tau\-accurate oracle𝒪\\mathcal\{O\}\. For anyδ\>0\\delta\>0, there exists a pvCSV scheme for𝒢\\mathcal\{G\}with failure probabilityδ\\deltaachievable in the following complexities\.

- •Honest prover sample complexity:mP≤O​\(k⋅log⁡\(k/δ\)⋅log⁡\(1/δ\)/τ2\)m\_\{P\}\\leq O\\left\(\{\\sqrt\{k\\cdot\\log\(k/\\delta\)\\cdot\\log\(1/\\delta\)\}\}/\{\\tau^\{2\}\}\\right\)
- •Verifier sample complexity:mV≤O​\(log⁡\(k/δ\)/τ2\)m\_\{V\}\\leq O\(\\log\(k/\\delta\)/\\tau^\{2\}\)
- •Certificate size:\|π\|≤O​\(k⋅log⁡\(1/τ\)\)\\left\|\\pi\\right\|\\leq O\(k\\cdot\\log\(1/\\tau\)\)

###### Proof\.

Let\(P,V\)\(P,V\)be Protocol[1](https://arxiv.org/html/2607.15528#algorithm1)\. By Lemma[3\.3](https://arxiv.org/html/2607.15528#S3.Thmtheorem3), to run a fully\-adaptive SQ algorithm usingkkqueries, it suffices to have a\(k,k,τ/3\)\(k,k,\{\\tau\}/\{3\}\)\-implementation of𝒪P\\mathcal\{O\}\_\{P\}and a\(1,k,τ/3\)\(1,k,\{\\tau\}/\{3\}\)\-implementation of𝒪V\\mathcal\{O\}\_\{V\}\. The honest prover and verifier sample complexities follow from Proposition[2\.11](https://arxiv.org/html/2607.15528#S2.Thmtheorem11)and Proposition[2\.10](https://arxiv.org/html/2607.15528#S2.Thmtheorem10), respectively\. The original SQ verification protocol contributesγ=0\\gamma=0failure probability, so by union bounding over the failure probability of implementing𝒪P\\mathcal\{O\}\_\{P\}and𝒪V\\mathcal\{O\}\_\{V\}, completeness and universal soundness hold with probability at least1−δ1\-\\delta\.

Finally, we analyze the size of the certificateπ\\pi\. Without loss of generality, we modify the certificate so thatπ:=𝒂\\pi:=\\bm\{a\}, and the verifier so that it doesn’t check forq~i=qi\\tilde\{q\}\_\{i\}=q\_\{i\}\. As mentioned above, this does not change the validity of Lemma[3\.3](https://arxiv.org/html/2607.15528#S3.Thmtheorem3)\. Every answer to a statistical query requiresO​\(log⁡\(1/τ\)\)O\(\\log\(1/\\tau\)\)bits of space\. Sinceπ=𝒂=\(a1,a2,…,aB\)\\pi=\\bm\{a\}=\(a\_\{1\},a\_\{2\},\\ldots,a\_\{B\}\), then\|π\|=O​\(B​log⁡\(1/τ\)\)\|\\pi\|=O\(B\\log\(1/\\tau\)\)\. ∎

Finally, we remark informally on the time complexities of the honest prover and verifier\. Both parties run a direct simulation of the original SQ algorithm𝒜\\mathcal\{A\}\. Additionally, the honest prover must implement the mechanism of\[[BLA25](https://arxiv.org/html/2607.15528#bib.bib26)\]for adaptive data analysis to answer the queries to𝒪P\\mathcal\{O\}\_\{P\}, whereas𝒪V\\mathcal\{O\}\_\{V\}may respond with the empirical statistics from its sample\. In most settings, the overall running time for both will be dominated by the simulation of𝒜\\mathcal\{A\}\.

## 4Delegation of Randomized SQ Learning

In this section, we address delegating SQ learning algorithms that use randomness\. Our investigation leads us to develop a number of new definitions and tools for understanding SQ protocols\. With these tools in place, we obtain \(computationally\-sound\) pvCSVs, not only for randomized SQ algorithms, but for a large class of SQ protocols\.

We start by giving essential definitions, highlighting important properties of randomized SQ algorithms and protocols\. Using these definitions, we then show that for a large class of SQ protocols, there exists a reformulation into a Canonical SQ Protocol\. This canonical protocol allows for non\-adaptive verification of the statistical queries, leading to exponential savings in sample complexity for the verifier, for any original SQ protocol \(including randomized algorithms that make adaptive statistical queries\)\. We conclude the section with a construction of pvCSVs for this class, by showing how to apply a Fiat\-Shamir transformation to the canonical protocol\.

### 4\.1Definitions for Randomized SQ Learning and SQ Protocols

To begin, we fix a standard, mechanical format for describing randomized SQ algorithms that proceed in*epochs*\. In thett\-th epoch,

- •𝒜\\mathcal\{A\}samples randomnessrt∈\{0,1\}dtr\_\{t\}\\in\\\{0,1\\\}^\{d\_\{t\}\}, for some \(efficiently\-bounded\)dt∈ℕd\_\{t\}\\in\\mathbb\{N\}
- •𝒜\\mathcal\{A\}then executes a deterministic SQ algorithm𝒜t\\mathcal\{A\}\_\{t\}as a subroutine, withrtr\_\{t\}as fixed input, which may issue adaptive statistical queries\.

The choice of thett\-th subroutine𝒜t\\mathcal\{A\}\_\{t\}may be chosen adaptively as a function of prior randomness, as well as any statistical queries issued\. In terms of expressivity, formatting randomized algorithms into epochs is not a restriction, as we can simulate any algorithm in this format\. But the number of epochs turns out to be a key quantity that affects the complexity of our proof systems\.

###### Definition 4\.1\(Epoch Complexity\)\.

Fixτ\>0\\tau\>0andℓ∈ℕ\\ell\\in\\mathbb\{N\}\. A randomized SQ algorithm𝒜\\mathcal\{A\}hasepoch complexityℓ\\ellif for anyτ\\tau\-accuate SQ oracle𝒪\\mathcal\{O\}, the execution of𝒜𝒪\\mathcal\{A\}^\{\\mathcal\{O\}\}can be broken intoℓ\\ellepochs\.

Extending the notion of epoch complexity to SQ protocols, we standardize the verifier’s execution similarly\. In thett\-th epoch,

- •VVsamples randomnessrt∈\{0,1\}dtr\_\{t\}\\in\\\{0,1\\\}^\{d\_\{t\}\}for some \(efficiently\-bounded\)dt∈𝒩d\_\{t\}\\in\\mathcal\{N\}
- •VVexecutes a deterministic, interactive SQ algorithmVtV\_\{t\}as a subroutine, withrtr\_\{t\}as a fixed input, which may issue adaptive statistical queries and communicate withPP\.

Again, the choice of thett\-th subroutineVtV\_\{t\}can be chosen adaptively based on prior randomness,VV’s internal state, and messages from the prover\.

###### Definition 4\.2\(Epoch Complexity of SQ Protocols\)\.

FixτV\>0\\tau\_\{V\}\>0andℓ∈ℕ\\ell\\in\\mathbb\{N\}\. An SQ verifierVVhasepoch complexityℓ\\ellif for any proverP~\\tilde\{P\}and anyτV\\tau\_\{V\}\-accurate SQ oracle𝒪V\\mathcal\{O\}\_\{V\}, the execution ofVVwithin the interaction\(P~𝒪V,V𝒪V\)\(\\tilde\{P\}^\{\\mathcal\{O\}\_\{V\}\},V^\{\\mathcal\{O\}\_\{V\}\}\)can be broken intoℓ\\ellepochs\.

Intuitively, formatting randomized algorithms \(and SQ verifiers\) into epochs allows us to separate “adaptivity” of𝒜\\mathcal\{A\}based on fresh randomness and adaptivity based on the results of statistical queries \(and prover messages\)\. In the extreme, each epoch could issue a single statistical query, so adaptivity to the randomness and queries are essentially the same\. At the other extreme, we might consider algorithms that start with a random initialization, but then proceed deterministically\. Such algorithms may still make adaptive SQ queries, but could be implemented in a single epoch\. The number of epochs serves as a natural complexity measure of the algorithm’s use of its randomness\.

#### Oblivious vs\. Public\-State SQ Oracles\.

Recall that we model an SQ oracle as a stateful algorithm, who may respond adversarially \(withinτ\\tau\-accuracy\) based on the state of the algorithm𝒜\\mathcal\{A\}\. When our algorithms leverage randomness, we need to reason about what knowledge the oracle𝒪\\mathcal\{O\}has about the algorithm’s internal state—namely, the randomness sampled at the current epoch\.

One standard notion of SQ oracle allows the algorithm to maintain private state from the oracle\. In this case, the algorithm need not reveal any of its random coins to the oracle\. We refer to such oracles as*oblivious*SQ oracles, which follow the earlier notion given in Definition[2\.1](https://arxiv.org/html/2607.15528#S2.Thmtheorem1)\.

For randomized SQ algorithms, we mainly focus on oracles, who may respond adversarially with full knowledge of the algorithm’s randomness\. This notion is captured by a*public\-state*SQ oracle\.

###### Definition 4\.3\(Public\-State SQ Oracle\)\.

Apublic\-state SQ oracleis a stateful algorithm𝒪:𝒬×\{0,1\}∗→\[0,1\]\\mathcal\{O\}:\\mathcal\{Q\}\\times\\\{0,1\\\}^\{\*\}\\to\[0,1\]that takes as input a queryq∈𝒬q\\in\\mathcal\{Q\}and a stringr∈\{0,1\}∗r\\in\\\{0,1\\\}^\{\*\}representing random coins, and responds with an evaluation𝒪​\(q,r\)∈\[0,1\]\\mathcal\{O\}\(q,r\)\\in\[0,1\]\.

Forτ\>0\\tau\>0, the oracle𝒪\\mathcal\{O\}isτ\\tau\-accurate over𝒟\\mathcal\{D\}if for any finite, adaptively chosen sequence ofk∈ℕk\\in\\mathbb\{N\}queries and randomness\(q1,r1\),\(q2,r2\),…,\(qk,rk\)\(q\_\{1\},r\_\{1\}\),\(q\_\{2\},r\_\{2\}\),\\ldots,\(q\_\{k\},r\_\{k\}\), for alli∈\[k\]i\\in\[k\],

\|𝒪​\(qi,ri\)−EX∼𝒟⁡\[qi​\(X\)\]\|≤τ\.\\displaystyle\\left\|\\mathcal\{O\}\(q\_\{i\},r\_\{i\}\)\-\\operatorname\*\{\\textnormal\{\\bf E\}\}\_\{X\\sim\\mathcal\{D\}\}\[q\_\{i\}\(X\)\]\\right\|\\leq\\tau\.Concretely, consider a sequence issued by a randomized SQ algorithm𝒜\\mathcal\{A\}\. In thett\-th epoch, whenever𝒜t\\mathcal\{A\}^\{t\}issues a queryq∈𝒬q\\in\\mathcal\{Q\}, the randomnessr1​…​rtr\_\{1\}\\ldots r\_\{t\}is sent to the public\-state oracle𝒪​\(q,r1​…​rt\)\\mathcal\{O\}\(q,r\_\{1\}\\ldots r\_\{t\}\)\.

Further, a randomized SQ algorithmτ\\tau\-SQ learns𝒢\\mathcal\{G\}with public state, if correctness holds for anyτ\\tau\-accurate public\-state SQ oracle𝒪\\mathcal\{O\}; an SQ protocol\(P,V\)\(P,V\)\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-SQ verifies𝒢\\mathcal\{G\}with public verifier state, if completeness and soundness hold for anyτV\\tau\_\{V\}\-accurate public\-state SQ oracle𝒪V\\mathcal\{O\}\_\{V\}\.

In other words, a randomized algorithm equipped with a public\-state SQ oracle may, as usual, specify the queryq∈𝒬q\\in\\mathcal\{Q\}of interest, but necessarily reveals the randomness sampled so far\. By the standardization into epochs, the randomness captures all of the state of𝒜\\mathcal\{A\}\.

Note that any algorithm/protocol that succeeds with access to a public\-state oracle also works with an oblivious oracle, but the converse is not true\. Correctness with respect to a public\-state oracle is a stronger guarantee: no matter what information is leaked to the oracle through interaction, the algorithm will work\. That said, proving correctness may be more challenging, so designing correct algorithms with a public\-state oracle may be harder than with an oblivious oracle\.

#### Public\-Coin SQ Protocols\.

As with traditional interactive protocols, we can distinguish SQ protocols based on the verifier’s communication of its randomness\. Key to our study of non\-interactive proof systems for randomized SQ algorithms, we first consider*public\-coin*interactive SQ protocols\. Defining public\-coin protocols when the verifier is equipped with an SQ oracle \(which may introduce non\-determinism\) is nuanced\. We consider two alternative definitions\.

###### Definition 4\.4\(Public\-Coin SQ Protocols\)\.

An SQ protocol\(P,V\)\(P,V\)is a \(standard\)public\-coinSQ protocol if in every round of communication,VVsamples a uniformly random stringrr, independent of all prior randomness and messages, and sendsrrtoPP\. Concretely, forVVof epoch complexityℓ\\ell, the protocol consists ofℓ\\ellrounds, where in thett\-th round,VtV\_\{t\}sends its randomnessrtr\_\{t\}toPP\.

###### Definition 4\.5\(Mixed\-Message SQ Protocols\)\.

An SQ protocol\(P,V\)\(P,V\), whereVVhas epoch complexityℓ\\ell\.\(P,V\)\(P,V\)is amixed\-message\(public\-coin\) SQ protocol if for allt=1,…,ℓt=1,\\ldots,\\ell, the first message of thett\-th epoch is fromVtV\_\{t\}toPPand includes the epoch’s randomnessrtr\_\{t\}\.

In other words, a standard public\-coin SQ protocol adopts the formalism that the only messages the verifier sends to the prover are its randomness, whereas a mixed\-message SQ protocol must reveal its randomness to the prover, but may also send non\-random challenges\. Without an SQ oracle, the distinction is moot: in thett\-th epoch,VtV\_\{t\}is a deterministic algorithm, so the prover can simulate any challenges it would receive and respond accordingly\. But with an SQ oracle—which may respond adversarially within its tolerance—Vt𝒪VV\_\{t\}^\{\\mathcal\{O\}\_\{V\}\}may have non\-deterministic behavior, even conditioned onrtr\_\{t\}\. Thus, in principle, mixed\-message SQ protocols could be more expressive than public\-coin SQ protocols\. Despite this distinction, our main result in Section[4\.2](https://arxiv.org/html/2607.15528#S4.SS2)\(Protocol[3](https://arxiv.org/html/2607.15528#algorithm3)\) implies that \(as in standard interactive proofs\) any mixed\-message SQ protocol can be compiled into a public\-coin SQ protocol with the same completeness and soudness guarantees\.

#### Public\-Query SQ Protocols\.

A final consideration in classifying SQ protocols is whether the verifier’s queries are kept private or made public to the prover\. A public\-query protocol reveals its queries to the prover at every round of communication\.

###### Definition 4\.6\(Public\-Query SQ Protocols\)\.

An SQ protocol\(P,V\)\(P,V\)is apublic\-querySQ protocol if in every roundiiof communication, theiith messagemim\_\{i\}fromVVtoPPincludes every statistical queryqi1,…,qijq\_\{i\_\{1\}\},\\ldots,q\_\{i\_\{j\}\}issued byVVto𝒪V\\mathcal\{O\}\_\{V\}since the previous messagemi−1m\_\{i\-1\}\.

Note that, per the discussion above, whether the verifier’s queries are public or private is orthogonal to whether the verifier’s coins are public or private\. That said, Protocol[3](https://arxiv.org/html/2607.15528#algorithm3)also implies that any public\-coin, private\-query protocol can be made public\-query\. In this sense, we use the term “public\-query” to refer to private\-coin, public\-query SQ protocols\. We explore public\-query protocols further when we consider the strength and limits of SQ proof systems beyond pvCSVs in Section[5](https://arxiv.org/html/2607.15528#S5)\.

### 4\.2A Canonical Public\-Coin SQ Protocol

With the preliminaries on randomized SQ algorithms and SQ protocols in place, we are ready to describe protocols for delegating randomized SQ algorithms\. We describe, in Protocol[3](https://arxiv.org/html/2607.15528#algorithm3), an interactive public\-coin SQ protocol for delegating any randomized SQ algorithm that SQ\-learns a concept𝒢\\mathcal\{G\}with public state\. In fact, our protocol is much more general, and can take any mixed\-message, private\-query SQ protocol that SQ\-verifies𝒢\\mathcal\{G\}with public verifier state \(which include all randomized SQ algorithms with public state\) and compile it into a canonical public\-coin SQ protocol, where the verifier issues a single non\-adaptive batch of statistical queries\.

Setup:Let

𝒢,τP,τV,γ\\mathcal\{G\},\\tau\_\{P\},\\tau\_\{V\},\\gammaand

\(P,V\)\(P,V\)be as described in Lemma[4\.7](https://arxiv.org/html/2607.15528#S4.Thmtheorem7)\.

Let

𝒪𝖯𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}be a

min⁡\{τP,τV/3\}\\min\\\{\\tau\_\{P\},\\tau\_\{V\}/3\\\}\-accurate SQ oracle for

𝒟P\\mathcal\{D\}\_\{P\}\.

Let

𝒪𝖵𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}be a

τV/3\\tau\_\{V\}/3\-accurate SQ oracle for

𝒟V\\mathcal\{D\}\_\{V\}\.

1ex

1ex

Phase 1:*Interactive simulation of SQ protocol\(P,V\)\(P,V\)*

Initialize an empty transcript

π0=⟨⟩\\pi\_\{0\}=\\langle\\rangle
for*i=1,…,ℓi=1,\\ldots,\\ell*do

Prover

𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}andVerifier

𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}determine

ViV\_\{i\}for the

ii\-the epoch of

VV, based on

πi−1\\pi\_\{i\-1\}
Verifier

𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}samples the

ii\-th epoch’s randomness

rir\_\{i\}and sends to

𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}
Prover

𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}updates

πi←⟨πi−1,ri⟩\\pi\_\{i\}\\leftarrow\\langle\\pi\_\{i\-1\},r\_\{i\}\\rangle
𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}simulates the

ii\-th epoch by executing

\(P𝒪𝖯𝖼𝖺𝗇,Vi𝒪𝖯𝖼𝖺𝗇\)​\(πi\)\(P^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\},V\_\{i\}^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\}\)\(\\pi\_\{i\}\); specifically:

- •whenViV\_\{i\}issues SQqq,𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}queries𝒪𝖯𝖼𝖺𝗇​\(q\)\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\(q\)and updatesπi←⟨πi,q,𝒪𝖯𝖼𝖺𝗇​\(q\)⟩\\pi\_\{i\}\\leftarrow\\langle\\pi\_\{i\},q,\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\(q\)\\rangle
- •whenViV\_\{i\}sends messagesstoPP,𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}simulates proverP𝒪𝖯𝖼𝖺𝗇​\(πi\)P^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\}\(\\pi\_\{i\}\)
- •whenPPsends messagemmtoVV,𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}updatesπi←⟨πi,s,m⟩\\pi\_\{i\}\\leftarrow\\langle\\pi\_\{i\},s,m\\rangle

if*simulation ofVVreturnshh*then

𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}updates

π←πi\\pi\\leftarrow\\pi\_\{i\}and sends

\(h,π\)\(h,\\pi\)to

𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}
𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}breaks from loop

else if*simulation ofVVready for next epoch*then

𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}sends updates to transcript

πi\\pi\_\{i\}to

𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}for next epoch

end for

1ex

Phase 2:*Verification of interactive transcript*

Verifier𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}:

Read and typecheck

\(h,π\)\(h,\\pi\)\. Parse

π\\piinto

\(𝒒V,𝒂V,𝒓~,𝒎,𝒔\)\(\\bm\{q\}\_\{V\},\\bm\{a\}\_\{V\},\\tilde\{\\bm\{r\}\},\\bm\{m\},\\bm\{s\}\)as follows:

- •𝒒V:=\(q1,q2,…,qBV\)\\bm\{q\}\_\{V\}:=\(q\_\{1\},q\_\{2\},\\ldots,q\_\{B\_\{V\}\}\), the list of verifier SQs issued during simulation of\(P,V\)\(P,V\)
- •𝒂V:=\(a1,a2,…,aBV\)\\bm\{a\}\_\{V\}:=\(a\_\{1\},a\_\{2\},\\ldots,a\_\{B\_\{V\}\}\), the answers to𝒒V\\bm\{q\}\_\{V\}, whereaja\_\{j\}should equal𝒪P​\(qj\)\\mathcal\{O\}\_\{P\}\(q\_\{j\}\)
- •𝒓~:=\(r~1,…,r~ℓ\)\\tilde\{\\bm\{r\}\}:=\(\\tilde\{r\}\_\{1\},\\ldots,\\tilde\{r\}\_\{\\ell\}\), the public coins ofVV
- •𝒔:=\(s1,…,\)\\bm\{s\}:=\(s\_\{1\},\\ldots,\), the non\-random messages ofVVtoPP
- •𝒎:=\(m1,…,\)\\bm\{m\}:=\(m\_\{1\},\\ldots,\), the messages ofPPtoVV

Check that

π\\piis consistent with

\(P,V\)\(P,V\)outputting

hh; that is,

- •Check that𝒓~=r1,…,rℓ\\tilde\{\\bm\{r\}\}=r\_\{1\},\\ldots,r\_\{\\ell\}
- •SimulateVVwith randomness𝒓~\\tilde\{\\bm\{r\}\}; use𝒂V\\bm\{a\}\_\{V\}to answer SQs, and𝒎\\bm\{m\}for messages fromPP
- •Check thatVVreturnsh≠⊥h\\neq\\bot

if*π\\piis NOT consistent with\(P,V\)\(P,V\)*then

Reject and output

⊥\\bot
1ex

Phase 3:*Validation of simulated oracle queries*

Verifier𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}:

if*NOT𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾​\(𝐪V,𝐚V,τV/3,τV\)\\mathsf\{Validate\}\(\\bm\{q\}\_\{V\},\\bm\{a\}\_\{V\},\\tau\_\{V\}/3,\\tau\_\{V\}\)*then

Reject and output

⊥\\bot
Accept and output

hh

Protocol 3Canonical SQ Protocol#### Protocol Description\.

Protocol[3](https://arxiv.org/html/2607.15528#algorithm3)works as follows\. We start with a mixed\-message SQ protocol\(P,V\)\(P,V\)where the verifier may make private statistical queries, and each player is arbitrarily\-adaptive in their queries\. Note that randomized SQ algorithms are the special case of such protocols, where the algorithm must accepthhor output⊥\\botwithout assistance from any prover\. We want to build a public\-coin, public\-query SQ protocol\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)where the verifier issues a single batch of statistical queries\. As in Protocol[1](https://arxiv.org/html/2607.15528#algorithm1), the verifier will delegate its queries to the prover and check them at the end\.

Because\(P,V\)\(P,V\)is mixed\-message, we know that the verifierVVstarts each epoch by sending its randomness to the prover\. This random message will be the only message𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}sends to𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}per epoch; then,𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}will be responsible for simulating the remaining interactive execution of that epoch\.𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}will use its own SQ oracle𝒪𝖯𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}to make any queries\. This aspect of the protocol—where the prover simulates the queries of the verifier with knowledge of its randomness—is where we need to leverage the assumption that\(P,V\)\(P,V\)learns𝒢\\mathcal\{G\}with public verifier state; that is, even if the oracle \(or in this case the prover\) can respond adversarially based on the state of the verifier, the protocol is still sound\. Once the epoch finishes,𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}will send the transcript of the execution to𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}, who can update state and move to the next epoch\.

At the end, the canonical verifier𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}checks to ensure that the prover faithfully simulated the execution ofPPandVV\. Finally,𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}runs a statistical check to make sure all of the query values reported by the prover are actually within the required tolerance of the original protocol\.

In all, we obtain the following guarantee on our canonical public\-coin SQ protocol\.

###### Lemma 4\.7\(Formal Statement of Lemma[4](https://arxiv.org/html/2607.15528#Thmresult4)\)\.

Fix a learning goal𝒢\\mathcal\{G\},τP,τV\>0\\tau\_\{P\},\\tau\_\{V\}\>0, andγ\>0\\gamma\>0, and letτP′=min⁡\{τP,τV/3\}\\tau\_\{P\}^\{\\prime\}=\\min\\\{\\tau\_\{P\},\\tau\_\{V\}/3\\\}andτV′=τV/3\\tau\_\{V\}^\{\\prime\}=\\tau\_\{V\}/3\. Suppose\(P,V\)\(P,V\)is a mixed\-message, private\-query SQ protocol that\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-verifies𝒢\\mathcal\{G\}with public verifier state\. There is an SQ protocol\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\), described in Protocol[3](https://arxiv.org/html/2607.15528#algorithm3), with the following properties:

1. \(a\)\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)is a public\-coin SQ protocol that\(τP′,τV′,γ\)\(\\tau\_\{P\}^\{\\prime\},\\tau\_\{V\}^\{\\prime\},\\gamma\)\-verifies𝒢\\mathcal\{G\}
2. \(b\)ForVVof epoch complexityℓ\\ell,\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)has at mostℓ\\ellrounds of interaction\.
3. \(c\)𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}uses a non\-adaptive SQ oracle, regardless of the SQ adaptivity in\(P,V\)\(P,V\)\. That is, supposeVVhasτV\\tau\_\{V\}\-query complexity\(kV,BV\)\(k\_\{V\},B\_\{V\}\)andPPhasτP\\tau\_\{P\}\-query complexity\(kP,BP\)\(k\_\{P\},B\_\{P\}\); then, - •𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}hasτV′\\tau\_\{V\}^\{\\prime\}\-query complexity\(1,BV\)\(1,B\_\{V\}\); - •𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}hasτP′\\tau\_\{P\}^\{\\prime\}\-query complexity\(kP\+kV,BP\+BV\)\(k\_\{P\}\+k\_\{V\},B\_\{P\}\+B\_\{V\}\)
4. \(d\)𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}and𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}run in linear time in the original protocol\. That is, supposeVVruns in timeTV​\(τV\)T\_\{V\}\(\\tau\_\{V\}\)andPPruns in timeTP​\(τP\)T\_\{P\}\(\\tau\_\{P\}\); then - •𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}runs in timeO​\(TV​\(τV\)\)O\(T\_\{V\}\(\\tau\_\{V\}\)\) - •𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}runs in timeO​\(TV​\(τV\)\+TP​\(τP\)\)O\(T\_\{V\}\(\\tau\_\{V\}\)\+T\_\{P\}\(\\tau\_\{P\}\)\)
5. \(e\)ForPPof communication complexitycPc\_\{P\},𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}has communication complexityO​\(BV​log⁡\(1/τP′\)\)\+cPO\(B\_\{V\}\\log\(1/\\tau\_\{P\}^\{\\prime\}\)\)\+c\_\{P\}\.

###### Proof\.

Before we prove that the canonical protocol verifies𝒢\\mathcal\{G\}, we will analyze the other properties first\. First, we analyze round complexity\. Observe by construction that each round of communication corresponds to one epoch ofVV\. SinceVVhas epoch complexityℓ\\ell,\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)has round complexityℓ\\ell\. So part \(b\) holds\.

Next, we analyze statistical complexity\. Observe that𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}simulates the interaction\(P𝒪𝖯𝖼𝖺𝗇,V𝒪𝖯𝖼𝖺𝗇\)\(P^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\},V^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\}\), so𝒪𝖯𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}must answer at mostBPB\_\{P\}queries fromPPandBVB\_\{V\}queries fromVV, and compose the rounds of adaptivity forkP\+kVk\_\{P\}\+k\_\{V\}rounds\. Thus𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}hasτP′\\tau\_\{P\}^\{\\prime\}\-query complexity\(kP\+kV,BP\+BV\)\(k\_\{P\}\+k\_\{V\},B\_\{P\}\+B\_\{V\}\)\. Meanwhile,𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}only checks the statistical validity of the proposed verifier’s queries in a single batch to𝒪𝖵𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}, so it hasτV′\\tau\_\{V\}^\{\\prime\}\-query complexity\(1,BV\)\(1,B\_\{V\}\)\. Therefore part \(c\) holds\.

Next, we analyze run time\.𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}just simulates the entire interaction\(P𝒪𝖯𝖼𝖺𝗇,V𝒪𝖯𝖼𝖺𝗇\)\(P^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\},V^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\}\)\. While𝒪𝖯𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}operates atτP′\\tau\_\{P\}^\{\\prime\}accuracy, in order to meet the\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-learning guarantee of the original protocol,𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}simulatesPPrunning atτP\\tau\_\{P\}accuracy andVVrunning atτV\\tau\_\{V\}accuracy\. So𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}runs in timeO​\(TV​\(τV\)\+TP​\(τP\)\)O\(T\_\{V\}\(\\tau\_\{V\}\)\+T\_\{P\}\(\\tau\_\{P\}\)\)\. Similarly,𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}simulatesVVbut using transcriptπ\\piand running atτV\\tau\_\{V\}accuracy\. So𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}runs in timeO​\(TV​\(τV\)\)O\(T\_\{V\}\(\\tau\_\{V\}\)\), and part \(d\) holds\.

Now, we analyze the𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}’s communication complexity\. In the description of Protocol[3](https://arxiv.org/html/2607.15528#algorithm3),𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}implicitly sends the entire transcriptπ\\piof the simulation of\(P,V\)\(P,V\), which comprises of the queries𝒒V\\bm\{q\}\_\{V\}and answers𝒂V\\bm\{a\}\_\{V\}ofVV, public coins𝒓~\\tilde\{\\bm\{r\}\}ofVV, non\-random messages𝒔\\bm\{s\}fromVVtoPP, and messages𝒎\\bm\{m\}fromPPtoVV\. However, strictly speaking𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}does not need to relay𝒒V\\bm\{q\}\_\{V\},𝒓~\\tilde\{\\bm\{r\}\}, and𝒔\\bm\{s\}\.𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}already has the true public coins\(r1,…,rℓ\)\(r\_\{1\},\\ldots,r\_\{\\ell\}\), and can simulateVVusing that,𝒂V\\bm\{a\}\_\{V\}and𝒎\\bm\{m\}to generate the missing𝒒V\\bm\{q\}\_\{V\}and𝒔\\bm\{s\}\. Therefore, we can simplify𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}’s communication complexity to just𝒂V\\bm\{a\}\_\{V\}and𝒔\\bm\{s\}\. Then note\|𝒂V\|=O​\(BV​log⁡\(1/τP′\)\)\|\\bm\{a\}\_\{V\}\|=O\(B\_\{V\}\\log\(1/\\tau\_\{P\}^\{\\prime\}\)\)\. And\|𝒔\|=cP\|\\bm\{s\}\|=c\_\{P\}, the communication complexity ofPP\. So𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}’s communication complexity isO\(BVlog\(1/τP′\)\+cPO\(B\_\{V\}\\log\(1/\\tau\_\{P\}^\{\\prime\}\)\+c\_\{P\}, and part \(e\) holds\.

To complete the lemma, we show that\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)is a public\-coin SQ protocol that\(τP′,τV′,γ\)\(\\tau\_\{P\}^\{\\prime\},\\tau\_\{V\}^\{\\prime\},\\gamma\)\-SQ verifies𝒢\\mathcal\{G\}\. First, observe that𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}sends all random coins generated for theℓ\\ellrounds of communication, so it is public\-coin\. As noted in part \(c\),𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}employs aτP′\\tau\_\{P\}^\{\\prime\}\-accurate SQ oracle, and𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}employs aτV′\\tau\_\{V\}^\{\\prime\}\-accurate SQ oracle\. So what remains to be shown is that the canonical transformation preserves1−γ1\-\\gammacompleteness andγ\\gammasoundness\.

*Completeness:*Assume𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}, and consider the honest protocol\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)whose interaction generates\(h,π\)\(h,\\pi\)\. First, we note that in the honest protocol,π\\piis well\-formatted, so the canonical verifier can parseπ\\piinto\(𝒒V,𝒂V,𝒓~,𝒔,𝒎\)\(\\bm\{q\}\_\{V\},\\bm\{a\}\_\{V\},\\tilde\{\\bm\{r\}\},\\bm\{s\},\\bm\{m\}\)and successfully check thatπ\\piis consistent with an execution of\(P,V\)\(P,V\)that outputshh\. That is,VV, using randomness𝒓~\\tilde\{\\bm\{r\}\}receiving evaluations𝒂V\\bm\{a\}\_\{V\}and messages𝒎\\bm\{m\}, will make queries𝒒V\\bm\{q\}\_\{V\}, send messages𝒔\\bm\{s\}, and output the hypothesishh\. This works since𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}will properly simulate\(P,V\)\(P,V\)and relay the transcript to𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}\.

Second, we show that𝒂\\bm\{a\}passes the canonical verifier’s statistical validation𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾​\(𝒒V,𝒂V,τV/3,τV\)\\mathsf\{Validate\}\(\\bm\{q\}\_\{V\},\\bm\{a\}\_\{V\},\\tau\_\{V\}/3,\\tau\_\{V\}\), according to𝒪𝖵𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}\. Recall that𝒪𝖯𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}isτP′\\tau\_\{P\}^\{\\prime\}\-accurate for𝒟P\\mathcal\{D\}\_\{P\}\(which is equal to𝒟V\\mathcal\{D\}\_\{V\}by assumption\) andτP′≤τV′\\tau\_\{P\}^\{\\prime\}\\leq\\tau\_\{V\}^\{\\prime\}\. Similarly,𝒪𝖵𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}isτV′\\tau\_\{V\}^\{\\prime\}\-accurate for𝒟V\\mathcal\{D\}\_\{V\}andτV′=τV/3\\tau\_\{V\}^\{\\prime\}=\\tau\_\{V\}/3\. Thus, by the specification of𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾\\mathsf\{Validate\}\(which uses an argument via triangle inequality\), statistical validation passes\. Additionally since𝒓~\\tilde\{\\bm\{r\}\}is generated via𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}’s random coins\(r1,…,rℓ\)\(r\_\{1\},\\ldots,r\_\{\\ell\}\), in all𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}will always accept unlessh=⊥h=\\bot\.

Thus, it is sufficient to argue that, under the honest protocol,h∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at least1−γ1\-\\gamma\. Recall thathhis the output of simulating\(P𝒪𝖯𝖼𝖺𝗇,V𝒪𝖯𝖼𝖺𝗇\)\(P^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\},V^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\}\)on randomness𝒓~\\tilde\{\\bm\{r\}\}\. Since𝒪𝖯𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}is aτP′\\tau\_\{P\}^\{\\prime\}\-accurate for𝒟P\\mathcal\{D\}\_\{P\}andτP′≤τP\\tau\_\{P\}^\{\\prime\}\\leq\\tau\_\{P\}, then the simulatedPPhas access to aτP\\tau\_\{P\}\-accurate oracle for𝒟P\\mathcal\{D\}\_\{P\}\. Similarly, since𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}by assumption,τP′≤τV\\tau\_\{P\}^\{\\prime\}\\leq\\tau\_\{V\}, and𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}knows all random coins sent by𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}, then the simulatedVVhas access to a public\-stateτV\\tau\_\{V\}\-accurate oracle for𝒟V\\mathcal\{D\}\_\{V\}\. Since randomness is uniform and generated in epochs according to the canonical verifier, the simulation of\(P𝒪𝖯𝖼𝖺𝗇,V𝒪𝖵𝖼𝖺𝗇​\(𝒓~\)\)\(P^\{\\mathcal\{O\}\_\{\\mathsf\{P\}\_\{\\mathsf\{can\}\}\}\},V^\{\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}\}\(\\tilde\{\\bm\{r\}\}\)\)is indistinguishable from a true execution of\(P,V\)\(P,V\)\. Since\(P,V\)\(P,V\)\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-SQ verifies𝒢\\mathcal\{G\}, thenh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at least1−γ1\-\\gamma\. Thus, completeness of\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)is1−γ1\-\\gamma\.

*Universal Soundness:*It suffices to show that universal soundness of𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}reduces to the universal soundnessVV\. Take any cheating prover strategyP~𝖼𝖺𝗇\\tilde\{P\}\_\{\\mathsf\{can\}\}for𝖵𝖼𝖺𝗇𝒪𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}^\{\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}\}\. We construct a cheating proverP~\\tilde\{P\}and oracleO~V\\tilde\{O\}\_\{V\}forVVas follows\. We will argue anytimeP~𝖼𝖺𝗇\\tilde\{P\}\_\{\\mathsf\{can\}\}cheat, then\(P~,O~V\)\(\\tilde\{P\},\\tilde\{O\}\_\{V\}\)cheats as well\. Without loss of generality, letP~𝖼𝖺𝗇\\tilde\{P\}\_\{\\mathsf\{can\}\}be deterministic\. LetP~\\tilde\{P\}and𝒪~V\\tilde\{\\mathcal\{O\}\}\_\{V\}each simulateP~𝖼𝖺𝗇\\tilde\{P\}\_\{\\mathsf\{can\}\}, where the randomness of each epoch ofVVis used as input\. If the simulation ofP~𝖼𝖺𝗇\\tilde\{P\}\_\{\\mathsf\{can\}\}produces a valid transcriptπ=\(𝒒V,𝒂V,𝒓~,𝒔,𝒎\)\\pi=\(\\bm\{q\}\_\{V\},\\bm\{a\}\_\{V\},\\tilde\{\\bm\{r\}\},\\bm\{s\},\\bm\{m\}\), then𝒪~V\\tilde\{\\mathcal\{O\}\}\_\{V\}responds as the answers𝒂V=\(a1,a2,…,aBV\)\\bm\{a\}\_\{V\}=\(a\_\{1\},a\_\{2\},\\ldots,a\_\{B\_\{V\}\}\)andP~\\tilde\{P\}responds as the messages𝒎=\(m1,m2,…\)\\bm\{m\}=\(m\_\{1\},m\_\{2\},\\ldots\)\. To ensure that𝒪~V\\tilde\{\\mathcal\{O\}\}\_\{V\}is aτV\\tau\_\{V\}\-accurate oracle for𝒟V\\mathcal\{D\}\_\{V\}, any answeraawhich isτ\\tau\-far from the true expectation for𝒟V\\mathcal\{D\}\_\{V\}will be replaced with an arbitraryτV\\tau\_\{V\}\-accurate answer for𝒟V\\mathcal\{D\}\_\{V\}\. In the case whereP~𝖼𝖺𝗇\\tilde\{P\}\_\{\\mathsf\{can\}\}does not produce a valid transcript, thenP~\\tilde\{P\}will always reply with a well\-formed dummy message and𝒪~V\\tilde\{\\mathcal\{O\}\}\_\{V\}will always reply with aτV\\tau\_\{V\}\-accurate answer\.

We now reduce from between\(P~𝖼𝖺𝗇,𝖵𝖼𝖺𝗇𝒪𝖵𝖼𝖺𝗇\)\(\\tilde\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}^\{\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}\}\)and\(P~,V𝒪~V\)\(\\tilde\{P\},V^\{\\tilde\{\\mathcal\{O\}\}\_\{V\}\}\)\. Let the random coins of𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}andVVbe the same random coins\. Let us condition on the event that\(P~𝖼𝖺𝗇,𝖵𝖼𝖺𝗇𝒪𝖵𝖼𝖺𝗇\)\(\\tilde\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}^\{\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}\}\)accepts\. ThenP~𝖼𝖺𝗇\\tilde\{P\}\_\{\\mathsf\{can\}\}must have produced a valid transcriptπ=\(𝒒V,𝒂V,𝒓~,𝒔,𝒎\)\\pi=\(\\bm\{q\}\_\{V\},\\bm\{a\}\_\{V\},\\tilde\{\\bm\{r\}\},\\bm\{s\},\\bm\{m\}\)and a hypothesish≠⊥h\\neq\\botwhereπ\\picorresponds to a simulation ofVVthat produceshh\. Further,𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾​\(𝒒V,𝒂V,τV/3,τV\)\\mathsf\{Validate\}\(\\bm\{q\}\_\{V\},\\bm\{a\}\_\{V\},\\tau\_\{V\}/3,\\tau\_\{V\}\)passed\. Then𝒂V\\bm\{a\}\_\{V\}are2​τV/32\\tau\_\{V\}/3\-close to the answers from𝒪𝖵𝖼𝖺𝗇​\(𝒒V\)\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}\(\\bm\{q\}\_\{V\}\)\. Since𝒪𝖵𝖼𝖺𝗇\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}isτV/3\\tau\_\{V\}/3\-accurate for𝒟V\\mathcal\{D\}\_\{V\}, then by triangle inequality,𝒂V\\bm\{a\}\_\{V\}areτV\\tau\_\{V\}\-accurate for𝒟V\\mathcal\{D\}\_\{V\}\.

Since the random coins are shared between𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}andVV,\(h,π\)\(h,\\pi\), as generated above, is also the output ofP~\\tilde\{P\}and𝒪~V\\tilde\{\\mathcal\{O\}\}\_\{V\}’s simulation ofP~𝖼𝖺𝗇\\tilde\{P\}\_\{\\mathsf\{can\}\}\. Recall that we are conditioning on the event that the𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}accepts\. Thus, all answers𝒂V\\bm\{a\}\_\{V\}areτV\\tau\_\{V\}\-accurate for𝒟V\\mathcal\{D\}\_\{V\}, and all messages𝒎\\bm\{m\}are well\-formed\. Thus,P~\\tilde\{P\}sends messages𝒎\\bm\{m\}, andO~V\\tilde\{O\}\_\{V\}provides answers𝒂V\\bm\{a\}\_\{V\}\. Therefore, the view of the verifier in\(P~,V𝒪V\)\(\\tilde\{P\},V^\{\\mathcal\{O\}\_\{V\}\}\)is indistinguishable from𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}simulation ofVVusingπ\\pi\. Since𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}accepted and outputhh, thenVVmust have accepted and also outputhh\.

Suppose that\(P~𝖼𝖺𝗇,𝖵𝖼𝖺𝗇𝒪𝖵𝖼𝖺𝗇\)\(\\tilde\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}^\{\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}\}\)accepts and outputsh∉𝒢​\(𝒟V\)h\\notin\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probabilityγ′\\gamma^\{\\prime\}\. Then by monotonicity,\(P~,V𝒪~V\)\(\\tilde\{P\},V^\{\\tilde\{\\mathcal\{O\}\}\_\{V\}\}\)accepts and outputsh∉𝒢​\(𝒟V\)h\\notin\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at leastγ′\\gamma^\{\\prime\}\. But\(P~,V𝒪~V\)\(\\tilde\{P\},V^\{\\tilde\{\\mathcal\{O\}\}\_\{V\}\}\)accepts and outputsh∉𝒢​\(𝒟V\)h\\notin\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at mostγ\\gammaby universal soundness of\(P,V\)\(P,V\)\. Therefore,γ′≤γ\\gamma^\{\\prime\}\\leq\\gamma\. Since this holds over all𝒟V\\mathcal\{D\}\_\{V\}andτV/3\\tau\_\{V\}/3\-accurate oracles𝒪V\\mathcal\{O\}\_\{V\}for𝒟V\\mathcal\{D\}\_\{V\}, then\(P~𝖼𝖺𝗇,𝖵𝖼𝖺𝗇𝒪𝖵𝖼𝖺𝗇\)\(\\tilde\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}^\{\\mathcal\{O\}\_\{\\mathsf\{V\}\_\{\\mathsf\{can\}\}\}\}\)accepts and outputsh∉𝒢​\(𝒟V\)h\\notin\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at mostγ\\gamma\. So\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)satisfies universal soundnessγ\\gamma\. ∎

### 4\.3pvCSVs from the Canonical Protocol and Fiat\-Shamir

Next, we construct pvCSVs for SQ computations that use randomness\. Specifically, we compile the canonical Protocol[3](https://arxiv.org/html/2607.15528#algorithm3)from above into non\-interactive SQ protocols using a Fiat\-Shamir transformation\[[FS86](https://arxiv.org/html/2607.15528#bib.bib35)\]\. We prove soundness of the transformation in the Random Oracle Model \(ROM\), which allows us to replace the public coins of the verifier with non\-interactive calls to the random oracle\. We begin with preliminaries defining correctness and soundness in the ROM\. Then, we describe our Fiat\-Shamir transformation over canonical SQ protocols in Protocol[4](https://arxiv.org/html/2607.15528#algorithm4)\.

#### pvCSVs in the ROM\.

In the Random Oracle Model\[[BR93](https://arxiv.org/html/2607.15528#bib.bib36)\], both the prover and verifier have query access to a shared random function called the random oraclef:\{0,1\}∗→\{0,1\}mf:\\\{0,1\\\}^\{\*\}\\to\\\{0,1\\\}^\{m\}for some output sizem∈ℕm\\in\\mathbb\{N\}\. Completeness and soundness take probabilities over the sampling of the random oracle which is denotedf←𝒰f\\leftarrow\\mathcal\{U\}\. Furthermore, we restrict the cheating prover to at mostt∈ℕt\\in\\mathbb\{N\}queries of the random oracle, called the random oracle budget, typically taken to be polynomial in some security parameter\. We adapt Definition[3\.2](https://arxiv.org/html/2607.15528#S3.Thmtheorem2)of pvCSVs to define computationally\-sound pvCSVs in the ROM\.

###### Definition 4\.8\(pvCSV in the ROM\)\.

Let𝒢\\mathcal\{G\},τP,τV\>0\\tau\_\{P\},\\tau\_\{V\}\>0,γ𝖼𝗌𝗏\>0\\gamma\_\{\\mathsf\{csv\}\}\>0, and\(𝖯𝖼𝗌𝗏,𝖵𝖼𝗌𝗏\)\(\\mathsf\{P\}\_\{\\mathsf\{csv\}\},\\mathsf\{V\}\_\{\\mathsf\{csv\}\}\)be defined in the setup of Definition[3\.2](https://arxiv.org/html/2607.15528#S3.Thmtheorem2)\. The pvCSV prover𝖯𝖼𝗌𝗏\\mathsf\{P\}\_\{\\mathsf\{csv\}\}and verifier𝖵𝖼𝗌𝗏\\mathsf\{V\}\_\{\\mathsf\{csv\}\}are given query\-access to a random oracleff\. The pvCSV\(τP,τV,γ,γ′\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma,\\gamma^\{\\prime\}\)\-certifies𝒢\\mathcal\{G\}in the ROMif the following guarantees hold:

- •γ\\gamma\-Completeness in the ROM: if𝒟P=𝒟V\\mathcal\{D\}\_\{P\}=\\mathcal\{D\}\_\{V\}, then for any verifier distribution𝒟V\\mathcal\{D\}\_\{V\},τV\\tau\_\{V\}\-accurate oracle𝒪V\\mathcal\{O\}\_\{V\}for𝒟V\\mathcal\{D\}\_\{V\},τP\\tau\_\{P\}\-accurate oracle𝒪P\\mathcal\{O\}\_\{P\}for𝒟V\\mathcal\{D\}\_\{V\}, over sampling of the random oracleff, random coins of𝖯𝖼𝗌𝗏\\mathsf\{P\}\_\{\\mathsf\{csv\}\}and𝖵𝖼𝗌𝗏\\mathsf\{V\}\_\{\\mathsf\{csv\}\}, the honest prover can generate a hypothesis\-certificate pair\(h,π\)←𝖯𝖼𝗌𝗏𝒪P,f\(h,\\pi\)\\leftarrow\\mathsf\{P\}\_\{\\mathsf\{csv\}\}^\{\\mathcal\{O\}\_\{P\},f\}such that𝖵𝖼𝗌𝗏𝒪V,f\\mathsf\{V\}\_\{\\mathsf\{csv\}\}^\{\\mathcal\{O\}\_\{V\},f\}accepts andh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at least1−γ1\-\\gamma\. That is, ∀𝒟V,𝒪V,𝒪P\.Pr⁡\[𝖵𝖼𝗌𝗏𝒪V,f​\(h,π\)=1∧h∈𝒢​\(𝒟V\)\|f←𝒰,random coins of𝖯𝖼𝗌𝗏and𝖵𝖼𝗌𝗏,\(h,π\)←𝖯𝖼𝗌𝗏𝒪P,f\]≥1−γ\\forall\\mathcal\{D\}\_\{V\},\\mathcal\{O\}\_\{V\},\\mathcal\{O\}\_\{P\}\.\\ \\operatorname\*\{\\textnormal\{\\bf Pr\}\}\\left\[\\begin\{array\}\[\]\{l\}\\mathsf\{V\}\_\{\\mathsf\{csv\}\}^\{\\mathcal\{O\}\_\{V\},f\}\(h,\\pi\)=1\\\\ \\land\\ h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)\\end\{array\}\\left\|\\begin\{array\}\[\]\{l\}f\\leftarrow\\mathcal\{U\},\\\\ \\text\{random coins of $\\mathsf\{P\}\_\{\\mathsf\{csv\}\}$ and $\\mathsf\{V\}\_\{\\mathsf\{csv\}\}$\},\\\\ \(h,\\pi\)\\leftarrow\\mathsf\{P\}\_\{\\mathsf\{csv\}\}^\{\\mathcal\{O\}\_\{P\},f\}\\end\{array\}\\right\.\\right\]\\geq 1\-\\gamma
- •γ′\\gamma^\{\\prime\}\-Universal Soundness in the ROM: for any verifier distribution𝒟V\\mathcal\{D\}\_\{V\}andτV\\tau\_\{V\}\-accurate oracle𝒪V\\mathcal\{O\}\_\{V\}for𝒟V\\mathcal\{D\}\_\{V\}, for any random oracle budgett∈ℕt\\in\\mathbb\{N\}, for anytt\-query prover strategyP~𝖼𝗌𝗏\\tilde\{P\}\_\{\\mathsf\{csv\}\}, for\(h,π\)←P~𝖼𝗌𝗏𝒪V,f\(h,\\pi\)\\leftarrow\\tilde\{P\}\_\{\\mathsf\{csv\}\}^\{\\mathcal\{O\}\_\{V\},f\}, thenV𝒪VV^\{\\mathcal\{O\}\_\{V\}\}rejects orh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)with probability at least1−γ′​\(t\)1\-\\gamma^\{\\prime\}\(t\)over sampling of the random oracleff, random coins of𝖵𝖼𝗌𝗏\\mathsf\{V\}\_\{\\mathsf\{csv\}\}\. That is, ∀𝒟V,𝒪V,P~𝖼𝗌𝗏\.Pr⁡\[𝖵𝖼𝗌𝗏𝒪V,f​\(h,π\)=0∨h∈𝒢​\(𝒟V\)\|f←𝒰,random coins ofV,\(h,π\)←P~𝖼𝗌𝗏𝒪V,f\]≥1−γ′​\(t\)\\forall\\mathcal\{D\}\_\{V\},\\mathcal\{O\}\_\{V\},\\tilde\{P\}\_\{\\mathsf\{csv\}\}\.\\ \\operatorname\*\{\\textnormal\{\\bf Pr\}\}\\left\[\\begin\{array\}\[\]\{l\}\\mathsf\{V\}\_\{\\mathsf\{csv\}\}^\{\\mathcal\{O\}\_\{V\},f\}\(h,\\pi\)=0\\\\ \\lor\\ h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)\\end\{array\}\\left\|\\begin\{array\}\[\]\{l\}f\\leftarrow\\mathcal\{U\},\\\\ \\text\{random coins of $V$\},\\\\ \(h,\\pi\)\\leftarrow\\tilde\{P\}\_\{\\mathsf\{csv\}\}^\{\\mathcal\{O\}\_\{V\},f\}\\end\{array\}\\right\.\\right\]\\geq 1\-\\gamma^\{\\prime\}\(t\)

We denote ROM soundness againsttt\-query provers asγ′​\(t\)\\gamma^\{\\prime\}\(t\)whereγ′\\gamma^\{\\prime\}is a function andt∈ℕt\\in\\mathbb\{N\}is the random oracle query budget\. Additionally, since soundness is parameterized whereas completeness is not, we split completeness and soundness error into\(γ,γ′\)\(\\gamma,\\gamma^\{\\prime\}\)\.

#### Applying Fiat\-Shamir to the Canonical Protocol\.

We transform the Canonical SQ protocol\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)into a pvCSV in the ROM by applying the Fiat\-Shamir transformation to the initial phase of public\-coin interaction\. As is standard in Fiat\-Shamir, the canonical verifier’s randomness in theii\-th round is the query of the random oracle with the partial transcript of interaction up to roundii\. We describe the resulting protocol\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\)in Protocol[4](https://arxiv.org/html/2607.15528#algorithm4)\. The honest prover𝖯𝖥𝖲\\mathsf\{P\}\_\{\\mathsf\{FS\}\}simulates the interaction\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)where𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}’s randomness is sampled via the random oracleff\. Then, the verifier𝖵𝖥𝖲\\mathsf\{V\}\_\{\\mathsf\{FS\}\}runs the second and third phase of the canonical protocol as before, checking the correctness of the computational simulation and the statistical validity of the relevant SQs via a batch evaluation of the queries of𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}\.

Setup:Let

\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)be a canonical SQ protocol that

τ\\tau\-SQ verifies

𝒢\\mathcal\{G\}, where

- •𝖯𝖥𝖲\\mathsf\{P\}\_\{\\mathsf\{FS\}\}accesses aτ\\tau\-accurate SQ Oracle𝒪P\\mathcal\{O\}\_\{P\}for𝒟P\\mathcal\{D\}\_\{P\}\.
- •𝖵𝖥𝖲\\mathsf\{V\}\_\{\\mathsf\{FS\}\}accesses aτ\\tau\-accurate SQ Oracle𝒪V\\mathcal\{O\}\_\{V\}for𝒟V\\mathcal\{D\}\_\{V\}\.
- •ℓ\\ellis the round complexity of\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)\.
- •Both𝖯𝖥𝖲\\mathsf\{P\}\_\{\\mathsf\{FS\}\}and𝖵𝖥𝖲\\mathsf\{V\}\_\{\\mathsf\{FS\}\}have access to a random oracleff\.

1ex

Prover

𝖯𝖥𝖲𝒪P,f\\mathsf\{P\}\_\{\\mathsf\{FS\}\}^\{\\mathcal\{O\}\_\{P\},f\}:

Initialize an empty transcript

π0=⟨⟩\\pi\_\{0\}=\\langle\\rangle
Simulate the interaction

\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)as follows:

for*i=1,…,ℓi=1,\\ldots,\\ell*do

𝖯𝖼𝖺𝗇𝒪P\\mathsf\{P\}\_\{\\mathsf\{can\}\}^\{\\mathcal\{O\}\_\{P\}\}sends

𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}a message

mim\_\{i\}
Generate

𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}’s randomness at the

ii\-th round as

ri:=f​\(⟨m1,…,mi⟩\)r\_\{i\}:=f\(\\langle m\_\{1\},\\ldots,m\_\{i\}\\rangle\)
𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}sends

rir\_\{i\}to

𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}
Update

πi:=⟨πi−1,mi,ri⟩\\pi\_\{i\}:=\\langle\\pi\_\{i\-1\},m\_\{i\},r\_\{i\}\\rangle
end for

Let

π:=πℓ\\pi:=\\pi\_\{\\ell\}
Send

π\\pitoVerifier

𝖵𝖥𝖲\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\.

1ex

Verifier

𝖵𝖥𝖲𝒪V,f\\mathsf\{V\}\_\{\\mathsf\{FS\}\}^\{\\mathcal\{O\}\_\{V\},f\}:

Parse the transcript

π\\pias

- •𝒎=\(m1,m2,…,mℓ\)\\bm\{m\}=\(m\_\{1\},m\_\{2\},\\ldots,m\_\{\\ell\}\)purported messages from𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}
- •𝒓=\(r1,r2,…,rℓ\)\\bm\{r\}=\(r\_\{1\},r\_\{2\},\\ldots,r\_\{\\ell\}\)purported generated randomness for𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}

for*i=1,…,ℓi=1,\\ldots,\\ell*do

if*ri≠f​\(⟨m1,…,mi⟩\)r\_\{i\}\\neq f\(\\langle m\_\{1\},\\ldots,m\_\{i\}\\rangle\)*then

Reject and output

⊥\\bot
end for

ExecutePhase 2andPhase 3of

𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}
if*either phase fails*then

Reject and output

⊥\\bot\.

Accept and output

hh\.

Protocol 4Non\-Interactive SQ Protocol in Random Oracle ModelThe correctness of the resulting pvCSV follows from the state restoration argument of\[[BCS16](https://arxiv.org/html/2607.15528#bib.bib12)\], with some subtleties that arise in the SQ protocol setting\. The structure of the Canonical protocol simplifies the analysis considerably: the protocol naturally divides into a phase of public\-coin interaction, followed by \(computational and statistical\) verification of the transcript\. Completeness of the protocol follows from completeness of Protocol[3](https://arxiv.org/html/2607.15528#algorithm3), since the honest prover can execute the same sequence of queries and computations\. Thus, we focus on establishing soundness\.

There are two key aspects of Protocol[4](https://arxiv.org/html/2607.15528#algorithm4)that require us to be careful in establishing soundness of the transformation\. First, in our setting, the cheating prover has considerable powers related to the statistical learning problem, with full knowledge of the underlying distribution𝒟\\mathcal\{D\}and access to the verifier’s SQ oracle\. But, importantly, the cheating prover in the Fiat\-Shamir protocol and Canonical protocol are afforded the same powers\. The approach of establishing Fiat\-Shamir soundness via state restoration is a black\-box reduction, so we can apply the same argument even in our setting where the provers have non\-standard computational and statistical powers\. Second, our application of Fiat\-Shamir is used to generate a legitimate prover\-verifier transcript, which produces a hypothesishh, rather than directly certifying a known predicate \(e\.g\., certifying a givenh∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)\)\. That said, once we have a sound transcript, Phase 2 and Phase 3 of the original protocol allow us to validate that thehhis actually good for the verifier’s distribution\.

Specifically, we invoke the following guarantee about the Fiat\-Shamir transformation applied to public\-coin protocols\.

###### Theorem 4\.9\(Corollary of Lemma 13\.2\.7 and Theorem 14\.3\.1 of\[[CY24](https://arxiv.org/html/2607.15528#bib.bib51)\]\)\.

Let\(P,V\)\(P,V\)be a public\-coin interactive protocol with round complexityℓ\\elland soundnessγ\\gamma\. Let\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\)be the Fiat\-Shamir transformed protocol, and suppose it hasγ𝖥𝖲\\gamma\_\{\\mathsf\{FS\}\}soundness in the ROM\. There is a black\-box reduction that establishes the following upper bound on soundness of\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\)in terms of soundness of\(P,V\)\(P,V\), round complexityℓ\\ell, and random oracle budgett∈ℕt\\in\\mathbb\{N\}\.

γ𝖥𝖲​\(t\)≤\(t\+ℓℓ\)​γ\\gamma\_\{\\mathsf\{FS\}\}\(t\)\\leq\\binom\{t\+\\ell\}\{\\ell\}\\gamma

Specifically, the reduction goes through a state restoration game and demonstrates how, given a cheating prover for the Fiat\-Shamir proof system𝖯~𝖥𝖲\\tilde\{\\mathsf\{P\}\}\_\{\\mathsf\{FS\}\}, there exists a cheating proverP~\\tilde\{P\}for the original interactive protocol that makes calls to𝖯~𝖥𝖲\\tilde\{\\mathsf\{P\}\}\_\{\\mathsf\{FS\}\}, at a\(t\+ℓℓ\)\\binom\{t\+\\ell\}\{\\ell\}\-factor loss in success probability\. With this fact, we establish the correctness of Protocol[4](https://arxiv.org/html/2607.15528#algorithm4)\.

###### Lemma 4\.10\(Fiat\-Shamir for Canonical Protocol\)\.

Fix𝒢\\mathcal\{G\},τP,τV\>0\\tau\_\{P\},\\tau\_\{V\}\>0,γ𝖼𝖺𝗇\>0\\gamma\_\{\\mathsf\{can\}\}\>0, and canonical SQ protocol\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)that\(τP,τV,γ𝖼𝖺𝗇\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\_\{\\mathsf\{can\}\}\)\-verifies𝒢\\mathcal\{G\}with round complexityℓ\\ell\. Then the Fiat\- Shamir transformed protocol\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\), described in Protocol[4](https://arxiv.org/html/2607.15528#algorithm4), is a pvCSV that\(τP,τV,γ𝖼𝖺𝗇,\(t\+ℓℓ\)​γ𝖼𝖺𝗇\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\_\{\\mathsf\{can\}\},\{t\+\\ell\\choose\\ell\}\\gamma\_\{\\mathsf\{can\}\}\)\-certifies𝒢\\mathcal\{G\}in the ROM wheret∈ℕt\\in\\mathbb\{N\}is the random oracle budget\.

###### Proof sketch\.

Completeness is immediate, by the fact that the random oracle calls are identically distributed to the challenges sent by the public\-coin verifier\. Thus, the honest prover generates a transcript from the same distribution as the honest execution of Protocol[3](https://arxiv.org/html/2607.15528#algorithm3)\.

Soundness follows by Theorem[4\.9](https://arxiv.org/html/2607.15528#S4.Thmtheorem9)applied to Phase 1 of Protocol[3](https://arxiv.org/html/2607.15528#algorithm3)\. In particular, the black\-box reduction allows us to convert any cheating prover for Protocol[4](https://arxiv.org/html/2607.15528#algorithm4)𝖯~𝖥𝖲\\tilde\{\\mathsf\{P\}\}\_\{\\mathsf\{FS\}\}into a cheating prover for Protocol[3](https://arxiv.org/html/2607.15528#algorithm3)𝖯~𝖼𝖺𝗇\\tilde\{\\mathsf\{P\}\}\_\{\\mathsf\{can\}\}\. While the provers are afforded non\-standard SQ oracles and knowledge of the distribution, the Canonical interactive prover𝖯~𝖼𝖺𝗇\\tilde\{\\mathsf\{P\}\}\_\{\\mathsf\{can\}\}has the same oracle access as the Fiat\-Shamir prover𝖯~𝖥𝖲\\tilde\{\\mathsf\{P\}\}\_\{\\mathsf\{FS\}\}, so𝖯~𝖼𝖺𝗇\\tilde\{\\mathsf\{P\}\}\_\{\\mathsf\{can\}\}can implement the black\-box calls to𝖯~𝖥𝖲\\tilde\{\\mathsf\{P\}\}\_\{\\mathsf\{FS\}\}in the reduction\. Thus, converting the interactive SQ protocol into a non\-interactive protocol is sound up to theγ𝖥𝖲​\(t\)≤\(t\+ℓℓ\)​γ𝖼𝖺𝗇\\gamma\_\{\\mathsf\{FS\}\}\(t\)\\leq\\binom\{t\+\\ell\}\{\\ell\}\\gamma\_\{\\mathsf\{can\}\}loss as stated in Theorem[4\.9](https://arxiv.org/html/2607.15528#S4.Thmtheorem9)\. In particular, the Fiat\-Shamir protocol generates a legitimate transcript of the original Canonical protocol, with all butγ𝖥𝖲​\(t\)\\gamma\_\{\\mathsf\{FS\}\}\(t\)soundness error\.

Finally, we argue that in the SQ model, the verifier’s additional checks establish thath∈𝒢​\(𝒟V\)h\\in\\mathcal\{G\}\(\\mathcal\{D\}\_\{V\}\)or result in rejection\. After the non\-interactive simulation of the interactive Phase 1, the verifier additionally executes Phase 2 and Phase 3 of Protocol[3](https://arxiv.org/html/2607.15528#algorithm3)\. Phase 2 certifies that the transcript is a legitimate execution of the SQ protocol \(based on the responses to statistical queries\) and Phase 3 validates that the query responses are statistically correct\. In the SQ model, these checks contribute zero additional soundness error\. Thus, the upper bound on soundness holds as claimed\. ∎

#### pvCSVs for all mixed\-message protocols with public\-verifier state\.

We conclude with a statement of the overall pvCSV guarantee established in this section within the ROM\. In Lemma[4\.7](https://arxiv.org/html/2607.15528#S4.Thmtheorem7), we argue that for the class of mixed\-message, private\-query SQ protocols with public verifier state can be transformed into a Canonical public\-coin SQ protocol\. Then, in Lemma[4\.10](https://arxiv.org/html/2607.15528#S4.Thmtheorem10), we apply the Fiat\-Shamir transform to turn any Canonical protocol into a pvCSV in the ROM\. Chaining these lemmas together, we obtain the following theorem\.

###### Theorem 4\.11\.

Fix𝒢\\mathcal\{G\},τP,τV\>0\\tau\_\{P\},\\tau\_\{V\}\>0,γ\>0\\gamma\>0, and a mixed\-message, private\-query SQ protocol\(P,V\)\(P,V\)with public verifier state\. LetτP′=min⁡\{τP,τV/3\}\\tau\_\{P\}^\{\\prime\}=\\min\\\{\\tau\_\{P\},\\tau\_\{V\}/3\\\}andτV′=τV/3\\tau\_\{V\}^\{\\prime\}=\\tau\_\{V\}/3\. Suppose\(P,V\)\(P,V\)\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-verifies𝒢\\mathcal\{G\}\. Applying the canonical transformation described in Protocol[3](https://arxiv.org/html/2607.15528#algorithm3), and then the Fiat\-Shamir transformation, described in Protocol[4](https://arxiv.org/html/2607.15528#algorithm4), yields a pvCSV\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\)that certifies𝒢\\mathcal\{G\}with the following characteristics:

1. \(a\)ForVVwith epoch complexityℓ\\ell,\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\)\(τP′,τV′,γ,\(t\+ℓℓ\)​γ\)\(\\tau\_\{P\}^\{\\prime\},\\tau\_\{V\}^\{\\prime\},\\gamma,\{t\+\\ell\\choose\\ell\}\\gamma\)\-certifies𝒢\\mathcal\{G\}in the ROM\.
2. \(b\)𝖵𝖥𝖲\\mathsf\{V\}\_\{\\mathsf\{FS\}\}uses a non\-adaptive SQ oracle, regardless of the SQ adaptivity in\(P,V\)\(P,V\)\. That is, supposeVVhasτV\\tau\_\{V\}\-query complexity\(kV,BV\)\(k\_\{V\},B\_\{V\}\)andPPhasτP\\tau\_\{P\}\-query complexity\(kP,BP\)\(k\_\{P\},B\_\{P\}\); then, - •𝖵𝖥𝖲\\mathsf\{V\}\_\{\\mathsf\{FS\}\}hasτV′\\tau\_\{V\}^\{\\prime\}\-query complexity\(1,BV\)\(1,B\_\{V\}\); - •𝖯𝖥𝖲\\mathsf\{P\}\_\{\\mathsf\{FS\}\}hasτP′\\tau\_\{P\}^\{\\prime\}\-query complexity\(kP\+kV,BP\+BV\)\(k\_\{P\}\+k\_\{V\},B\_\{P\}\+B\_\{V\}\)
3. \(c\)𝖵𝖥𝖲\\mathsf\{V\}\_\{\\mathsf\{FS\}\}and𝖯𝖥𝖲\\mathsf\{P\}\_\{\\mathsf\{FS\}\}run in linear time in the original protocol\. That is, supposeVVruns in timeTV​\(τV\)T\_\{V\}\(\\tau\_\{V\}\)andPPruns in timeTP​\(τP\)T\_\{P\}\(\\tau\_\{P\}\); then - •𝖵𝖼𝖺𝗇\\mathsf\{V\}\_\{\\mathsf\{can\}\}runs in timeO​\(TV​\(τV\)\)O\(T\_\{V\}\(\\tau\_\{V\}\)\) - •𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}runs in timeO​\(TV​\(τV\)\+TP​\(τP\)\)O\(T\_\{V\}\(\\tau\_\{V\}\)\+T\_\{P\}\(\\tau\_\{P\}\)\)
4. \(d\)ForPPwith communication complexitycPc\_\{P\}, the certificate size\|π\|=O​\(BV​log⁡\(1/τP′\)\)\+cP\|\\pi\|=O\(B\_\{V\}\\log\(1/\\tau\_\{P\}^\{\\prime\}\)\)\+c\_\{P\}\.

###### Proof\.

Let\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)be the intermediate, canonical SQ protocol\. By Lemma[4\.7](https://arxiv.org/html/2607.15528#S4.Thmtheorem7),\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)\(τP′,τV′,γ\)\(\\tau\_\{P\}^\{\\prime\},\\tau\_\{V\}^\{\\prime\},\\gamma\)\-verifies𝒢\\mathcal\{G\}\. SinceVVhas epoch complexityℓ\\ell,\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)has round complexityℓ\\ell\. Therefore, by Lemma[4\.10](https://arxiv.org/html/2607.15528#S4.Thmtheorem10),\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\)\(τP′,τV′,γ,\(t\+ℓℓ\)​γ\)\(\\tau\_\{P\}^\{\\prime\},\\tau\_\{V\}^\{\\prime\},\\gamma,\{t\+\\ell\\choose\\ell\}\\gamma\)\-certifies𝒢\\mathcal\{G\}in the ROM\. So part \(a\) holds\.

Observe that the Fiat\-Shamir transformation from\(𝖯𝖼𝖺𝗇,𝖵𝖼𝖺𝗇\)\(\\mathsf\{P\}\_\{\\mathsf\{can\}\},\\mathsf\{V\}\_\{\\mathsf\{can\}\}\)to\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\)preserves many properties including the precision, query complexity, and runtime of the prover and verifier, \(at least while assuming unit cost for evaluating the random oracle\)\. Therefore, parts \(b\) and \(c\) follow directly from Lemma[4\.7](https://arxiv.org/html/2607.15528#S4.Thmtheorem7)\.

LetcPc\_\{P\}be the communication complexity ofPP\. By Lemma[4\.7](https://arxiv.org/html/2607.15528#S4.Thmtheorem7),𝖯𝖼𝖺𝗇\\mathsf\{P\}\_\{\\mathsf\{can\}\}’s communication complexity isO​\(BV​log⁡\(1/τP′\)\)\+cPO\(B\_\{V\}\\log\(1/\\tau\_\{P\}^\{\\prime\}\)\)\+c\_\{P\}\. After applying the Fiat\-Shamir transformation, the communication complexity is the canonical prover’s communication complexity\. So, part \(d\) holds\. ∎

By application of known implementations for adaptive and non\-adaptive SQ oracles in Proposition[2\.11](https://arxiv.org/html/2607.15528#S2.Thmtheorem11)and Proposition[2\.10](https://arxiv.org/html/2607.15528#S2.Thmtheorem10), we have the following\.

###### Corollary 4\.12\.

Let𝒢\\mathcal\{G\},τP\\tau\_\{P\},τV\\tau\_\{V\},γ\\gamma,\(P,V\)\(P,V\), pvCSV\(𝖯𝖥𝖲,𝖵𝖥𝖲\)\(\\mathsf\{P\}\_\{\\mathsf\{FS\}\},\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\)be defined as in the above theorem\. LetτP′=min⁡\{τP,τV/3\}\\tau\_\{P\}^\{\\prime\}=\\min\\\{\\tau\_\{P\},\\tau\_\{V\}/3\\\}\. Suppose that bothPPandVVmake fully\-adaptive queries, that is,kP=BPk\_\{P\}=B\_\{P\}andkV=BVk\_\{V\}=B\_\{V\}\. Then for all failure probabilityδ\>0\\delta\>0, the pvCSV has sample complexity\(m𝖯𝖥𝖲,m𝖵𝖥𝖲\)\(m\_\{\\mathsf\{P\}\_\{\\mathsf\{FS\}\}\},m\_\{\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\}\)is as follows:

m𝖯𝖥𝖲=O​\(\(kV\+kP\)⋅log⁡\(\(kV\+kP\)/δ\)⋅log⁡\(1/δ\)τP′⁣2\)m𝖵𝖥𝖲=O​\(log⁡\(kV/δ\)τV2\)\\displaystyle m\_\{\\mathsf\{P\}\_\{\\mathsf\{FS\}\}\}=O\\left\(\\frac\{\\sqrt\{\(k\_\{V\}\+k\_\{P\}\)\\cdot\\log\(\(k\_\{V\}\+k\_\{P\}\)/\\delta\)\\cdot\\log\(1/\\delta\)\}\}\{\\tau\_\{P\}^\{\\prime 2\}\}\\right\)\\penalty 50\\qquad m\_\{\\mathsf\{V\}\_\{\\mathsf\{FS\}\}\}=O\\left\(\\frac\{\\log\(k\_\{V\}/\\delta\)\}\{\\tau\_\{V\}^\{2\}\}\\right\)

## 5Beyond pvCSVs: Strengths and Limits of SQ Protocols

In this section, we consider the power and limitations of SQ protocols\. First, we reiterate that, statistically, SQ protocols are very powerful\. In even more generic settings than our pvCSV constructions, SQ algorithms/protocols can be delegated via interactive SQ protocol such that the verifier’s sample complexity scales logarithmically in the number of queries\. Then, we show that SQ protocols—despite their sample efficiency—do not generically provide a computationally efficient verification scheme\. In particular, by a lower bound of\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]on the sample complexity required to PAC Verify certain VC classes, we show a subexponential lower bound on the query complexity of SQ verification for the same class\.

#### Interactive Non\-Adaptive SQ Verification\.

One of the key limitations in our construction of pvCSVs is the reliance on correctness under a public\-state SQ oracle\. We show that it is possible to achieve non\-adaptive statistical verification of SQ algorithms that are only correct under an oblivious SQ oracle, albeit with interaction\. This result is analogous to a result showed in the recent journal version of\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]\. Given any SQ algorithm, the verifier simply executes the algorithm using the prover as its oracle\. The prover responds interactively to each query\. And then at the end, the verifier checks the answers of the prover non\-adaptively\.

In fact, this simple idea also establishes that a large class of SQ protocols—even more general than those covered by Lemma[4\.7](https://arxiv.org/html/2607.15528#S4.Thmtheorem7)—can be verified using non\-adaptive statistical complexity\. Specifically, for any public\-query \(private\-coin\) SQ protocol that verifies𝒢\\mathcal\{G\}with public verifier state, there is an implementation of the protocol that only requires non\-adaptive verifier sample complexity\.

###### Proposition 5\.1\.

Fix a learning goal𝒢\\mathcal\{G\},τP,τV\>0\\tau\_\{P\},\\tau\_\{V\}\>0, andγ\>0\\gamma\>0, and letτP′=min⁡\{τP,τV/3\}\\tau\_\{P\}^\{\\prime\}=\\min\\\{\\tau\_\{P\},\\tau\_\{V\}/3\\\}andτV′=τV/3\\tau\_\{V\}^\{\\prime\}=\\tau\_\{V\}/3\. Suppose\(P,V\)\(P,V\)is a public\-query SQ protocol that\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-verifies𝒢\\mathcal\{G\}with public verifier state, wherePPhasτP\\tau\_\{P\}\-query complexity\(kP,BP\)\(k\_\{P\},B\_\{P\}\)andVVhasτV\\tau\_\{V\}\-query complexity\(kV,BV\)\(k\_\{V\},B\_\{V\}\)\. There is an SQ protocol\(P′,V′\)\(P^\{\\prime\},V^\{\\prime\}\)that\(τP′,τV′,γ\)\(\\tau\_\{P\}^\{\\prime\},\\tau\_\{V\}^\{\\prime\},\\gamma\)\-verifies𝒢\\mathcal\{G\}with public verifier state, whereP′P^\{\\prime\}hasτP′\\tau\_\{P\}^\{\\prime\}\-query complexity\(kP\+kB,BP\+BV\)\(k\_\{P\}\+k\_\{B\},B\_\{P\}\+B\_\{V\}\)andV′V^\{\\prime\}has non\-adaptiveτV′\\tau\_\{V\}^\{\\prime\}\-query complexity\(1,BV\)\(1,B\_\{V\}\)\.

Proposition[5\.1](https://arxiv.org/html/2607.15528#S5.Thmtheorem1)follows, again, by asking the prover to make the verifier’s statistical queries\. The completeness, soundness, and resulting bounds are analogous to those established by Lemma[4\.7](https://arxiv.org/html/2607.15528#S4.Thmtheorem7)\.

#### Query Lower Bound for SQ Verification of a VC Class\.

We show that the statistical upper bound we achieve for the SQ verifier actually implies a computational lower bound for SQ protocols\. Specifically, there exists a hypothesis class of VC dimensionddthat cannot be SQ verified, even using the most general interactive SQ protocols, using polynomially many queries indd\. Our lower bound piggybacks off of the lower bound proved in\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]for PAC Verification\.101010Informally, PAC Verification is the problem of delegation of learning, for the specific learning goal of Agnostic PAC learning\. We refer the unfamiliar reader to\[[GRS\+21](https://arxiv.org/html/2607.15528#bib.bib41)\]\.

###### Theorem\(Restatement of Theorem 2\.1 of\[[MS23](https://arxiv.org/html/2607.15528#bib.bib42)\]\)\.

Fixε\>0\\varepsilon\>0,δ=1/3\\delta=1/3, and let\(P,V\)\(P,V\)be an interactive proof system for learning\. For any hypothesis classℋ\\mathcal\{H\}of VC Dimensiondd, if\(P,V\)\(P,V\)PAC verifiesℋ\\mathcal\{H\}\(for all distributions𝒟\\mathcal\{D\}\) with accuracyε\\varepsilonand failure probabilityδ\\delta, then the verifierVVmust use at leastmV≥Ω​\(d/ε2\)m\_\{V\}\\geq\\Omega\(\\sqrt\{d\}/\\varepsilon^\{2\}\)i\.i\.d\. samples from𝒟\\mathcal\{D\}\.

Stringing this lower bound on the sample complexity of PAC verifying a VC class with our upper bound on the sample complexity of SQ verification, we immediately get a query complexity lower bound for SQ verification\. Taking our upper bound oflog⁡\(k\)/τ2\\log\(k\)/\\tau^\{2\}from Proposition[5\.1](https://arxiv.org/html/2607.15528#S5.Thmtheorem1), in terms of the number of statistical querieskk, and their lower bound ofd/ε2\\sqrt\{d\}/\\varepsilon^\{2\}in terms of the VC dimensiondd, we obtain the following corollary\.

###### Corollary 5\.2\.

Fixγ=1/3\\gamma=1/3and fix the verifier toleranceτV=Ω​\(ε\)\>0\\tau\_\{V\}=\\Omega\(\\varepsilon\)\>0in terms of the agnostic learning accuracyε\\varepsilon\. For every hypothesis classℋ\\mathcal\{H\}of VC dimensiondd, and for anyτP\>0\\tau\_\{P\}\>0, any public\-query SQ protocol that\(τP,τV,γ\)\(\\tau\_\{P\},\\tau\_\{V\},\\gamma\)\-SQ verifiesε\\varepsilon\-Agnostic PAC learning ofℋ\\mathcal\{H\}with public verifier state requires the verifier to makek=2Ω​\(d\)k=2^\{\\Omega\(\\sqrt\{d\}\)\}statistical queries\.

That is, even for the strongest model of SQ protocol we consider—interactive, public\-query SQ protocols that use a public\-state SQ oracle—when the tolerance of the SQ oracle is fixedτV≈ε\\tau\_\{V\}\\approx\\varepsilon, verification may be computationally inefficient, despite statistical efficiency\.

## 6Differential Privacy and SQ Verification

In many statistical analyses, Differential Privacy \(DP\)\[[DMN\+06](https://arxiv.org/html/2607.15528#bib.bib9)\]is a desirable property to satisfy to maintain the privacy of individuals’ data within a database\.111111DP is the gold standard notion for privacy\-protections in statistical analyses\. We refer the unfamiliar reader to introductory materials on DP, including\[[DR14](https://arxiv.org/html/2607.15528#bib.bib11),[VAD17](https://arxiv.org/html/2607.15528#bib.bib13),[KAM20](https://arxiv.org/html/2607.15528#bib.bib14)\]\. For the sake of presentation, we omit background on the Exponential Mechanism of\[[MT07](https://arxiv.org/html/2607.15528#bib.bib10)\]\.DP protects individuals’ privacy by requiring stability in a randomized algorithm’s behavior on neighboring databasesD,D′D,D^\{\\prime\}that differ on a single element\.

###### Definition 6\.1\(Differential Privacy\[[DMN\+06](https://arxiv.org/html/2607.15528#bib.bib9)\]\)\.

Fix a domain𝒳\\mathcal\{X\}and rangeℛ\\mathcal\{R\}, andε,δ\>0\\varepsilon,\\delta\>0\. A randomized algorithmM:𝒳∗→ℛM:\\mathcal\{X\}^\{\*\}\\to\\mathcal\{R\}is\(ε,δ\)\(\\varepsilon,\\delta\)\-differentially privateif for all neighboring databasesD,D′∈𝒳∗D,D^\{\\prime\}\\in\\mathcal\{X\}^\{\*\}and for all measurable subsetsS⊆ℛS\\subseteq\\mathcal\{R\},

Pr⁡\[M​\(D\)∈S\]≤eε⋅Pr⁡\[M​\(D′\)∈S\]\+δ\.\\operatorname\*\{\\textnormal\{\\bf Pr\}\}\[M\(D\)\\in S\]\\leq e^\{\\varepsilon\}\\cdot\\operatorname\*\{\\textnormal\{\\bf Pr\}\}\[M\(D^\{\\prime\}\)\\in S\]\+\\delta\.

DP provides rigorous protections to individuals, but comes at a cost\. Even for non\-adaptive statistical queries, in high\-dimensional settings \(d≥kd\\geq k\), answeringkkqueries requires sample complexity scaling polynomially inkk\. Concretely, to answerkkqueries withτ\\tautolerance under pure\(ε,0\)\(\\varepsilon,0\)\-DP requiresΩ​\(k/τ​ε\)\\Omega\(k/\\tau\\varepsilon\)i\.i\.d\. samples from𝒟\\mathcal\{D\}\[[HT10](https://arxiv.org/html/2607.15528#bib.bib4)\]; under approximate\(ε,δ\)\(\\varepsilon,\\delta\)\-DP requiresΩ​\(k⋅log⁡\(1/δ\)/τ​ε\)\\Omega\(\\sqrt\{k\\cdot\\log\(1/\\delta\)\}/\\tau\\varepsilon\)\[[SU16](https://arxiv.org/html/2607.15528#bib.bib3)\]\. Both of these results are tight \(up to poly\-logarithmic factors\); in fact, the upper bound on answering adaptive statistical queries is tightly connected to the upper bound on answering queries under approximate DP\.

Certifying the results of a statistical analysis, while maintaining DP with respect to the verifier’s samples, offers a potential for significant savings\. We show, generically, that the verifiers for our pvCSVs \(in fact, for all of our SQ protocols\) can be implemented under DP using essentially the same non\-adaptive sample complexity\.

Input :Batch of statistical queries

𝒒\\bm\{q\};

List of candidate answers to queries

𝒂\\bm\{a\};

Candidate accuracy

τP\>0\\tau\_\{P\}\>0and final accuracy

τ\>0\\tau\>0, where

τP≤τ/3\\tau\_\{P\}\\leq\\tau/3
Setup :

mVm\_\{V\}i\.i\.d\. samples drawn from

𝒟V\\mathcal\{D\}\_\{V\};

x1,…,xmVx\_\{1\},\\ldots,x\_\{m\_\{V\}\}
Sensitiviy of empirical queries

Δ=1/mV\\Delta=1/m\_\{V\}
1ex

for*j=1,…,Bj=1,\\ldots,B*do

Define

a^j=1mV​∑i=1mVqj​\(xi\)\\hat\{a\}\_\{j\}=\\frac\{1\}\{m\_\{V\}\}\\sum\_\{i=1\}^\{m\_\{V\}\}q\_\{j\}\(x\_\{i\}\)
Define

νj=\|a^j−aj\|\\nu\_\{j\}=\|\\hat\{a\}\_\{j\}\-a\_\{j\}\|
end for

Use the Exponential Mechanism to sample a noisy maximum

ν∗\\nu^\{\*\}over

\{νj\}\\\{\\nu\_\{j\}\\\}according to:

Pr⁡\[ν∗=νj\]∝exp⁡\(ε⋅νj2​Δ\)\\displaystyle\\operatorname\*\{\\textnormal\{\\bf Pr\}\}\[\\nu^\{\*\}=\\nu\_\{j\}\]\\propto\\exp\\left\(\\frac\{\\varepsilon\\cdot\\nu\_\{j\}\}\{2\\Delta\}\\right\)
if*ν∗\>τ/2\\nu^\{\*\}\>\\tau/2*then

returnFalse

returnTrue

Algorithm 5𝖣𝖯𝖵𝖺𝗅𝗂𝖽𝖺𝗍𝖾​\(𝒗,𝒂,τP,τ\)\\mathsf\{DPValidate\}\(\\bm\{v\},\\bm\{a\},\\tau\_\{P\},\\tau\)i\.e\., Differentially\-Private Statistical Validation###### Proposition 6\.2\.

There exists an\(ε,0\)\(\\varepsilon,0\)\-DP implementation of the non\-adaptive statistical validation, given in Algorithm[5](https://arxiv.org/html/2607.15528#algorithm5), with failure probabilityβ\\betathat usesmVm\_\{V\}i\.i\.d\. samples from𝒟V\\mathcal\{D\}\_\{V\}, where for any number of adaptive querieskk,

mV≤O​\(log⁡\(k/β\)τ2\+log⁡\(k/β\)τ​ε\)\.m\_\{V\}\\leq O\\left\(\\frac\{\\log\(k/\\beta\)\}\{\\tau^\{2\}\}\+\\frac\{\\log\(k/\\beta\)\}\{\\tau\\varepsilon\}\\right\)\.

###### Proof sketch\.

The proposition follows from a standard application of the Exponential Mechanism\[[MT07](https://arxiv.org/html/2607.15528#bib.bib10)\]\. The original non\-adaptive statistical validation step evaluates each query on the samples from𝒟V\\mathcal\{D\}\_\{V\}\.121212This is the simplest implementation of Algorithm[2](https://arxiv.org/html/2607.15528#algorithm2)given i\.i\.d\. samples\.Namely, the original verifier computesa^1,…,a^k\\hat\{a\}\_\{1\},\\ldots,\\hat\{a\}\_\{k\}wherea^j=1mV​∑i=1mVqj​\(xi\)\\hat\{a\}\_\{j\}=\\frac\{1\}\{m\_\{V\}\}\\sum\_\{i=1\}^\{m\_\{V\}\}q\_\{j\}\(x\_\{i\}\)\. Instead, the new verifier checks the \(noisy\) maximum difference between the statistics reported by the prover and the empirical statistics on their samples,\|aj−a^j\|\|a\_\{j\}\-\\hat\{a\}\_\{j\}\|\.

To compute the new verifier’s sample complexity, we need to reason about the accuracy of the empirical statisticsa^1,…,a^k\\hat\{a\}\_\{1\},\\ldots,\\hat\{a\}\_\{k\}, as well as the accuracy of the exponential mechanism\. For target toleranceτ\\tauand prover toleranceτ/3\\tau/3\(as in our protocols\), we will insist that each of these components achievesτ/16\\tau/16additive error with all butβ/2\\beta/2probability each\.

First, the accuracy of the empirical statistics: per Proposition[2\.10](https://arxiv.org/html/2607.15528#S2.Thmtheorem10),mVm\_\{V\}can scale asO​\(log⁡\(k/β\)/τ2\)O\(\\log\(k/\\beta\)/\\tau^\{2\}\)\. Then, the accuracy of the release of the maximum differencemax1≤j≤k⁡\|aj−a^j\|\\max\_\{1\\leq j\\leq k\}\|a\_\{j\}\-\\hat\{a\}\_\{j\}\|: per\[[MT07](https://arxiv.org/html/2607.15528#bib.bib10)\], with all butβ/2\\beta/2probability, the exponential mechanism achieves errorα\\alphawhere

α≤2​Δε⋅log⁡\(2​k/β\)\\displaystyle\\alpha\\leq\\frac\{2\\Delta\}\{\\varepsilon\}\\cdot\\log\(2k/\\beta\)whereΔ=1/mV\\Delta=1/m\_\{V\}is the sensitivity of the release from a database ofmVm\_\{V\}samples\. Thus, the exponential mechanism guaranteesτ/16\\tau/16\-accuracy to the empirical statistics for somemV≤O​\(log⁡\(k/β\)/τ​ε\)m\_\{V\}\\leq O\(\\log\(k/\\beta\)/\\tau\\varepsilon\)\. With these accuracies fixed with all butβ\\betatotal failure probability, we can define the new verifier and analyze Completeness and Soundness\.

For a sequence ofkkfully\-adaptive SQs, Algorithm[5](https://arxiv.org/html/2607.15528#algorithm5)runs the exponential mechanism to release the noisy maximum differencemax1≤j≤k⁡\|aj−a^j\|\\max\_\{1\\leq j\\leq k\}\|a\_\{j\}\-\\hat\{a\}\_\{j\}\|\. If the difference is less thanτ/2\\tau/2, it accepts; otherwise, it rejects\.

*Completeness:*Per our earlier protocols, we assume the honest prover reports eachaja\_\{j\}withinτP=τ/3\\tau\_\{P\}=\\tau/3of the true query value\. The verifier’s empirical statisticsa^j\\hat\{a\}\_\{j\}are withinτ/16\\tau/16of the true query value, and their difference is released withτ/16\\tau/16\-accuracy, so in sum, the reported maximum difference will be strictly less thanτ/2\\tau/2, with all butβ\\betaprobability\.

*Soundness:*Suppose there is some statisticaja\_\{j\}that was reported with more thanτ\\tauadditive error from the true value, so the SQ guarantee is violated\. Again, the verifier’s accuracy ensures that the difference\|aj−a^j\|\|a\_\{j\}\-\\hat\{a\}\_\{j\}\|is at least15​τ/1615\\tau/16, which is released with at mostτ/16\\tau/16additive error\. So, with all butβ\\betaprobability, the reported maximum difference is strictly more thanτ/2\\tau/2\. ∎

## Acknowledgements

The authors thank Noah Stephens\-Davidowitz for significant conversations at the start of this work and feedback throughout the project\. We also thank Robert Kleinberg, Jonathan Shafer, and Nick Spooner for helpful discussions\.

## References

- \[BAB85\]L\. Babai\(1985\)Trading group theory for randomness\.InProceedings of the seventeenth annual ACM symposium on Theory of computing,pp\. 421–429\.Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.15528#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.p1.6)\.
- \[BAR01\]B\. Barak\(2001\)How to go beyond the black\-box simulation barrier\.InProceedings 42nd IEEE Symposium on Foundations of Computer Science,pp\. 106–115\.Cited by:[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.SSS0.Px2.p4.1)\.
- \[BNS\+16\]R\. Bassily, K\. Nissim, A\. Smith, T\. Steinke, U\. Stemmer, and J\. Ullman\(2016\)Algorithmic stability for adaptive data analysis\.InProceedings of the forty\-eighth annual ACM symposium on Theory of Computing,pp\. 1046–1059\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§1\.2](https://arxiv.org/html/2607.15528#S1.SS2.p4.7),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1),[§2\.3](https://arxiv.org/html/2607.15528#S2.SS3.p6.3)\.
- \[BGK\+24\]Z\. R\. Bell, S\. Goldwasser, M\. P\. Kim, and J\. Watson\(2024\)Certifying private probabilistic mechanisms\.InAnnual International Cryptology Conference,pp\. 348–386\.Cited by:[§1\.2](https://arxiv.org/html/2607.15528#S1.SS2.SSS0.Px5.p2.3),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p2.1)\.
- \[BTF\+25\]Z\. R\. Bell, A\. Thudi, O\. Franzese\-McLaughlin, N\. Papernot, and S\. Goldwasser\(2025\)Efficient public verification of private ml via regularization\.arXiv preprint arXiv:2512\.04008\.Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p2.1)\.
- \[BR93\]M\. Bellare and P\. Rogaway\(1993\)Random oracles are practical: a paradigm for designing efficient protocols\.InProceedings of the 1st ACM Conference on Computer and Communications Security,pp\. 62–73\.Cited by:[§1\.1](https://arxiv.org/html/2607.15528#S1.SS1.SSS0.Px3.p2.2),[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.SSS0.Px2.p2.1),[§4\.3](https://arxiv.org/html/2607.15528#S4.SS3.SSS0.Px1.p1.4)\.
- \[BCS16\]E\. Ben\-Sasson, A\. Chiesa, and N\. Spooner\(2016\)Interactive oracle proofs\.InTheory of Cryptography Conference,pp\. 31–60\.Cited by:[§1\.2](https://arxiv.org/html/2607.15528#S1.SS2.SSS0.Px2.p5.1),[§4\.3](https://arxiv.org/html/2607.15528#S4.SS3.SSS0.Px2.p2.1)\.
- \[BLA25\]G\. Blanc\(2025\)Subsampling suffices for adaptive data analysis\.Journal of the ACM72\(1\),pp\. 1–45\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§1\.2](https://arxiv.org/html/2607.15528#S1.SS2.p4.7),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1),[§2\.3](https://arxiv.org/html/2607.15528#S2.SS3.p6.3),[Proposition 2\.11](https://arxiv.org/html/2607.15528#S2.Thmtheorem11),[§3\.1](https://arxiv.org/html/2607.15528#S3.SS1.p4.4),[footnote 8](https://arxiv.org/html/2607.15528#footnote8)\.
- \[CG18\]A\. Chiesa and T\. Gur\(2018\)Proofs of proximity for distribution testing\.In9th Innovations in Theoretical Computer Science Conference \(ITCS 2018\),pp\. 53–1\.Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p3.1)\.
- \[CY24\]A\. Chiesa and E\. Yogev\(2024\)Building cryptographic proofs from hash functions\.External Links:[Link](https://github.com/hash-based-snargs-book)Cited by:[§1\.2](https://arxiv.org/html/2607.15528#S1.SS2.SSS0.Px2.p5.1),[Theorem 4\.9](https://arxiv.org/html/2607.15528#S4.Thmtheorem9)\.
- \[DK22\]Y\. Dagan and G\. Kur\(2022\)A bounded\-noise mechanism for differential privacy\.InConference on Learning Theory,pp\. 625–661\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§1\.2](https://arxiv.org/html/2607.15528#S1.SS2.p4.7),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1),[§2\.3](https://arxiv.org/html/2607.15528#S2.SS3.p6.3),[footnote 8](https://arxiv.org/html/2607.15528#footnote8)\.
- \[DFH\+15a\]C\. Dwork, V\. Feldman, M\. Hardt, T\. Pitassi, O\. Reingold, and A\. Roth\(2015\)Generalization in adaptive data analysis and holdout reuse\.Advances in neural information processing systems28\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1),[§2](https://arxiv.org/html/2607.15528#S2.p1.1)\.
- \[DFH\+15b\]C\. Dwork, V\. Feldman, M\. Hardt, T\. Pitassi, O\. Reingold, and A\. L\. Roth\(2015\)Preserving statistical validity in adaptive data analysis\.InProceedings of the forty\-seventh annual ACM symposium on Theory of computing,pp\. 117–126\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p1.1),[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1),[§2\.3](https://arxiv.org/html/2607.15528#S2.SS3.p3.2)\.
- \[DFH\+15c\]C\. Dwork, V\. Feldman, M\. Hardt, T\. Pitassi, O\. Reingold, and A\. Roth\(2015\)The reusable holdout: preserving validity in adaptive data analysis\.Science349\(6248\),pp\. 636–638\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1)\.
- \[DMN\+06\]C\. Dwork, F\. McSherry, K\. Nissim, and A\. Smith\(2006\)Calibrating noise to sensitivity in private data analysis\.InTheory of cryptography conference,pp\. 265–284\.Cited by:[§1\.1](https://arxiv.org/html/2607.15528#S1.SS1.SSS0.Px5.p1.1),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1),[§2\.3](https://arxiv.org/html/2607.15528#S2.SS3.p5.1),[Definition 6\.1](https://arxiv.org/html/2607.15528#S6.Thmtheorem1),[§6](https://arxiv.org/html/2607.15528#S6.p1.1)\.
- \[DR14\]C\. Dwork and A\. Roth\(2014\)The algorithmic foundations of differential privacy\.Vol\.9,Now Publishers Inc\.\.External Links:[Document](https://dx.doi.org/10.1561/0400000042),ISBN 978\-1\-60198\-818\-8Cited by:[footnote 11](https://arxiv.org/html/2607.15528#footnote11)\.
- \[FS18\]V\. Feldman and T\. Steinke\(2018\)Calibrating noise to variance in adaptive data analysis\.InConference On Learning Theory,pp\. 535–544\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1)\.
- \[FS86\]A\. Fiat and A\. Shamir\(1986\)How to prove yourself: practical solutions to identification and signature problems\.InConference on the theory and application of cryptographic techniques,pp\. 186–194\.Cited by:[§1\.1](https://arxiv.org/html/2607.15528#S1.SS1.SSS0.Px3.p4.1),[§1\.2](https://arxiv.org/html/2607.15528#S1.SS2.SSS0.Px2.p1.1),[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.SSS0.Px2.p2.1),[§4\.3](https://arxiv.org/html/2607.15528#S4.SS3.p1.1)\.
- \[GL89\]O\. Goldreich and L\. Levin\(1989\)A hard\-core predicate for all one\-way functions\.InProceedings of the 21st Annual ACM Symposium on Theory of Computing \(STOC ’89\),pp\. 25–32\.External Links:[Document](https://dx.doi.org/10.1145/73007.73011)Cited by:[§1](https://arxiv.org/html/2607.15528#S1.p3.1)\.
- \[GKR08\]S\. Goldwasser, Y\. T\. Kalai, and G\. N\. Rothblum\(2008\)Delegating computation: interactive proofs for muggles\.InProceedings of the 40th Annual ACM Symposium on Theory of Computing \(STOC ’08\),Victoria, British Columbia, Canada,pp\. 113–122\.External Links:[Document](https://dx.doi.org/10.1145/1374376.1374396)Cited by:[§1\.1](https://arxiv.org/html/2607.15528#S1.SS1.SSS0.Px2.p2.3)\.
- \[GK03\]S\. Goldwasser and Y\. T\. Kalai\(2003\)On the \(in\) security of the fiat\-shamir paradigm\.In44th Annual IEEE Symposium on Foundations of Computer Science, 2003\. Proceedings\.,pp\. 102–113\.Cited by:[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.SSS0.Px2.p4.1)\.
- \[GMR85\]S\. Goldwasser, S\. Micali, and C\. Rackoff\(1985\)The knowledge complexity of interactive proof\-systems\.InProceedings of the Seventeenth Annual ACM Symposium on Theory of Computing \(STOC ’85\),Providence, Rhode Island,pp\. 291–304\.External Links:[Document](https://dx.doi.org/10.1145/22145.22178)Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.15528#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.p1.6)\.
- \[GRS\+21\]S\. Goldwasser, G\. N\. Rothblum, J\. Shafer, and A\. Yehudayoff\(2021\)Interactive proofs for verifying machine learning\.In12th Innovations in Theoretical Computer Science Conference \(ITCS 2021\),pp\. 41–1\.Cited by:[§1\.1](https://arxiv.org/html/2607.15528#S1.SS1.SSS0.Px3.p3.1),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.15528#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.SSS0.Px1.p1.1),[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.p1.6),[Definition 2\.7](https://arxiv.org/html/2607.15528#S2.Thmtheorem7),[§2](https://arxiv.org/html/2607.15528#S2.p1.1),[1st item](https://arxiv.org/html/2607.15528#S3.I2.i1.p1.1),[footnote 10](https://arxiv.org/html/2607.15528#footnote10)\.
- \[GJK\+24\]T\. Gur, M\. M\. Jahanara, M\. M\. Khodabandeh, N\. Rajgopal, B\. Salamatian, and I\. Shinkar\(2024\)On the power of interactive proofs for learning\.InProceedings of the 56th Annual ACM Symposium on Theory of Computing,pp\. 1063–1070\.Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.15528#S1.p2.1)\.
- \[HR10\]M\. Hardt and G\. N\. Rothblum\(2010\)A multiplicative weights mechanism for privacy\-preserving data analysis\.In2010 IEEE 51st annual symposium on foundations of computer science,pp\. 61–70\.Cited by:[§2\.3](https://arxiv.org/html/2607.15528#S2.SS3.p3.2)\.
- \[HT10\]M\. Hardt and K\. Talwar\(2010\)On the geometry of differential privacy\.InProceedings of the 42nd Annual ACM Symposium on Theory of Computing \(STOC ’10\),pp\. 705–714\.External Links:[Document](https://dx.doi.org/10.1145/1806689.1806786)Cited by:[§6](https://arxiv.org/html/2607.15528#S6.p2.10)\.
- \[HU14\]M\. Hardt and J\. Ullman\(2014\)Preventing false discovery in interactive data analysis is hard\.In2014 IEEE 55th annual symposium on foundations of computer science,pp\. 454–463\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§2\.3](https://arxiv.org/html/2607.15528#S2.SS3.p7.1)\.
- \[HAU92\]D\. Haussler\(1992\)Decision\-theoretic generalizations of the pac model for neural net and other learning applications\.Information and Computation100\(1\),pp\. 78–150\.External Links:[Document](https://dx.doi.org/10.1016/0890-5401%2892%2990046-D)Cited by:[§1](https://arxiv.org/html/2607.15528#S1.p2.1)\.
- \[HR22\]T\. Herman and G\. N\. Rothblum\(2022\)Verifying the unseen: interactive proofs for label\-invariant distribution properties\.InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing,pp\. 1208–1219\.Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p3.1)\.
- \[HR23\]T\. Herman and G\. Rothblum\(2023\)Doubley\-efficient interactive proofs for distribution properties\.In2023 IEEE 64th Annual Symposium on Foundations of Computer Science \(FOCS\),pp\. 743–751\.Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p3.1)\.
- \[HR24a\]T\. Herman and G\. Rothblum\(2024\)How to verify any \(reasonable\) distribution property: computationally sound argument systems for distributions\.arXiv preprint arXiv:2409\.06594\.Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p3.1)\.
- \[HR24b\]T\. Herman and G\. Rothblum\(2024\)Interactive proofs for general distribution properties\.In2024 IEEE 65th Annual Symposium on Foundations of Computer Science \(FOCS\),pp\. 528–538\.Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p3.1)\.
- \[JLN\+19\]C\. Jung, K\. Ligett, S\. Neel, A\. Roth, S\. Sharifi\-Malvajerdi, and M\. Shenfeld\(2019\)A new analysis of differential privacy’s generalization guarantees\.arXiv preprint arXiv:1909\.03577\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px2.p1.1)\.
- \[KAM20\]G\. Kamath\(2020\)CS 860: algorithms for private data analysis\.Note:Lecture notes and videos available athttp://www\.gautamkamath\.com/CS860\-fa2020\.htmlExternal Links:[Link](http://www.gautamkamath.com/CS860-fa2020.html)Cited by:[footnote 11](https://arxiv.org/html/2607.15528#footnote11)\.
- \[KSS94\]M\. Kearns, R\. E\. Schapire, and L\. M\. Sellie\(1994\)Toward efficient agnostic learning\.Machine Learning17\(2–3\),pp\. 115–141\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.p2.1)\.
- \[KEA98\]M\. Kearns\(1998\)Efficient noise\-tolerant learning from statistical queries\.Journal of the ACM \(JACM\)45\(6\),pp\. 983–1006\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p1.1),[§2\.1](https://arxiv.org/html/2607.15528#S2.SS1.p1.3),[§2\.1](https://arxiv.org/html/2607.15528#S2.SS1.p2.1),[§2](https://arxiv.org/html/2607.15528#S2.p1.1)\.
- \[MT07\]F\. McSherry and K\. Talwar\(2007\)Mechanism design via differential privacy\.In48th Annual IEEE Symposium on Foundations of Computer Science \(FOCS\),pp\. 94–103\.Cited by:[§6](https://arxiv.org/html/2607.15528#S6.1.p1.4),[§6](https://arxiv.org/html/2607.15528#S6.3.p3.5),[footnote 11](https://arxiv.org/html/2607.15528#footnote11)\.
- \[MS23\]S\. Mutreja and J\. Shafer\(2023\)PAC verification of statistical algorithms\.InThe Thirty Sixth Annual Conference on Learning Theory,pp\. 5021–5043\.Cited by:[§1\.1](https://arxiv.org/html/2607.15528#S1.SS1.SSS0.Px4.p3.1),[§1\.2](https://arxiv.org/html/2607.15528#S1.SS2.SSS0.Px4.p2.1),[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2607.15528#S1.p2.1),[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.SSS0.Px1.p1.1),[§2\.2](https://arxiv.org/html/2607.15528#S2.SS2.SSS0.Px1.p2.2),[Definition 2\.7](https://arxiv.org/html/2607.15528#S2.Thmtheorem7),[§2](https://arxiv.org/html/2607.15528#S2.p1.1),[§5](https://arxiv.org/html/2607.15528#S5.SS0.SSS0.Px1.p1.1),[§5](https://arxiv.org/html/2607.15528#S5.SS0.SSS0.Px2.p1.2),[§5](https://arxiv.org/html/2607.15528#S5.p1.1),[Theorem](https://arxiv.org/html/2607.15528#Thmtheoremx1)\.
- \[MS26\]S\. Mutreja and J\. Shafer\(2026\)PAC verification of statistical algorithms\.Theory of Computing22\(5\),pp\. 1–40\.Note:A preliminary version appeared in the[Proceedings of COLT’23](https://proceedings.mlr.press/v195/mutreja23a.html)External Links:[Document](https://dx.doi.org/10.4086/toc.2026.v022a005),[Link](https://theoryofcomputing.org/articles/v022a005)Cited by:[§1\.3](https://arxiv.org/html/2607.15528#S1.SS3.SSS0.Px1.p1.1)\.
- \[SU15\]T\. Steinke and J\. Ullman\(2015\)Interactive fingerprinting codes and the hardness of preventing false discovery\.InConference on learning theory,pp\. 1588–1628\.Cited by:[§1](https://arxiv.org/html/2607.15528#S1.SS0.SSS0.Px2.p3.2),[§2\.3](https://arxiv.org/html/2607.15528#S2.SS3.p7.1),[Proposition 2\.12](https://arxiv.org/html/2607.15528#S2.Thmtheorem12)\.
- \[SU16\]T\. Steinke and J\. Ullman\(2016\)Between pure and approximate differential privacy\.Journal of Privacy and Confidentiality7\(2\),pp\. 3–22\.External Links:[Document](https://dx.doi.org/10.29012/2017.428)Cited by:[§6](https://arxiv.org/html/2607.15528#S6.p2.10)\.
- \[VAD17\]S\. Vadhan\(2017\)The complexity of differential privacy\.InTutorials on the Foundations of Cryptography,Y\. Lindell \(Ed\.\),pp\. 347–450\.External Links:[Document](https://dx.doi.org/10.1007/978-3-319-57048-8%5F9)Cited by:[footnote 11](https://arxiv.org/html/2607.15528#footnote11)\.
- \[VAL84\]L\. G\. Valiant\(1984\)A theory of the learnable\.Communications of the ACM27\(11\),pp\. 1134–1142\.External Links:[Document](https://dx.doi.org/10.1145/1968.1972)Cited by:[§1](https://arxiv.org/html/2607.15528#S1.p2.1)\.