Confidential-DPproof: Confidential Proof of Differentially Private Training

We thank you for your careful reading, detailed and kind comments!

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.

We confirm that this is correct, none of the prover and the auditor can bias the randomness seed. For example, the prover cannot bias the randomness seed $s$ by changing $k$ because the prover does not know the value of $r$ which is chosen by the auditor and is part of the computation of $s$. Therefore, even if the prover manipulates the value of $k$, the prover still sees $s$ as a uniformly random variable. The auditor, similarly, cannot bias the randomness seed $s$ because the auditor does not see $k$.

We revised the last part of Phase 2 near the top of page 5 which says:

“Observe that $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.”

to:

“Note that $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$.”

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.

We confirm that this is correct, the verification only requires the knowledge of the key (not the data). In particular, to authenticate each input $x$ possessed by the prover, the prover and the auditor run a secure protocol with subfield Vector Oblivious Linear Evaluation functionality where: the prover obtains a uniform Message Authentication Code (MAC) $M_x$, the auditor obtains a global authentication key $\Delta$ and a uniform key $K_x$, such that there is an algebraic relationship between them: $K_x = M_x \oplus x \Delta$.

Each step of the computation that modifies $x$, the prover and auditor will modify $K_x$ and $M_x$ in an agreed-upon way that will preserve this algebraic relationship given the new updated value of $x$. The auditor can detect if the prover made any modification to $x$ or/and did not perform the computation correctly only with the knowledge of $K_x$, not $x$ itself.

To further clarify the process, below we provide a simple summation example for which we:

1. Construct the corresponding circuit
2. Describe the circuit evaluation in detail
3. 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+x’$.

Circuit construction. The prover and the auditor hold a circuit with 1 addition gate.

A circuit is defined by a set of input wires along with a list of gates of the form $(\alpha,\beta,\gamma,T)$ where $\alpha,\beta$ are the indices of the input wires of the gate and $\gamma$ is the index of the output wire of the gate and $T$ is the type of the gate.

The prover has $(x_{\alpha},M_{\alpha})$, $(x_{\beta},M_{\beta})$ and $(x_{\gamma},M_{\gamma})$, and the verifier holds $K_{\alpha},K_{\beta},K_{\gamma}$ such that the above algebraic relationship holds between each pair of them. We denote the authenticated value by $[[x]]$ which means that the prover holds $(x_{\alpha},m_{\alpha})$ and the auditor holds $K_x$.

Circuit evaluation. Authenticated values are additively homomorphic, then they can locally compute $[x_{\gamma}]=[x_{\alpha}]+[x_{\beta}]$ as follows: The prover computing $x’’=x+x’$ and $M_{x’’}=M_x + M_{x’}$ The auditor computing $K_{x’’}=K_x+K_{x’}$

Verification. Once the parties have authenticated values for the output of multiplication, the prover sends $M_{x’’}$ to the auditor, and the auditor checks whether the algebraic relationship between $K_{x’’}$, $x’’$ and $M_{x’’}$ holds to detect whether the prover did not do the computation correctly or the prover modified $x$ without informing the auditor.

We added this discussion in Appendix A and referred to it in Section 3.

We thank you for your review!

The auditor needs to know many implementation details, e.g. clip threshold, and number of iterations.

Yes, as written at the beginning of Section 3, the prover and auditor agree on the DP-SGD training algorithm and specific values for its hyperparameters. This is also the case in all privacy auditing approaches and does not impose any overhead. These hyperparameters would typically be set by the prover to achieve high utility and shared with the auditor to verify the claimed privacy guarantees $(\varepsilon,\delta)$.

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.

Our protocol, coupled with the unbiased randomness sampling protocol we propose, can support any randomized polynomial-time computable function and thus any (tractable) DP mechanism. In particular, our protocol is designed to attest the correctness of the key and common building blocks of DP algorithms: 1) data subsampling; 2) gradient computation; 3) sensitivity analysis; 4) noise addition; and 5) model update. Therefore one does not need to design new protocols for a new DP algorithm; however, extra implementation in ZK is needed to support them. Note that our approach 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 [Jiayuan & Shokri, NeurIPS 2022; Altschuler & Talwar, NeurIPS 2022] as our protocol keeps the entire trajectory (i.e., intermediate model updates) hidden from the auditor and can help to improve the privacy by adding hidden states into the privacy accounting technique.

We added this discussion in Section 6.

[Ye & Shokri, NeurIPS 2022] Jiayuan Ye, and Reza Shokri. "Differentially private learning needs hidden state (or much faster convergence)." NeurIPS 2022

[Altschuler & Talwar, NeurIPS 2022] Jason M. Altschuler, Kunal Talwar: “Privacy of Noisy Stochastic Gradient Descent: More Iterations without More Privacy Loss.” NeurIPS 2022

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?

We would like to stress that rather than verifying each step separately, our protocol allows the prover to generate a single proof to show that every step in the DP-SGD is computed correctly. This is reflected in step 3 and 4 of Algorithm 3 where the DP-SGD algorithm is encoded as a public circuit. So if the prover skips a step in the algorithm, it will not be able to produce a valid proof and the auditor will be able to tell. This follows from the soundness property of the underlying ZKP framework. We clarified this at the beginning of Section 3 by saying:

``Prover and auditor run our zero-knowledge protocol and provide a certificate for the claimed privacy guarantee $(\varepsilon,\delta)$. 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 1).”

Thanks for your response. You have addressed some of my concerns such as the certified level of $\delta$, runtime on different machines, and that the proof relies on a single circuit rather than verifying each step separately. However I still have questions, and some of my questions might have been misunderstood so I would also like to clarify them here. Pretty much all of my concerns fall into two categories: I. the flexibility and applicability of the framework. II. whether the certified privacy level is actually valid and independent.

Flexibility of the proposed approach

As you have mentioned proving a different algorithm would require a new implementation of ZKP, I wonder how much work is needed? Say we want to verify DP-FTRL (Algorithm 1 in the arxiv version of [1]), how difficult it is to implement a ZKP for this "variant" of DP-SGD?

The scalability of large models is also an issue. While I agree that recent advancement in self-supervised learning enables private training of much smaller models on top of pre-trained models, there are recent works, e.g. [2] that try to privately train large foundation models due to copyright and privacy concerns of "public" datasets on the internet. Therefore auditing large models is still very relevant in practice.

You also mentioned that knowing the specific algorithm and hyperparameters is needed "in all privacy auditing approaches and does not impose any overhead". This might be true for "white-box" auditing. However, existing works in privacy auditing also consider the "black box" scenario where the auditor only has access to the model weights. See Algorithm 3 in [3].

Questions on the privacy claims.

The proposed approach only verifies that the DP-SGD algorithm is executed correctly at every step. My main concern is that this is may not sufficient to provide an independently certified privacy claim, and that is the main reason I brought up [4], not to ask you to address this finite precision issue but to show as an example that even if every step of the algorithm is perfectly and correctly executed, privacy failures can still exist due to other potentially unknown implementation issues. If a similar failure indeed occurs, then I believe that the ZKP protocol would still provide a "certified" privacy upper bound, but the actual privacy loss may be much higher.

In principle, I believe the certified privacy level given by the auditor should ideally be independent of the privacy accounting method and/or the theoretical derivations of the privacy upper bound, but this work heavily relies on those things to provide a certified privacy guarantee. Apart from the subtle implementation issues mentioned above, another issue actually comes from incorrect proof of privacy guarantees. Let's say some of the most popular privacy accounting methods actually have some subtle mistakes in their proof resulting in a higher privacy loss than their theoretical claims, I don't think the algorithm in this work can actually detect it and provide a certified privacy guarantee close to the true privacy loss.

Conclusion

As such, while this work proposes an interesting application of zero-knowledge proof to verify differential privacy claims, I do not think it is a revolutionary work that completely reshapes the current landscape of privacy auditing. In my opinion, this work is slightly orthogonal to existing works on privacy auditing because it only verifies that the algorithm is implemented correctly as opposed to providing an independently certified privacy guarantee. There are technical merits of the proposed approach such as not requiring access to the model and data, and taking into account both malicious auditor and prover.

I acknowledge that verifying the implementation can serve as an important primary step in verifying the privacy claims and has practical values. In that case, the applicability of the proposed framework to a wider class of DP algorithms would be paramount. I believe this submission would be much stronger if the authors could demonstrate or explain that extending the framework to other algorithms can be done with relatively small effort.

[1] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, Zheng Xu, Practical and Private (Deep) Learning Without Sampling or Shuffling https://arxiv.org/pdf/2103.00039.pdf

[2] Yaodong Yu, Maziar Sanjabi, Yi Ma, Kamalika Chaudhuri, Chuan Guo, ViP: A Differentially Private Foundation Model for Computer Vision

[3] Privacy Auditing with One (1) Training Run, Thomas Steinke, Milad Nasr, Matthew Jagielski, https://arxiv.org/abs/2305.08846

[4] Widespread Underestimation of Sensitivity in Differentially Private Libraries and How to Fix It, S Casacuberta, M Shoemate, S Vadhan, C Wagaman, CCS 2022

Due to my lack background of zero-knowledge proof, it's difficult to evaluate the contribution.

Our contribution lies at the intersection of machine learning, differential privacy and cryptography, and thus leverages and combines concepts from these multiple fields. We understand that it is difficult for a single person to have good expertise in all three domains, but we have done our best to make the paper as accessible as possible, and for this purpose we have added more discussion of the cryptographic primitives and our protocol. For example, we

1. Explained the data commitment, computation and verification in our framework with more details and provided an example of a summation, circuit construction, evaluation and verification [see Appendix A]
2. Explained that our framework represents the whole DP-SGD training procedure (not just a single iteration) as one single public circuit, allowing the prover to generate a single proof [see Section 3]
3. Explained with more details that our framework hides intermediate updates and the entire trajectory from the auditor, thus making it compatible with recent techniques of hidden states in DP which improve further the privacy of the prover

We can concisely summarize our contributions as follows:

1. Introduced desiderata for privacy auditing;
2. Proposed the first zero-knowledge protocol which enables auditors to directly verify the exact ε of a DP-SGD training run, and thus providing a certificate of privacy;
3. Protected the confidentiality of private training data, model parameters, and intermediate updates;
4. Designed and implemented a specialized ZK proof protocol to efficiently perform the DP training;
5. Submitted our code as supplementary material to facilitate the future work in this direction that we initiated.

Finally, please see the comments of reviewer yrMG who confirmed our contributions and said:

• ``I believe this to be an exciting, non-incremental contribution, one which has the potential to change the paradigm for privacy auditing moving forward”;
• ``a strong alternative to current methods for privacy auditing”;
• ``By approaching the problem from a different angle, the authors completely sidestep the need for optimal adversaries for verifying privacy guarantees. This is especially impressive’’.

How this framework to give guidance to correct DP-SGD implementation if the algorithm did not pass the privacy auditing?

Thanks for the good suggestion. Our framework can be extended to support identifying the cause of failure (i.e., which part of DP-SGD was not computed correctly) by generating separate proofs for each step of the DP-SGD. This comes at additional costs such as proving the consistency of intermediate values between proofs of each step. Given these complexities, we believe that a careful and thorough exploration is needed and we leave this to future work.