Secure and Confidential Certificates of Online Fairness

We thank the reviewer for noting the strength of our paper. We respond below to both questions raised.

The overall algorithm seems to apply classic zero-knowledge proof algorithm to the setting between a prover and verifier which would like to certify the group fairness gap is bounded by a small value. Could you further clarify why this is not a trivial combination?

We emphasised that our approach is indeed non-trivial, and we explicitly considered the baseline you suggested – a classic combination of ZKP with fairness verification.

Why the problem is non-trivial:

Securely auditing group fairness requires simultaneously satisfying two critical security properties:

1. query authentication from clients, and
2. output authentication from the model owner.

(1) is necessary to prevent model owners from cherry-picking data, which makes their model appear fair, and (2) is necessary to prevent malicious clients from interfering with the auditing process by presenting false outputs.

Ensuring both while keeping the protocol efficient and scalable, especially for large neural networks, poses a significant technical challenge.

Why the classic ZKP-based approach is insufficient:

As you suggested, one might attempt to apply a classic ZKP framework to prove correct inference on every query and then prove that the fairness metric holds over all queries. We implemented this baseline (Lines 260-262). As shown in Figure 4, applying classic ZKP to the setting introduces a huge increase in client-facing runtime, computationally infeasible for practical deployment. This is because this naive combination of fairness computation and ZKPs requires proof of correct inference for every user query.

Our approach – why it's non-trivial:

Our approach, OATH, introduces a novel cut-and-choose technique that exploits statistical properties of group fairness. OATH achieves strong bounds on fairness violation while only verifying a constant number of user queries (with respect to the total number of queries).

This paper did not discuss how floating number is handled. Do you truncate them to fixed point? The fairness gap in Definition 4.1 involves the difference between quantities computed from two groups. We only know the magnitude of quantities after the model is deployed, which may be challenging for fixed point?

We use the floating point number implementation in EMP-toolkit. EMP-toolkit supports floating point numbers by representing each float as a list of 32 authenticated bits, and then computing floating point operations as boolean circuits evaluated via the zero-knowledge proof protocol in [47].

Thank you for the review.

Fairness should be conceptually explained before the formal definition.

We will improve our exposition on fairness by revising the Fairness subsection in the preliminaries, and adding the following text:

“Demographic parity requires that the probability of a positive outcome for each demographic subgroup is nearly equal. For instance, if an ML model assists a bank with allocating loans, the model should give a male clients loans about as often as it gives them to female clients.”

Does the experiment include the evaluation of some real models, like CNN or GNN? How about the parameter number influence the method performance?

Yes, our experiments in the paper include evaluations of real CNN models such as ResNet-101 (42.5 million parameters) and ResNet-50 (23.5 million parameters). Our design enables “plug and play” fairness auditing for any classifier with a zero-knowledge proof of correct inference.

Figure 4.b illustrates the impact of model parameters on the method performance. The results indicate that the online runtime (i.e., service phase runtime) is independent of the number of model parameters. However, the audit runtime increases as the number of model parameters increases, as the correctness check (Algorithm 2 line 20) requires a ZKP correct inference of the model, which scales with the model size.

Secure auditing is a classical problem in information security, and fairness auditing of machine learning models can be considered as a special secure auditing problem. Are there any specific challenges faced by fairness verification when compared with the traditional secure auditing problem?

Most works in the literature that use Secure Auditing as a keyword (e.g. [a] “Secure auditing and deduplicating data in cloud” and [b] “Dynamic-hash-table based public auditing for secure cloud storage”) are concerned with verifying information integrity in cloud storage. Using these methods directly would be insufficient to verify the integrity of the predictions from the service provider’s ML model, though adapting them to efficiently verify the database of client queries $Q$ could be an interesting direction for future work. The key difference in the settings is that if we do not verify the integrity of the model prediction output by the service provider, i.e. that $M(q_i)=o_i$, then the service provider is free to switch models or indeed output arbitrary decisions, rendering the results of the fairness audit unreliable for future clients. This is why we require zero-knowledge proofs of ML inference as a component of OATH.

Would the reviewer please verify whether this is their intended meaning when referring to secure auditing as a classical problem in information security?

Related work.

We compared against existing published fairness auditing approaches, namely Black-Box audits [34, 35, 37] as well as both previous works that leveraged ZKPs to enforce model fairness (FairProof [49] and Confidential-PROFIT [40]). We also created a baseline based on ZKP of correct inference, Mystique [48].

The ref [1] suggested by you is a preprint that was submitted to arxiv on May 12, 2025 – only three days before the NeurIPS submission deadline (May 15, 2025). Given this it was not feasible to discuss it in our manuscript. We will add the following to our revision:

"In concurrent work, [1] proposed a new zkSNARK-based proof of fairness. Their approach is highly efficient, but relies on proving bespoke bounds for each new model type, unlike OATH which can "plug and play" to automatically prove fairness for any model with a zero-knowledge proof of inference. Thus we are able to evaluate our method on more complex architectures such as convolutional neural networks, while their study is limited to logistic regression and multi-layered perceptrons."

We thank the reviewer for the positive assessment of our paper.

Any other baseline methods to be compared, e.g. in terms of the trade-off of relaibility / efficiency?

We compared against existing fairness auditing approaches, namely Black-Box audits [34, 35, 37] as well as both previous works that leveraged ZKPs to enforce model fairness (FairProof [49] and Confidential-PROFIT [40]). We also created a baseline based on ZKP of correct inference, Mystique [48]. We will clarify these categories in the introduction as:

“Black-box fairness auditing considers an auditor who has only query access to a model, and so measures fairness based on submitted queries and observed decisions of the service provider. By contrast, white-box fairness auditing approaches release client data and the service provider’s model to the auditor, who can then verify fairness. Both approaches have drawbacks: the white-box setting is seldom used in practice due to issues with confidentiality, while the black-box setting does not provide the auditor enough information for a rigorous audit [9] (for example, nothing prevents a service provider from using one model during the audit, and a completely different one to answer client queries).

Zero-knowledge proofs of fairness [40, 49] are an emerging line of work that address both of these weaknesses using cryptographic tools. Zero-knowledge proofs essentially provide secure “white-box” access to the auditor for a set of pre-specified operations, while retaining (and in fact improving upon) the confidentiality of the black-box setting.”

We will add a comparison of all these fairness auditing approaches in terms of the trade-off of reliability / efficiency:

it would be good to empirically demonstrate the defense capability of the proposed method e.g. under various attacks (data-forging or model-swtiching).

Defence capability of the proposed method against

• Model switching attack: Model switching attacks are fully mitigated by the zero-knowledge proof of correct inference included in our protocol. This is because the proof verifies that the inference was run on the committed model (Line 20 in Algorithm 2).

• Data forging attack: Figure 3 (Section 5.2) and Figure 5 (Appendix H) empirically quantify the probability that a cheating service provider evades the detection component of our protocol when falsely claiming a group fairness threshold $\theta$ by using a forged dataset. These results show that our protocol is robust: a service provider that cheats with a larger than negligible $\epsilon$ will be caught by the auditor with high probability. The reason we have not added more empirical results is that we theoretically establish this robustness in Theorem 4.1 and proved that it only depends on the number of verified queries. However, we are happy to extend our empirical results under additional attack scenarios if the reviewer feels it would strengthen the paper.

have you ever considered to apply the same approach to address other issues e.g. online-security certificate?

Thank you for the thoughtful suggestion. Fairness has the convenient property of being a measurable function of model input/output pairs, allowing us to utilise evaluation data directly in order to audit fairness. That said, we agree that extending this approach to domains like online security is an interesting future direction. We will add the following to our discussion of future work:

“An interesting future direction would be to explore the applicability of ZKP certificates to online-security guarantees.”

The authors thank the reviewer for this perspective. We posit that weaknesses raised in this review are primarily issues with communication across an interdisciplinary line (between cryptography and machine learning), rather than problems with the merit of the work. The reviewer raises many good points which will help us address those communication issues. We hope that this rebuttal will make our contributions more clear, and that the reviewer will continue in dialogue with us to make the paper stronger and more impactful for all readers.

the paper makes it sound like the proposed zero-knowledge proof protocol protects the confidentiality of the model, namely, it prevents the auditor from learning the parameters of the model, but this is simply a consequence of the fact that the auditing is performed in a black-box fashion.

We clarify the difference between black-box audits and zero-knowledge proofs with the following text, which we will add to our introduction:

“Black-box fairness auditing considers an auditor who has only query access to a model, and so measures fairness based on submitted queries and observed decisions of the service provider. By contrast, white-box fairness auditing approaches release client data and the service provider’s model to the auditor, who can then verify fairness. Both approaches have drawbacks: the white-box setting is seldom used in practice due to issues with confidentiality, while the black-box setting does not provide the auditor enough information for a rigorous audit [9] (for example, nothing prevents a service provider from using one model during the audit, and a completely different one to answer client queries).

Zero-knowledge proofs of fairness [40, 49] are an emerging line of work that address both of these weaknesses using cryptographic tools. Zero-knowledge proofs essentially provide secure “white-box” access to the auditor for a set of pre-specified operations, while retaining (and in fact improving upon) the confidentiality of the black-box setting.”

Addressing the reviewer’s point directly: while a black-box audit does indeed keep model parameters confidential, only a zero-knowledge proof can keep model parameters confidential while also guaranteeing that the audit was computed correctly. For example, if we do not use a ZKP to verify that $M(q_i)=o_i$ (i.e. that the model prediction output by the service provider is correctly computed), then the service provider is free to switch models at will or even output fully arbitrary decisions, rendering the results of the fairness audit unreliable for future clients.

Why doesn’t the client simply query the model and then send the corresponding pair (sensitive attribute_i, prediction_i) to the auditor?

This black-box approach is insufficient for two main reasons:

• It can be abused by the clients who may report a prediction to the auditor which is different from the one they received, in order to make the service provider’s model appear unfair. We discuss this possibility in Appendix C: “a malicious [client] may seek retribution for an undesirable model prediction.” We will move this discussion to the main text for clarity.
• It can be abused by the service provider because it offers no way to verify whether the service provider’s output was a model prediction or simply an arbitrary decision. If we do not verify that $M(q_i)=o_i$ (where $q_i$ is the query data of the ith client, and $o_i$ is the prediction given to the ith client) using a zero-knowledge proof of inference, then the service provider is free to switch models or indeed output arbitrary decisions, rendering the results of the fairness audit unreliable for future clients. This opens the door to e.g. fairwashing attacks discussed in previous work [1, 39].

The consensus of many related works in the literature (e.g. [10, 28, 31, 32, 38, 40, 42, 48, 49]) is that cryptographic methods are necessary to close vulnerabilities such as these.

Is the sensitive attribute a feature of the client (Algorithm 1, Line 2) or of the query (Algorithm 2, Line 7)?

We thank the reviewer for raising this point. Indeed, in typical fairness literature sensitive attributes are considered a feature of the query only, rather than a feature of the client. We did not distinguish between these two cases, since they are equivalent in all of our experimental evaluations: e.g. in the COMPAS dataset the sensitive attribute is race, so a client’s sensitive attribute would not change for different queries. To align with the previous literature, we will update Algorithm 1, Line 2 to read: {$s \gets q.$sensitive_attribute}.

Our implementation handles this without modification.

the sensitive attribute can be inferred from other attributes in the query (proxies). Hence, protecting only the sensitive attribute, as is done in this paper, would not be sufficient. & it's not clear which entity performs Steps 6-10 in Algorithm 2: if it is the service provider, then I don't see how we can prevent it from cheating on this point, and simply return a number that verifies the fairness threshold. If it is the auditor, then it learns (in Line 7) the sensitive attribute of the client, since it knows from which client the query $q_i$ comes.

It is not the case that our method protects only the sensitive attribute of the client query. Our method prevents the auditor from learning any information about the entire client query, using the security guarantees of zero-knowledge proofs. It also prevents the service provider from cheating. These properties are both guaranteed by our ZKP building blocks. This is discussed in Appendix B, but we provide additional detail here:

• Values appearing in double brackets are IT-MAC authenticated. The notation $[[x]]$ means that that the auditor holds a global key $\Delta$ and a message key $K_x$, while the service provider holds the value $x$ and message tag $M_x$ such that $M_x = K_x + x \cdot \Delta$.
• Whenever operations on authenticated values are written (e.g. in Steps 6-10 of Algorithm 2), it means that we are using the zero-knowledge proof protocols in [46, 47, 17] to perform those operations securely. The auditor and service provider work together, computing distinct operations on their respective pieces of the authenticated values. These result in new authenticated values for the outputs.
  • The methods for performing secure operations on authenticated values are complicated (see [47]), but we will give a simple example: finding sum of authenticated values $[[z]] \gets [[x]] + [[y]]$. To accomplish this, the auditor computes $K_z \gets K_x + K_y$, while the service provider computes $z \gets x + y$ and $M_z \gets M_x + M_y$. This preserves the relation $M_z = K_z + z \cdot \Delta$ (which can be checked at the end of the protocol to prevent the service provider from cheating by changing the value of $z$) even while the auditor never sees the values $x, y, z$.
• The security proofs in [47, 17] show that these operations are guaranteed to compute the outputs correctly (via the Soundness property of the zero-knowledge proof) and without revealing any information to the service provider (via the Zero-Knowledge property).

Thus, cheating and breach of confidentiality are indeed prevented in Steps 6-10 of Alg 2. We will add more detailed exposition to the zero-knowledge proof section of the preliminaries, and add an expanded walk-through example to the Appendix, to make the use of authenticated values more clear.

Notation.

In cryptography literature $||$ and $\oplus$ are standard notation for concatenation and XOR respectively. We will define both explicitly in the revision.

What are the values of the sensitive attribute? In Line 78 they are a,b, but in Algorithm 2, they seem to be 0,1.

We will clarify this by unifying sensitive attribute values to be {0,1} everywhere in our revision.

Thanks for the explanation, the example of COMPAS is very clear now. I had misunderstood and scenarios you are addressing and the goals of your paper, because I am used to a different trade-off between fairness and privacy in the context of ethical AI. I will raise my score.

I suggest that you include the example of COMPAS, in the way you have explained to me, in the revised version.