Secure and Confidential Certificates of Online Fairness
Authors: Olive Franzese
Ali Shahin Shamsabadi
Carter Luck
Hamed Haddadi
Venue: NeurIPS 2025 poster ()
Keywords: auditing
fairness
zero-knowledge proofs
privacy-preserving ML
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: We design an efficient cryptographic method for verifying ML fairness with respect to data received online during deployment.

Abstract: The "black-box service model" enables ML service providers to serve clients while keeping their intellectual property and client data confidential. Confidentiality is critical for delivering ML services legally and responsibly, but makes it difficult for outside parties to verify important model properties such as fairness. Existing methods that assess model fairness confidentially lack either (i) *reliability* because they certify fairness with respect to a static set of data, and therefore fail to guarantee fairness in the presence of distribution shift or service provider malfeasance; and/or (ii) *scalability* due to the computational overhead of confidentiality-preserving cryptographic primitives. We address these problems by introducing *online fairness certificates*, which verify that a model is fair with respect to data received by the service provider *online* during deployment. We then present OATH, a deployably efficient and scalable zero-knowledge proof protocol for confidential online group fairness certification. OATH exploits statistical properties of group fairness via a "cut-and-choose" style protocol, enabling  scalability improvements over baselines.

Secure and Confidential Certificates of Online Fairness
Olive Franzese
Ali Shahin Shamsabadi Brave Software London, UK
University of Toronto & Vector Institute
Toronto, ON olive. fransess@@acttoiissttttte
Carter Luck
Hamed Haddadi
University of Massachusetts, Amherst Amherst, MA
Imperial College London Brave Software London, UK
Abstract
The "black-box service model" enables ML service providers to serve clients while keeping their intellectual property and client data confidential. Confidentiality is critical for delivering ML services legally and responsibly, but makes it difficult for outside parties to verify important model properties such as fairness. Existing meth- ods that assess model fairness confidentially lack either (i) reliability because they certify fairness with respect to a static set of data, and therefore fail to guarantee faimess in the presence of distribution shift service provider malfeasance; and/or (ii) scalability due to the computational overhead of confidentiality pereeler---eerinnggg cryp- tographic primitives. We address these problems by introducing online fairness certificates, which verify that a model is fair with respect to data received by the service provider online during deployment. We then present OATH, a deployably efficient and scalable zero- vero-knowledgs proof protocol for confidential online group fairness certification. OATH exploits statistical properties of group fairness via a cout-and-choose style protocol, enabling scalability improvements over baselines.
Introduction
Service providers commonly adopt a "black-box service model" provide ML-driven services to clients in sensitive domains like finance and healthcare. The confidentiality offered by the black box critical for protecting data privacy and Intellectual Property (IP), but hinders the ability of outside
parties to verify properties of the model such as fairness [16] 24 Since MI. models are susceptible
bias based on race, sex, color, disability, or location 43 25
21 6 20 2), verification
of fairness is also critical in sensitive applications. In this work reconcile these two important objectives-fairess and confidentiality-be asking:
How ensure that deployed models are fair while preserving confidentiality?
Existing solutions (detailed in Appendix A) for confidential fairness assessment include black-box auditing (35 34 37 and cryptographic verification [40] 49 28 38 44), but nearly all certify fairness only with respect to offline data such as a static training or audit dataset. Such offline fairness certificates suffer from unintentional or intentional fairness assessments failures when the model is deployed (Figure I first row).
Unintentional issues of offline fairness certificates. In practice, offline faimess certificates fail generalize to unseen data encountered during deployment (e.g., online client data) as distribution shift is common in real-world applications [13 and challenging account for during training (IT). Distributional shifts can actively reinforce biases [ As a result, faimess guarantees established offline may not hold once the model is deployed. For example, previous study of real-world
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Prover (Service Provider)
Random Challenge
Validation
Offiine
Online
O2
02
On
Violation 0
Check ZKP
Distribution Shift oe Audit
Gaming
Fairness
Faimess
Verifier (Auditoo)
Violation: 0.00
Violation: 1,00
Service Phase
Audit Phase
Class
Sensitive Altribute
fy Decision Boundury
Client Data
Figure 1: Limitations of Offline Fairness Certificates (left) and Overview of OATH (right). Offline fairness certificates based on offline audit data fail when facing real-world distribution shifts or audit gaming, leading to significant fairness deviation-Demon Demographie Parity (DP) fairness violation increases from 1. OATH issues an online fairness certificate of the black-box service provided to clients reliably, efficiently, and securely. During the service phase, OATH authenticates client queries and service provider responses to enable accountability without having to perform client-facing ZKPs. In the audit phase, the service provider and auditor verify only asymptotically constant number of client queries while providing provable guarantees on overall group fairness violation.
distribution shift on US census data showed that fairness certified under distributions from 2014 failed to provide fairness for data gathered in 2018 [II.
Intentional abuse of offline fairmess certificates. Many approaches for offline fairness certifica- tion [35 34 37 9 can be circumvented entirely via a "model switching attack" wherein the service provider fair model during the audit, and different model during deployment. This attack allows arbitrary alterations to fairness on online client data, and can be concealed very effectively via post-hoc "fairwashing" methods (39 Service providers can bypass other audit methods (40) via "data forging attack", wherein the malicious institution constructs an "easy" offline dataset on which the model satisfies fairness constraints, despite failing to meet those constraints for online data.
We formulate the concept of online fairness certificates, which remediate these issues by measuring fairness directly from the client data received online during deployment. To preserve confidentiality, we issue online fairness certificates using zero-knowledge proofs (ZKPs), a cryptographic method that enables verification of information about hidden data [18 19]
Zero-knowledge proofs of fairness 440 49 are an emerging line of work that address weaknesses of both black-box and white-box fairness audits using cryptographic tools. 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 faimess. 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 rigorous audit [9] (for example, nothing prevents service provider from using one model during the audit, and a completely different one to answer client queries). Zero-knowledge proofs essentially provide secure "white-box" access the auditor for of pre-specified operations, while retaining (and in fact improving upon) the confidentiality of the black-box setting.
We place two recent works in ZKP auditing into the newly defined category of online fairness certificates: [49] proves online certification of individual fairness, and [I] certifies general audit metrics. While these works important, their deployment is substantially limited by lack of scalability ZKPs for validating ML services are computationally expensive, often requiring minutes of runtime answer each client query [8
49 42 Here we complement these works with new
method for online certification of group fairness [16] [22] with excellent scalability. Group fairness assesses statistical parity between demographic groups for outcome attribution and error rates. OATH achieves its scalability by exploiting a synergy between cryptographic ceut-and-choose"-sttee
5
verification and statistical properties of group fairness.
Overview of OATH. Our method consists of two phases (Figure second row):

---

Service Phase. Clients query the service provider's model, and send the auditor cryptographic commitments to their results. They perform no expensive ZKP operations, offloading them the service provider and auditor in the next phase.
Audit Phase. The service provider commits
measurement of the fairness metric across all queries in the evaluation set. Then, they verify validity on a randomly sampled subset the queries. [53] verification provides statistical bound on the group fairness that is robust to arbitrary malicious behavior from the service provider, while maintaining excellent scaling for large numbers of client queries.
This "cut-and-choose"-sty
Contributions. We summarize our contributions as follows.
Online Group Fairness Certificate. OATH audits group fairesss over large sets of data received from clients online, rather than assuming fairness will generalize from a static set of offline data.
Scalability. We exploit statistical properties of group fairness audit arbitrarily large set of queries to large neural networks using a constant-sized probabilistic sample (Theorem 4.1). On neural networks with 42.5 million parameters, OATH achieves 4.4 seconds of amortized runtime per query, of which only 0.23 seconds require the client to be online.
Confidentiality & Reliability. Our cryptographic protocols guarantee that i) the auditor learns no information about the evaluation data or model parameters; and ii) the service provider cannot tamper with the audit's s measurement of fairness, except within very small probability and effect size that do not impact practical use.
Our code
publicly available
https://github..
ctt.aau.ocoomeeeeeeeeaaaa /
oath zk- onl ine- www.nesiires...ee. git
Background, Preliminaries & Related Work
ML Preliminaries. In this work we focus on probabilistic binary classifiers. That is, we consider models that can be represented as mappings M : X' x {0, 1) + {0, 1}. where X is feature space, and {0, 1 for some &t E N is the space of random seeds. We assume that one feature of each query point E X' corresponds to a binary demographic attribute {0, 1} E S such as sex, race, or disability.
Fairness.
The ML community has proposed various fairness definitions tailored to different philo- sophical assumptions and contexts. We focus on group fairness [2) 12 22 which ensures statistical parity across different subgroups. For simplicity, we demonstrate verification of demographic par- ity 77] in the main text, and generalize to other metrics in Appendix [B] In this work
interested in verifying whether demographic parity is satisfied within public threshold, as formalized below.
Definition 2.1. [Thresholded demographic parity] A predictor Y satisfies demographic parity with respect to sensitive attribute S within a public threshold 0 if:
Pr[ý = =| = -P(f 1|S 11 50
Demographic parity equalizes the probability of providing positive outcome, V = across each subgroups with different demographic variables 0 and Therefore, receiving positive outcomes is independent of inclusion in particular subgroup. This fairness definition is necessary for several life- changing tasks such as loan approval and recruitment so that applicants from different demographic groups have equal access to financial services and have equal chances of being hired 30].
is cryptographic protocol conducted between prover P and verifier V, who both have access to public circuit ZKP allows to convince V that they know some witness w such that P(w) 1. See Appendix C for formal properties of ZKPs. We use two ZKP protocols from prior work as building blocks for general zero-knowledge boolean circuit evaluation [77. and verified array random-access [17] respectively. The security of our methods follow directly from the security of these underlying building blocks, which are proven secure under the Universal Composability [8] framework.
Zero-Knowledge Proofs (ZKPs). A ZKP I8 19
3

---

We use the notation [>>] to indicate that P and V hold an IT-MAC-based authentication of z. More precisely, means that V holds a global key A and message key KG. while P holds message tag M, and the value æ. These components hold the algebraic relationship
M K2 + x
as an invariant.
In this work, whenever an operation on authenticated values is written (e.g. [=] means that P and V are working together to perform special secure operations on their respective pieces of the authenticated values (detailed in 47 17 46),, such that the algebraic relationship is maintained. The relationship is used the end of the ZKP protocol to check whether P performed computation accurately, without the V learning any information about the underlying values. See Appendix
- [a]] + L&D, it
C for additional details.
Commitments. We employ a standard hash-based commitment scheme [77. which enables party with an input value x to produce a commitment string Cr that can later be opened to verify the committed value. This prevents P from modifying client queries between the Service and Audit phases of our protocol. See Appendix (eanndxxffoor for details.
ZKPs of Correct Inference. A subset of ZKP methods are devoted to efficiently proving that inference was computed correctly given ML model [88 10]. We note that while their efficiency is improving substantially, they are still not fit for client-facing facing usage in many applications, requiring over ten minutes per verified inference for larger models. We use ZKPs of inference generically as subroutine in our work as a component of proving fairness, conducted while the client is offline.
Cryptographic Protocols and Fairness. A few previous works leveraged ZKPs and secure multiparty computation (MPC) to enforce model fairesss. Confidential-PRRFFE ZKP protocol for proving that a decision tree adheres to group fairness constraints training time. However, Confidential-PROFTE work most closely related and complementary to ours, introduces online individual fairness [16 26
44) provides an efficient
suffers from issues of offline fairness certificates. FairProof [49]. the
certificates. However, FairProof requires several minutes of runtime per client query even for very small models. (28) extended MPC protocols proposed by [32] to enable a service provider to train fair logistic regression model clients' data while keeping their demographic attributes confidential. (38 uses MPC to verify fairness inference. These MPC-based approaches require secure computation between the service provider and every client, which limits scalability. Our work achieves greatly improved efficiency by having the service provider commit to queries, and prove their validity probabilistically when the clients are offline.
In concurrent work. [52] proposed new zkSNARK-bass proof of fairness. While their approach is highly efficient, it relies proving bespoke bounds for each new model type. In contrast, our work can "plug and play" automatically prove fairness for any model with zero-knowledge proof of inference. Thus while their results on logistic regression and multi-layered perceptrons are laudable, our work differs in its ability to support proofs of fairness for more complex architectures such as convolutional neural networks we show in the results section.
See Appendix D for a recap of notation used in the paper.
3 Problem Formulation
Parties and Inputs. We consider three classes of parties: service provider or prover P, and a third third-party auditor or verifier V. and set of clients {C, ) who possess the online data. Specifically, each client has query point zi E X, which they send to P in order to receive binary decision o, E {0. from model M.
Goal. The auditor V aims to assess whether P's model is fair. Formally, the auditor wants to check whether M satisfies Definition 2.1 given some public threshold 0 on the fairness gap (set e.g. by regulations as acceptable fairness gap in practice), measured via empirical probabilities over the online data and model decisions.
Security Model. Our protocols are secure against malicious adversary corrupting P or V. The adversary may perform arbitrary behavior during protocol execution to disrupt it. Nevertheless it

---

is guaranteed that (i) P cannot falsely convince V that the model is fair, except with negligible probability and effect size (characterized in Theorem 4.I., and (ii) V learns no information about any data or model parameters other than whether the faimess condition holds.
We assume that each client submits query points that are representative of real features and de- mographic attributes. Authentication of this information is typically placed outside of scope for algorithmic techniques. Instead delegated outside mechanisms (e.g. the financial system authenticates inputs to loan recommendation models via legal liability for perjury). For clarity of notation in this work, we assume that each C, submits a single query point qi X, though in practice clients could submit multiple queries.
We assume that none of P. V. {c,)=_1 collude with each other. Severe legal penalties prevent collusion between regulatory bodies and companies, making this reasonable in practice. We assume that all parties have access to secure point-to-point communication channels, and that all C 's have been authenticated before protocol initiation - i.e. neither P nor V can launch "Sybil" attacks wherein they generate fake clients. We operate under the random oracle model for cryptographie hashing.
Blame Attribution and Denial of Service. A malicious P or C may tamper with the message sent to V during the Service Phase, which could be used to launch a denial of service attack. To deter this, we guarantee that if the Audit Phase aborts, either P or C can reveal information which correctly identifies the party responsible for the failure, preventing repeated denial of service.
4 OATH
The goal of our method is to enable a third-party auditor V to measure the fairness of the service provider P's ML model from online data provided by the clients {C, We use ZKPs to guarantee correct measurement of group fairesss, while ensuring that V learns no information about the data or model parameters. OATH is made computationally efficient by its "cut-and-choom" maad-choose"-stie -style [33 design: during the Service Phase, clients send the auditor binding and hiding cryptographic commitments to the online data and output they received from the service provider. Then in the Audit Phase, the auditor and service provider perform a ZKP to (i) measure group fairness from all online data, and then (ii) check group-balanced random sample of the online data for tampering.
Example Application. Consider the of algorithms deployed in criminal justice. Suppose P is the service provider of a proprietary ML model used in courtrooms to assign risk scores to defendants. set of N court offices utilizing the model are the clients {C+, and an independent review body seeking to measure fairness of the algorithm is the auditor V.
To utilize OATH, in the Service Phase each court office collects dossiers from the defendants. The offices submit the dossiers as queries to P. and send a cryptographic 'receipt' of each query to V via Algorithm[] [ Then in the Audit Phase, P and V use Algorithm 2t prove group fairness across all received queries. Using OATH in this application accomplishes three main goals: (i) the fairness of P's model is measured correctly - cannot alter their outputs make the model appear more fair, (ii) intellectual property is protected since neither the court offices nor V learn anything about the model, and (iii) data privacy is protected since the review body obtains no information about the defendants, which is important in many real-world settings where legislation may prevent the sharing of data across jurisdictions.
4.1 Service Phase
The first part of OATH is the Service Phase, wherein each C, queries P's model, and V receives cryptographic commitment to each answer. These commitments leak no information to V. They will later be used in the Audit Phase to verify the correctness of the faimess audit via ZKP.
Algorithm I performs committed query answering. First, and P generate fair random coins (obtained using e.g. (33) to prevent manipulation of the randomness used for the model decision. C samples two random strings an, O' to encode their sensitive attribute s. They send both og. ai to V, and only a, to P. We note that the purpose of a, is not to hide from P 8 is a component of which P gets to see in plain text. Rather, these values prevent from being able to change s before the audit without getting caught.
5

---

Algorithm 1: OATH Committed Query Answering.
Input:
Public: security parameter X; C: query point 4: P: model M: V: inputs.
Output: model decision o, randomness r: P: query point q, randommess vs commitment string
(q]lo]rr)
C and P generate fair coins r;
+- secnsitive_atttibutee 10,1};
samples cto, 01 _ [0,1)"
C sends ql a. to P;
C computes sig, computes Vrfy(g||a=||r;; sigp). Abort if fails; P computes o +- MM (q. and sige Sign(g]]a_|lo(|r) P sends o, sigg to C:
Sign(g]lo=_|Ir) and sends sig, to P;
C computes Vrfy(gl <x. |lo|/ll/ sigc). Abort if it fails; 10 C computes C f H (glla lollr), and sends C' and Cip Or to V.
In the Audit Phase, P will prove in zero-knowledge that the string matches the sensitive attribute they received from C. can only guess a with negligible probability, so this prevents them from flipping the client's s sensitive attribute bit before the Audit Phase. This enables an efficient sensitive attribute check Algorithm
C then sends a signed query to P, and P responds with a model output only if they successfully verify the signature. Likewise, P sends C signed query answer, which the client verifies before accepting the output. If both steps succeed, C sends commitment to the query and result to V. C also sends ag. 0r, the random strings encoding
Blame Attribution. If verification fails in the Audit Phase, the signature each party's 'stt'' inputs provides a publicly verifiable record of the query which can be revealed to to identify which party was the source of the dishonest behavior. See Appendix E for technical details.
Online Efficiency. Cryptographic commitments are much less computationally intensive than ZKPs. By supplying V with commitments that can be verified via ZKP without any client input, we obtain client-facing efficiency comparable to ML as service query answering without cryptographic verification. By contrast, performing a ZKP of fair inference online with each client requires runtimes on the order of minutes per client with state of the art methods, even tiny neural networks [49]. Our commit online, prove offline design dramatically improves usability and scalability.
At the end of the Service Phase, V will have obtained a commitment C₁ and sensitive attribute check strings aij af corresponding the query and answer each {C, In the Audit Phase, these committed queries are assessed for fairness.
4.2
Audit Phase
The second phase of OATH measures group fairness from committed online data via suite of ZKP operations conducted solely between P and V while C. stays offline. Our protocols guarantee correctness of the fairness measurement, and prevent from learning any additional information about the data or model parameters.
Algorithm 2 begins with P making IT-MAC-based authentications of all query-answer tuples (gi, Ti, 0:) E Q. This enables assessment of fairness in lines 6- 11, via verified estimation of
Pr(o; = 8 0] and Pr(o: = 1|s; 1] (line 11) on all queries in Q. Line 12 samples queries uniformly from each group (i.e. with
0 and v with s; = 1). Algorithm 6 details ZKP subroutine for group-balanced sampling. placed in Appendix for brevity.
Validity Checks. We implement three validity checks to deter P from modifying Q:
Sensitive Attribute Check P fails they try to modify the sensitive attribute of any client.
Commitment Consistency Check P fails they modified any part of the query sent by C, during the Service Phase, for all C, selected by the group-balanced uniform sample.

---

Algorithm 2:
OATH Zero- Knoooodd Fairness Audit.
Input: public: the number of client queries faimess gap threshold 0, soundness parameter vs; P: model M. online data = [[gs a2e, oz rs)] commitments {C.) sensitive attribute check
strings {(o ai ) =
Output: V obtains Upacs E {0, 1] indicating whether M satisfies demographic parity with respect to Q.
// Step 1: imitialization
for i E [1. do
L authenticates (Iv.I: [at]. [r]] [o.]):
PP authenticates [M];
P authenticates [co]] and [ei] initialized to zero;
Count positive out-cones in each denographic group Count individusls denographic group
P authenticates [[o]] and [T]]] initialized to zero;
// Step 2: Measuring Group Fairness
i E [1, do
[s:] f- gg.dregggapphcc
_ttrribbut
[b] <- [[s:] == 0).
[b]] [[s:] == 1):
b. Indicator bit for denographic attribute Update group counte
[no] [no]] + [6o]. [mn]
< [m]] [b1]
10
b Update positive outcome counte Fairness gap computation and comparison to the threshold [Araed] <-
[co] < [co] + [[6b] [o.]] [e]] f [ei] + (16.1 [o]]):
[col
// Step 3: Validity Checks
12 <- Group-Balanced Uniform Sampling(Q. v); b An array indicating selected samples (Algorithn 6
13 for i [1, do // Sensitive Attribute Check
14
V/ sends ab, af to P:
15
P proves [[[a:] = ob) @ ([af] = at)) = 1:
16
[&a] + [[o.] [|ao]== = a
P proves [s, == [<]]
18
if [eS]
then
// Conmi tment Consistency Check proves H (1:1lo)/[)):]))) == Cs;
// Inference Correctness Check
20
P proves [o:] = [ using Fist
21 If any of the proof's fail, abort. Otherwise, Reveal ([
Inference Correctesss Check - P fails if they gave C, any output o, * M(q,, during the Service Phase, for all C, selected by the group-balanced uniform sample.
In line 15 P verifies that the [o:]] authenticated in Step 1 is equal to least one of the sensitive attributes committed to the client, without revealing which one. Since C, only sends a to P in the Service Phase and V waits until after [a is authenticated to send a at a malicious P can only falsify this check they guess a².. This occurs only with negligible probability. This approach to verification is similar to the generation of random labels for wire values in garbled circuits, classical cryptographic technique [50]. Lines 16 and 17 verify that the sensitive attribute encoded by [a is consistent with the sensitive attribute used in the rest of the protocol.
Line 19 verifies commitment consistency by proving that the values P used in the Audit Phase are consistent with the values that C, committed to in the Service Phase. Line 20 verifies that was the proper result of inference with the authenticated model M (q,, ) by using ZKP of correct inference Firt as subroutine. In line 21, the indicator bit bpass is revealed as long as the ZKP protocol was carried out correctly and all of the checks lines 13-20 pass. This signals to V whether the fairness condition (Definition 2.1 holds, within probabilistic bound characterized in the next section.
4.3 Analysis of Probabilistic Audit
To achieve highly efficient amortized runtime and communication, the zero-knowledge audit in Algorithm 2 performs probabilistic check audit integrity by verifying random subset of queries sampled from Q. Our analysis shows that the probability with which malicious P. can wrongly demonstrate that their model is fair decreases exponentially as a function of sample size.
7

---

We proceed by defining an ideal measure of fairness - the group faimess gap that would be computed was fully honest and comparing it to the group fairness gap computed when malicious P submits a modified collection of queries as input to Algorithm [
We then analyze the probability that P is able to execute Algorithm 2 without detection when these quantities differ by some <>>
Qh be the collection of query-answer answer tuples imput to Algorithm P assuming perfectly honest P, which notably implies: i) queries are always answered using correct computations of inference M; and ii) modifications have been made to the queries recorded in the Service Phase.
Definition 4.1. Honest & Measured Fairness Gaps. Let (q., rs,
We will refer to Xh. demographic parity gap computed on Qu. as the honest fairness gap. We have
Xn ElaroootER Of (T((8)
Digonoo)E 04 (x))))
(mnoroo))) Ta(%) Where the indicator La if and otherwise.
Σ (m..ooo))) Is(8))
Let Xm. the measured fairness gap, refer to the same quantity but computed on an arbitrary collection of query-answer tuples of malicious P's choosing Qm-
Xm Ein.rooiee.... 04 (1(8))
Einroneee... OF Io(8s)
Eigirr.o))E..... Ia(s)
Theorem 4.1. Let Xn, be the honest group fairness gap and Xm the measured group fairness gap computed during Algorithm Consider > O, the deviation between these quantities caused by
malicious P cheating, defined: E |X - -xm| Then is caught with probability
Poatch 2 1 -1-(1-1 2
where v is the number of queries uniformly sampled within each group via Algorithm (a total 2v).
The proof is in Appendix G The intuition is that the larger Q is, the more queries P must maliciously modify to alter the group fairness gap (Definition 4.1. This in turn increases the probability that a modified query shows up in the verified random sample, resulting in P getting caught.
Theorem shows that the probability that P can escape detection for altering V's measurement of function of the number of sampled queries 2v. The base of the exponent increases with the magnitude of the alteration e. This bounds the probability that P escapes detection any given Thus, we can parameterize the audit to make it highly improbable that P could impact the measured fairness by amounts that matter practice. We conduct empirical analysis of parameter settings in Section
the group fairness gap declines exponentially
5 Empirical Evaluation
We empirically evaluate the efficiency. scalability, and correctness of OATH for providing repeatable fairness audit of ML-based services while protecting the confidentiality of evaluation data and model parameters.
Objectives.
Datasets. We consider five common datasets for fairness benchmarking (described in Appendix COMPAS (2) Crime [36], Default Credit [51], Adult B and German Credit [15].
Implementation. We implement OATH in C++ using EMP-toolkit 446 (under an MIT License). All experiments were conducted by locally simulating the parties on a MacBook Pro laptop CPU.
Models. OATH uses zero-knowledge proof of correct inference Filt subroutine in order to accommodate arbitrary binary classifiers. We evaluate OATH using three different settings for Funt (i) logistic regression (LR) implemented in EMMPtoolkin (ii) small
neural network (FFNN) with ReLU activations suitable for tabular data implemented in EMP-toolkit, (iii) larger neural networks suitable for image data using Mystique (48 with three different networks LeNet-5 (62K parameters), ResNet-50 (23.5 mil parameters), and ResNet-101 (42.5 mil parameters).
Baselines. We compare the efficiency of OATH against a baseline method for confidential online fairness certificates of group faimess.. The runtime for this baseline is estimated by (i) computing

---

Table Mean & SD runtimes across 3 trials of the Service and Audit Phases of OATH when applied to Logistic Regression (LR) or Feed-Forwart Neural Network (FFNN). For the Service Phase, we report the runtime (s) per query for each client C₁. For the Audit Phase, which occurs between the service provider (P) and the auditor (V), we report the total runtime (min) across 10 client queries.
Audit (min)
Dataset
Service (siquery)
LR
FFNN
COMPAS
0,25 0.01
82.8 = 0,01
93.1
0.29
Crime
0.23 4 0.02
83.3 2 0.02
101.8 + 0.6
Credit
0.23 0.03
53.3 1: 0.03
103.2 1 1.0
Adult
0.22 + 0.02
$3.1 + 0.02
German
0.23
84.7 0.06
123.3 =
a ZKP of correct inference using Fint for each query, and (ii) proving that the fairness metric is satisfied over all queries. We compute this baseline for LR, FFNN, and larger neural networks using Mystique [48]. We also compare to FairProof [49]. ZKP method for online certificates of individual fairness. We emphasize that individual fairness and group fairness are distinct metrics, and as such OATH and FairProof are performing distinct, complementary tasks. We compare against FairProof to give context for the computational overhead of online fairness certification.
5.1 Efficiency of Certifying Standard Fairness Benchmarks
OATH consists of client-facing Service Phase, and an Audit Phase conducted solely between the service provider and auditor after many client queries have been aggregated. Table [ shows the runtime of each phase for all five datasets across multiple runs. Overall, the run times are practically efficient even for very large numbers of queries.
Service Phase Runtime. The first column of Table I reports Service Phase runtime, the time required to provide a committed response to client query using P's model. The Service Phase has a negligible and consistent runtime across all datasets ranging from 0,22 to 0.25 seconds. This consistent efficiency is due to the small amounts of communication involved in the Service Phase, making the bottleneck the round time rather than the amount of communication. This makes the runtime appear independent of the number of attributes and the type of model used by the prover across all the datasets in these experiments. The excellent efficiency of the Service Phase means that OATH can be integrated into deployed ML pipelines without disrupting service.
Audit Phase Runtime. The second and third columns of TTble|]repon Audit Phase runtime when OATH is verifying either a LR or FFNN model respectively. This the time required to audit the faimess of authenticated client query answers with our ZKP protocols. We assume 10 total client queries, 7600 of which are randomly selected for consistency and correctness checks. This size of the random sample was identified empirically as good tradcoff between efficient runtime and strong 2 tamper protection (see Section 5.2 for details). Figure presents an ablation study of runtimes for the different components of the Audit Phase for logistic regression. The Correctness Check (Algorithm line 20) dominates the runtime. See Appendix [. for detailed breakdown Audit Phase runtime. Though the Audit Phase is more computationally intensive, it is highly practical for periodic auditing.
5.2 Parametrization of Probabilistic Audit
Section 4.3 proves an efficiency / reliability trade-off: the more verified queries 2v, the smaller the probability that P can alter the audit's fairness measurement by e without being caught, As shown in the previous section, the runtime bottleneck of OATH scales with the number of verified queries. Therefore, it is important to identify parameters that limit the required runtime for the consistency check while ensuring reliable measurement of fairness.
For example, setting v 1000 means that any e 2 0.01 evades detection with probability at most 6.65 x 10 For v = 3800, the same evades with probability at most 5.34 x 10 We select this value as good tradeoff between efficiency and reliability. See Figure 3 for possible deviations from example group fairness threshold 0 at varying numbers of verified queries. Figure 5 in Appendix 1.2 gives additional details. These results show that OATH robust: service provider that cheats with larger than negligible will be caught by the auditor with high probability.

---

60
Sampling
Correctness
0.20
Faimess
4,000
Consistency
Faimess gup
= 0.15
40
Running
0.10
20
2,000
0.00
10
10
6. 105
8. 10s
1. 10e
2,000
4,000
6,000
8,000
10 00,000
5,000
10,000 15,000
20,000
2.
4.
Verified Queries 2v
Online Queries
[Q]
Verified Queries 2v
Figure 3: Green:
models underneath the ex-
ample fairness threshold 0 0.15; Red: mod- els placed over the by cheating which escape detection with greater than 1% probability. The possible deviation that escapes detec- tion decreases exponentially with number of verified queries by Theorem 4.
Figure 2: Ablation study of Audit Phase run- time for OATHER: (left) group-balancee uni- form sampling and fairness metric computa- tion total online queries [Q] varies; (right) correctness check and consistency check function number verified user queries.
BlaNs
BlaN-50
BLavoo
OATHiN
OATHaN:10
OATHax111
8,000
#Param
Online
(siquery)
Total
Running (hr)
80
6,000
FairProof
130
236.4
316.8
OATHyexs
0.23
0.235
Baseline
62K
5.9
5.9
40
4,000
OATHLNS
62K
0.23
0.28
Baseline
23.5M
333
333
2,000
OATHee-1
23.5M
0,23
2.90
Baseline
42.3M
535
536
OATH
0.23
4.43
10,000 30,000 50,000
10,000 30,000 50,000
(b) Amortized runtime for [Q] 10
Online Queries [Q]
Online Queries (
(a) Total Runtime
Figure 4: Scalability of OATH compared to baseline with varying neural network sizes. Runtimes are estimated using ZKP inference times from [88] The baseline approach ZKP verified inference
with each client (as in 49 31 followed by verified group fairness computation over all queries.
5.3 Scalability for Neural Networks
Figure 4 shows experiments and estimated runtimes of OATH compared to neural network baselines. OATH more efficient than the baselines by orders of magnitude. Especially important is the client-facing runtime, since this is arguably the most relevant factor for enabling the integration of ZKP auditing into ML pipelines. In this category, OATH gives at least a thousand-fold runtime improvement over the alternatives in three out of four categories, primarily due to the fact that it requires no client-facing ZKP. Even in terms of total amortized runtime, OATH provides a substantial increase in efficiency in all categories due to our probabilistic auditing method.
6 Conclusion
In this study we present OATH, the first method for privacy-preeerving certificates of online group fairness. In particular, use knowledge proofs which make possible to measure fairness directly from evaluation data, thus removing onerous resource requirements for third-party auditors and the generalization error incurred by using validation sets. Further, our method makes dramatic improvements to scalability in comparison to baselines. See Appendix | for limitations. In future work, may be interesting extend cut-and-choose style 7KPss obtain efficient proofs of other online properties, such security, robustness, and/or calibration.
10

---

Acknowledgements
Olive Franzese's work on this project was primarily supported by a Brave Software Internship. Olive Franzese was also supported by the National Science Foundation Graduate Research Fellowship Grant No. DGE- AGE-1842165. Resources used in preparing this research were provided, part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.
References
[1] Ulrich Aivodji, Hiromi Arai, Olivier Fortineau, Sébastien Gambs, Satoshi Hara, and Alain Tapp. Fairwashing: the risk of rationalization. In International Conference on Machine Learning,
pages 161-170. PMLR. 2019.
[2] Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias. ProPublica, May 2016. Retrieved January 15, 2022.
[3] Barry Becker and Ronny Kohavi. Adult. UCI Machine Learning Repository, 1996.
[4] Arpita Biswas and Suvam Mukherjee. Ensuring fairness under prior probability shifts. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Sociery, AIES '21, page 414 424, New York, NY, USA, 2021. Association for Computing Machinery.
[5] Manuel Blum. Coin flipping by telephone protocol for solving impossible problems. SIGACT News, 1511)233-27, January 1983.
[6] Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in commercial gender classification. Conference on Fairness, Accountability and Transparency (ACM FAccT), pages 77-91. PMLR, 2018.
[7] Toon Calders, Faisal Kamiran, and Mykola Pechenizkiy. Building classifiers with independency constraints. In 2009 IEEE International Conference on Data Mining Workshops (ICDM), Miami, Florida, USA, December 2009.
[8] R. Canetti. Universally composable security: a new paradigm for cryptographic protocols. In Proceedings 42nd IEEE Symposium Foundations of Computer Science, pages 136-145, 2001.
[9] Stephen Casper, Carson Ezell, Charlotte Siegmann, Noam Kolt, Taylor Lynn Curtis, Benjamin Bucknall, Andreas Haupt, Kevin Wei, Jérémy Scheurer, Marius Hobbhahn, et al. Black-box access is insufficient for rigorous ai audits. In Proceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency, pages 2254 2272 2024.
[10] Bing-Jyue Chen, Suppakit Waiwitlikhit, Ion Stoica, and Daniel Kang. 7kml: An optimizing system for ml inference in zero-knowledge proofs. In Proceedings of the Nineteenth European Conference on Computer Systems, pages 560-574, 2024.
[11] Yatong Chen, Reilly Raab, Jialu Wang, and Yang Liu. Faimess transferability subject to bounded distribution shift. Advances in neural information processing systems, 15:11266-1127. 2022.
[12] Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments, 2016.
[13] Andrew Cotter, Maya Gupta, Heinrich Jiang, Nathan Srebro, Karthik Sridharan, Serena Wang, Blake Woodworth, and Seungil You. Training well gell-gemeralizing classifiers for faimess metrics and other data-dependent constraints. In International Conference on Machine Learning, pages 1397-1405. PMLR, 2019.
[14] Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Reihaneh Nafavi-Naini and Ran Canetti, editors, Advances Cryptology- CRYPTO 2012, pages 643-662, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg

---

[15] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[16] Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), pages 214-226, 2012.
[17] Olive Franzese, Jonathan Katz, Steve Lu, Rafail Ostrovsky, Xiao Wang, and Chenkai Weng. Constant-overheed zero-knowledge for ram programs. Cryptology ePrint Archive, Paper 2021/979, 2021. https::/eprint.. iacr. 0actot///0crr.000/////9
[18] 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 (JACM), 38(3):690-728, 1991.
[19] S Goldwasser, S Micali, and C Rackoff. The knowledge complexity of interactive proof-systems. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC '85, page 291-304, New York, NY, USA, 1985, Association for Computing Machinery.
[20] Sixue Gong, Xiaoming Liu, and Anil K Jain. Mitigating face recognition bias via group adaptive classifier. In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 3414-3424, 2021.
[21] Melissa Hall, Candace Ross, Adina Williams, Nicolas Carion, Michal Drozdzal, and Adriana Romero-Soriano. Dig in: Evaluating disparities in image generations with indicators for geographic diversity. Transactions Machine Learning Research, 2023.
[22] Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in Neural Information Processing Systems (NIPS), 29:3315-3323, 2016.
[23] Hans Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994. DOI: http://do..orgr11222444422C2CC
[24] Ben Hutchinson and Margaret Mitchell. 50 years of test (un) faimess: Lessons for machine learning. In Proceedings of the conference on fairness, accountability, and transparency, pages 49-58, 2019.
[25] Basileal Imana, Aleksandra Korolova, and John Heidemann. Having your privacy cake and eating it too: Platform-supported auditing of social media algorithms for public interest. Pro- ceedings of the ACM Human- Computr Interaction, ((CSCWI):1-33 2023.
[26] Philips George John, Deepak Vijaykeerthy, and Diptikalyan Saha. Verifying individual fairness in machine learning models. In Conference on Uncertainty in Artificial Intelligence, pages 749-758. PMLR, 2020.
[27] Jonathan Katz and Yehuda Lindell. Introduction Modern Cryptography, Second Edition. Chapman & Hall/CRC, 2nd edition, 2014.
[28] Niki Kilbertus, Adrià Gascón, Matt Kusner, Michael Veale, Krishna Gummadi, and Adrian Weller. Blind justice: Fairness with encrypted sensitive attributes. In International Conference on Machine Learning, pages 2630-2639, PMLR, 2018.
[29] Jon Kleinberg, Himabindu Lakkaraju, Jure Leskovec, Jens Ludwig, and Sendhil Mullainathan. Human decisions and machine predictions. The quarterly journal of economics, 133(1):237-293,
2018.
[30] Anja Lambrecht and Catherine Tucker. Algorithmic bias? an empirical study of apparent gender- based discrimination in the display of stem career ads. Management science, 65(7):2966-298) 2019.
[31] Hidde Lycklama, Alexander Viand, Nicolas Küccher,, Christian Knabenhans, and Anwar Hith- nawi. Holding secrets accountable: Auditing privacy-preserving machine learning. arXiv preprint, 2024.
12

---

[32] Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable machine learning. In 2017 IEEE symposium on security and privacy (SP), pages 19-38. IEEE, 2017.
[33] Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. A new approach practical active-secure two-party computation. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology CRYPTO 2012, pages 681-700, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
[34] Cecilia Panigutti, Alan Perotti, André Panisson, Paolo Bajardi, and Dino Pedreschi. Fairlens: Auditing black-box box clinical decision support systems. Information Processing & Management, 58(5):002657, 2021.
[35] Sikha Pentyala, David Melanson, Martine De Cock, and Golnoosh Farnadi. Privfair: library for
fairness auditing. arXiv preprint arXiv:2202.04058, 2022.
[36] Michael Redmond. Communities and Crime. UCI Machine Learning Repository, 2009.
[37] Pedro Saleiro, Benedict Kuester, Loren Hinkson, Jesse London, Abby Stevens, Ari Anisfeld, Kit T Rodolfa, and Rayid Ghani. Aequitas: A bias and fairness audit toolkit. arXiv preprint arXiv:1811.0555 2018.
[38] Shahar Segal, Yossi Adi, Benny Pinkas, Carsten Baum, Chaya Ganesh, and Joseph Keshet. Fairness the eyes of the data: Certifying machine-learning models. In Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, pages 926-935, 2021.
[39] Ali Shahin Shamsabadi, Mohammad Yaghini, Natalie Dullerud, Sierra Wyllie, Ulrich Aīvodji, Aisha Alaagib, Sébastien Gambs, and Nicolas Papernot. Washing the unwashable: On the (im) possibility of fairwashing detection. Advances in Neural Information Processing Systems, 15:14170-1418 2022.
[40] Ali Shahin Shamsabadi, Sierra Calanda Wyllie, Nicholas Franzese, Natalie Dullerud, Sébastien Gambs, Nicolas Papernot, Xiao Wang, and Adrian Weller. Confidential-proffiee confiden- tial proof fair training of trees. In The Eleventh International Conference on Learning Representations, 2022.
[41] Nacem Siddiqi. Credit risk scorecards: developing and implementing intelligent credit scoring, volume 3. John Wiley & Sons, 2012.
[42] Haochen Sun, Jason Li, and Hongyang Zhang. zkllm: Zero knowledge proofs for large language models. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pages 4405-4419, 2024.
[43] Latanya Sweeney. Discrimination in online ad delivery: Google ads, black names and white names, racial discrimination, and click advertising. Queue, 11(3):00-29, 2013.
[44] Ehsan Toreini, Maryam Mehrnezhad, and Aad van Moorsel. Verifiable fairness: Pri- vacy-preserving computation of fairness fo machine learning systems. In Computer Security. ESORICS 2023 International Workshops: CPS4CIP, ADIoT, SecAssure, WASP, TAURIN, PriST- AI, and SECAI, The Hague, The Netherlands, September 25-29, 2023, Revised Selected Papers, Part II, page 569-584, Berlin, Heidelberg, 2023. Springer- Verlag.
[45] Kaveh Waddell. How algorithms can bring down minorities' credit scores. The Atlantic, 2016.
[46] Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. EMP-toolkit: Efficient MultiParty computation toolkit. https://gitthb.... wtt.uuu..oomm/maataa
wttpg//tthh...ooomeeoooooooooooo htmm//mp-toolkee 2016.
[47] Chenkai Weng, Kang Yang. Jonathan Katz, and Xiao Wang. Wolverine: Fast, scalable, and
communication-effiiine zero-knowledee proofs for boolean and arithmetic circuits, Cryptology ePrint Archive, Paper 2020/925. 2020. htttps://eprint. iacr 90g/2202//25/
[48] Chenkai Weng, Kang Yang, Xiang Xie, Jonathan Katz, and Xiao Wang. Mystique: Efficient conversions for (Zeoo-Knowleege) proofs with applications to machine learning. In 30th USENIX Security Symposium (USENIX Security 21), pages 501-518, 2021.
13

---

[49] Chhavi Yadav, Amrita Roy Chowdhury. Dan Boneh, and Kamalika Chaudhuri. Fairproof: Confidential and certifiable fairness for neural networks. arXiv preprint arXiv:240.11257.
2024.
[50] Andrew Chi-Chih Yao. How generate and exchange secrets. In 27th Annual Symposium Foundations of Computer Science (sfes 1986), pages 162-167, 1986.
[51] I-Cheng Yeh and Che hui Lien. The comparisons data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36(2, Part 1):2473-2480, 2009.
[52] Tianyu Zhang, Shen Dong, O Deniz Kose, Yanning Shen, and Yupeng Zhang, Fairzk: A scalable system prove machine learning fairness in zero-knowledge. In 2025 IEEE Symposium on Security and Privacy (SP), pages 3460-3478 IEEE, 2025.
[53] Ruiyu Zhu, Yan Huang, Jonathan Katz, and Abhi Shelat. The (Cut-and-Choose, game and its application cryptographic protocols. In 25th USENIX Security Symposium (USENIX Security 16), pages 1085-1100, 2016.
14

---

Table 2: Comparison of fairness auditing approaches terms of fairness definition (individual; group:
various), fairness certificate (online; offline), reliability and efficiency.
Approach
Fairness
Certificate Reliable
Efficient
Black- Box [34 35 37
Various
Online
Confidential- Ponidential-ROOFFT 40
Group
Offline
FairProof (49
Individual
Online
Fairness Baseline w/ Mystique
48
Various
Online
OATH
Group
Online
A
Comparison of fairness auditing approaches
We compared against existing fairnsss auditing approaches (summarised in Table namely Black- Box audits [34] 35 37 as well both previous works that leveraged ZKPs to enforce model fairness (FairProof 449 and Confidential-PROFTT [40). We also created a baseline based on ZKP correct
inference, Mystique 48
Black-box fairness auditing considers an auditor who has only query access 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 seldom used in practice due issues with confidentiality, while the black-box setting does not provide the auditor enough information for rigorous audit (9] (for example, nothing prevents 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 box setting.
B Certifying Other Group Fairness Metrics
Here we present modified version of the Audit Phase which measures equalized odds [22], another group fairness metrie. Rather than measure the difference in positive outcomes between demographic groups in demographic parity, equalized odds measures the difference in false positive and false negative rate between demographic groups.
Definition B.1. [Thresholded equalized odds] predictor Y satisfies equalized odds with respect to sensitive attribute. S within a public threshold 0 if both of the following hold:
Prpr 1 = 0 n = a] Pr(ý y = 0 n
b] S 0
be
|Pr( = y- 1 Pr = 1
S.
Computing equalized odds requires knowledge of the ground-truth labels for the data used. In certain applications such as finance, hiring, and medicine, ground truth labels may be readily available at audit time. For example, it is easy determine whether a loan was repaid, whether an employee was promoted, or whether a patient's 's health metrics improved, at a later time point after the model makes prediction. We abstract these sources of information via oracle that gives access ground truth labels, and present a version of OATH modified for equalized odds auditing in Algorithm 3 Other than the addition of the oracle in lines 4-5, it is highly similar to Algorithm except that it computes empirical false positive and false negative rates for each group, which we abstract as a subroutine (Algorithm
C Details of Cryptographic Preliminaries
C.1 Properties of -ero-Knoeee Proofs
A zero-knowledge proof (ZKP) 18 I9
is cryptographic protocol conducted between a prover P
and verifier V. who both have access to a public eircuit P. 7KP allows P convince that they know some witness such that Pww) 1. ZKPs have the following properties:
15

---

Algorithm 3: OATH Zero- Knoro-neoeeegeeee Equalized Odds Audit.
Input: public: the number of client queries n. fairness gap threshold 6, soundness parameter v,
ground truth oracle O; P: model M, evaluation data Q {(qt, o², 0z,
r;))) V:
commitments {C;] sensitive attribute check strings ((a): oj )
Output: V/ obtains Apass E {0. 1} indicating whether M satisfies demographic parity with respect to Q.
// Step 1: Initialization for i [] do L authenticates (Io.I, [og]. [r. [o.]]:
P authenticates [M]]
for i E 11 do
L [9.] +- O[I..])
// Step 2: Fairness Verification
pass <- Fquualized-Odds((n, 0, [Q], [lo:])=1)
/ Step 3: Validity Checks
+ Group-Balanced Uniform Sampling Q v);
An array indicating selected samples
(Algorithm
8 for i [1, do
// Sensitive Attribute Check
V sends ag. aj to P; P proves ([[o'] = a/) ([a')] == a4)) = =;;
[ + [[a:]] = )
11
12
P proves [s.] = [
13
[Reveat[[S(]]]]
1 then
// Commi tment Consistency Check
14
p proves (q. l [1:)) = C₁;
// Inference Correctness Check
15
P proves [o:] = [M] ([::), [r:]] using Fint:
16 If any of the proofs fail, abort. Otherwise, Reveal
Completeness: For any such that P(w) 1, P can use the ZKP protocol to convince an honest that P(w) =
Soundness: Given such that P(w) * malicious P cannot use the ZKP protocol to falsely convince that 1
Zero Knowledge: The protocol reveals information even a malicious V about w (other than what can be inferred from knowing that (ww) 1).
C.2 IT-MAC Authentication
We follow the methods for IT-MAAC-hased authentication in 33 14]. In more detail, we fix field F, for some prime p E N, and an extension field Fy 2 Fp. The notation [x:] means that holds uniform global key A E Fpr and for each authenticated value uniform local key K2 Fpr, while P holds the value z F, and a uniform tag M. E F Fpr, over which the following algebraic relationship holds:
M, KK K, + A +.
when for the purposes of the equality, is represented in the natural way as an element of Epr. P can "open" an IT-MAC authenticated value by sending æ and M, to V, who can then verify that the relationship holds. If P has modified x after authentication, it will only pass verification with negligible probability. The generic ZKP protocol in 47 works by authenticating the input values to circuit, and then updating them in ways that preserve the algebraic relationship. which can only succeed if both P and V agree to perform the update (again, except with negligible probability). IT-MACs are homomorphic for addition and scalar multiplication, which means that if P and V agree, they can update authenticated values with these operations locally without any communication. This makes these operations very efficient in IT-MAC-based ZKPs.
16

---

Algorithm 4: OATH Equalized Odds Calculation.
Input: public: the number of client queries n, fairness gap threshold 6; P: authenticated evaluation data [Q] = [[ [ot], [o:] (r:][[r:))) -- authenticated ground truth labels
= [_
Output: authenticated [ {0, indicating whether the decisions in Q satisfy
demographic parity.
P authenticates [Po], [ [No]] and [Ni] initialized to zero;
Count positive and negative
outcones in each denographic group
P authenticates [T]..]] [F]] [TP]] and [FP] initialized to zero;
true
positives in each demographic group
for i E 1, n do
[s:] <- Iq.demographic _tttributtt
[bp - 8i. [b1 < 8;;
Indicator denographic attribute
[Pll < [Pol + [[b]] [g. [P] + 1 [P]] ([b,] [g:]];
b Updata pesitive counts
[No] [No [luo]
(1 [o.l)),
[Ni] - [N ([b.) (1 [g:l]) ; Update nogative
counta
[TP]] [TP]] ([bn] [o:] [o:1),
[TP]] - [TP:] + [[6b] [o:] [9:I]::
Update
true positive counta
[FPo]
[FPo] [[6o] [o:] (1 -1-I)))))
[FP]]
[FP]] + ([b1] [o.]] (1 l1.1))::
Update false positive counte
10 Fairness gap computation and comparison to the threshold [passs]] f-
12
[TP.
[P]]
(o
IFP.1
[FA]]
P.
[A.
[N.]
[MS]
11 Return [[ppsss]
To provide a concrete example, we will briefly demonstrate how a secure addition is computed. Suppose P and V have authenticated values [>]] and [y] This means that P holds x: and message tags M₁ and My. while holds a global key A and message keys K₂ and Ky, with the algebraic relationships M2 K2 + A x and M, Ky + A y. To compute secure addition, P and V must obtain [>] with the underlying value = + y and a message key and message tag such that M, K2 A
Observe that by adding the respective components [x] and [y] we can see that the following two equalities equivalent
M2 + My = K2 + A K, + (M₂ + My) = (K, + K2) + (x + y)-
Thus P and can achieve the goal of obtaining [z] as follows: P computes z +- x + y, and M2 +- M, + My. while V computes K= + K, Ky.
We will also overload the double bracket notation to include collections of values: if is vector and A matrix, [o] and [A] mean that each value in v and A is individually authenticated.
In summary, IT-MAC-based authentication provides way prevent P from modifying values except in ways that are approved by V. even while keeping those values hidden. They also enable efficient computation with our ZKP building blocks [47] [7), however they require global key A to be shared among all authenticated values for efficiency. This makes them cumbersome in applications with many parties. Accordingly, to prevent P from modifying the queries obtained by the many client parties, we use cryptographic comnitments rather than IT-MAC authentication.
C.3
Commitments
A commitment scheme enables party with an input value to produce a commitment string C' which can later be opened to verify that æ has not changed. They possess the following properties:
Binding. P commits to æ and then modifies æ in any way without V's knowledge, verification of the commitment string will fail.
Hiding. The commitment string reveals no information about to V.
17

---

A standard approach 27 for instantiating a commitment scheme is to use random oracle hash H, with
Cx = (>)lrr)
giving the commitment string for any I E {0, 13", where E {0. 1)a a randomly chosen bit string for some & E N. Verification conducted by computing the hash again given and r, and confirming that it is equal to C2 produced by the party giving the commitment. In this work, we use ZKP protocol to confirm that C H (x [r) without having send æ to V. Thus client queries have not been altered without revealing the queries to V. We use a scheme from [48) to enable conversion of hash-based commitments IT-MAC authentications within a ZKP protocol to enable this.
able verify that
C.4 Digital Signatures
A digital signature scheme guarantees that signed message sent by sender with known public key. Formally, a digital signature scheme consists of two algorithms:
A key generation algorithm Gen(1^) - (sk, which, given security parameter generates secret key and public key pair
A signing algorithm Sign (m) > sig which takes a secret key and message, and generates signature
A verification algorithm Vrrypa(mm, sig) - {0, 1) which takes public key, a signature, and message, and outputs boolean value indicating whether the signature is valid (1 for valid, 0 for invalid).
signature valid the pair (sk, pk)) was obtained from Gen, and sig was obtained from Sign (m). Informally, secure signature scheme ensures that for any m, adversary forge sig' such that Vrfypa sig') outputs unless they have access to the sk corresponding to pk. See [27 for formal details.
D
Notation
Table shows the notation used throughout this paper.
Table 3: Notation table.
Meaning
Meaning
P Prover
V Auditor
C Client
M Model
D Training Dataset
Evaluation dataset
9 Group fairness gap threshold
[x] Authentication of value x
S Binary demographic attribute
The number of client queries
X Feature space
Y Predictor
9 Client's query
P Public circuit
Witness
Model binary decision
V Number of sampled queries from each demographic group
concatenation operator
XOR operator
E
Details of Blame Attribution
any of the proofs Algorithm fail, then the protocol aborts (line 21). To prevent denial service attacks in real world applications, it is necessary to find out which party caused the failure. Notably, both the service provider P and the client C have incentives to deny service: malicious may seek to obscure the fact that they have noncompliant model, and a malicious C may seek retribution for an undesirable model prediction. Here we formalize method for correctly identifying which party to blame if Algorithm 2 ends in abort.
18

---

Algorithm 5: Blame Attribution
Input: Public: list of indices for all clients which failed validity checks in Algorithm
2 P's public key (C:)
pki list of sensitive attribute labels L {(as. a heeq)) list of commitments query (qi, a oz) and P signature sigo; V inputs. Output: a bit b, for each i E I, indicates C, malfeasance, I indicates malfeasance.
for E do
C. reveals (4s, ats, rz) re) and P signature sigè
V checks Vrfy(g: [ [|o] rı, sigè) using P's public key pk:
checks Open(qi |la ;
checks that af oi o., aá and that equal the sensitive attribute reported in qe any of the checks fail, V sets b; + O, otherwise b, +
Since clients do not participate in the Audit Phase, they cannot interfere with any of the proofs before the validity checks (lines 13-20). Thus if protocol failure happens here, P is to blame. The interesting cases occur during the validity checks, where for some client C, P is verifying the sensitive attribute label a', consistency of the commitment C, and correctness of the inference o; M(g, rt). If these proof's fail, then there are two possibilities:
(i) P modified the 7th entry of Q between the Service Phase and the Audit Phase, or (ii) C, submitted an invalid od of or C, to V during the Service Phase to intentionally disrupt the Audit Phase.
Algorithm [ gives a protocol for post-hoc blame attribution. relies on the security of the digital signature scheme used during the Service Phase (Algorithm[I) []: no malicious C can forge a signature sigo such that Vrfy || | [o]]] sigE: will verify under P's public key (Appendix C.4). Thus, if line 3 succeeds must indicate that (gi, a. 0z, ri) was exactly the query-response tuple given C; in line 8 of Algorithm M Thus if it matches up with the commitment C. given to V in line 10 of Algorithm I and a, indexes the proper sensitive attribute, then C, must have carried out Algorithml [ honestly. This means that protocol failure in Algorithm 2 must have been caused by malicious P.
We note that Algorithm 5 requires Cj reveal their data to V. This be remediated by instead using a zero-kmowledge proof of digital signature verification, which has been explored in previous work. We reserve this possibility for future work.
ZKP Verification of Group-Balanced Uniform Sample
Algorithm Algorttmm_givees gives an interactive ZKP protocol for verifying that a sample contains v uniform samples of points from each demographic group. Theorem G.2 characterizes its security guarantees.
G Proof of Soundness
Theorem G.1. Let Xt, be the honest group fairness gap and X the measured group fairness gap computed during Algorithm Consider >> 0, the deviation between these quantities caused by malicious P cheating, defined:
E c= 1Xp -Xml.
Then P is caught with probability
Peatch 2 2 (1-
where is the number queries uniformly sampled within each group via Algorithm ((a total of 2v).
Proof. We begin by considering available options for P to dishonestly influence Xm (i.e. the quantity compared to 0 in line 11 of Algorithm 2). Since any deviations influencing the computation of
co, C1, No, n1, S in lines 6-11 will be caught by the underlying ZKP protocols 47 [7]. P can only
cause a deviation in X,, by behaving dishonestly to alter the query-answer tuples (gi, Ti, 0:) before they are committed during line 2.
19

---

This can happen in two ways: (i) by breaching correctness of the outcome given to C, during
Algorithm ! (i.e. o; + (4. D. or (ii) by breaching consistency (i.e. (4, r,, o;) provided as
input during Algorithm line 2 o (q, o) returned to C; during Algorithm 1 A query-answer tuple breaching either condition will caught by lines 18-20 of Algorithm ii sampled in S during line 12.
Thus, in order assess P's likelihood of being caught we must understand the number of modified queries required to produce a deviation between XA. and Xm of size e. Since the Sensitive Attribute Check (lines 14-17) causes the audit fail if P modifies the sensitive attribute, we can proceed by just considering the case where P only modifies from (gi, r's 0₂) Qm. Let no be the number of query points in Qn such that s; 0, and let n1 be defined similarly. Note that in the case where P only modifies these quantities are exactly the same when defined over Qm
Flipping any o from Qn can produce most no alteration of X if 0, or ni alteration if 1. This is because the numerator term changes by most 1 per query. This means that in order to create a deviation size e, P must modify at least Pu no + P1 nh queries for some po. P1 E [0, 1], where
6 E Pa + P1-
This necessarily implies that either po 2 or 5. Without loss of generality, assume the former.
Then we uniformly sample v queries with 8; = O, the probability that none of them violate correctness consistency (and P evades being caught) is given by
Pr[no modified queries in sample] = (1 - po)
- (1 2 ")
Since symmetrical analysis holds for P1, taking v-sized uniform sample of queries from both groups (for total of 2v verified queries) gives us the bound stated in the thcorem.
Cases where P instead modifies or r; reduce to the case of modifying o, So this completes the proof.
Theorem G.2. The sample array output by Algorithm 6 has the following guarantees:
1. Queries are selected uniformly within each group. Formally, consider i E Io. the subset of all indices such that the query-answer tuple (yi, 0z) Q has sensitive attribute 8; = Then
Pr[S[(] -|]s]=
Vi,j To-
And similarly for queries with sensitive attribute 1.
2. Exactly queries in group and v queries in group 1 are included in the sample, for total of 2y selected queries. Formally, entries in S are binary-valued, with Eier, S(i] v. And similarly for queries with sensitive attribute 1.
3. (Informal) Algoritium 6 reveals no information to V other than no and nı, the number of queries made by members of each group.
Proof Sketch. In detail, Algorithm 6 randomly permutes all members of group 0 and places the first of them the sample, and also randomly permutes the all members of group and places first of them in the sample. To accomplish this operation in zero-knowledge on committed array of queries, constructs two random permutations To, #i of the appropriate sizes and sends them to P. Each permutation is then loaded into read-only ZKRAM (see [17] for details), which will allow to read permuted elements from To in the case that they have sensitive attribute s = 0 and 1 otherwise (and similarly for group 1), without revealing to V which case is occurring. We use 1 as symbol to represent the fact that a query is outside the group relevant to a permutation.
In lines 4-7, the parties perform a linear traversal of all queries in Q, updating committed counter [[]] whenever a query from group 0 is encountered, and either placing To(co) in an array An or L depending group membership via read to the ZKRAM. At the end of step 10, every query in Q has a corresponding entry Ag which is [mo g: E group 0, (where 4 the jth query that belongs to group 0), and [[L] otherwise. We also construct A₁ symmetrically for group 1. Thus, each
20

---

Algorithm 6: Group-Balanced Uniform Sample
Input:
The number of queries answered in the Service Phase, n, the soundness parameter, v, which controls how many queries should be sampled per group;
P holds an re-ized array of committed client queries [Q[ where no entries are from clients in Group and n4 are from clients in Group O, with no n1 n; and 1/ holds commitments to the queries [Q].
Output: V and P respectively receive commitments and committed values for an array of indicator bits [S] that encode which values of Q are selected in the sample.
P sends 1l. to V;
2 sends P Tas random permutation of the integers in [L, no]. and TT random permutation of n,1;
loads Ta into a read-only ZKRAM RG such that Rg [ Na (t)] Vi E [1l Set
[o] [-]. P loads n6 into Rs similarly, and sets R., 00 = [1]
P commits to group counter [co] and initializes it to 1. initializes group-specific
permutation array A, with n entries. for i [1,m] do
[ba] f- indicator bit for (t-ddeoggraphic_.n attribbbbe == a;
[t'] < [6.] [co]]
qi group otherwise.
7
Ag []] f Rg
> [<a(C)]] if ie in group [1] otherwise.
[co] f [co] + 6..]
Obtain group-specific permutation array A by repeating lines 4-7 but replacing Group a with Group b.;
10 Initialize an array S of size n containing bits indicating whether query qi is in the sample.; for i 10, n) do
12
S11 + [A.[]] < w1 [A.]]] w ;D o sample it's nenber Group (a( v.
or it's a member of Group b and (f) < v.
13 return S.
member of group 0 is labeled with an output from the random permutation To, and each member of group is labeled with an output from TT. Then to determine whether a query qi is included in the uniform sample, lines 10-11 perform one more linear pass over Q wherein committed sample bit is set to 1 it's a member of group 0 and To (i) < v, or if it's member group and x (i) < v (we define (1 < k)) 0 for any k).
The construction thus guarantees claims (1) and (2) since group queries with S(i] = 1 are exactly those which are mapped to [0, 1/) by the random permutation To. and group queries with S(i] = 1 are exactly those which are mapped to v) by æ1, which is equivalent taking a v-sized uniform sample from each group. Claim (3) is guaranteed by the underlying ZKP protocols used to perform the authenticated operations and ZKRAM access [4 17.
Corollary G.1. (Informal) Algorithm 2 reveals no information to V about the client data and model parameters other than what can be inferred from no and n,, and the sample array S.
Proof Sketch. By Theorem G.2 taking the group-balanced sample with Algorithm reveals Yip 71 to V. but no other information. By the security of the underlying ZKP protocol 47 and hash-based commitment scheme [48] all lines besides line 14 leak no additional information to V.
In line 14, after obtaining the sample array S, P opens each of the 2v bits of S such that [S|]]] which effectively reveals S since all other entries are guaranteed to be O.
Revealing S to V gives some knowledge of which of their commitments correspond to clients included in the sample. By itself, this is an innocuous piece of information it simply gives V knowledge that a small subset of query commitments correspond to users with probability of being from group 0 group 1, rather than and æ1 as is implied by knowledge of no. fh, and If we consider stronger adversarial capacities of V, e.g. that they somehow have outside knowledge about 2 1 of the queries in the sample, more precise information can be inferred. In this example, V can infer the
21

---

Algorithm 7: Fairness Audit w/o S Reveal.
Input:
Public values: n is the number of client queries, thresholds the acceptable level of group
fairness gap, and is soundness parameter.
P holds a committed model M, and a set of queries authenticating values (q,, Ts, Ts, Q with i nl..
holds hash-based commitments C, H (1:11r:s/oo:) with E [1,
// Step 1: Initialization
1 for i [1, do
L authenticates (Ia:1, [r:], [o:]):
P authenticates
[M]; P authenticates [ca] and [co] initialized to zero;
Count pasitive outcomes in each demographic
group
$ d authenticates [no]] and [mo] initialized to zero;
Count individuala in each denographic group
// Step Neasuring Group Fairness
6 for E 1, do
[s:] + .g..emoggpp
attribbuee]:
[b] f- [[s]] == a),
[b - [[s;] == b):
Indicator bit for denographic attribute
[no] f- [no] + [b... [1 [m]] [bal
Update group counte
10
[col + [col + [ba [o.1),
[ci] + [ell + [[96] [o.1];;
Update positive outcene counts
11 PP shows that demographic parity gap underneath threshold 0 by proving
[co]
[c]]
[paas]]
0
[no]
[n1]]
// Step Validity Checks 12 + Group-Balancd Uniform Sampling (2 v):
b. in array indicating selected samples
(Algorithm [
13 Initialize committed counter [x:] to 1;
V publishes all C. P loads them into read-only ZKRAM 17 Z;
15 Initialize read/write ZKRAM [17] R with (2v/ + 1) 82 entries, where s2 is the number values required store query-answer tuple rg plus its index n). Initialize the tuple-sized block starting at R2[0] with 1:
for [1, n do
17
[6] + S
[[[=] [[b]] < first value in (g (gillrsllo:)) R[=]] [6] 1] second value in (q/l)v/loo)lli.
18
R[[=] [b] + s2] +- s2 value (g:l)r:|lo:)]1
19
[-]l + [>]]
+ [b].
20
for e [1, 21,2v]d do
([ [r]
[ind]]] + load from R[i];
22
P proves [ = M(gg], [r]) using Fiati
23
proves that ([ [o]) [[[nd]]]
If any of the proofs fail, abort. Otherwise, Reveal [[6pus]]
demographic attribute of the single unknown query since they know which group has sampled queries and which group has v.
While it is important to be mindful of this possible inference, in the proposed setting of a regulatory body auditing the fairness of machine learning model we anticipate a threat model much closer to the former case than the latter. Further, by integrating a read/write ZKRAM [7 we can remove this leakage in exchange for a minor to moderate additional computational cost (depending on the size of the query input). This is demonstrated in Algorithm
22

---

H
Datasets
Table describes five standard fairness benchmarking datasets used in this paper: COMPAS (2).
Communities and Crime 36 Default Credit [51]. Adult Income [3] and German Credit (23
Table 4: Summary of datasets.
Dutasel
Lacense
#Samples
AAlir.
Demographic Var.
Task
COMPAS
DbCL 1.0
6,131
Race
Recidivism
Crime
4.0
1,993
Credit
CC BY 4.0
30,000
23
Age
Card Payment
Adult
CC BY 4.0
45.222
Gender
Income
German
CC BY 4.0
800
61
Foreign Worker
Lian
I Supplementary Results
L.1 Details of Audit Phase Ablation Study
Runtime Profiling for Total Query Volume. OATH computes fairness on all user queries, and uniformly samples queries from each subpopulation for correctness and consistency checks. Both sampling runtime (Algorithm (6) and fairness computation runtime (Algorithm 2 lines 6-11) are independent of the number of sampled queries and the model type they depend only the number of user queries |Q] n. Therefore, we show their relationship to the number of queries in Figure (left (left column). In general, the runtime of both SrouppBalancee
Uniform Sampling and Fairness Computation increases linearly with the number of user queries. However, the slope of the increase varies across different parts. Given specific number of user queries, the runtime of fairness computation is significantly lower than the runtime of group-balanced uniform sampling. This is because Algorithm geporithm@@utiizzze @utilizes a ZKRAM primitive [17 in order to realize the group-balance balanced uniform sample securely, while the faimess computation in Algorithm uses lighter-weight ZK arithmetic operations [47)
Runtime Profiling for Verified Queries. OATH verifies user queries through correctness (line 20 in Algorithm|2 2 and consistency (line 19 in Algorithm 2 checks. Figure 2 (right column) shows the runtime of these operations. Both correctness and consistency checks have time complexity linear in the number of verified client queries. The runtime of the consistency check dominates the overall runtime because relies on a scheme for converting hash-based commitments IT-MAC- authenticated values, which is relatively expensive operation [48].
based 33 14
I,2 Additional Details for Parameterizing the Number of Verified Queries
Figure (left column) shows the probability of catching cheating with respect to the number of verified user queries ranging from 1,000 to 10,000. The more queries are verified, the higher chance that cheat- ing is caught. We consider various values for this is the change that P seeks to induce between the fairness gap measured by the audit, and the true fairness gap during the Service Phase (Definition 1). The more unfair P's model is, the higher they need ity of evading detection for cheating decreases exponentially as e gets bigger (Figure 5 right column).
pass the audit. Meanwhile, the probabil-
1.3 Additional Benchmarks
Figure 6 shows the accumulative runtime of computing fairness and checking the correctness of the model using all five datasets.
Limitations
In this study we present OATH, the first method for fairness. In particular, we use zero-knowledge proofs which make possible to measure fairness directly from evaluation data, thus removing onerous resource requirements for third-party auditors and the generalization error incurred by using validation sets. Further, our method makes dramatic improvements to scalability in comparison to basclines.
certificates of online group
23

---

10
Evading probability
0.005
0.8
0.020
10 45
0.4
0.0
10
1,000
5,000
9,000
0.04
0.08
Verified Queries
Deviation amount
Figure The probability that cheating P evades detection when: (Left) deviating from the fairness measurement by three fixed values at varying numbers of verified queries; (Right) deviating with 7600 verified queries with varying e. As e gets smaller, the probability of evasion gets higher but becomes substantially less impactful on the audit.
COMPAS
Adult
25
40
Running dime (6)
Rumning time (6)
20
20
1000
2000
7600
1000
2000
7600
Number verified
verified
50
Runaing time (5)
40
20
1000
2000
7600
Number of verified witnesses
Default Credit
German
Running time (s)
Running time (s)
100
40
20
1000
2000
7600
1000
2000
7600
Number of verified witnesses
Number of verified witnesses
Figure 6: Effect of the number of verified witnesses on the runtime of computing fairness and verifying the inference using the correct model.
24

---

While OATH improves the scalability of ZKP fairness auditing by orders of magnitude, the computa- tional requirements could still be an obstacle to adoption in applications that use very large models. Improving the consistency check which comprises our runtime bottleneck is thus an interesting future direction. Of note, our work uses ZKPs of inference (e.g. benefit from ongoing advancements in this area.
48 10 42 ) and thus will automatically
We also note that while verification of group fairness important, the metric itself has limitations. Machine learning models can cause inequitable treatment of minority populations even while satisfy- ing group fairnsss, and thus it important to not consider cryptographic verification group faimess as a satisfactory end goal in isolation. Rather, we intend that OATH is used as part of an ensemble of auditing approaches in order to achieve more equitable outcomes from ML tools. To realize this, it may be of interest to expand our cut and choose methodology as more general framework for efficient PKP--ased MI. auditing. Extending this design pattern to wider classes of MI. models, fairness metrics, and other trustworthy properties (such as reliability, interpretability. and privacy) is a promising avenue for future work.
Lastly, we comment that while OATH provides security against malicious service providers, auditors, and clients individually, it does not account for collusion between parties. 'Sybil' attacks, wherein malicious service provider produces fake clients, could be used in real world attack to make a model appear fair on evaluation data. This could be handled by authentication of clients by the auditor, but it is worth noting as potential real world attack.
K
Impact Statement
The present study proposes method for auditing ML systems for fairness. It is the hope of the authors that OATH and other ZKP-based auditing techniques can be used in service of making deployed ML systems function more ethically by providing accountability for equitable treatment of disadvantaged populations. We stress that OATH and other ZKP-based methods should not be seen as replacement for other forms of auditing. Mathematical fairness criteria alone are not sufficient to determine whether an ML system functioning ethically human needs to be in the loop somewhere. Rather we see these methods as a pathway for providing accountability and transparency ML systems, to used as a complement with other methods, so that Al can be regulated more effectively and with lesser expenditure of resources.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We claim that existing methods for confidential certification of fairness either lack reliability, due to the problems with offline fairness outlined in our introduction, and/or scalability, due to the high computational overhead of cryptographic methods for verifying ML operations. Our method remediates these problems by proving group fairness online, as detailed in Section 4. and 4.2) and doing so efficiently as detailed in Section [
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings. is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
25

---

Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations are discussed in Appendix U
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "L.mitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Theorem 4.1 is proven in Appendix G
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We fully disclose algorithms, datasets, and experimental setup.
26

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel urchitecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification:
We will release code upon acceptance of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
hhipss.c//ublic/uuddds wttpeese/eooeSeeeeooooeoeoe
www.obiiiiiiioooooooiiooo for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
27

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Our experiments are runtime benchmarks, and they run identically regardless of training and test details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
We report standard deviations for main benchmarks in Table [
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: As mentioned in the experimental evaluation, all our experiments are run on MacBook Pro laptop CPU.
Guidelines:
28

---

The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer:
[Yes]
Justification:
This research complies with the code ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Yes]
Justification:
We provide an Impact Statement Appendix
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
29

---

Justification:
Methods in our paper do not have high risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging. and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide citations and licenses for all datasets (Appendix H and EMP- toolkit in the paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi twwoeethcde...m caree.com/eee com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
30

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper includes no crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This paper includes no crowdsourcing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLMs were not used in any part of this work.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our L.MM policy fbttps://neure www.eripppp..coooeeeeeeeeeeeee / for what should or should be described.
31


Reviews:
[{"review_id": "8QeyZvar2c", "reviewer": "Reviewer_7kjt", "summary": "This paper introduces OATH, a method to audit the fairness of machine learning (ML) models in a black-box fashion. The method uses a zero-knowledge proof (ZKP) protocol in order to ensure confidentiality, namely to prevent the auditor from learning the value of the sensitive attribute. The values of the sensitive attribute represent the groups with respect to which fairness is defined. \n\nThe paper focuses on the notion of fairness called \"statistical parity\", which limits the difference between the probability of obtaining a positive prediction across different groups. In the appendix, however, the paper discusses the extension to other kinds of fairness notions. \n\nThe protocol operates in two phases:\n\n- Service Phase: the clients query the model and send cryptographic commitments of their queries and results to the auditor. \n\n- Audit Phase: The auditor interacts with the model to verify the validity of the fairness threshold, and then it checks whether there has been tampering on a randomly sampled subset of the queries provided by the clients, chosen to be balanced across the various groups. This subset is of bounded size, which provides scalability of the tampering check. This phase performs various validity checks (sensitive attribute check, commitment consistency check, and inference correctness check)  using ZKPs.\n\nThe paper also provides a formal proof that the probability with which a malicious service provider can wrongly demonstrate that its model is fair (by tampering with the data) decreases exponentially as a function of sample size.", "questions": "Please clarify whether the sensitive attribute is a characteristic of the client (which is consistent with what is written in Algorithm 1, Line 2), or of the query  (which is consistent with what is written in Algorithm 2, Line 7).", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "I had to re-read the paper several times because, at first, it did not make any sense to me. Then, I think I finally understood that this paper considers the sensitive attribute to be a feature of the client, rather than -- as it is usually assumed -- an attribute within the query. \n\nUnder the standard assumption that the sensitive attribute is part of the query (and that a client can deal with queries with different values of the sensitive attribute), all the effort made by this paper to ensure confidentiality is \"the classic cannon to kill a fly\". A much simpler protocol would be the following: for each query, a client queries the model and then sends the corresponding pair (sensitive attribute_i, prediction_i) to the auditor. Once all these pairs are collected,  the auditor performs a simple calculation to check whether the fairness threshold is respected. There is no substantial confidentiality issue since the pair (sensitive attribute_i, prediction_i) does not leak any significant information about the data, other than there is a data point with that sensitive attribute. \n\nThe paper must therefore assume that the sensitive attribute is a characteristic of the client, and that we want to prevent the auditor from learning it. Even then, however, I don't see the need for such complicated protocol. One could just use some protocol for collecting the pairs (sensitive attribute_i, prediction_i) anonymously, for instance, a mixnet protocol, and then send the collection to the auditor. \n\nFurthermore, often 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. \n\nThe paper is also lacking clarity. For instance, 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.  \n\nFurthermore, readability is poor due to several undefined notations and notions, and to the presence of some inconsistencies: For instance, what is the meaning of the $\\parallel$ symbol in Algorithm 1? What is the meaning of the symbol $\\oplus$ in Algorithm 2? 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$. \n\nSome of the claims are misleading. For instance, 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.", "was_revised": true, "final_justification": "I had initially misunderstood the scenarios that the paper is addressing and the goals. The authors clarified these misunderstandings during the discussion phase, and consequently, I have raised my score.", "rebuttal": "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.\n\n> **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.**\n\nWe clarify the difference between black-box audits and zero-knowledge proofs with the following text, which we will add to our introduction:\n\n“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). \n\n*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.”\n\nAddressing 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. \n\n> **Why doesn’t the client simply query the model and then send the corresponding pair (sensitive attribute_i, prediction_i) to the auditor?**\n\nThis black-box approach is insufficient for two main reasons:\n- *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. \n- *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]. \n\nThe 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.\n\n\n> **Is the sensitive attribute a feature of the client (Algorithm 1, Line 2) or of the query (Algorithm 2, Line 7)?**\n\nWe 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:\n{$s \\gets q.$sensitive_attribute}.\n\nOur implementation handles this without modification.\n\n\n> **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.**\n&\n>  **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.**\n\nIt 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: \n\n- 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$.\n- 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. \n     - 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$.\n- 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). \n\nThus, 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. \n\n> **Notation.**\n\nIn cryptography literature $||$ and $\\oplus$ are standard notation for concatenation and XOR respectively. We will define both explicitly in the revision.\n\n> **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.** \n\nWe will clarify this by unifying sensitive attribute values to be {0,1} everywhere in our revision."}, {"review_id": "YHEIane1es", "reviewer": "Reviewer_64AH", "summary": "The presented work introduces ​online fairness certificates​ using zero-knowledge proofs (ZKPs), addressing critical limitations of offline fairness certification. The problem arise in scenarios where both fairness in life-changing tasks (loan approval and recruitment) and data privacy & model IP are to be protected. \n\nThis paper proposed to measure fairness directly from the client data received online during deployment, and preserve confidentiality by issuing online fairness certificates with zero-knowledge proofs (ZKPs).", "questions": "The paper is well-organized and presented. Nevertheless, I do have few questions/suggestion concerning the experiments and applicability of the method. \n\n1. Any other baseline methods to be compared, e.g. in terms of the trade-off of relaibility / efficiency ?\n2. it would be good to empirically demonstrate the defense capability of the proposed method e.g. under various attacks (data-forging or model-swtiching).  \n\nAnd at last, have you ever considered to apply the same approach to address other issues e.g. online-security certificate?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "+ the notion of online group fairline certificate is well-defined and presented. \n+ a reliably and scalable solution is provided s.t. third-party verifier can be convinced.\n\n- it seems only one baseline method is compared in empricial evaluation, while FairProof is only compared for computatoinal overhead. It would be good to present more emprical results.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment of our paper.\n\n> **Any other baseline methods to be compared, e.g. in terms of the trade-off of relaibility / efficiency?**\n\nWe 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]. \nWe will clarify these categories in the introduction as:\n\n“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).\n\nZero-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.”\n\nWe will add a comparison of all these fairness auditing approaches in terms of the trade-off of reliability / efficiency: \n\n| **Approach**        | **Fairness** | **Certificate** | **Reliable**                         | **Efficient** |\n|---------------------|--------------|------------------|--------------------------------------|---------------|\n| Black-Box [34,35,37]  | Various      | Online        | -                      | ✓             |\n| Confidential-PROFIT [40]      | Group        | Offline         | -                    | -             |\n| FairProof [49]      | Individual   | Online        | ✓          | -             |\n| Fairness Baseline w/ Mystique [48]      | Various   | Online        | ✓          |  -            |\n| OATH            | Group    | Online   | ✓     | ✓         |\n\n\n\n> **it would be good to empirically demonstrate the defense capability of the proposed method e.g. under various attacks (data-forging or model-swtiching).**\n\nDefence capability of the proposed method against \n- 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). \n\n- 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.  \n\n\n\n> **have you ever considered to apply the same approach to address other issues e.g. online-security certificate?**\n\nThank 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. \nThat 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: \n\n“An interesting future direction would be to explore the applicability of ZKP certificates to online-security guarantees.”"}, {"review_id": "p2GoMCzJyH", "reviewer": "Reviewer_oaNR", "summary": "The authors discuss the fairness verification of black-box model with confidentiality preservation, which is a significant research topic, since security remains a critical issue in artificial intelligence. The authors proposed to employ zero-knowledge proof method to achieve this goal as well scalability and efficiency. Several experiments are performed to demonstrate its effectiveness and scalability.", "questions": "1. Does the experiment include the evaluation of some real models, like CNN or GNN? How about the parameter number influence the method performance?\n2. 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?\n3. It seems that there are some key references not discussed in the work:\n[1] FairZK: A Scalable System to Prove Machine Learning Fairness in Zero-Knowledge\n[2] Oath: Efficient and flexible zero-knowledge proofs of end-to-end ml fairness\nPlease have a detailed comparison to illustrate the difference between the proposed work and these references.", "limitations": "Refer to the weakness.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1. The work is well-written, and the research topic is significant.\n2. The work is technically solid, and zero-knowledge proof can well address the target issue;\n3. Several analyses and experiments are performed to demonstrate the scalability and security of the work. \n\nWeaknesses:\n1. The fairness should be conceptually explained before the formal definition.\n2. It seems the work does not fully review existing works, and more analyses should be added.\n3. 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?\n4. It seems that there are some key references not discussed in the work:\n[1] FairZK: A Scalable System to Prove Machine Learning Fairness in Zero-Knowledge\n[2] Oath: Efficient and flexible zero-knowledge proofs of end-to-end ml fairness\nPlease have a detailed comparison to illustrate the difference between the proposed work and these references.", "was_revised": true, "final_justification": "My original concern mainly lies in two points. The first one is that the fairness verification issue discussed in this paper can be considered as a secure auditing problem, which has been widely discussed in the field of information security. The proposed method is not directly related to the model structure, but works on the model output. Nevertheless, after reading the response from the authors and the discussion of other reviewers, I consider that the efficient fairness verification method in this work is of significance and indicates contributions. Thus, my first concern is addressed. The second concern is that the mentioned arXiv paper indicates certain similarities to this one, including research problems, methods, performance, and figures, and that is why I expect the authors to discuss the work as well and provide some comparison. However, this concern is not currently addressed. \n\nTherefore, considering that my concerns are partially addressed, I raise the rating from 3 to 4.", "rebuttal": "Thank you for the review. \n\n> **Fairness should be conceptually explained before the formal definition.**\n\nWe will improve our exposition on fairness by revising the Fairness subsection in the preliminaries, and adding the following text:\n\n“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.”\n\n> **Does the experiment include the evaluation of some real models, like CNN or GNN? How about the parameter number influence the method performance?**\n\nYes, 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.\n\nFigure 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.  \n\n\n> **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?**\n\nMost 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. \nThe 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. \n\nWould the reviewer please verify whether this is their intended meaning when referring to secure auditing as a classical problem in information security?\n\n> **Related work.**\n\nWe 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].\n\nThe 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:\n\n\"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.\""}, {"review_id": "BObOoI8haf", "reviewer": "Reviewer_UnaJ", "summary": "This paper examines the problem of certifying online group fairness while maintaining data privacy. Ensuring fairness in machine learning models is particularly important when these models process sensitive user data, yet auditing fairness for confidential datasets remains a significant challenge. To address this, the authors propose the OATH protocol, an efficient and scalable approach based on zero-knowledge proofs for real-time fairness certification. Empirical results demonstrate the protocol's effectiveness in practical settings.", "questions": "See \"Strengths And Weaknesses\".", "limitations": "No.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "1. Clarity: Clear.\n2. Significance: The group fairness and privacy are very important for serving machine learning models.\n3. Originality: I am not very familiar with the literature. Looks original to me.\n4. Quality: The overall quality seems good. A few things that I hope authors can clarify:\n    1. 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?\n    2. 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?", "was_revised": true, "final_justification": "I standby my initial review.", "rebuttal": "We thank the reviewer for noting the strength of our paper. We respond below to both questions raised.\n\n\n> **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?**\n\nWe emphasised that our approach is indeed non-trivial, and we explicitly considered the baseline you suggested – a classic combination of ZKP with fairness verification. \n\n**Why the problem is non-trivial:**\n \nSecurely auditing group fairness requires simultaneously satisfying two critical security properties: \n\n1. query authentication from clients, and \n2. output authentication from the model owner. \n\n(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. \n\nEnsuring both while keeping the protocol efficient and scalable, especially for large neural networks, poses a significant technical challenge.\n\n**Why the classic ZKP-based approach is insufficient:**\n\nAs 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. \n\n**Our approach – why it's non-trivial:**\n\nOur 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).\n\n\n\n> **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?**\n\nWe 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]."}]

Author rebuttal:

Meta-review: The paper proposes a zero-knowledge method for auditing the fairness of a black-box model. The problem statement is clear and well-motivated, and the authors propose a reasonable algorithm for realizing the stated goals. The reviewers have made multiple suggestions related to improving the clarity of the problem setting and guarantees. These include: (a) clarifying the problem statement and notion of fairness under consideration, and including a concrete example to explain the intended use case, (b) including a qualitative description comparing to other baselines, and also addressing the method's resilience to various attacks. Overall, the reviewers' major concerns were largely addressed during the rebuttal phase. I strongly suggest incorporating these clarifications into the next revision of the paper.
Decision: Accept (poster)