Confidential-DPproof: Confidential Proof of Differentially Private Training
Authors: Ali Shahin Shamsabadi
Gefei Tan
Tudor Ioan Cebere
Aurélien Bellet
Hamed Haddadi
Nicolas Papernot
Xiao Wang
Adrian Weller
Venue: ICLR 2024 spotlight (2024)
Keywords: privacy auditing
zero knowledge proof
differentially private training
Primary area: societal considerations including fairness, safety, privacy

Abstract: Post hoc privacy auditing techniques can be used to test the privacy guarantees of a model, but come with several limitations: (i) they can only establish lower bounds on the privacy loss, (ii) the intermediate model updates and some data must be shared with the auditor to get a better approximation of the privacy loss, and (iii) the auditor typically faces a steep computational cost to run a large number of attacks. In this paper, we propose to proactively generate a cryptographic certificate of privacy during training to forego such auditing limitations. We introduce Confidential-DPproof , a framework for Confidential Proof of Differentially Private Training, which enhances training with a certificate of the $(\varepsilon,\delta)$-DP guarantee achieved. To obtain this certificate without revealing information about the training data or model, we design a customized zero-knowledge proof protocol tailored to the requirements introduced by differentially private training, including random noise addition and privacy amplification by subsampling. In experiments on CIFAR-10, Confidential-DPproof trains a model achieving state-of-the-art $91$% test accuracy with a certified privacy guarantee of $(\varepsilon=0.55,\delta=10^{-5})$-DP in approximately 100 hours.

Published as a conference paper at ICLR 2024
Confidential-DPprooff CONFIDENTIAL PROOF OF DIFFERENTIALLY PRIVATE TRAINING
Ali Shahin Shamsabadi', Gefei Tan', Tudor Ioan Cebere', Aurélien Bellet"i
Hamed Haddadi" Nicolas Papernot* 76. Xiao Wang Adrian Weller
Brave Software, Northwestern University, 3 Inria, Univ Lille, Inria, Univ Montpellier, 5 Imperial College London, Vector Institute, University of Toronto, University of Cambridge,
9 The Alan Turing Institute
ABSTRACT
Post hoc privacy auditing techniques can be used to test the privacy guarantees of a model, but come with several limitations: (i) they can only establish lower bounds the privacy loss, (ii) the intermediate model updates and some data must be shared with the auditor to get a better approximation of the privacy loss, and (iii) the auditor typically faces a steep computational cost to run a large number of attacks. In this paper, we propose to proactively generate a cryptographic certificate of pri- vacy during training forego such auditing limitations. We introduce Confidential- DPproof, a framework for Confidential Proof of Differentially Private Training, which enhances training with a certificate of the (c, 8)- guarantee achieved. To obtain this certificate without revealing information about the training data or model, we design a customized zero-knowledge proof protocol tailored to the requirements introduced by differentially private training, including random noise addition and privacy amplification by subsampling. In experiments on CIFAR-10, Confidential- DPproof trains model achieving state-of-the-art 91% test accuracy with certified privacy guarantee of (s = 0.55, å = 10 10-5)-1 ->-DP in approximately 100 hours.
INTRODUCTION
Training Machine Learning (ML) models poses a potential threat to the privacy of users whose sensitive data being analyzed. Indeed, ML models have been shown to leak information contained
in individual training examples (Fredrikson et al. 2015 Shokri et al. 2017 Rahman et al.) 2018 [Song |
Shmatikov] 2019 Balle et al.] [arlina Carlini al.] (022)) To protect the privacy training data, the de facto approach is to train models with guarantees of Differential Privacy (DP) (Dwork et al.
2014p. This provides a statistical upper bound e on the privacy loss, i.e. the amount of information that a model leaks about individual training examples. Differentially Private Stochastic Gradient Descent (DP-SGD) is the canonical approach for training models under the framework of DP (Song ct al. 2013 Abadi et al. 2016).
The guarantees of privacy provided by DP-SGD are derived analytically and constitute a theoretical upper bound the leakage of information from the training set once the DP-SGD algorithm was executed correctly. Unfortunately, it is difficult for an external party (i.e., auditor) to audit claims of privacy made by the modal trainer (i.e., prover) when they are only given query access to the model. Typically, in such black-box audits, the auditor must empirically measure the privacy loss of trained model through the instantiation of practical attacks (Jagielski et al., 2020 Nast et al. 202T
Lu et al. 2022
et al. 2023 Nasr et al.) 2023). Such post hoc privacy auditing. however, suffers from some drawbacks:
it only establishes lower bound on the privacy loss, as it is generally impossible to rule out the existence of better attacks that would yield larger privacy loss: (2) computing tighter lower bounds compromises confidentiality, as decreasing the gap between the lower bound and the theoretical privacy guarantee requires that the auditor be given more information about the training dataset and model (such as intermediate model updates, as shown in Figure in Nasr al. 2021); y and (3) such improvements also come at significant computational cost as the auditor needs to either train models millions of times (Nast et al.) 2021) or use many
Alphahetical order

---

Published as a conference paper at ICLR 2024
samples (Zanella- Baalllll--lllnn al. 2023) to obtain statistically reliable estimates of the privacy loss. Therefore, an auditor using these post hoc approaches can only hope to disprove a false claim of privacy they cannot provide certificate of the guarantees of DP-SGD privacy claimed by the prover when the audit is performed by a third party with limited access to the training phase.
In this work, we remediate these issues with the introduction of confidential proofs of DP training. We design Donfidential--PPrron that enables a company to proactively prove to the auditor that their model was correctly trained using DP-SGD. This proof takes the form of certificate which the auditor can use to verify the claimed value of s. To obtain such a certificate, we rely on Zero Knowledge Proofs (ZKP) (Goldwasser et al.) 1985 Goldreich et al., 199T). This allows us to prove statements about the training algorithm without revealing anything else about the training data or the model.
Our protocol for ZKP attests that the model trainer correctly executed the DP-SGD algorithm, i.c. that at each step i) it correctly subsampled a minibatch to benefit from privacy amplification by sub-sampling: ii) computed and clipped the associated per-example gradients to a preset norm to bound the influence of individual training examples model updates; iii) added properly calibrated noise to the aggregated gradients; and iv) updated the model parameters using the noisy aggregated gradients. This is challenging for several reasons, the first of which is the existence of randomness at different stages of training performed with DP-SGD: this includes data subsampling to form minibatches and noise added to the gradients themselves. This randomness makes it possible for an adversarial prover (i.e., one that seeks to deviate from the DP-SGD training algorithm) to pick randomness that meets their needs. One avenue address this problem would be for the prover to reveal its randomness to the auditor or let the auditor pick this randomness. However, this approach i) invalidates the guarantees of DP and thus risks the privacy of the prover as an informed adversary with knowledge of the randomness can infer information from the prover's training data; and ii) enables an adversarial auditor to bias the computations and blame the prover. To avoid this, we design a custom ZKP protocol that seeds the randomness privately and interactively so as to prevent its manipulation by provers while keeping hidden from auditors: i) prior to the training, the prover commits to a random key k; ii) the auditor picks fresh random value r and sends it to the prover and iii during the training. the prover proves in ZK that the unbiased randomness seed s = O r is used without revealing or l to the auditor.
In summary, we introduce desiderata for privacy auditing and propose the first ZK protocol which enables auditors to directly verify the exact privacy budget of DP-SGD training run, and thus provide a certificate of privacy. Because we rely on ZKPs, the prover does not need to reveal any information about their model and training dataset. Confidentiall-DPrroog is appealing alternative to the current status quo, where attacks are used to perform computationally costly audits. Our approach is made possible through the co-design of a DP training algorithm with a customized Z.K protocol. We design and implement a specialized ZK proof protocol to efficiently perform the DP training. We implement and evaluate our framework in terms of accuracy, privacy, running times and communication costs. Confidential -ariiiall-DPPrerr Dprroof affords low running time and high levels of accuracy.
2 PROBLEM STATEMENT
Motivation. Models that were trained without a crivacy-preserving algorithm may leak information contained in their training set. For example, membership inference attacks (Shokri et al.] [017] Rahman et al.] 2018) exploit access to model's predictions to infer the presence (or absence) of a
particular data point in its training set. It is also possible to reconstruct data points through an analysis of the model's 's parameters (Balle et al. 2022 HHai et al., [022 Guo et al. [002 Shamsabadi et al.)
2023 Differential Privacy (DP) is the most established framework to reason about privacy leakage when analyzing data. It reasons about the properties of the algorithm itself rather than the data.
Definition 1 (Differential Privacy (Dwork et al. 2014)). A randomized algorithm A is (s, 8)-DP if for any two neighbouring datasets D and D' and any measurable outcome S E Range
PH(A(D) S) S e PH(A(D') E E5 5
(1)
Neighbouring datasets differ only in single data point, and different variants for the definition of neighbouring datasets have been considered: diding-or-removinn one record, zeroing-out out one record or replacing one record (Ponomareva al. 2023). We consider the replace one version, which is
2

---

Published as a conference paper at ICLR 2024
most commonly used in machine learning and assumes that neighbourhing datasets D and D' have the same size. Therefore, the size of the dataset can be public, avoiding complications that might arise when designing our ZKP protocol.
Training with DP mitigates many attacks against the privacy of training data, including membership inference and training data reconstruction. Therefore, it is important for institutions that handle sensitive data to demonstrate that they train ML models under the framework of DP. These institutions must also be able to prove that their training run achieved a specific privacy budget (c, 6): lower values of imply a tighter bound on privacy leakage and thus a stronger privacy guarantee.
Goal and notation. We consider a setting with two parties: a prover and an auditor. The prover is an institution like company or a hospital that wants train model different purposes such as providing ML-driven services. The auditor is an external entity that aims to verify the privacy guarantees of the prover's model. These two parties engage in communication to complete the audit. We identify the following desiderata for this audit:
sensitive dataset for
Completeness. The audit must infer the exact privacy guarantee and provide a certificate of this privacy guarantee. The guarantees of privacy provided by training with DP are derived analytically and constitute an exact upper bound s, obtained based on the given privacy accounting technique, on the leakage of information from the training set. However, existing post hoc auditing approaches empirically estimate lower bound of this leakage. There is a significant gap between the upper bound e that is claimed analytically (by the prover) and the empirical estimates of this upper bound that can be derived when the auditor uses existing post hoc privacy auditing methods with limited access to the training phase (Jagielski et al.) 2020 Nasr et al. 202 I Lu et al. 2022 Zanella- Beguulll et al. 2023). Thus, it is difficult to draw conclusions as to whether the privacy claim made is valid or not. For instance, Nasr at. (2023) obtain an audited value of 1.6 while the theoretical upper bound is 8.
Soundness. The audit must be robust to malicious provers. Training models with DP often comes at a significant cost in utility (Tramer& & Boneh, 2021] De et al. 2022). Furthermore, implementing DP training algorithms can be challenging and hard- to-tett errors can easily occur (Tramer et al. (202)) as result of uncommon and complex modification to the underlying training optimizer (e.g., minibatch sampling, gradient clipping, noise calibration, and privacy accounting). Therefore, institutions may not adhere to their claims of training ML. models with DP guarantees intentionally [I] (e.g., g. if they are trying to evade privacy regulations to maximize utility) or accidentally (e.g.. if there is hard-to-detect bug in the implementation of their private algorithm).
The audit must preserve the confidentiality of the training data, model pa- rameters, randomness used, and intermediate updates computed during training. Institutions are not willing to share their models and data with external parties due to privacy regulations and intellectual property concerns.
Zero Knowledge.
Our solution. We propose a vero-knowledge proof (ZKP) protocol to proactively generate a certificate of privacy during training while preserving the confidentiality of training data, intermediate model updates and trained model. An auditor can then use this certificate to confirm that the prover did train their model on a private dataset with specific DP guarantee. A ZKP protocol IT allows a party to prove to an auditor that the evaluation of an agreed upon circuit C representing a program on a private input Inp is Out, i.e., C(Ip))
Out, while revealing et al. 1985; Goldreich et al. 1991). In our paper, the private input Inp of the prover consists of the training dataset D and the random seed 8. The circuit C represents a privacy-preserving training algorithm which the prover and auditor agreed on, while Out is the correct output of that algorithm. In the following, we consider the DP-SGD algorithm (Abadi al. 2016), the prevailing approach to differentially private training The circuit C also captures specific values for the hyperparameters of DP-SGD- - such as its noise multiplier, clipping norm, minibatch size and number of training
additional information about Inp (Goldwasser
For example see Apple's ambiguity around not releasing the exact privacy budget of deployed DP mechanism and/or other relevant details (Tang et al. 2017). More generally, institutions often have incentives not train models under the framework of DD or consider a large privacy budget to get a better utilityy.
?Our approach can be easily extended to other DP training algorithms. We illustrate this on the DP-FTRI. algorithm (Kairouz al. 202T in Appendix [)
3

---

Published as a conference paper at ICLR 2024
Algorithm 1: Differentially Private Stochastic Gradient Descent (DP-SGD)
Input: Training dataset
{x, Y), clipping C, learning rule noise multiplier loss function Z(-)
Output: Parameters
Initialize W randomly
2: for 1 E 1 do
Sample minihanch (X((9) yy(0) (X,Y) randonly with probahility 1/Y
for (x.) E [X(0, y00)
g Vw, C(W,, 36]]
Compute per-example gradient clip per-exemple gradient
g: g. min(1, Tells)
+ (2: B: NNU,
> Add calibrated noise Update model parameters Final model parameters
Wil <- W return W
iterations. These hyperparameters influence the strength of the (e, 8)-PP guarantee. Put altogether, our ZK proof protocol II has the above desired properties: Completeness For any input training data and model that is trained on this data with the correct (c, 8) guarantees in the clear, an honest prover (who behaves correctly) can convince an honest auditor that C(mp) Out using nEpoundnesss- Given an input training data and model that is trained on this data with incorrect (e,0)-DP guarantees the clear, no malicious prover (with the ability to behave arbitrarily) can falsely convince an honest auditor that C(Ip)) Out using II; and Zero Knowledge If the prover and auditor execute II to prove that ((mp)) = Out, even a malicious auditor (with the ability to behave arbitrarily) learns no information about the training data, intermediate updates and trained model other than what can be inferred from the fact that the model is trained with the DP-SGD algorithm with (c, 6D guarantees on the training data.
Confidential-
We design a framework, Confidential-DPPe -PProoff. that confidentially and efficiently certifies the upper bound on the privacy leakage achieved by a training run of DP-SGD, foregoing the need to empir- ically audit the protections afforded by the resulting model. ConfidemiallDPproo) works as follows:
Prover publicly announces the privacy guarantees (s, that it is planning to achieve.
Prover and auditor agree on the DP-SGD training algorithm and specific values for its hyperparameters including minibatch size, noise multiplier, clipping norm, learning rate, number of iterations and loss function. These hyperparameters are set to achieve the claimed privacy guarantees (c, 5) while retaining the ability to learn models with high utility.
Prover and auditor run our interactive zero-knowledge protocol and provide a certificate for the claimed privacy guarantee (E, 6). We represent the whole procedure as one single public circuit, allowing the prover to generate one single proof demonstrating to the auditor that it correctly executed all of the steps of the DP-SGD algorithm (see Algorithm
Our proolknoweedg proof protocol can be decomposed into three main phases: i) data commitment; ii) interactive and private randomness seed generation; and iii) zero-knowledge proof of the DP-SGD training. Below, we describe each phase of ConfueentillDPPrroof in detail.
Phase 1: Data commitment. The prover commits to the training data D. Let D (X,Y), be the srivacy-sensitive dataset owned by the prover in which X = {x,, X,,) and Y = [Vr..... }n denote data points and ground-truth labels, respectively, collected from users. These commitments are binding and hiding, meaning that the prover cannot change the content being committed without the auditor's consent and that the commitment does not reveal anything about the underlying content.
..,,
We use Theorettion-Theoretic Message Authentication Codes (IT-MACs) as the basis of this data commitment (Franzese et al. 202T). For each bit possessed by the prover, the prover holds (r, M) and the auditor holds K such that K M @ aA where A is global authentication key uniformly generated by the auditor, and @ denotes XOR. This algebraic relationship prevents the prover, at each
'The (s, -DP guarantees obtained by relying (public) privacy accounting technique. Ensuring the correctness of privacy accounting and of its underlying theoretical derivations are out of our scope.
4

---

Published as a conference paper at ICLR 2024
Algorithm 2: Unbiased randomness seed commitment
Input: Commitment scheme [Commit, Reveal), Hash function H-)), digital signature schome [Gen, Sign, Verify)
Output: Random seed s and signature a
Praver commits uniformly random value obtaining [A] Commit (R), and send [4]] the auditoe.
2: Auditor runs Gen to get signing key sk and verification key pk. generates uniformly random value r. computes
" Sign, ([]] r)), and send u, r. pk to the prover.
Prover sets the seed as = 6
step of the computation, from modifying in any ways that the auditor does not agree to. For more details, please see Appendix B
Phase 2: Interactive and private randomness seed generation. The privacy guarantees of DP-SGD stem from the introduction of randomness at different stages of training randommess which is cali- brated to the sensitivity of the training run to individual training points. Two randomization primitives contribute to privacy in DP-SGD: data subsampling and the addition of noise to the clipped gradients. However, an adversarial prover can bias these sources of randomness to increase the accuracy of their model at the expense privacy, for instance by repeatedly running the training algorithm and selecting the seed that yields the best accuracy, or by deliberately choosing noise terms that have small magni- tudes. In this case, the prover should not be able to demonstrate that the training run provides (c, 5-D guarantees. To ensure that the prover cannot perform such manipulations, we design an unbiased randomness commitment protocol (Algorithm 2 that interactively generates an unbiased randomness seed, and then commits that seed prior to beginning training. First, the prover commits to a random value h and sends the commitment [k] to the auditor. Next, the auditor generates a random r, com- putes and signs the 5 hash Si (H[[k], r)) where sk is the signing key, and sends both the signature v and the random value r to the prover. The prover then sets the unbiased randomness seed as s k@r, and uses it to derive all the randomness in the algorithm. Note that the unbiased ran- domness seed s is random and cannot be biased by the prover or auditor, which guarantees an unbiased source of randomness when subsampling data or noising clipped gradients. This is because the prover and the auditor cannot see values generated by other parties which contribute to the computation of s. When executing DP-SGD, the prover demonstrates that it used the correct seed by verifying the sig- nature v in Algorithm 3 We use SHA-256 as the hash function modeled as random oracle (Bellare & Rogaway| 1993) and AES- 128 as the pseudorandom generator. The hiding and binding quality follows from the security of the underlying scheme for obtaining the commitment and digital signature. We refer to Goldreich| (204) for more detailed discussion on commitment schemes and digital signatures.
Phase 3: Proving the privacy guarantees in ZK. The prover must follow the DP-SGD training algorithm exactly and prove that i) 1 data points were sampled randomly to form a minibatch x(O) at each iteration 4; ii) the associated gradients of a loss function L(:,-) with respect to the model parameters We are computed on a per-example basis, g; = Vw; L(W,, x, Vx; E x()) so that no information is shared across individual data points; iii) the contribution of each example to the gradient are bounded by clipping the l2 norm of these individual per-example gradients by C. gi f gi min(1, ||g: ); iv) draw m (cardinality of each per-example gradient) independent noise samples n = [ni, rmm] from a Normal distribution scaled by C' and the noise multiplier o, Ri, ..., 7m ~ AO0 o²C²), and add to the sum of all clipped per-example gradients g + HE v) model parameters are updated with the aggregated noisy gradients once multiplied by the learning rate 17, ((++1) + W ng: and vi) total of exactly T training iterations were performed. Then, the auditor can verify the claimed privacy guarantee based on the fact that the DP-SGD training algorithm was executed correctly and executed with the specific hyperparameter values for the minibatch size, number of iterations, and noise multiplier.
We represent all the above-mentioned computations in circuits and use EMP (Wang et al. 2016) to encode all operations faithfully and our ZK protocol proves that the circuit evaluation is done correctly. Next, we describe our ZK design (Algorithm 3 for steps involving randomness.
Regarding data subsampling in step (1), we shuffle data points based on a random value generated through Algorithm 2 and then partition the shuffled array of data points into minibatches of the predefined size- starting from the first data point in the shuffled array. This "random shuffle" strategy is often used in practice even though it does not completely match the privacy accounting of
5

---

Published as a conference paper at ICLR 2024
Algorithm 3: Zero Knowledge Proof of DP-SGI Training
Input: Input dataset (X,Y). final model parameters W Zero Knowledge Proof System (P, V
Output: Accept or Reject
1: Prover commitss to the datasel
Praver and Auditor
interactive Algorithm Lio obtain and and prover commits
3: Prover and Auditor agree on circuit Co, (c.c). representing the public Algorithm| [ with fixed inpur hypesparameters [C.n,ee ((-).
circuit takes input as randomness
and as input training dataset.
Prover runs the algorithm P to generate proof for the statement: Cc...e.et)) (D, a) W" and & and
Verifyya ([k]). r). v) Auditor the algorilim V the prouf rr, and outpui Accept and only it V accepts; else outputs Reject
DP-SGD (Tramer& & Boneh 2021). We note that our unbiased randomness commitment protocol can be easily extended to support Poisson sampling (as considered by the privacy accounting of DP-SGD) with negligible cost: each training sample is selected by independently flipping biased coin with probability I/n based on random value generated through our unbiased uniform randomness.
When it comes to sampling independently drawn normally distributed noise to perturb each dimension of aggregated gradients in step (iv), efficiency is paramount. Thus, we first generate uniformly dis- tributed random values and then leverages the Box-Muller transform Box Muller Muller((1955) (1958) to convert them to the desired normally distributed noise. In particular, our confidential noise sampling protocol works as follows: i) Fix the randomness seed by running Algorithm 2 ii) Generate two uniformly distributed random values U1 and U2 in ZK using pseudorandom generator with the above-computed seed s; iii) Compute in ZK ø1 = V-2 In U1 cos (2Tuz) and 22 = v-2 2 In ti sin (2ruz) (these two values are i..dd following normal distribution ensured by Theorem D and iv) Create nn oC21 and n2 = 2C22 that are distributed according to a scaled normal distribution (N0, CO))
Theorem If uy and u2 are two independent and uniformly distributed random values, then 2-2 2n un cos (2xuu) and 22 = --22ln wi sin (2mua) are independent random values from normal distribution with mean zero and unit variance.
Proof. Computing the distribution of V-2 in and using the transformation law (Theorem 1.101 (Klenke, 2013)), we get the following joint density of 21 and 22:
-1
=3
f(21, 22)
{22))(=2).
2
2T
demonstrating that 21 &t2y are independent and normally distributed with mean 0 and variance 1.
4 EXPERIMENTAL EVALUATION
Since we design Confidential-DPprree DPproof to enable institutions to prove the DP guarantees of their model to an auditor while protecting the confidentiality of their data and model, our experiments consider the following major dimensions: i) What the best trade-off' between utility and certified privacy guarantees that Confidential-DPrroo can achieve given the respective interests of the institution training model (in terms of utility) and the auditor (in terms of privacy)? ii) What the cost of verifying the training run while ensuring confidentiality? In particular, how does this cost scale as function of the number of training iterations? To answer these questions, we evaluate the performance of Confidential -Prrof as follows: i) Effectiveness: We design an empirical evaluation of our DP training algorithm in achieving high accuracy in a limited number of iterations; ii) Efficiency: We implement our customized 7KP protocol in EMP-toolkit (Wang et al., 2016) and evaluate its running time in proving the DP guarantees.
Dataset and Feature extractors. We consider two common datasets (see Appendix A). for DP-SGD training benchmarking Tramer & Boneh (202T): Papernot et al. (2021): De et al. y: Shhmssabadi & Papernot (2023): CIFAR-10 and MNIST. Verifying the entire training procedure of complex models calls for heavy cryptographic machinery and the associated computational cost would be prohibitively expensive in most settings of interest once it is implemented cryptographicall. We address this issue by incorporating feature extractors (Tramer & Boneh (021) to enable DP-SGD training of simpler models. We still achieve accuracy-privart tradeoffs that are competitive with the SOTA: instead of training complex model raw dataset with DP-SGD, we train logistic

---

Published as a conference paper at ICLR 2024
CIFAR-10
CIFAR-10
80
0.500
Test accuracy
Ceriified
60
0.400
40
0.300
20
0.200
20
40
60
80
100
20
40
60
80
100
Running time (hours)
Running time (hours)
MNIST
MNIST
Test accuracy (%)
100
Certified
0.600
80
0,400
60
0.200
0
20
40
60
80
100
20
40
60
80
100
Running time (hours)
Running time (hours)
Figure Accuracy and privacy guarantees achieved by Confidential- -Droioff as function of its running time. The running time is computed based on the number of DP training iterations for various DP budgets (e, 10-5). prover can obtain its desired privacy certificate by proving that they cor- rectly executed DP-SGD algorithm over sufficient amount of time using our ZKP protocol without revealing any information about its training data and model. Confidential-DPprog trains models achieving high test accuracy with strong certified privacy guarantees in practical running time.
regression on an embedding of the data. In particular, we extract features for CIFAR-I0 10 and MNIST from the penultimate layer of a SimCLR model (Chen al., 2020) and ScatterNet (Lowe 1999) (see [2, respectively. Following (Tramer & Boneh 2021), we use unlabeled ImageNet, which considered as public data (Tramer et al.) (022) coming from different distribution compared to the distribution of the private data, for training SimCLRR-based feature extractor. ScatterNet is non-learnable SIFT-like feature extractor that uses a cascade of data-independent wavelet transforms. We then train logistic regression model with the DP-SGD algorithm these extracted features. In a private setting, training logistic regressions on extracted features outperforms training complex networks in terms of eecuracy-privant tradeoff (Tramer & Boneh 2021). We also demonstrate that it significantly improves the efficiency of confidential proof of DP training.
Implementation. Two distinct code bases are utilized. We implement our customized ZKP protocol in EMP-toolkit (Wang et al. 2016). EMP-toolkit is a C++ framework with efficient implementations of cryptographic building blocks. Our experiment is conducted on two Amazon Ec2 ml .xlarge machines (ARM machines), representing the prover and auditor. We report the average running time of 100 experiments for each different parameter. We adopt the Python implementation of (Tramer & Boneh 2021 to train our models and assess accuracy and privacy. Recall that our protocol certifies that DP-SGD has been executed correctly. Then the DP guarantee is obtained by running a (public) privacy accounting technique which typically takes as input an arbitrary value of 8 and produces a value for e. We consider the standard the moments accountant technique (Abadi et al., 2016). In practice, a popular choice of is easily verified by the auditor in our framework after the prover has committed to the training dataset.
it as the reciprocal of the size of the dataset, which can be
Results. Figure I shows the effectiveness and efficiency of Confidential- -PPrrif in training models for both CIFAR-TO and MNIST. We visualize the relationship between accuracy and running time and the relationship between certified privacy guarantees and running time. We run in total 225 training iterations and 55 training iterations for CIFAR-IO and MNIST, respectively, and reported the accuracy in the left column of Figure [ and the certified DP guarantee (e) in the right column of Figure [ which both change as function of training iterations. Figure D shows that the company can achieve 80% (respectively 88%) test accuracy with certified privacy guarantee of 0.18 (respectively E = 0.28) in 4 hours (respectively 25 hours) when training a model on CIFAR- 10. Institutions can achieve models with higher accuracy if they are willing train for more iterations: as expected,
7

---

Published as a conference paper at ICLR 2024
Per-example running time
Per Per-minibatch running time
#Attributes
Gradient computation + clipping (8)
Model update (8)
Noise sampling (s)
16
0,005
0.0003
0.0230
64
0,021
0.0011
0.0754
256
0.091
0.0098
0.2713
1024
0.324
0.0550
1.0873
4096
1,462
0.1614
4.5596
8192
3.068
0.3750
9.3851
Table 1: Efficiency and scalability of each building block of Confidential-DPpree in terms of running time for certifying DP guarantees of models trained on benchmark datasets for DP-SGD training. Obtaining privacy guarantee in DP-SGD requires correct per-example gradient computation followed by clipping, carefully calibrated noise addition and correct model updates. Sonfidential-DPprror efficiently proves each of these requirements of DP-SGD while protecting the confidentiality of training data, randomness and model parameters. See Appendix C for experiments conducted on different machines.
the higher the accuracy, the higher the running time. For example, Confudential-PPproodf enables the company to train 91 % accurate model on CIFAR-10 10 with certified privacy guarantees of = 0.55 at the expense of 100 hours running time. Using the same amount of running time but using MNIST this time, Confidential-DPpaee pfroof can train model achieving 98% test accuracy with certified privacy guarantee of & = 0.74. Note that DP-SGD training is costly even in the clear due to the need for per-example gradient computations instead of per-minibatch gradients (Subramani et al.) 2021).
We further evaluate the scalability of Confidential-DD -Prrifff by analyzing the running time of the basic building blocks including per-example gradient computation, noise sampling and model updates as a function of the number of data attributes (values vary in [16, 8192). The results are shown in Table [ and averaged over 100 runs. The second column of Table shows the effect of the number of attributes on the per-example gradient running time. Confidential orppppon can prove the correct per-example gradient computation in a matter of seconds. For example, it takes less than second to compute per-example gradient when the number of attributes is 2048. The third and last columns of Table I report the running time of updating model updates and drawing normally distributed random variables at the end of each iteration for each minibatch. We comment that the per-example gradient computation running times scale linearly for multiple samples, while noise sampling and model updates running times scale linearly for multiple iterations.
5 RELATED WORK
Data-driven privacy auditing. The objective of privacy auditing is to assess the privacy guarantees offered by a given mechanism. This approach has been instrumental in evaluating the tightness
(Nasr et al. 1021: 2023) and correctness (Tramer et al., 2022 Nasr et al.] 2023) of DP machine learning algorithms. The concept of auditing DP originated from the hypothesis testing framework of differential privacy (Wasserman & Zhou 2010). In this framework, an adversary aims to distinguish whether an output O has been sampled from mechanism run either D or one of its neighbouring datasets D' = {D U 2). The adversary's performance, measured by Type I (False Negative Rate, FNR) and Type II (False Positive Rate, FPR) errors, can be translated into a quantifiable privacy guarantee, provided these eтror rates are statistically valid. The conversion to a privacy guarantee can be done in any notion of differential privacy: Jagielski et al. (2020); Nasr al. 2021 used (c, DDP.
Nasr et al. (2023) employed stronger assumptions and used Gaussian Differential Privacy (Dong lt al. 2022). while Maddock al. (2023) converted Renyi Differential Privacy (Mironov] 2017).
The existing privacy auditing methodologies effectively assess system robustness and detect generic bugs, yet they fail to deliver formal proofs for asserted privacy guarantees. This poses a barrier for end-users intending to verify privacy claims. The obstacles to using existing privacy auditing techniques as privacy proofs are two-folded: 1) Adversary Instantiation: The verification of privacy guarantee necessitates the creation of an adversary capable of executing provably optimal membership inference attacks for each user that would like to verify the privacy guarantees of the model. However, the design of such adversary remains unresolved challenge. Provable worst-case adversaries are only identified in restrictive scenarios (Nasr et al., (02T) or when additional
assumptions made on the threat model (Narr et al. 2023 Maddock et al. 2023 Steinke et al.
8

---

Published as a conference paper at ICLR 2024
2023). Although there has been progress towards identifying universally worst-case adversaries for auditing (Andrew et al. 2023), the existing results are only empirical. The lack of a provably optimal adversary when performing privacy auditing calls for alternative strategies verify the correctness of claimed privacy guarantees: 2) Data Accessibility: The formulation of a strong adversary (Shokri et al. 2017, Carlini al. (022) often implies access the training data surrogate dataset with comparable attributes, Such access is often unrealistic in privacy scenarios, highlighting the need for data-independent privacy verification algorithms algorithms that can deliver reliable auditing without access to sensitive data. This will enable audits of privacy guarantees that are able to operate within the practical constraints of privacy- for our proposed methodology, which aims to address these challenges, employing the theory of ZnoolKnoweedge proofs to provide an efficiently verifiable proof for the users.
applications of ML. This sets the stage
Zero-knowledge proof, differential privacy and model training. Prior works mostly use 7K (ZKProots) 2022) to verify the correctness of ML inference (Weng et al.) 2202bb. Recently, it has been shown that cryptographic approaches are necessary for verifying the training of model in non-private setting (Zhagg et al. 2022, Fang et al. (023). There is only one work (Shamsabadi et al.) (2022) that developed ZKP protocols for training but they consider decision trees and the property being verified was faimess- rather than privacy. A handful of work has explored the combination of DP and ZKP. Narayan et al. (2015) change the language primitive of the Fuzz compiler such that the structure of the ZKP that proves the correctness of a response to a query does not leak any information about the dataset. Biswas & Cormode (202)) verify a specific DP histogram-like computation, while Sabater et al. (2022) use 7KP verify decentralized DP averaging queries. In contrast, we propose and implement the first ZK protocol for verifying the correctness of DP training with DP-SGD. Cryp- tographically verifying properties of a training algorithm always more challenging than verifying properties at inference time or verifying statistical queries on datasets; this is in large part due to the limited compatibility of cryptographic primitives with hardware accelerators. In our setting, this challenge is exacerbated because of the specificity of i) per-example gradient computations and clipping in DP training; and ii) the existence of randomness at different stages of DP training such as data subsampling to form minibatches. To address the challenges of efficiency and utility created by ZK proofs for DP training, we instantiate our ZK protocol from a vector-oblivious linear evaluation (Weng et al. a02 and build on SOTA interactive ZK protocols (Yang et al. 202T)
CONCLUSION
Confidential- PProoff can be used to confidentially verify the guarantees of a DP-SGD training run. We demonstrated the effectiveness and efficiency of Confidential-DPprog in enabling institutions to obtain certificate for the DP guarantee they achieved while training high-accuracy models in reasonable amount of time. Confidential- -DProof provides a cryptographic approach to auditing the protections afforded by DP-SGD and will thus enable trust from both end users and regulators.
The certificate provided by Confiddential-PPruugg upper bounds the information leakage from the committed training data. Confidential -atpirttaa----PPoooooo DPproof reduces the incentive for prover to manipulate data to achieve a desired output and then commit to the manipulated data. This is because the prover cannot control the randomness seed as it is been set through our interactive and private protocol with the audi- tor. However, one could further extend Confidential-DPpronn nipulation, such as sharing information across data points, was performed prior to data commitment.
by proving that no adversarial data ma-
Our protocol is designed to attest the correctness of the key and common building blocks of DP algorithms including i) data subsampling: ii) gradient computation: iii) gradient clipping: iv) noise addition; and v) model update. Therefore, our protocol can support any randomized polynomial-time computable function and thus any (tractable) DP mechanism, as illustrated by our extension to DP-FTRL (Kairouz et al. 202T) in Appendix D However, additional implementation in our ZK protocol needed to support them. Once the correctness of the algorithm has been certified, the privacy guarantee can be computed and verified using any existing (public) privacy accounting technique. Therefore, Confidentiall Srifiddenttal-PPproof DPproof is also decoupled from the privacy accounting technique used. For example, our framework is compatible with recent advanced results for DP in the hidden state model YYe & Shokri [2022] Altschuler & Talwar 2022) as our protocol keeps the entire trajectory (i.e., intermediate model updates) hidden from the auditor and can help to improve privacy by incorpo- rating hidden states into the privacy accounting technique. Finally, our framework naturally benefits from future advances in cryptography, which would further improve the scalability of our approach.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
Work of Gefei Tan and Xiao Wang is supported by DARPA under Contract No. HR001120COM 120C0087, NSF award #2310927, #2236819 19, and #2318974. Work of Tudor Cebere and Aurélien Bellet TRR-20CEE230011 (Project PRIDE) and the ANR 22-PECY-0002 IPOP
is supported by grant (Interdisciplinary Project on Privacy) project of the Cybersecurity PEPR. Hamed Haddadi is supported by UKRI Open Plus Fellowship 1P/W005271/1: Securing the Next Billion Consumer Devices the Edge. Nicolas Papernot would like to acknowledge his sponsors, who support his research with financial and in-kind contributions: Amazon, Apple, CIFAR through the Canada CIFAR AI Chair, DARPA through the GARD project, Intel, Meta, NSERC through the Discovery Grant, the Ontario Early Researcher Award, and the Sloan Foundation. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute. Adrian Weller acknowledges support from a Turing Al and the Leverhulme Trust via CFI. Ali Shahin Shamsabadi started
Fellowship under EP/V0252799 this work while he was at The Alan Turing Institute. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.
ETHICS STATEMENT AND REPRODUCIBILITY STATEMENT
Confidential-Pppae enables interested third parties (e.g, users or government) to audit privacy claims made by model trainers (e.g., institutions), while protecting the intellectual properties of institutions. Therefore, Confidential-DPProdd encourages the consideration of privacy while training machine learning models.
We have described our framework in details and our code is available at https://githut com Comm/Draveeeexerimeettt het.eeeeetttttiieeeeeeeeeeeeeeee iat.eeetttttttiiiiieaaaaeaooaoop Gefei Tan/Confidet DPProof 2k
and https:: com/
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the ACM SIGSAC conference on computer and communications security, 2016.
Jason Altschuler and Kunal Talwar. Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. Advances in Neural Information Processing Systems, 2022.
Galen Andrew, Peter Kairouz, Sewoong Oh, Alina Oprea, H Brendan McMahan, and Vinith Suriyakumar. One-shot empirical privacy estimation for federated learning. arXiv preprint arXiv:2302.03098, 2023.
Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In IEEE Symposium on Security and Privacy (SP), 2022.
Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby (eds.), ACM CCS 93, pp. 62-73, Fairfax, Virginia, USA, November 3-5, 1993. ACM Press. doi: 01111666688888188966
Ari Biswas and Graham Cormode. Verifiable differential privacy. arXiv preprint arXiv:2208.0900119 2023.
George EP Box and Mervin E Muller. A note on the generation of random normal deviates. The annals of mathematical statistics, 1958.
Nicholas Carlini, Steve Chien, Milad Nasr, Shuang Song, Andreas Terzis, and Florian Tramer. Membership inference attacks from first principles. In IEEE Symposium on Security and Privacy (SP), 2022.
10

---

Published as a conference paper at ICLR 2024
Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, 2020.
Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlocking high- accuracy differentially private image classification through scale. arXiv preprint arXiv:2204. 2022.
Jinshuo Dong, Aaron Roth, and Weijie J. Su. Gaussian Differential Privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 2022.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014.
C. Fang, H. Jia, A. Thudi, M. Yaghini, C. A. Choquette- Choo, N. Dullerud, V. Chandrasekaran, and N. Papernot. Proof-of-leamne learning is currently more broken than you think. IEEE 8th European Symposium on Security and Privacy (EuroS&P), 2023.
Nicholas Franzese, Jonathan Katz, Steve Lu, Rafail Ostrovsky, Xiao Wang, and Chenkai Weng. Constant-overheud crowedneeedge for ram programs. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, 2021.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security (CCS), 2015.
Oded Goldreich. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, USA, 2004. ISBN 0521830842.
Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):691-729, 1991.
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In 17th ACM STOC, pp. 291-304, Providence, RI, USA, May 6-8, 1985. ACM Press. doi: 10.1 10.1144/22145.22178.
Chuan Guo, Brian Karrer, Kamalika Chaudhuri, and Laurens der Maaten. Bounding training data reconstruction in private (deep) learning. In International Conference on Machine Learning, 2022.
Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani, Reconstructing training data from trained neural networks. In Advances in Neural Information Processing Systems, 2022.
Matthew Jagielski, Jonathan Ullman, and Alina Oprea. Auditing differentially private machine learning: How private is private sgd? Advances in Neural Information Processing Systems, 2020.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling shuffling. In International Conference on Machine Learning, pp. 5213-5225. PMLR, 2021.
Achim Klenke. Probability theory: a comprehensive course. Springer Science & Business Media, 2013.
David G Lowe. Object recognition from local ecale-invarian features. In Proceedings of the seventh IEEE international conference on computer vision, 1999.
Fred Lu, Joseph Munoz, Maya Fuchs, Tyler LeBlond, Elliott Zaresky-Wiin Williams, Edward Raff, Francis Ferraro, and Brian Testa. A general framework for auditing differentially private machine learning. Advances in Neural Information Processing Systems, 2022.
Samuel Maddock, Alexandre Sablayrolles, and Pierre Stock. CANIFE: crafting canaries for empirical privacy measurement in federated learning. In The Eleventh International Conference on Learning Representations, ICLR, 2023.
Ilya Mironov. Rényi differential privacy. In IEEE 30th computer security foundations symposium (CSF), 2017.
11

---

Published as a conference paper at ICLR 2024
Arjun Narayan, Ariel Feldman, Antonis Papadimitriou, and Andreas Haeberlen. Verifiable differential privacy. In Proceedings of the Tenth European Conference on Computer Systems, pp. 1-14, 2015. 2015.
Milad Nasr, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary instantiation: Lower bounds for differentially private machine learning. 2021.
Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagielski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. arXiv preprint w3Xh:22302.07956, 2023.
Nicolas Papernot, Abhradeep Thakurta, Shuang Song, Steve Chien, and Úlfar Erlingsson. Tempered sigmoid activations for deep learning with differential privacy. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1 113-121,,,, 2023.
Md Atiqur Rahman, Tanzila Rahman, Robert Laganière, Noman Mohammed, and Yang Wang. Membership inference attack against differentially private deep learning model. Transactions Data Privacy, 2018.
César Sabater, Aurélien Bellet, and Jan Ramon. An Accurate, Scalable and Verifiable Protocol for Federated Differentially Private Averaging. Machine Learning, 111:4249--44 -293, 2022.
Ali Shahin Shamsabadi and Nicolas Papernot. Losing less: A loss for differentially private deep learning. Proceedings on Privacy Enhancing Technologies, 2023.
Ali Shahin Shamsabadi, Sierra Calanda Wyllie, Nicholas Franzese, Natalie Dullerud, Sébastien Gambs, Nicolas Papernot, Xiao Wang, and Adrian Weller. Confidential-profitt Confidential proof of fair training of trees. In The Eleventh International Conference on Learning Representations, 2022.
Ali Shahin Shamsabadi, Jamie Hayes, Borja Balle, and Adrian Weller. Mnemonist: Locating model parameters that memorize training examples. In Uncertainty in Artificial Intelligence, 2023.
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference attacks against machine learning models. In Proceedings of the IEEE Symposiun on Security and Privacy (SP), 2017.
Congzheng Song and Vitaly Shmatikov, Auditing data provenance in text-generation models. In Proceedings of the ACM SIGKDD International Conference Knowledge Discovery & Data Mining (KDD), 2019.
Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate. Stochastic gradient descent with dif- ferentially private updates. In IEEE global conference on signal and information processing, 2013.
Thomas Steinke, Milad Nasr, and Matthew Jagielski. Privacy auditing with one (1) training run. arXiv preprint arXh::2305.08800 2023.
Pranay Subramani, Nicholas Vadivelu, and Gautam Kamath. Enabling fast differentially private sgd via just-in-time compilation and vectorization. Advances in Neural Information Processing Systems, 34:26409-26421 2021.
Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Privacy loss in
apple's ss implementation of differential privacy on macos 10.12. arXiv preprint arXiv: 1709.02753, 2017.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In The International Conference on Learning Representations (ICLR), 2021.
12

---

Published as a conference paper at ICLR 2024
Florian Tramer, Andreas Terzis, Thomas Steinke, Shuang Song, Matthew Jagielski, and Nicholas Carlini. Debugging differential privacy: A case study for privacy auditing. arXiv preprint arXiv:2202.12219, 2022.
Florian Tramèr, Gautam Kamath, and Nicholas Carlini. Considerations for differentially private learning with large-scale public pretraining, 2022.
Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. EMP-toolkit: Efficient MultiParty computation toolkit. https: btttp::/gittub. com/ www-eeollleeee 2016.
Larry Wasserman and Shuheng Zhou, A statistical framework for differential privacy. Journal of the American Statistical Association, 2010.
Chenkai Weng. Kang Yang, Jonathan Katz, and Xiao Wang. Wolverine: fast, scalable, and communication-cffione zero-knowledge proofs for boolean and arithmetic circuits. In IEEE Symposium on Security and Privacy (SP), 2021a.
Chenkai Weng, Kang Yang, Xiang Xie, Jonathan Katz, and Xiao Wang. Mystique: Efficient proofs with applications to machine learning. In 30th USENIX
conversions for Security Symposium (USENIX Security), 2021b.
Kang Yang. Pratik Sarkar, Chenkai Weng, and Xiao Wang. QuickSilver: Efficient and affordable zero-knowledge proofs for circuits and polynomials over any field. In Giovanni Vigna and Elaine Shi (eds.), ACM CCS 2021, pp. 2986-3001, Virtual Event, Republic of Korea, November 15-19, 2021. ACM Press. doi: 10.1 0155334601103448455
Jiayuan Ye and Reza Shokri. Differentially private learning needs hidden state (or much faster convergence). Advances in Neural Information Processing Systems, 35:703-715, 2022.
Santiago Zanella-Beguelin, Lukas Wutschitz, Shruti Tople, Ahmed Salem, Victor Rühle, Andrew Paverd, Mohammad Naseri, Boris Köpf, and Daniel Jones. Bayesian estimation of differential privacy. In Proceedings of the 40th International Conference Machine Learning, 2023.
Rui Zhang, Jian Liu, Yuan Ding, Zhibo Wang, Qingbiao Wu, and Kui Ren. "adversarial examples" for proof-of-learning. In IEEE Symposium on Security and Privacy (SP), 2022.
ZKProofs. Zkproof community reference, 2022. https:// http://occs..o www.:os..ooooooooooooooo pdf
13

---

Published as a conference paper at ICLR 2024
A
DETAILS ON DATASET
Table shows the details on dataset.
Dataset CIFAR-10 10
Feature Extractor #Attributes
MiniBatch size
Clipping norm
Noise multiplier
ResNeXt ScatterNet
4096
1024
0.1
3
MNIST
3969
4096
0.1
3.32
Table 2: Datasets, feature extractors and hyperparameter values.
B MORE DETAILS ON THE CRYPTOGRAPHIC PRIMITIVES
To authenticate each input z possessed by the prover, the prover and the auditor run secure protocol with subfield Vector Oblivious Linear Evaluation functionality (Weng et al. 2021a) where:
the prover obtains a uniform Message Authentication Code (MAC) Ma;
the auditor obtains global authentication key A and a uniform key Kzi
such that there is algebraic relationship between them: K₂ = M₂ @ xA.
Each step of the computation that modifies v, the prover and auditor will modify K₂ and M2 in an agreed-upon way that will preserve this algebraic relationship given the new updated value of x. The auditor can detect the prover made any modification to or/and did not perform the computation correctly only with the knowledge of Kz, not itself.
To further clarify the process, below we provide a simple summation example for which we: construct the corresponding circuit; iii) describe the circuit evaluation in detail; and iv) describe the verification of the correct behavior in detail.
Assume that the computation that we want to verify is the summation of x and x', x² = + x'.
Circuit construction. The prover and the auditor hold circuit with 1 addition gate. A circuit is defined by a set of input wires along with a list gates of the form (ar, (0,,3,7, T) where o, B are the indices of the input wires of the gate and y is the index of the output wire of the gate and T the type of the gate. The prover has (Ia m.), (z'. m.) and (I,, my), and the verifier holds Ka, K3, K-, such that the above algebraic relationship hold between each pair of them. We denote such authenticated value by [>i] which means that the prover holds (Ia, m.) and the auditor holds Ka.
Circuit evaluation. Authenticated values are additive homomorphic, then they can locally compute [a:"]] = [xx.]] + [xa]] as follows: i) the prover computing x" = x + x' and M." M2 + M and ii) the auditor computing K2. K2 + Kg--
Verification. Once the parties have authenticated values for the output of multiplication, the prover sends Mf to the auditor, and the auditor checks whether the algebraic relationship between Kz x" and Mf holds to detect whether the prover did not do the computation correctly or the prover modified without informing the auditor.
C PERFORMING EXPERIMENTS ON DIFFERENT MACHINES
To demonstrate consistency across different hardware, we have included results from experiments conducted on different machines. We analyze the running time of the basic building blocks including per-example gradient computation, noise sampling and model updates data attributes across three different machines with different CPUs: ARM. intel, and AMD (m I. Exlarge, m77..xxlarge m7a.2 2xlarge, all with 16GB of RAM) in Table and Table These results demonstrate that the trends and conclusions drawn from our results reman consistent and reliable across different machines.
function of the number of
14

---

Published as a conference paper at ICLR 2024
Per-example running time
Per-minibatch running time
#Attributes
Gradient computation + clipping (8)
Model update (8)
Noise sampling (s)
16
0,009
0.0004
0.0285
0,018
0.0014
0.0505
0.032
0.0020
0.1004
128
0.052
0.0051
0.1995
256
0.124
0.0062
0.3885
512
0,248
0.0187
0.7625
1024
0.533
0.0275
1.5874
2048
1.048
0.0689
3.1763
4096
2.121
0. 0.1498
6,4705
8192
4.196
0.2844
12.657
Table 3: Efficiency and scalability of each building block of Confidential -Proooff in terms of rumning time for certifying differential private guarantees of models trained on real-world datasets. Experiment result Intel machines.
Per-example running time
Per-minibatch running time
#Attributes
Gradient computation + clipping (s)
Model update (8)
Noise sampling (s)
16
0,012
0.0005
0,0344
32
0,025
0.0017
0.0676
0.047
0.0028
0.1320
128
0.095
0.0077
0,2587
256
0.188
0.0099
0.5352
512
0.375
0.0250
1,0065
1024
0.747
0.0467
2.0179
2048
1,489
0.0934
4.0886
4096
2.984
0.1944
8.0601
8192
5.944
0.3867
16.2481
Table 4: Efficiency and scalability of each building block of Confidential -PPocoff in terms of rumning time for certifying differential private guarantees of models trained on real-world datasets. Experiment results on AMD machines.
D VERIFYING DIFFERENTIALLY PRIVATE FOLLON-THE-REGUUAARZEE--
(DP-FTRL)
In this section, we demonstrate that our protocol can support Differentially Private Follow-The- Regularized-Leadee (DP-FTRL) (Kairouz et al., 2022). To do that, we demonstrate that implementing DP-FTRL using our ZK framework is simple.
Implementation. The DP-FTRL protocol only needs the following operations: arithmetic operations, public indexing of arrays, and sampling noise from the Normal distribution. All of these operations are already supported in our ZK protocol for DP-SGD. These operations used in the ZK proof only need to rearrange/repliccaeed to support the steps DP-FTRL. In fact, the implementation of DP-FTRL in ZK is easier than the DP-SGD one as the DP-FTRL algorithm does not need shuffling and sampling which are needed DP-SGD. These two operations are complicated due to existence of randomness.
Results. We train for one epoch over dataset of size 100 with 16 attributes. We report the running time of verifying DP-FTRI. and compare it with DP-SGD (for DP-SGD, we set the size of the minibatch to 5). Table reeports the running time of our framework for verifying DP-FTRL algorithm and its comparison to DP-SGD. The "Model update" column shows that the cost tree aggregation of DP-FTRL is low. The "Noise sampling" column shows that noise sampling is the most expensive part of DP-FTRL which is expected as it needs to generate as many noise samples as the number of nodes in the tree. These results demonstrate that implementing framework is simple.
DP algorithm using our
Implementing other algorithms. In general, an extension our framework for verifying a new DP algorithm A can be seen as separate steps:
15

---

Published as a conference paper at ICLR 2024
DP Algorithm
Gradient computation + clipping (8)
Model update (8)
Noise sampling (s)
DP DGD
0.822
0,084
0,519
DP-FTRL
0.824
0.161
3,460
Table 5: Verifying Differentially Private Follow-The Thw--eeguarizzed-eeeeee (DP-FTRL) and its compar-
ison with DP-SGD.
Using our unbiased randomness protocol to generate an unbiased randomness seed. If A requires randomness to be unbiased (for example for noise sampling and data subsampling), it can take advantage of our unbiased randomness protocol.
Rewriting A in C++ using ZK framework library. Our ZK framework is intuitive to as it supports all essential floatpoint arithmetics. Our ZK framework will then automatically generate circuit for A (step of Algorithm B) The input of the circuit and the public parameter can all be set using our framework. Once we have the circuit for A, our framework will proceed to the rest of Algorithm
16


Reviews:
[{"review_id": "2IyJtXqTOM", "reviewer": "Reviewer_y3Ya", "summary": "This work studies important problem in data privacy research, the privacy auditing problem. The main approach is a zero-knowledge proof protocol for differential private machine learning.", "questions": "1. How this framework to give guidance to correct DP-SGD implementation if the algorithm did not pass the privacy auditing?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper seems well-written.", "weaknesses": "Due to my lack background of zero-knowledge proof, it's difficult to evaluate the contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NJXbKtL4tU", "reviewer": "Reviewer_PSjV", "summary": "This work proposes a protocol for auditing DP-SGD. The approach is based on zero-knowledge proof and does not require the auditor to access the model and raw data.", "questions": "1. What are the hyper-parameters: $C, \\sigma, T$ in your experiments, and what are the corresponding theoretical upper bounds on $\\epsilon, \\delta$?\n2. Compared to the privacy upper bound provided for the chosen $\\sigma$, how accurate are the certified privacy guarantees?\n3. The results do not show certified level of $\\delta$.\n4. The running time may vary across different machines and may not be a consistent measure of computational cost.\n\n## Update\nIncrease my score to 6 after the authors quickly implemented ZKP for DP-FTRL.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The problem of verifying privacy claims of algorithms is very important practically.\n2. The proposed protocol based on zero-knowledge proofs does not require the auditor to access model parameters, data, and intermediate updates. \n3. The authors take into account malicious auditors and dishonest provers in various aspects of the protocol such as random seed generation and", "weaknesses": "1. The auditor needs to know many implementation details, e.g. clip threshold, and number of iterations. Also, the protocol is specifically designed for DP-SGD. It seems that we need to design different protocols for different algorithms, even if we only make minor adjustments to the algorithm. \n2. Many steps in the DP-SGD algorithm need to be proved in Phase 3. If one step is missing, for example, the auditor forgets to let the prover verify step vi, the total number of iterations, how would it affect validity of the privacy audit claims made by the auditor?\n3. The proposed cryptographic approach does not scale to large models trained with DP-SGD.\n4. It seems to me that the protocol only attempts to verify that every step of the DP-SGD algorithm is executed correctly as claimed, and the certified privacy parameters are simply derived based on the verified $\\sigma$ and subsampling level, which is an upper bound on the actual privacy guarantee (as stated in the conclusion). Thus, when the certified upper bound exceeds the claimed value, we do not know whether there is a privacy failure. Note that even with 100% correct execution of DP-SGD, privacy failure may still exist due to other issues like finite precision computation of floats [1]. Thus, verifying all steps are executed correctly is not sufficient to audit privacy claims, and a privacy lower bound should still be necessary.\n5. How does the approach compare to the recent work of [2]?\n6. I have questions regarding the experiment setup. See the question section.\n\n[1] Widespread Underestimation of Sensitivity in Differentially Private Libraries and How to Fix It, S Casacuberta, M Shoemate, S Vadhan, C Wagaman, CCS 2022\n\n[2] Privacy Auditing with One (1) Training Run, Thomas Steinke, Milad Nasr, Matthew Jagielski, https://arxiv.org/abs/2305.08846\n\n\nTypos:\n1. Page 5, line 10 (the description of phase 2): \"Next, the auditor generates... and sends.. to the auditor\". The second \"auditor\" should be \"prover\"?\n2. Page 6, line 2: we first generates -> generate", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8LBLiVafDS", "reviewer": "Reviewer_yrMg", "summary": "The authors propose a zero-knowledge proof (ZKP) protocol, dubbed Confidential-DPproof, for an auditor to verify that a company (prover) has trained a ML model using DP-SGG at a certain privacy level, on a fixed private dataset (which should not be revealed to the auditor). Their method has three desirable properties:\n\n1. An honest prover can convince an honest auditor that they have correctly implemented DP-SGD (and therefore that the resulting model is differentially private at a certain level, known to both parties);\n2. A dishonest prover cannot convince an honest auditor that the trained model satisfies DP when it in fact does not; and\n3. A dishonest auditor cannot bias the computations of an honest prover. In particular, a dishonest auditor cannot gain additional information about the training data, beyond what they would know from observing the output of a DP algorithm trained on the private data.\n\nExperiments with Confidential-DPproof show that the ZKP mechanisms still allow for practically feasible runtimes for model training. The authors obtain strong model utility on CIFAR-10 and MNIST, while still enforcing strong DP guarantees ($\\epsilon < 1$).", "questions": "I do not have extensive background with ZKPs, so I would like to make sure my understanding of the paper is correct. Can the authors confirm if the following statements are true?\n\n**Unbiased random seed generation:** From the honest prover's perspective, since $k$ was chosen uniformly at random and the auditor only knows $[[k]]$ (but nothing about $k$ itself), the random seed $s=k\\oplus r$ is still uniformly random. From the honest auditor's perspective, since $r$ was chosen uniformly at random _after_ $k$ was fixed, $s$ must be uniformly random.\n\n**Dataset commitment:** For verifying that the computations were performed on the committed dataset, we can think of it as follows. The data commitment is another key $K$ which depends on the dataset $\\mathcal{D}$, but which gives the auditor no information about $\\mathcal{D}$ (since it was an XOR with a private random quantity $M$ known only to the prover; this is similar to the relationship between $k$ and $[[k]]$ above). However, for each circuit $\\mathcal{C}$ making up a step of the DP-SGD procedure, the prover can verify that the output of this step was computed on $\\mathcal{D}$ using the agreed upon random seed, and this verification _only requires knowledge of $K$_, not $\\mathcal{D}$ itself.\n\n**DP-SGD privacy accounting:** This leads to my final question. It seems that the ZKP building blocks allow you to generate a proof for each iteration in DP-SGD, then the proof for the whole procedure is just the AND of all of these steps. In particular, this means that the auditor actually will see all of the intermediate models during the DP-SGD training procedure. There has been some recent work on improving the privacy guarantees of DP-SGD under the assumption that the algorithm output is only the _final_ model parameters $W^T$, rather than the entire trajectory [1]. Confidential-DPproof would be incompatible with this analysis, since there isn't a ZKP protocol (yet) which encodes the entire model training procedure, rather than just the individual steps.\n\nReference:\n[1] Ye, Jiayuan, and Reza Shokri. \"Differentially private learning needs hidden state (or much faster convergence).\" Advances in Neural Information Processing Systems 35 (2022): 703-715.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "Confidential-DPproof provides a strong alternative to current methods for privacy auditing, which require instantiating membership inference adversaries to exploit the output of allegedly DP algorithms, thereby providing a lower bound on the privacy leakage. Unless the adversary can be shown to be optimal, however, this approach cannot provide an _upper_ bound on the privacy leakage. In general, implementing such attacks is also computationally difficult, and optimal adversaries are often intractable.\n\nBy approaching the problem from a different angle, the authors completely sidestep the need for optimal adversaries for verifying privacy guarantees. This is especially impressive because many of the strongest membership inference attacks require access to the private data in order to be trained (or at least a very good proxy), but this is unrealistic in practical scenarios requiring privacy. In contrast, their method does not require the auditor to have access to any private training data. As such, I believe this to be an exciting, non-incremental contribution, one which has the potential to change the paradigm for privacy auditing moving forward.", "weaknesses": "As ICLR is not primarily a security conference, it is likely that many readers will be unfamiliar with the terms and methodology used. As such, more discussion of the cryptographic primitives used would be helpful in improving the clarity of the paper. (See the \"Questions\" section below.)\n\nDue to the additional computational overhead imposed by both DP-SGD itself, and the need to represent the steps of the algorithm in circuits which can be integrated with existing ZKP systems, the authors cannot train full neural networks. Instead, they rely on fixed feature extraction methods trained on public data or using other methods independent of the private training data, then train a logistic classifier on top of these representations. Even with these simplifications, gradient computation + clipping can still take over a second per sample in higher feature dimensions. However, as the authors point out in the related work, even the problem of computationally feasible non-private proof of learning is still unresolved. This would be an important avenue for future work in order for this auditing protocol to be applied to modern models with hundreds of billions of parameters trained on massive datasets.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)