PAC to the Future: Zero-Knowledge Proofs of PAC Private Systems

1. Problem Statement

The rapid growth of large-scale machine learning (ML) and cloud-based data processing has intensified privacy concerns regarding sensitive user data. While Probably Approximately Correct (PAC) Privacy offers a robust framework for protecting data in black-box algorithms by adding noise (often superior to Differential Privacy in terms of utility-noise trade-offs), it suffers from a critical limitation in trustless environments: verifiability.

In outsourced computation scenarios (e.g., cloud providers), users cannot verify if the service provider:

1. Correctly computed the intended mechanism (e.g., training a model).
2. Applied the correct amount of privacy-preserving noise as promised.
3. Did so without revealing proprietary data or the specific noise parameters.

Existing solutions like Fully Homomorphic Encryption (FHE) or Multi-Party Computation (MPC) protect data but often lack efficient verifiability. Conversely, standard Zero-Knowledge Proofs (ZKPs) ensure integrity but have not been effectively combined with PAC Privacy to prove that the specific noise generation required for PAC guarantees was performed correctly.

2. Methodology

The authors propose a novel framework that integrates PAC Privacy with non-interactive Zero-Knowledge Proofs (specifically zk-STARKs) to create a system where privacy guarantees are both mathematically rigorous and cryptographically verifiable.

Core Components

• PAC Privacy Mechanism: The system uses the PAC framework where a mechanism $M$ processes sensitive data $X$. To ensure privacy, a noise vector $B$ is added to the output $M(X)$. The noise is determined by a covariance matrix $\Sigma$, calculated based on the data distribution to ensure the mutual information between the input and the noisy output is bounded by a parameter $\beta$.
• Zero-Knowledge Proofs (zk-STARKs): The authors utilize zk-STARKs (Zero-Knowledge Scalable Transparent Arguments of Knowledge) via the RISC-Zero framework.
  • Why zk-STARKs? They offer post-quantum security (relying on hash functions rather than elliptic curves), do not require a trusted setup (transparent), and support non-interactive proofs (publicly verifiable).
• Non-Interactive Flow: The system operates in a non-interactive setting where the Prover (cloud server) generates a single proof that can be verified by any Verifier (client) without further communication.

Technical Implementation Steps

The methodology is divided into two distinct phases, both executed within the ZK circuit:

1. Noise Generation Phase (Algorithm 1):

   • The Prover computes the covariance matrix $\Sigma$ based on the dataset to determine the necessary noise distribution.
   • To maintain privacy, $\Sigma$ is never revealed. Instead, the Prover computes a hash $h(\Sigma)$ within the ZK circuit.
   • The Prover generates a proof $\pi_1$ attesting that $h(\Sigma)$ was correctly derived from a valid noise generation algorithm without revealing $\Sigma$ itself.

2. PAC Computation Phase (Algorithm 2):

   • The Verifier sends a data point $x$ and a secret random seed $s$ (used to deterministically generate the noise vector $B$ from $\Sigma$).
   • The Prover uses the seed $s$ and the private $\Sigma$ to generate the noise $B$.
   • The Prover computes the final output $M(x) + B$.
   • Crucially, the Prover proves within the circuit that the hash of the $\Sigma$ used to generate $B$ matches the public hash $h(\Sigma)$ provided in the first phase.
   • The output is the noisy result $M(x) + B$ accompanied by a proof $\pi_2$ verifying the correctness of the computation and the adherence to the PAC privacy constraints.

Adaptation for ZK Constraints

Implementing ML algorithms in ZK circuits (specifically RISC-Zero) requires specific adaptations because ZK circuits must be deterministic and have fixed execution traces (no data-dependent loops or branches):

• K-Means: Randomness is replaced by fixed input ordering. Centroid assignments are handled via fixed-size lists with boolean flags to simulate variable group sizes. Iterations are fixed to a maximum number rather than running until convergence.
• SVM: Models are normalized to ensure scale invariance, and canonicalization is applied to the output hyperplane.
• Database Statistics: Queries are translated into fixed-size "Formula" vectors representing filters (e.g., Age > 26 AND Age < 100) to ensure memory usage remains constant regardless of the query result size.

3. Key Contributions

1. First Framework for Verifiable PAC Privacy: The paper presents the first end-to-end system combining PAC Privacy with zk-STARKs to provide verifiable privacy guarantees in trustless, outsourced environments.
2. Non-Interactive Post-Quantum Security: By leveraging zk-STARKs, the system provides publicly verifiable proofs without a trusted setup and offers resistance against quantum attacks.
3. Practical Implementation: The authors successfully implemented and adapted complex algorithms (K-Means, SVM, and statistical database queries) to run within the constraints of a zk-STARK virtual machine (RISC-Zero).
4. Efficiency Analysis: The study demonstrates that while ZK proofs introduce overhead, the system maintains near-plaintext utility and the proof generation overhead scales predictably (affinely) with dataset size.

4. Experimental Results

The authors evaluated the system on three mechanisms using the RISC-Zero framework:

• K-Means Clustering:
  • Performance: The number of RISC cycles (computational cost) showed a perfect affine growth relative to the number of samples ($M$) and the number of clusters ($K$).
  • Observation: Once noise is generated, the cost of the PAC version is comparable to the cost of processing a single sample in the noise generation phase.
• Support Vector Machines (SVM):
  • Performance: Showed a general affine trend but with slight fluctuations compared to K-Means.
  • Cause: SVMs require more memory operations (caching), leading to non-deterministic cycle counts in the zkVM, though the overall scaling remains linear.
• Database Statistics:
  • Performance: Demonstrated similar affine behavior for statistical queries (e.g., averages, medians) over filtered datasets.
• Utility: The system maintained "near-plaintext utility," meaning the noisy output remained highly useful for the intended ML or statistical tasks while satisfying strict privacy bounds.

5. Significance and Conclusion

This work bridges a critical gap between privacy theory and computational integrity.

• Trust in Cloud AI: It enables users to outsource sensitive data processing to untrusted cloud providers with the mathematical certainty that the provider applied the correct privacy protections (PAC noise) and computed the result correctly.
• Beyond Differential Privacy: By utilizing PAC Privacy, the system avoids the severe utility degradation often associated with Differential Privacy (DP) in high-dimensional or small-dataset scenarios, while still providing verifiable guarantees.
• Future of Trustless Computing: The integration of post-quantum secure, non-interactive ZKPs with advanced privacy frameworks sets a new standard for auditable, privacy-preserving machine learning and database systems.

In summary, "PAC to the Future" demonstrates that it is feasible to build verifiable, privacy-preserving systems where the "black box" of the cloud provider is opened just enough to prove compliance with privacy laws, without ever exposing the raw data or the provider's proprietary algorithms.