Manipulation-Proof Oblivious Audits against Deceptive Model Providers

# Manipulation-Proof Oblivious Audits against Deceptive Model Providers
Source: [https://arxiv.org/html/2608.04365](https://arxiv.org/html/2608.04365)
###### Abstract

Audits have emerged as a critical instrument for algorithmic governance, providing a mechanism for external scrutiny and governance of machine learning models\. However, ensuring the integrity of such assessments remains a challenging issue\. For instance in regulatory contexts, audits are typically declared or easily detected, thus enabling model providers to manipulate the process, whether intentionally or inadvertently\. This vulnerability is particularly acute in the context of fairness evaluations, in which providers can often infer sensitive attributes and strategically equalize allocation rates between groups to satisfy fairness metrics\. In this paper, we introduce a novel audit protocol designed to significantly increase the post\-audit detectability of such manipulations by enabling the auditor to query the model in an oblivious manner\. Our approach leverages a Private Information Retrieval mechanism to require the provider to label a large set of instances, while preventing it from knowing which subset will ultimately be used for the audit\. The protocol is efficient, imposes minimal overhead on the auditor, and requires no modification to the audited model, its training procedure, or its inference pipeline\. We provide theoretical guarantees showing that, under this protocol, a provider attempting to hide unfairness must falsify a significantly larger number of responses, thereby increasing both the difficulty and the likelihood of detection of manipulation\. Experimental results across representative audit scenarios confirm the effectiveness and practicality of our approach\.

Code—github\.com/sofianeazogagh/oblivious˙audit

## 1Introduction

As machine learning \(ML\) systems increasingly mediate access to essential resources and public discourse, robust ML governance has become necessary to ensure these systems operate fairly and comply with legal and ethical standards\(chandrasekaranSoKMachineLearning2021\)\. A central pillar of this governance is algorithmic auditing, which allows independent evaluators to scrutinize model behavior\(metaxaAuditingAlgorithmsUnderstanding2021;costanza2022audits\)\. However, effective external auditing is currently hindered by a severe power asymmetry: model providers maintain strict control over system access, training data and usage statistics\(birhaneAIAuditingBroken2024\)\.

While several mechanisms attempt to bridge this transparency gap—such as dedicated research APIs\(entrena2025tiktok\), academic partnerships\(socialScienceOneStatement2019\)and legally mandated data access—they often face practical limitations and remain vulnerable to provider interference\(bourreeRelevanceAPIsFacing2023\)\. A recent example highlights this fragility: the Meta Ad Library, a tool intended to help regulators and researchers track fraudulent advertisements via keyword searches\. A 2025 Reuters’ report revealed that Meta actively monitored the specific keywords and celebrity names used by Japanese regulators investigating scam ads\(horwitzMetaCreatedPlaybook2025\)\. The company then repeatedly ran those exact searches to preemptively delete the targeted ads in Japan\. By selectively scrubbing the specific data surfaced by the regulators’ queries rather than deploying systematic scam filtering, the provider was able to avoid a regulatory crackdown while avoiding the cost of systematic ad verification\. This reactive curation creates a false impression of compliance, demonstrating how easily current transparency mechanisms can be manipulated by providers when audits queries are observable by the auditee\(fukuchiFakingFairnessStealthily2020;garciabourreeRobustMLAuditing2025\)\.

In this work, we consider a generic regulation setting that captures the dynamics illustrated by the Ad Library example\. A regulator wishes to audit a company providing a prediction service, whether a prediction API or a model used as part of a larger system\. We assume that the regulator can impose an audit protocol on the provider, provided a reasonable computational cost\. The provider is modeled as a*malicious*adversary: rather than incurring the cost of genuinely improving its system, it seeks to pass the audit by adversarially flipping a number of predictions, without modifying its deployed model\. Indeed, the central challenge in this setup \(regulator\-led audits, requiring provider cooperation\) is that the audited provider may strategically modify its outputs when answering audit queries, deviating from the outputs it would provide to genuine users\. Not only is this type of manipulation difficult to detect\(garciabourreeRobustMLAuditing2025\), but a few modifications of the outputs on the audit set can have a dramatic impact on the audit conclusions \(see[Proposition1](https://arxiv.org/html/2608.04365#Thmproposition1)\)\. To address this, we propose a rigorous auditing framework that offers formal theoretical guarantees on the audit’s conclusions and limits the extent of strategic manipulation the provider can perform\. While our proposed framework is model\- and metric\-agnostic, we restrict our presentation to auditing demographic parity in binary classifiers for simplicity, and discuss in[Section6\.1](https://arxiv.org/html/2608.04365#S6.SS1)how it extends to other settings\. Our main contributions are as follows:

- •We introducerespir, an audit protocol designed to mitigate audit manipulations\. The core idea is to hide the actual audit setSSwithin a larger candidate setCC, provably making manipulation harder for a deceptive provider\. The only prerequisite for this protocol is that the audited provider must label a candidate setCClarger than the actual audit setSS\.
- •We prove thatrespirforces a deceptive provider to modify its answers on a substantially larger number of points in the candidate setCCin order to fake the same level of demographic parity \([Theorem1](https://arxiv.org/html/2608.04365#Thmtheorem1)\)\. This results in an increased probability of manipulation detection by the auditor\.
- •We characterize how large the candidate setCCmust be, relative to the audit setSS, to achieve a desired level of manipulation detection while demonstrating that the protocol does not incur prohibitive computational overhead, making it practical for real\-world deployment\.

##### Outline\.

First, in[Section2](https://arxiv.org/html/2608.04365#S2)we review the background on audits, attempts at making them robust, and Private Information Retrieval, which serves as a core building block of our approach\. Next, in[Section3](https://arxiv.org/html/2608.04365#S3)we describe the auditing framework on which our work relies, and we explain why standard black\-box fairness audits can be vulnerable to manipulation\. To address this issue, we introduce in[Section4](https://arxiv.org/html/2608.04365#S4)an oblivious auditing protocol based on PIR, which we callrespir\. We then establish the protocol’s theoretical guarantees in terms of manipulation effort and detectability, and evaluate it experimentally in[Section5](https://arxiv.org/html/2608.04365#S5)\. Finally, we conclude in[Section6](https://arxiv.org/html/2608.04365#S6)with a discussion regarding our framework’s applicability, the main design principles for hidden\-audit\-set protocols, and directions for future work\.

## 2Background & Related Work

### 2\.1Audits and Manipulations

*Audits and regulation\.*Independent audits are a key mechanism for holding model providers accountable and fostering healthier algorithmic ecosystems\(metaxaAuditingAlgorithmsUnderstanding2021;vecchione2021algorithmic;costanza2022audits\)\. This view has been adopted by recent regulations: the EU AI Act\(RegulationEU20242024\), DSA\(RegulationEU20222022\), DMA\(RegulationEU20222022a\)and related frameworks increasingly mandate external assessments of high\-risk AI systems, making algorithmic auditing not only a research concern but a legal requirement\.

*Practical challenges to auditing\.*Several incidents highlight the practical difficulties of conducting trustworthy audits\. In some cases, the studied algorithm changed without notice during the study, as in the 2020 Facebook polarization study\(ribeiroFacebookStandardAlgorithm2024\)\. In others, promised \(or required\) data access was repeatedly delayed\(socialScienceOneStatement2019\)or simply not provided\(EuropeanCommission2025\)\. Finally, when data or models are eventually shared, they may contain errors that undermine published academic work\(timberg\_facebook\_2021\)or fail to reflect the reality experienced by users\(entrena2025tiktok;pearson\_beyond\_2025\)\.

*Manipulability of audit targets\.*Beyond practical obstruction, a growing body of work demonstrates that many components of ML systems can be strategically manipulated\. Training data and sampling procedures can be biased to fake fairness\(fukuchiFakingFairnessStealthily2020\)\. Model explanations can be fairwashed to conceal discriminatory behavior\(aivodjiFairwashingRiskRationalization2019;andersFairwashingExplanationsManifold2020;shamsabadiWashingUnwashableImpossibility2022;fokkemaAttributionbasedExplanationsThat2023\)\. Model outputs themselves can be selectively altered to deceive black\-box auditors\(bourreeRelevanceAPIsFacing2023;garciabourreeRobustMLAuditing2025\)\. And more broadly, fairness metrics are susceptible to gaming when providers can anticipate the evaluation procedure\(hutchinson2022evaluation;thomas2022reliance\)\.

### 2\.2Related Work on Robust Auditing

Existing work on making audits more robust to manipulation can be organized into three broad categories\.

*\(1\) Data\-driven and prior\-based approaches\.*Several works propose auditing protocols that leverage prior knowledge or careful query design to limit manipulation\.yanActiveFairnessAuditing2022study active fairness auditing, where the auditor adaptively selects queries to efficiently estimate fairness violations\.yadavXAuditTheoreticalLook2023provide a theoretical framework for auditing with explanations\. Most closely related to our work,garciabourreeRobustMLAuditing2025formally study manipulation\-proof auditing and show that auditors with prior knowledge about the ground truth can detect manipulations, provided the provider does not know the exact prior they use\. Complementary to these approaches, our method allows to relax the private prior assumption by cryptographically hiding the auditor’s queries\.

*\(2\) Cryptographic approaches\.*A second line of work uses cryptographic tools to provide verifiable guarantees\.shamsabadiConfidentialPROFITTConfidentialPROof2023propose zero\-knowledge proofs of fair training for decision trees\.waiwitlikhitTrustlessAuditsRevealing2024design a protocol based on zero\-knowledge proofs that enables trustless audits without revealing models or data\.franzese\_secure\_2025introduce online fairness certificates via a scalable zero\-knowledge proof protocol that verifies fairness with respect to data received during deployment\.pentyalaPrivFairLibraryPrivacyPreserving2022develop privacy\-preserving fairness auditing using secure computation\. These approaches offer strong guarantees but typically require the provider’s active cooperation in running the cryptographic protocol and may impose significant computational overhead\. In contrast, our proposed framework relies on lightweight PIR primitives and incurs only negligible overhead\.

*\(3\) Secure hardware\.*A third category relies on trusted execution environments or secure hardware to ensure audit integrity\(park2022fairness\)\. While promising, these approaches require trust in the hardware manufacturer and physical deployment constraints, which limit their applicability in many regulatory contexts\.

### 2\.3Private Information Retrieval

Private Information Retrieval \(PIR\) is a cryptographic primitive that enables a client to retrieve an item from a database without revealing to the server which item is being accessed\(ChorKGS98\)\. A large body of work has proposed different PIR constructions depending on the trust and deployment assumptions\. One approach distributes the database across multiple non\-colluding servers to obtain information\-theoretic privacy guarantees\(OlumofinG11\)\. Other approaches rely on trusted hardware\(SmithS01\)but the most promising ones are homomorphic encryption schemes based on lattice problems such as Learning With Errors \(LWE\)\(xpir16;sealpir18;mulpir21;fastpir21;onionpir21;spiral22;frodopir23;simplepir23\)\. In these computational PIR based on homomorphic encryption, the client typically encodes its query as an encrypted selection vector, conceptually corresponding to a one\-hot vector indicating the desired record index\. Afterwards, the server homomorphically combines this encrypted query with the database contents, which are generally represented as a matrix, which means that answering a query essentially reduces to an encrypted matrix\-vector multiplication\. The resulting ciphertext decrypts to the requested record while the server learns nothing about the queried index\. However, this approach generally incurs a computational cost linear in the database size for each query, which severely limits its practicality for large\-scale databases\. To overcome this limitation, a recent line of work has introduced so\-called*stateful PIR*schemes, in which a significant portion of the computation and communication is shifted to an offline preprocessing phase\(corrigan2020private;kogan2021private;shi2021puncturable;onionpir21;corrigan22single\)\. In this stateful PIR, the server first computes and sends to the client a public or semi\-public hint \(or*digest*\) that depends solely on the database and can be reused across multiple queries\. Once this preprocessing step is completed, each individual query can be answered with substantially reduced communication complexity and the server becomes sublinear in the database size\.

Beyond achieving sublinear asymptotic costs, stateful PIR techniques have also been leveraged, not necessarily to achieve sublinear costs, but to make the linear cost per query significantly more efficient\(simplepir23;frodopir23\)\. A prominent example is SimplePIR\(simplepir23\), which relies on Regev’s LWE\-based encryption scheme\(regev2009lattices\)\. The key insight of SimplePIR is to exploit the linear structure of Regev encryption to precompute the vast majority of the expensive matrix operations associated with the database during the offline phase\. As a result, the online query phase only requires lightweight computations that depend on the encrypted query, while the bulk of the matrix\-vector multiplication is carried out in advance and depends exclusively on the database\. This property makes SimplePIR particularly well suited to our setting, in which the provider is informed in advance of an upcoming audit and jointly agrees with the auditor on the audit set\. Once this agreement is established, the provider can label the audit set accordingly and transmit a corresponding digest to the auditor \(see details in Section[4](https://arxiv.org/html/2608.04365#S4)\)\. Furthermore, De Castro and Lee\(verisimplepir24\)introduced VeriSimplePIR, an extension of SimplePIR that ensures verifiability\. More precisely, it allows the client \(*i\.e\.*, the auditor in our case\) to verify that the database queried is exactly the one used to generate the digest sent by the server \(*i\.e\.*, the provider in our setting\) without disclosing the content of the database\. This verifiability is achieved at no additional online cost and can be used to prevent the provider from changing the labels during the audit\.

## 3The Black\-Box Auditing Game

In this section, we first describe the typical black\-box fairness auditing setup considered in this paper\. Then, we theoretically quantify its vulnerability to manipulation\.

### 3\.1Black\-Box Fairness Auditing

Let𝒳\\mathcal\{X\}be the input space, and leth:𝒳→\{0,1\}h:\\mathcal\{X\}\\to\\\{0,1\\\}denote the provider’s \(binary\) prediction function\. Each queryx∈𝒳x\\in\\mathcal\{X\}is associated with a binary*protected*attributeA​\(x\)∈\{0,1\}A\(x\)\\in\\\{0,1\\\}, which partitions the population into two*protected groups*\(those withA=1A=1and those withA=0A=0\)\.

The*demographic parity*gap ofhhquantifies how differentlyhhassigns positive outcomes across these two groups\. More precisely, it is defined as the difference between the probability of predicting the positive class for individuals in groupA=1A=1and the corresponding probability for individuals in groupA=0A=0:

d𝒟​\(h\)\\displaystyle d\_\{\\mathcal\{D\}\}\(h\):=ℙX∼𝒟\(h\(X\)=1\|A\(X\)=1\)\\displaystyle=\\mathbb\{P\}\_\{X\\sim\\mathcal\{D\}\}\\left\(h\(X\)=1\\middle\|A\(X\)=1\\right\)−ℙX∼𝒟\(h\(X\)=1\|A\(X\)=0\),\\displaystyle\\quad\-\\mathbb\{P\}\_\{X\\sim\\mathcal\{D\}\}\\left\(h\(X\)=1\\middle\|A\(X\)=0\\right\),in which𝒟\\mathcal\{D\}denotes the underlying data distribution\. In practice, since𝒟\\mathcal\{D\}is typically unknown, this quantity is estimated on a finite sample setS⊂𝒳S\\subset\\mathcal\{X\}\. Fora∈\{0,1\}a\\in\\\{0,1\\\}, letna=\|\{x∈S:A​\(x\)=a\}\|n\_\{a\}=\\bigl\|\\\{x\\in S:A\(x\)=a\\\}\\bigr\|and define the empirical positive prediction rate over protected groupaaas

pa,S​\(h\):=1na​∑x∈Sah​\(x\)\.p\_\{a,S\}\(h\)\\;:=\\;\\frac\{1\}\{n\_\{a\}\}\\sum\_\{x\\in S\_\{a\}\}h\(x\)\.The demographic parity gap ofhhonSSis then

dS​\(h\):=p1,S​\(h\)−p0,S​\(h\)\.d\_\{S\}\(h\)\\;:=\\;p\_\{1,S\}\(h\)\-p\_\{0,S\}\(h\)\.
When the classifierhhis clear from the context, we omit it from the notation and simply writepa,Sp\_\{a,S\}anddSd\_\{S\}\. Given a toleranceε≥0\\varepsilon\\geq 0, we say thathhsatisfies the demographic parity constraint onSSif

\|dS\|≤ε,\\displaystyle\|d\_\{S\}\|\\leq\\varepsilon,\(1\)in whichε\\varepsilonis a chosen tolerance threshold\. The objective of the auditor is to verify whether Constraint \([1](https://arxiv.org/html/2608.04365#S3.E1)\) holds for a given*audit set*SS\. More precisely, if\|dS\|≤ε\|d\_\{S\}\|\\leq\\varepsilon, the ML provider passes the test while otherwise, if\|dS\|\>ε\|d\_\{S\}\|\>\\varepsilon, the provider is flagged as unfair by the auditor\. However, a key challenge is that the auditor often does not have access to the modelhhitself, nor to its training data, code or documentation\. To estimate the demographic parity gap on an audit setSS, the auditor must therefore*resort to black\-box access*and queryhhon a set of inputsS⊂𝒳S\\subset\\mathcal\{X\}that they collect\. The resulting predictions are then used to computedSd\_\{S\}\. This black\-box audit procedure is described in[Algorithm1](https://arxiv.org/html/2608.04365#alg1)\. In the next subsection, we show how this framework is vulnerable to provider manipulation\.

### 3\.2Manipulating Black\-box Audit

One important limitation of typical demographic parity audits conducted as described in Section[3\.1](https://arxiv.org/html/2608.04365#S3.SS1)is that the auditor only has access to query answers \(through the provider’s audit API\) and no knowledge of the underlying model\. It is therefore possible for a malicious provider to adversarially manipulate the audit by returning a labelh​\(x\)h\(x\)that differs from the underlying model’s true output\. To quantify how easy such manipulation is, Proposition[1](https://arxiv.org/html/2608.04365#Thmproposition1)characterizes the minimum number of predictions that the model provider must flip in order to fall below the detection threshold\.

###### Proposition 1\(Black\-box audit manipulation\)\.

LetS⊂𝒳S\\subset\\mathcal\{X\}be the audit set \(with\|S\|=n\\lvert S\\rvert=n\), letdtrued\_\{\\text\{true\}\}denote the demographic parity gap of the provider’s model onSS\(in the absence of manipulation\), letnmin=min⁡\(n0,n1\)n\_\{\\min\}=\\min\(n\_\{0\},n\_\{1\}\)be the size of the smallest protected group inSS, and letε\\varepsilonbe the audit threshold\. Assuming the model would fail the audit,*i\.e\.*,\|dtrue\|\>ε\|d\_\{\\text\{true\}\}\|\>\\varepsilon, the minimum numbermvanillam\_\{\\text\{vanilla\}\}of predictions that the provider must flip in order to pass the audit satisfies

mvanilla≥⌈\(\|dtrue\|−ε\)​nmin⌉\.m\_\{\\text\{vanilla\}\}\\;\\geq\\;\\lceil\\bigl\(\|d\_\{\\text\{true\}\}\|\-\\varepsilon\\bigr\)\\,n\_\{\\min\}\\rceil\.\(2\)
###### Proof\.

Assume without loss of generality thatdtrue\>0d\_\{\\text\{true\}\}\>0\. Flipping a predictionh​\(x\)h\(x\)from11to0for an example withA​\(x\)=1A\(x\)=1decreasesp1,Sp\_\{1,S\}, and hence the gap onSS, by at most1/n11/n\_\{1\}\. Similarly, flipping a prediction from0to11for an example withA​\(x\)=0A\(x\)=0increasesp0,Sp\_\{0,S\}and decreases the gap by at most1/n01/n\_\{0\}\. Since a single flip affects only one group rate, the gap can decrease by at most

max⁡\(1n0,1n1\)=1nmin\\max\\\!\\left\(\\frac\{1\}\{n\_\{0\}\},\\frac\{1\}\{n\_\{1\}\}\\right\)=\\frac\{1\}\{n\_\{\\min\}\}per modification\. Therefore, reducing the gap fromdtrued\_\{\\text\{true\}\}to at mostε\\varepsilonrequires at least\(dtrue−ε\)​nmin\(d\_\{\\text\{true\}\}\-\\varepsilon\)\\,n\_\{\\min\}modifications, hence at least⌈\(dtrue−ε\)​nmin⌉\\lceil\(d\_\{\\text\{true\}\}\-\\varepsilon\)\\,n\_\{\\min\}\\rceilsincemvanillam\_\{\\text\{vanilla\}\}is an integer\. ∎

Algorithm 1Black\-Box audit procedure1:𝒳\\mathcal\{X\},hh

2:Auditor gathers or generate an audit datasetS⊂𝒳S\\subset\\mathcal\{X\}

3:For each examplex∈Sx\\in S, the auditor queries the provider forh​\(x\)h\(x\)

4:The auditor computes the parity gapdSd\_\{S\}

5:ifdS<εd\_\{S\}<\\varepsilonthen

6:returnPass

7:else

8:returnFail

Algorithm 2Therespiraudit procedure1:𝒳\\mathcal\{X\},hh

2:Provider and auditor agree on a large candidate setC⊂𝒳C\\subset\\mathcal\{X\}

3:Provider privately labels all examples inCC, creatingD=\{\(x,h​\(x\)\):x∈C\}D=\\left\\\{\(x,h\(x\)\):x\\in C\\right\\\}

4:Auditor interacts withDDto retrieve outputs on an audit setS⊂DS\\subset D5:using thePIR\(PIR\) primitive

6:ifdS<εd\_\{S\}<\\varepsilonthen

7:returnPass

8:else

9:returnFail

Proposition[1](https://arxiv.org/html/2608.04365#Thmproposition1)provides a lower bound on the number of output modifications that a provider must perform in order to pass the audit\. This bound is linear in the amount of unfairness to be hidden but also in the size of the smallest protected group in the audit set, which means that unbalanced audit sets therefore greatly facilitate manipulation\. However, even for a balanced audit set, manipulating the audited fairness remains easy\. For instance, to hide a disparity of0\.010\.01\(*i\.e\.*,dtrue−ε=0\.01d\_\{\\text\{true\}\}\-\\varepsilon=0\.01\) with a balanced audit set ofn=400n=400queries, the provider only has to modify two predictions\.

The manipulation model considered in this work therefore consists of arbitrary output flipping\. By allowing any \(worst\-case\) modification to the prediction vector returned by the platform, this model generalizes more constrained threat models and yields model\-agnostic guarantees\.

Assume that the auditor possesses a small*verification set*ofkkqueries \(also called*canaries*\)\. These queries are externally labeled \(*e\.g\.*, via crowdsourcing or by directly querying the provider’s public API\), and manipulation is detected as soon as at least one verification query is modified by the provider\. Since the auditor controls the audit setSS, we assume that the canaries are included inSSby construction\. Therefore, the canary effectiveness can be modeled through a single*catch\-all*parameterq∈\[0,1\]q\\in\[0,1\], interpreted as the probability that a canary included in the audit set remains indistinguishable to the provider \(so that the provider cannot selectively avoid modifying it\)\. Letn:=\|S\|n\\;:=\\;\\lvert S\\rvertdenote the size of the audit set, and letmmdenote the number of audit set queries whose outputs are adversarially modified by the provider\. Then, conditional on being effectively present, a canary is modified with probabilitym/nm/n, and the probability that manipulation is detected satisfies

ℙ​\(manipulation detected\)=1−\(1−q​m/n\)k\.\\mathbb\{P\}\(\\text\{manipulation detected\}\)\\;=\\;1\-\\bigl\(1\-q\\,m/n\\bigr\)^\{k\}\.\(3\)Overall, this highlights that typical black\-box fairness audits can be highly brittle, as a small number of targeted output modifications may suffice to hide unfairness\. Moreover, our detection analysis shows that the probability of catching such manipulation depends critically on both the number of adversarial manipulationsmmand the sizekkof the verification set: smallkkprovides limited guarantees when only a few outputs are modified, whereas detection quickly becomes likely as eithermmorkkincreases\.

While increasing the number of canarieskkis a simple countermeasure, it is often impractical or too costly in practice\. Instead, in the next section, we propose an oblivious auditing protocol that prevents the provider from tailoring its modifications to the specific audit set\. As a result, to hide unfairness with high probability, the provider is forced to perform a larger numbermmof output modifications, which increases the cost of manipulation and its detectability\.

## 4Oblivious Auditing

### 4\.1respirProtocol

Based on the observation that hiding unfairness over a known finite set is easily achieved, we propose a new audit protocol coinedrespir\(respir\)\. To mitigate audit manipulations,respirforces the provider to find a strategy to optimize its manipulations on a significantly larger*candidate set*CCrather than on the particular audit setSSdrawn by the auditor\. The cryptographic primitive that prevents the provider from knowing which sample is used in the audit is thePIR\(*cf\.*Section[2\.3](https://arxiv.org/html/2608.04365#S2.SS3)\)\. The audit protocol consists of three steps, described in[Algorithm2](https://arxiv.org/html/2608.04365#alg2):

- •Step 1 \([Algorithm2](https://arxiv.org/html/2608.04365#alg2),[2](https://arxiv.org/html/2608.04365#alg2.l2)\)\. The provider and the auditor agree on a \(large\)*candidate set*CC\. In practice the candidate set can be proposed by the auditor \(*e\.g\.*, derived from a large public dataset\) or by the provider \(*e\.g\.*, the company is required to share internal information to prepare for the audit\)\. The selection process forCCcan even be iterative: after one party proposes a first candidate set, the other can ask for additions or deletions to reach a more representative distribution\.
- •Step 2 \([Algorithm2](https://arxiv.org/html/2608.04365#alg2),[3](https://arxiv.org/html/2608.04365#alg2.l3)and[4](https://arxiv.org/html/2608.04365#alg2.l4)\) The auditor samples an*audit set*S⊂CS\\subset Camong the candidate set and runs it through the PIR mechanism\. ThePIRmechanism guarantees that 1\) the provider cannot infer the exact audit queries used inSSand 2\) the auditor cannot use the interaction to gather more information about the output ofhhother than what is given byh​\(S\)h\(S\)\. Thus, thePIRproperties effectively exclude any manipulation during the interaction between the auditor and the provider at step 2\.
- •Step 3 \([Algorithm2](https://arxiv.org/html/2608.04365#alg2),[6](https://arxiv.org/html/2608.04365#alg2.l6),[7](https://arxiv.org/html/2608.04365#alg2.l7)and[9](https://arxiv.org/html/2608.04365#alg2.l9)\) Using the answers of the providerh​\(S\)h\(S\)gathered during thePIRphase, the auditor produces an estimatedSd\_\{S\}of the audit metric and decides whether the provider passes the audit or not\. The goal of a malicious provider is to make the auditor accept its model \(*i\.e\.*,dS≤εd\_\{S\}\\leq\\varepsilon\) when it should not have passed \(*i\.e\.*,dtrue\>εd\_\{\\text\{true\}\}\>\\varepsilon\)\.

We further highlight the following design properties\. First, the candidate setCCis constructed to be representative of the \(unknown\) data distribution𝒟\\mathcal\{D\}\. Consequently, when the audit setS⊆CS\\subseteq Cis sampled uniformly at random and is sufficiently large, it is expected to closely reflect𝒟\\mathcal\{D\}\. WhileSScould be sampled fromCCin other ways, uniform sampling is used because it \(i\) yields representativeness via standard concentration arguments and is easier for the provider to accept, whereas tailored sampling can appear arbitrary to target specific fairness values, \(ii\) requires no prediction\-dependent design since the auditor sees features inCCbut not the model’s outputs, and \(iii\) enables a clean probabilistic derivation of manipulation lower bounds \(Theorem[1](https://arxiv.org/html/2608.04365#Thmtheorem1)\)\. Moreover, planting a small numberkkof verification queries \(*canaries*\) intoSSdoes not materially affect this representativeness whenk≪\|S\|k\\ll\|S\|\. As a result, it is reasonable to require the provider to pass the fairness verification \(*i\.e\.,*to exhibit unfairness of at mostε\\varepsilon\) onSS\.

Second, although the provider is required to label a potentially large candidate setCC, the amount of information revealed to the auditor is the same as in the traditional black\-box auditing setup described in Section[3\.1](https://arxiv.org/html/2608.04365#S3.SS1), since the sampled audit setSSneed not be larger\. Because the provider’s underlying model may be proprietary or constitute a business secret, this property is important in practice\.

Third, the use of aPIRscheme prevents the provider from tailoring its responses to a known audit set\. Instead, to pass the audit with high probability, the provider must ensure that the fairness constraint holds for a random audit set drawn from the candidate set, implying that fairness must generalize across the candidate set rather than being satisfied only on a specific subset\. In[Section4\.3](https://arxiv.org/html/2608.04365#S4.SS3), we provide a probabilistic analysis showing that this substantially increases both the cost and detectability of manipulation\.

### 4\.2VeriSimplePIR Applied to an Audit Set

LetSSdenote the audit set andhhthe provider’s prediction function\. The primary advantage of using a PIR protocol for auditing, as opposed to sending an encrypted version of the audit setSS, lies in its efficiency as PIR is considerably faster than evaluating the model onSSvia homomorphic encryption\. For example, ifhhis a neural network, runningx∈Sx\\in Sthroughhhwith homomorphic encryption would require as many matrix\-vector multiplications as there are network layers\. In contrast, the PIR protocol reduces this to a single, lightweight matrix\-vector multiplication perx∈Sx\\in S\.

While a detailed description of the interaction during the PIR between the auditor and the provider is provided in[Figure3](https://arxiv.org/html/2608.04365#A1.F3)in Appendix[A](https://arxiv.org/html/2608.04365#A1), we summarize here the main steps of the protocol at a high level\. VeriSimplePIR proceeds in two phases: an offline phase for setup and commitment and an online phase for querying\. The process starts when the auditor requests an audit from the provider\. After both parties agree on the audit setSS, the provider applies its prediction functionhhto label the samples, resulting in a databaseh​\(S\)h\(S\)\. These labels are then packed into a small matrix𝐃∈ℤpℓ×μ\\mathbf\{D\}\\in\\mathbb\{Z\}\_\{p\}^\{\\ell\\times\\mu\}, with the parametersℓ\\ell,pp, andμ\\muspecified by the auditor to satisfy security requirements\. Additionally, the provider provides an indexing table to assist the auditor in mapping labels to the corresponding samples in𝐃\\mathbf\{D\}\.

The protocol then proceeds through four main functions:Commitment,Query,AnswerandRecovery\. During the offline phase, the provider performs theCommitmentfunction by generating a cryptographic digest of the matrix𝐃\\mathbf\{D\}and a “hint” sent to the auditor to verify that𝐃\\mathbf\{D\}is well formed\. The auditor cannot learn the content of the database from the digest or the hint\. Optionally, the provider can also precompute a proofπ\\pithat will later be used to verify that queries are performed on the committed database \(see Construction 5\.1 in\(verisimplepir24\)for more details about this proof\)\.

In the online phase, the auditor executes theQueryfunction by selecting an indexi=\(ir,ic\)i=\(i\_\{r\},i\_\{c\}\)and sending an encryption of the one\-hot encoding ofici\_\{c\}to the provider using the Regev’s LWE encryption scheme\(regev2009lattices\)\. The provider then performs theAnswerfunction by computing a matrix\-vector multiplication between the𝐃\\mathbf\{D\}and the encrypted query\. Finally, the auditor executes theRecoveryfunction to decrypt and extract the queried value from the response\. The auditor can perform multiple queries and verify them all at once using the precomputed proofπ\\pi\(see\(verisimplepir24\)for more details about this proof\)\. To demonstrate how the protocol performs in practice,[Table1](https://arxiv.org/html/2608.04365#S4.T1)reports timing measurements for the online phase \(query, answer and recovery steps\) along the bandwidth usage, across various sizes ofh​\(S\)h\(S\), in whichhhis a binary classifier\. The given results are an average of 10 runs\. When∀y∈h​\(S\),log2⁡\(y\)<log2⁡\(p\)\\forall y\\in h\(S\),\\log\_\{2\}\(y\)<\\log\_\{2\}\(p\), multiple labelsyycan be encoded within a single element inℤp\\mathbb\{Z\}\_\{p\}, so each entry in𝐃\\mathbf\{D\}can store several labels\. As a result, the matrix𝐃\\mathbf\{D\}can be considerably smaller than the raw set of labelsh​\(S\)h\(S\)\. The results reported shows that the PIR protocol maintains practical efficiency even when handling large audit sets\.

Table 1:Performance of VeriSimplePIR\(verisimplepir24\)on the online phase for different database sizes\.
### 4\.3Manipulation Difficulty Analysis

We now establish probabilistic guarantees that hiding the audit set throughrespirincreases the difficulty of targeted manipulations\. The results formalize a core intuition: if the provider cannot identify the audited queries, then passing the audit with high probability requires improving behavior on a nontrivial fraction of the entire candidate set, rather than selectively patching a known evaluation subset\.

###### Theorem 1\(respiraudit manipulation\)\.

LetC⊂𝒳C\\subset\\mathcal\{X\}be the candidate set \(with\|C\|=N\\lvert C\\rvert=N\) and letS⊂CS\\subset Cbe the audit set \(with\|S\|=n\\lvert S\\rvert=n\), sampled uniformly at random without replacement fromCC\. LetdC,trued\_\{C,\\text\{true\}\}denote the demographic parity gap of the provider’s model onCC\(in the absence of manipulation\), letnmin=min⁡\(n0,n1\)n\_\{\\min\}=\\min\(n\_\{0\},n\_\{1\}\)be the size of the smallest protected group inSS, letNmin=min⁡\(N0,N1\)N\_\{\\min\}=\\min\(N\_\{0\},N\_\{1\}\)be the size of the smallest protected group inCC, and letε\\varepsilonbe the audit threshold\. Forδ∈\(0,12\]\\delta\\in\(0,\\frac\{1\}\{2\}\], assuming the model would fail the audit,*i\.e\.*,\|dC,true\|\>ε\|d\_\{C,\\text\{true\}\}\|\>\\varepsilon, it suffices for the provider to flip at least

mrespir≥⌈\(\|dC,true\|−ε\+2​ln⁡\(4/δ\)nmin\)​Nmin⌉m\_\{\\text\{\\acs\{respir\}\}\}\\;\\geq\\;\\left\\lceil\\left\(\\lvert d\_\{C,\\text\{true\}\}\\rvert\-\\varepsilon\+\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}\}\}\\right\)N\_\{\\min\}\\right\\rceil\(4\)predictions inCCin order to pass the audit with probability at least1−δ1\-\\delta\.

![Refer to caption](https://arxiv.org/html/2608.04365v1/x1.png)

![Refer to caption](https://arxiv.org/html/2608.04365v1/x2.png)

\(a\)Lower bounds on the number of output flipsmmrequired to hide unfairness, for the unbalanced setting \(left\) and the balanced setting \(right\)\.
![Refer to caption](https://arxiv.org/html/2608.04365v1/x3.png)

![Refer to caption](https://arxiv.org/html/2608.04365v1/x4.png)

\(b\)Probability that the auditor detects manipulation, for the unbalanced setting \(left\) and the balanced setting \(right\)\.

Figure 1:Illustration of our theoretical bounds on manipulation difficulty for a vanilla black\-box audit and forrespir\. We consider audit sets of size\|S\|=400\|S\|=400andk∈\{1,3,5\}k\\in\\\{1,3,5\\\}canaries, each detected with effectiveness probabilityq=0\.8q=0\.8\. Forrespir, we use a candidate set of size\|C\|=2,000\|C\|=2\{,\}000and target passing probability1−δ=0\.951\-\\delta=0\.95\. We compare two protected group\-composition regimes: an unbalanced regime where the minority group represents10%10\\%ofSS\(and ofCCforrespir\) and a balanced regime with equal group sizes\. The horizontal axis varies the amount of unfairness above the toleranceε\\varepsilon\.###### Proof\.

Letγ:=2​ln⁡\(4/δ\)nmin\\gamma:=\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}\}\}\. By Theorem[2](https://arxiv.org/html/2608.04365#Thmtheorem2)\(provided hereafter in Section[4\.3](https://arxiv.org/html/2608.04365#S4.SS3.SSSx1)\), a sufficient condition for passing the audit with probability at least1−δ1\-\\delta\(conditional onn0,n1n\_\{0\},n\_\{1\}\) is that the \(post\-manipulation\) candidate\-set gap satisfies

\|dC\|≤ε−γ\.\|d\_\{C\}\|\\leq\\varepsilon\-\\gamma\.Thus, it suffices for the provider to modify predictions onCCso as to reduce the initial gap\|dC,true\|\|d\_\{C,\\text\{true\}\}\|down to at mostε−γ\\varepsilon\-\\gamma\.

We now bound the number of prediction flips required to achieve such a reduction onCC\. Assume without loss of generality thatdC,true\>0d\_\{C,\\text\{true\}\}\>0\(otherwise apply the same argument to−dC,true\-d\_\{C,\\text\{true\}\}\)\. Consider a single flip of one prediction onCC\. If the flipped example belongs to groupA=1A=1, thenp1,Cp\_\{1,C\}changes by at most1/N11/N\_\{1\}, hencedCd\_\{C\}changes by at most1/N11/N\_\{1\}\. If it belongs to groupA=0A=0, thenp0,Cp\_\{0,C\}changes by at most1/N01/N\_\{0\}, hencedCd\_\{C\}changes by at most1/N01/N\_\{0\}\. Therefore, a single flip can changedCd\_\{C\}by at most

max⁡\(1N0,1N1\)=1Nmin\.\\max\\\!\\left\(\\frac\{1\}\{N\_\{0\}\},\\frac\{1\}\{N\_\{1\}\}\\right\)=\\frac\{1\}\{N\_\{\\min\}\}\.To reachdC≤ε−γd\_\{C\}\\leq\\varepsilon\-\\gamma, the provider must decrease the gap by at least

dC,true−\(ε−γ\)=\|dC,true\|−ε\+γ\.d\_\{C,\\text\{true\}\}\-\(\\varepsilon\-\\gamma\)=\|d\_\{C,\\text\{true\}\}\|\-\\varepsilon\+\\gamma\.Since each flip can reducedCd\_\{C\}by at most1/Nmin1/N\_\{\\min\}, it suffices to flip at least

⌈\(\|dC,true\|−ε\+γ\)​Nmin⌉\\left\\lceil\\left\(\|d\_\{C,\\text\{true\}\}\|\-\\varepsilon\+\\gamma\\right\)N\_\{\\min\}\\right\\rceilpredictions inCC, as claimed\. ∎

The manipulation resistance ofrespir\([Theorem1](https://arxiv.org/html/2608.04365#Thmtheorem1)\) improves on that of a “vanilla” black\-box audit \([Proposition1](https://arxiv.org/html/2608.04365#Thmproposition1)\) in two complementary ways\. First,respirenforces a stricter effective target on the provider’s underlying disparity because of the sampling uncertainty term2​ln⁡\(4/δ\)/nmin\\sqrt\{2\\ln\(4/\\delta\)/n\_\{\\min\}\}\. This term materializes the fact that under uniform random sampling fromCC, audits setsSSmight exhibit unfairnessdSd\_\{S\}slightly lower or higher due to the sampling process\. Nevertheless, as long as they are representative of the underlying distribution \(which is the case unlessn=\|S\|n=\\lvert S\\rvertis pathologically small\), the provider’s model is expected to behave fairly on them as well\. In other words, to ensure unfairness does not exceedε\\varepsilonon the sampledSSwith high probability, the provider must over\-correct unfairness over the candidate set\. Second,respirincreases the scale at which modifications must be performed\. In a vanilla black\-box audit, the provider may concentrate changes on the audited setSS, so the best\-case manipulation complexity scales withnminn\_\{\\min\}\. Underrespir, the provider must instead improve fairness across the entire candidate setCCto pass for an unknown randomSS, implying a manipulation complexity that scales withNminN\_\{\\min\}, the size of the smaller protected group inCC\. Since typicallyNmin≫nminN\_\{\\min\}\\gg n\_\{\\min\}, this yields a substantially larger manipulation cost\.

Taken together, these two effects force the provider to modify a substantially larger number of outputs to pass reliably, which in turn increases the probability that manipulation is detected\. Indeed, given a verification set ofkkcanaries \(drawn fromCCand externally labeled\), the probability of detection increases with the manipulated fractionm/Nm/N\(according to \([3](https://arxiv.org/html/2608.04365#S3.E3)\), in which we substitutennbyNNto model the probability that a canary’s output is modified\)\. Moreover, whenkkis small compared to the audit sizenn, the auditor can include these canaries alongside the sampled audit setSSwithout materially affecting the fairness estimation guarantees derived above\.

##### Illustrative Example

The manipulation difficulty of both the vanilla black\-box audit and our proposedrespiraudit is illustrated in[Figure1](https://arxiv.org/html/2608.04365#S4.F1)for a representative parameter setting\. In particular,[Figure1\(a\)](https://arxiv.org/html/2608.04365#S4.F1.sf1)reports the number of output flips the provider must perform as a function of the amount of unfairness to hide, while[Figure1\(b\)](https://arxiv.org/html/2608.04365#S4.F1.sf2)shows the corresponding probability that the auditor detects such manipulation for different numbers of canaries included in the audit setSS\. As expected, protected group imbalance \(left panels\) substantially facilitates audit manipulation compared to the balanced case \(right panels\), as fewer output flips are needed to drive the observed disparity below the toleranceε\\varepsilon\. In both regimes,respirnotably increases the required number of flipsmmand, consequently, the probability of manipulation detection\.

#### Intermediate Concentration Result

Theorem[1](https://arxiv.org/html/2608.04365#Thmtheorem1)follows from Theorem[2](https://arxiv.org/html/2608.04365#Thmtheorem2), which formalizes the fact that the audit only observes the disparity through the sample\-based estimatedSd\_\{S\}\. WhenSSis sampled uniformly at random fromCC,dSd\_\{S\}concentrates arounddCd\_\{C\}, with deviations controlled at scaleln⁡\(1/δ\)/nmin\\sqrt\{\\ln\(1/\\delta\)/n\_\{\\min\}\}\. Consequently, to pass with high probability, the provider must keep its candidate\-set gap at least this far*below*the fairness threshold\.

###### Theorem 2\(respiraudit: Sufficient candidate set condition for high\-probability passing\)\.

Letnmin:=min⁡\(n0,n1\)n\_\{\\min\}:=\\min\(n\_\{0\},n\_\{1\}\)and fixδ∈\(0,1\)\\delta\\in\(0,1\)\. If the provider’s candidate set gap satisfies

\|dC\|≤ε−2​ln⁡\(4/δ\)nmin,\|d\_\{C\}\|\\;\\leq\\;\\varepsilon\\;\-\\;\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}\}\},then the provider passes the audit with probability at least1−δ1\-\\delta:

Pr⁡\(\|dS\|≤ε∣n0,n1\)≥1−δ\.\\Pr\(\|d\_\{S\}\|\\leq\\varepsilon\\mid n\_\{0\},n\_\{1\}\)\\;\\geq\\;1\-\\delta\.

###### Proof\.

Conditioning on\(n0,n1\)\(n\_\{0\},n\_\{1\}\), we apply finite\-population Hoeffding/Serfling bounds\(hoeffding1963;serfling1974\)to each group ratepa,Sp\_\{a,S\}, and then use the triangle inequality and a union bound to obtain

Pr⁡\(\|dS−dC\|≥γ∣n0,n1\)≤4​exp⁡\(−γ22​nmin\)\.\\Pr\\\!\\left\(\|d\_\{S\}\-d\_\{C\}\|\\geq\\gamma\\mid n\_\{0\},n\_\{1\}\\right\)\\leq 4\\exp\\\!\\left\(\-\\frac\{\\gamma^\{2\}\}\{2\}n\_\{\\min\}\\right\)\.Withγ=2​ln⁡\(4/δ\)/nmin\\gamma=\\sqrt\{2\\ln\(4/\\delta\)/n\_\{\\min\}\}, this probability is at mostδ\\delta\. Hence, if\|dC\|≤ε−γ\|d\_\{C\}\|\\leq\\varepsilon\-\\gamma, then\|dS\|≤ε\|d\_\{S\}\|\\leq\\varepsilonwith probability at least1−δ1\-\\delta\. See Appendix[B](https://arxiv.org/html/2608.04365#A2)for the detailed proof\. ∎

Table 2:Overview of the characteristics of the considered datasets\.DatasetA​c​cAcc\|dC,true\|\|d\_\{C,\\text\{true\}\}\|NNnnNminN\_\{\\text\{min\}\}nminn\_\{\\text\{min\}\}NminN\\frac\{N\_\{\\text\{min\}\}\}\{N\}CCDgender30,0000\.8230\.02813,5006,7505,3502,6750\.396education0\.820\.0442,4171,2090\.179marriage0\.8210\.0096,1473,0730\.455age0\.820\.0274,9562,4780\.367COMPASgender6,1720\.660\.1482,7781,3895292640\.19race0\.670\.1649474730\.341hatedaylanguage81,0000\.950\.00836,45018,2253,0381,5190\.083

## 5Experimental Evaluation

To illustrate and empirically validate our results, we selected three datasets spanning tabular and text domains: Default of Credit Card Clients \(CCD\)\(Yeh2009TheCO\), COMPAS\(larsonHowWeAnalyzed2016\), and HateDay\(tonneauHateDayInsightsGlobal2025\)\. We extracted numerical features from the HateDay text data using an off\-the\-shelf sentence transformer111huggingface\.co/sentence\-transformers/distiluse\-base\-multilingual\-cased\-v2\. For a fixed protected attribute, each dataset was randomly split70/3070/30into a training set and a candidate set, using stratification with respect to the sensitive attribute\. The model and data pre\-processing is a histogram gradient boosted tree baseline from theskrublibrary222skrub\-data\.org/stable/reference/generated/skrub\.tabular˙pipeline\.html\. We tuned the learning rate, number of leaf nodes and number of estimators via random search with55\-fold cross\-validation on the training set\. After hyperparameter selection, we retrained the model on the full training set\. Our source code is available in our online repository333github\.com/sofianeazogagh/oblivious˙audit, which includes all scripts and datasets required to reproduce our experiments and results, as well as our PIR\-based auditing framework implemented as a user\-friendly module\.

[Table2](https://arxiv.org/html/2608.04365#S4.T2)summarizes the main characteristics of each dataset\. Specifically, for each dataset we report the model accuracy \(A​c​cAcc\) and the demographic parity gap \(\|dC,true\|\|d\_\{C,\\text\{true\}\}\|\) before any manipulation, both measured on the candidate setCC\. We also report the candidate set sizeNN, the audit set sizennas well as the size of the smallest protected group in each set \(respectivelyNminN\_\{\\min\}andnminn\_\{\\min\}\)\. As shown in the last column, some setups are highly imbalanced\. For example, in HateDay the smallest protected group represents only about8%8\\%of the candidate set\.

We then simulate audit manipulation, in which a malicious provider attempts to hide half of its unfairness\. That is, for each dataset and protected attribute, we setε=\|dC,true\|/2\\varepsilon=\|d\_\{C,\\text\{true\}\}\|/2\. We leverage[Proposition1](https://arxiv.org/html/2608.04365#Thmproposition1)and[Theorem1](https://arxiv.org/html/2608.04365#Thmtheorem1)to compute the number of output modifications required to hide this amount of unfairness against a traditional \(“vanilla”\) black\-box audit and against arespir\-based audit\. Forrespir, the provider targets passing probability1−δ=80%1\-\\delta=80\\%\. Finally, we plug these modification counts into[Equation3](https://arxiv.org/html/2608.04365#S3.E3)to obtain the corresponding probability of manipulation detection in a setting where the auditor has a verification set ofk∈\{5,10,20,50\}k\\in\\\{5,10,20,50\\\}canaries \(see[Section4\.3](https://arxiv.org/html/2608.04365#S4.SS3)\)\. Note that Theorem[1](https://arxiv.org/html/2608.04365#Thmtheorem1)should be interpreted as an analytical characterization of manipulation difficulty, rather than as an operational recipe\. Indeed, the bound depends on quantities that are not all known to the auditor, such as the platform’s true candidate\-set disparity, and, under random sampling, on quantities not known in advance to the platform, such as the realized value ofnminn\_\{\\min\}\.

The results are summarized in Table[3](https://arxiv.org/html/2608.04365#S5.T3), and displayed in Figure[2](https://arxiv.org/html/2608.04365#S5.F2)for a subset of our experiments\. As expected, the number of output manipulations required to hide unfairness increases substantially underrespircompared to a traditional \(“vanilla”\) black\-box audit\. This, in turn, leads to systematically higher probabilities of detecting such manipulation, often by roughly a factor of two, which is particularly noteworthy since the final audit set sizen=\|S\|n=\|S\|is identical for both audit frameworks\. Comparing results across datasets and protected attributes and relating them to the dataset characteristics summarized in Table[2](https://arxiv.org/html/2608.04365#S4.T2), two main factors drive detectability\. First, protected group imbalance greatly facilitates manipulation\. For instance, for the highly imbalanced HateDay setting, the probability of detecting manipulation remains very small even withk=50k=50canaries\. Second, larger unfairness levels to be hidden require more output flips, which increases detectability\. For example, the highest detection probabilities for both audit frameworks occur for COMPAS with race as the protected attribute, which is also the configuration with the largest initial unfairness\. As shown in Figure[2](https://arxiv.org/html/2608.04365#S5.F2), the number of canaries owned by the auditor remains a crucial parameter, strongly influencing manipulation detectability for both methods\.

Table 3:Manipulation cost and manipulation detection probability for each dataset and protected attribute\. For each setting, we report the required number of output flips to hide half of the initial unfairness under a vanilla black\-box audit and underrespir, together with the resulting detection probabilities for different numbers of canarieskk\.![Refer to caption](https://arxiv.org/html/2608.04365v1/x5.png)Figure 2:Probability of manipulation detection for a subset of our experiments, as a function of the number of canarieskk, for vanilla audits and for our proposedrespiraudit framework\.It is also worth noting that when the toleranceε\\varepsilonis close to zero, and in particular when it is smaller thanγ=2​ln⁡\(4/δ\)nmin\\gamma=\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}\}\}\(which can occur, for instance, whennminn\_\{\\min\}is small\), the sufficient target

\|dC\|≤ε−2​ln⁡\(4/δ\)nmin\|d\_\{C\}\|\\;\\leq\\;\\varepsilon\\;\-\\;\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}\}\}for passing with probability at least1−δ1\-\\deltamight become unattainable, since\|dC\|≥0\|d\_\{C\}\|\\geq 0\. In our experiments, such cases arise for some configurations in which\|dC,true\|\|d\_\{C,\\text\{true\}\}\|is already very small\. In these regimes, the provider may be unable to reach the desired passing confidence level1−δ1\-\\deltafor therespiraudit\. Nevertheless, we still report its best\-effort manipulation, namely the number of output modifications required to achieve\|dC\|=0\|d\_\{C\}\|=0, which, as reflected in our results, still tends to make manipulation more detectable by the auditor\.

Overall, these findings confirm the purpose ofrespir\. By hiding the audited setSSthrough PIR, our protocol forces malicious providers to spread manipulations over a larger fraction of the candidate set, thereby increasing the effort required to hide unfairness and substantially improving the probability of detecting such manipulation\.

## 6Limitations, Discussion and Conclusion

### 6\.1Applicability of the Proposed Approach

##### Audited Model\.

Our proposed framework, as well as the accompanying theoretical analysis, is agnostic to the type of audited model\. Indeed, the provider’s model class matters only if the provider must realize flips by retraining a new classifier within the same hypothesis space\. Our adversary model is more powerful as the provider can patch the deployed system by overriding outputs on selected inputs without retraining\. This is at the same time realistic but also a worst\-case situation for the auditor\. If the provider was not able to flip selected answers without a full model retraining, arbitrary flips might be infeasible and the provider could need more changes to hide unfairness, so our lower bounds \(Proposition[1](https://arxiv.org/html/2608.04365#Thmproposition1)and Theorem[1](https://arxiv.org/html/2608.04365#Thmtheorem1), holding for any input\-output mapping\) would remain valid but potentially conservative\.

##### Audited Metric\.

While in this paper, we focus on the demographic parity metric, our approach naturally extends to auditing other model properties\. Indeed, the PIR\-based component treats the fairness computation as a modular measurement block, so our proposed auditing framework is metric\-agnostic\. In particular, Proposition[1](https://arxiv.org/html/2608.04365#Thmproposition1)and Theorem[1](https://arxiv.org/html/2608.04365#Thmtheorem1)can be straightforwardly adapted to other fairness criteria \(including separation\- and sufficiency\-based metrics, which encompasses but is not limited to group fairness metrics based on true positive rates \(equal opportunity\), false positive rates \(predictive equality\) or both \(equalized odds\)\), by incorporating the proper sensitivity value suited to the audited measure\. Similar guarantees regarding resilience to manipulation would then hold, as illustrated for the equal opportunity metric in Appendix[C](https://arxiv.org/html/2608.04365#A3)\. On the same line, our framework and guarantees can also be applied to setups with several sensitive attributes or multi\-class problems, as long as the sensitivity of the audited function can be analytically expressed or bounded \(as in the proofs of Proposition[1](https://arxiv.org/html/2608.04365#Thmproposition1)and Theorem[1](https://arxiv.org/html/2608.04365#Thmtheorem1)\), key to lower bounding the number of flips required to fool the audit\. We therefore expect the same modularity could support regression as well, though fairness for regression has been less explored in the literature\.

### 6\.2Discussion

We studied the problem of auditing fairness claims in adversarial settings, in which an audited provider may adapt its outputs once it can anticipate which inputs will be inspected\. Our main contribution isrespir, an oblivious auditing protocol that leverages PIR to hide the auditor’s queries within a larger candidate set\. By construction, this prevents the provider from patching a known audit set\. Instead, passing with high probability requires spreading modifications over a nontrivial fraction of the candidate set\. We formalized this intuition through concentration\-based guarantees that lower bound the manipulation effort needed to pass, and we combined these bounds with a canary\-based verification mechanism to translate manipulation effort into a detection probability\. Our experiments on tabular and text datasets confirms that for a fixed audit set size,respirincreases the number of required output flips and, consequently, improves the detectability of targeted manipulation, with the strongest gains arising when the candidate set is large and sufficiently balanced across protected groups\.

Nevertheless, as illustrated by our experiments, strong protected group imbalance and small audit sets remain limiting factors\. The manipulation guarantees in[Section4\.3](https://arxiv.org/html/2608.04365#S4.SS3)and their empirical evaluation in[Section5](https://arxiv.org/html/2608.04365#S5)highlight three main design principles:

1. 1\.*Large and representative candidate sets\.*As the best\-case manipulation cost scales withmin⁡\(N0,N1\)\\min\(N\_\{0\},N\_\{1\}\), the candidate set should be large and should contain nontrivial representation of each protected group\.
2. 2\.*Balanced auditing\.*Since detection power scales withmin⁡\(n0,n1\)\\min\(n\_\{0\},n\_\{1\}\), the auditor should sampleSSusing a rule that avoids severe group imbalance; stratified sampling fromCCis a natural option\.
3. 3\.*Hiding the audit set is necessary but not always sufficient\.*PIR prevents the provider from learning*which*queries are in the audit set, blocking the cheapest form of manipulation \(patching exactlySS, as in[Proposition1](https://arxiv.org/html/2608.04365#Thmproposition1)\)\. However, our guarantees rely on the candidate set capturing a meaningful portion of the provider’s operational domain\. IfCCis not representative, then passing the audit may not translate into improved fairness outsideCC\.

##### Limitations\.

We viewrespiras a proof\-of\-concept showing how cryptographic primitives can be leveraged to hide the actual queries used during an algorithmic audit\. Its main benefit is to prevent audit set adaptivity: the platform can no longer tailor its responses to the particular audit setSS, but must instead commit to outputs over a larger candidate setCC\. This makes manipulation more costly and, when combined with external verification queries, more detectable\. Nonetheless,respiralso has inherent limitations\.

First, because the candidate setCCis known to both the platform and the auditor, the protocol does not prevent all forms of manipulation\. A strategic platform can still attempt to modify its outputs overCCso as to satisfy the audited fairness criterion with high probability\. A stronger alternative would be to require a private\-inference API, for instance based on verifiable homomorphic encryption or on hybrid cryptographic protocols, allowing the auditor to evaluate the commited model on private inputs without revealing the audited queries to the platform\. Conceptually, this would remove the need for an explicit shared candidate set, since the auditor’s query domain would no longer have to be enumerated in advance\. In practice, however, such a requirement remains restrictive\. Encrypted inference typically incurs substantial computational and communication overhead, and often requires model\-specific adaptations such as polynomial approximations, quantization, or hybrid protocols for non\-linear operations\(giladbachrach2016cryptonets;brutzkus2019lola;juvekar2018gazelle;mishra2020delphi;gong2024practical\), not to mention the verification step which introduces additional overhead\. Therefore, we view the use of a fixed candidate set as a pragmatic compromise between limiting the platform’s computational burden, ensuring deployment feasibility, and preserving audit usefulness\.

Second, manipulation detectability could be further enhanced by using an iterative protocol, in which the auditor progressively requires the platform to label the candidate setCC, in an order designed to trigger its worst\-case manipulation bounds\. For instance, the auditor could first require the platform to label the smallest protected group, thereby constraining the platform’s subsequent manipulation strategy and potentially forcing its final flips to be performed on the largest subgroup, resulting in more changes and higher detectability\. This would prevent the platform from reaching its lower\-cost manipulation bounds, making manipulation more difficult in practice\. However, such an extension would need to be designed carefully to preserve the non\-adaptivity property ofrespir; otherwise, the iterative structure itself could reveal information that the platform may exploit strategically\.

### 6\.3Conclusion

Overall,respiris a step toward manipulation\-resistant audits combining cryptographic query hiding with probabilistic guarantees\. We hope this work will motivate further research at the intersection of auditing, cryptography and trustworthy machine learning, and inform the design of regulatory audits robust to adversarial environments\.

Several directions remain open\. A first avenue is to extend the analysis beyond demographic parity to separation\- and sufficiency\-based criteria, as well as to settings with continuous outputs or multi\-class protected attributes\. A second direction is to study candidate\-set design in greater depth, including how to construct representative candidate sets under limited data access, how to allocate audit budgets across groups to mitigate imbalance, and how to choose the confidence parameter to balance robustness and audit cost\. Finally, from a systems perspective, deployingrespirin real auditing pipelines calls for exploring the performance trade\-offs of different PIR instantiations, robust engineering under rate limits and latency constraints and protocol mechanisms for logging and accountability that remain compatible with query privacy\.

## Acknowledgments

This research was enabled in part by funding from the SCALE\-AI Chair in Data\-Driven Supply Chains as well as by the*Fonds de recherche du Québec*–*Nature et technologies \(FRQNT\)*through a Team Research Project*\(327090\)*\. Sébastien Gambs is supported by the Canada Research Chair program \(CRC on Privacy\-preserving and Ethical Analysis of Big Data\) and a Discovery Grant from NSERC\. The authors would like to thank the anonymous reviewers for their valuable suggestions\.

## References

## Appendix AInteractions during the PIR

Figure[3](https://arxiv.org/html/2608.04365#A1.F3)provides a detailed description of the interaction during the PIR between the auditor and the provider using VeriSimplePIR\(verisimplepir24\)\.

AuditorProviderRequest an auditOffline Commitment𝐃∈ℤpℓ×μ\\mathbf\{D\}\\in\\mathbb\{Z\}\_\{p\}^\{\\ell\\times\\mu\}Uniformly sampleA∈ℤqμ×nA\\in\\mathbb\{Z\}\_\{q\}^\{\\mu\\times n\}H←𝐃⋅AH\\leftarrow\\mathbf\{D\}\\cdot AC←𝖧𝖺𝗌𝗁​\(A,H\)C\\leftarrow\\mathsf\{Hash\}\(A,H\)←A,H,Z\\xleftarrow\{\\qquad A,H,Z\\qquad\}Z←C⋅𝐃Z\\leftarrow C\\cdot\\mathbf\{D\}C←𝖧𝖺𝗌𝗁​\(A,H\)C\\leftarrow\\mathsf\{Hash\}\(A,H\)ReturnFailif‖Z‖∞\>p⋅ℓ\|\|Z\|\|\_\{\\infty\}\>p\\cdot\\ellorZ​A≠C​HZA\\neq CHQueryChoose an indexi=\(ir,ic\)∈ℤℓ×ℤμi=\(i\_\{r\},i\_\{c\}\)\\in\\mathbb\{Z\}\_\{\\ell\}\\times\\mathbb\{Z\}\_\{\\mu\}bic←𝖮𝗇𝖾𝖧𝗈𝗍​\(ic\)b\_\{i\_\{c\}\}\\leftarrow\\mathsf\{OneHot\}\(i\_\{c\}\)⊳\\trianglerightRegev’s Encryption using the generated A during the commitmentSample a uniform secrets∈ℤqns\\in\\mathbb\{Z\}\_\{q\}^\{n\}Sample an error vectore∈χμe\\in\\chi^\{\\mu\}⟦bic⟧=As\+e\+⌊qp⌋⋅bic\\llbracket b\_\{i\_\{c\}\}\\rrbracket=As\+e\+\\lfloor\\frac\{q\}\{p\}\\rfloor\\cdot b\_\{i\_\{c\}\}→⟦bic⟧\\xrightarrow\{\\qquad\\llbracket b\_\{i\_\{c\}\}\\rrbracket\\qquad\}Answerv←𝐃×⟦bic⟧v\\leftarrow\\mathbf\{D\}\\times\\llbracket b\_\{i\_\{c\}\}\\rrbracket←⟦r⟧\\xleftarrow\{\\qquad\\llbracket r\\rrbracket\\qquad\}Recoverr~←v​\[ir\]−⟨H​\[ir\],s⟩\\tilde\{r\}\\leftarrow v\[i\_\{r\}\]\-\\langle H\[i\_\{r\}\],s\\rangler←⌊p⋅r~q⌉r\\leftarrow\\lfloor\\frac\{p\\cdot\\tilde\{r\}\}\{q\}\\rceilFigure 3:The interaction between the auditor and the provider based on the SimplePIR protocol\(simplepir23\)and using the commitment to the database from VeriSimplePIR\(verisimplepir24\)\. More details can be found in\(verisimplepir24\)\(Construction 5\.1\) to verify the integrity of the queries\.
## Appendix BProof of Theorem[2](https://arxiv.org/html/2608.04365#Thmtheorem2)

###### Proof\.

Fix a realization of\(n0,n1\)\(n\_\{0\},n\_\{1\}\)and letnmin:=min⁡\(n0,n1\)n\_\{\\min\}:=\\min\(n\_\{0\},n\_\{1\}\)\. Recall thatdC=p1,C−p0,Cd\_\{C\}=p\_\{1,C\}\-p\_\{0,C\}anddS=p1,S−p0,Sd\_\{S\}=p\_\{1,S\}\-p\_\{0,S\}, in whichpa,Cp\_\{a,C\}\(resp\.pa,Sp\_\{a,S\}\) denotes the protected group\-aapositive prediction rate onCC\(resp\. onSS\)\.

Conditioning onnan\_\{a\}, the quantitypa,Sp\_\{a,S\}is the average ofnan\_\{a\}binary values in\[0,1\]\[0,1\]obtained by samplingnan\_\{a\}elements uniformly without replacement from theNaN\_\{a\}elements ofCCin groupaa\. For i\.i\.d\. sampling with replacement, Hoeffding’s inequality for bounded random variables yields, for anyt\>0t\>0,

Pr⁡\(\|pa,S−pa,C\|≥t\|na\)≤2​exp⁡\(−2​na​t2\)\.\\Pr\\\!\\left\(\\left\|p\_\{a,S\}\-p\_\{a,C\}\\right\|\\geq t\\,\\middle\|\\,n\_\{a\}\\right\)\\;\\leq\\;2\\exp\(\-2n\_\{a\}t^\{2\}\)\.The same exponential bound remains valid under uniform sampling without replacement\(hoeffding1963\), so we use it here\.

Using the decomposition

dS−dC=\(p1,S−p1,C\)−\(p0,S−p0,C\),d\_\{S\}\-d\_\{C\}=\(p\_\{1,S\}\-p\_\{1,C\}\)\-\(p\_\{0,S\}\-p\_\{0,C\}\),and the triangle inequality,

\|dS−dC\|≤\|p1,S−p1,C\|\+\|p0,S−p0,C\|,\|d\_\{S\}\-d\_\{C\}\|\\leq\|p\_\{1,S\}\-p\_\{1,C\}\|\+\|p\_\{0,S\}\-p\_\{0,C\}\|,we obtain the event inclusion \(as at least one of the two terms must be greater thanγ/2\\gamma/2for their sum to be greater thanγ\\gamma\):

\{\|dS−dC\|≥γ\}⊆\\displaystyle\\\{\|d\_\{S\}\-d\_\{C\}\|\\geq\\gamma\\\}\\subseteq\{\|p1,S−p1,C\|≥γ/2\}\\displaystyle\\\{\|p\_\{1,S\}\-p\_\{1,C\}\|\\geq\\gamma/2\\\}∪\{\|p0,S−p0,C\|≥γ/2\}\.\\displaystyle\\cup\\\{\|p\_\{0,S\}\-p\_\{0,C\}\|\\geq\\gamma/2\\\}\.Applying the union bound and the concentration inequality above gives

Pr⁡\(\|dS−dC\|≥γ∣n0,n1\)\\displaystyle\\Pr\(\|d\_\{S\}\-d\_\{C\}\|\\geq\\gamma\\mid n\_\{0\},n\_\{1\}\)≤Pr⁡\(\|p1,S−p1,C\|≥γ/2∣n1\)\\displaystyle\\leq\\Pr\\\!\\left\(\|p\_\{1,S\}\-p\_\{1,C\}\|\\geq\\gamma/2\\mid n\_\{1\}\\right\)\+Pr⁡\(\|p0,S−p0,C\|≥γ/2∣n0\)\\displaystyle\\quad\+\\Pr\\\!\\left\(\|p\_\{0,S\}\-p\_\{0,C\}\|\\geq\\gamma/2\\mid n\_\{0\}\\right\)≤2​exp⁡\(−2​n1​\(γ/2\)2\)\\displaystyle\\leq 2\\exp\\\!\\left\(\-2n\_\{1\}\(\\gamma/2\)^\{2\}\\right\)\+2​exp⁡\(−2​n0​\(γ/2\)2\)\\displaystyle\\quad\+2\\exp\\\!\\left\(\-2n\_\{0\}\(\\gamma/2\)^\{2\}\\right\)≤4​exp⁡\(−γ22​nmin\)\.\\displaystyle\\leq 4\\exp\\\!\\left\(\-\\frac\{\\gamma^\{2\}\}\{2\}\\,n\_\{\\min\}\\right\)\.
Setγ:=2​ln⁡\(4/δ\)nmin\\gamma:=\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}\}\}\. Then

Pr⁡\(\|dS−dC\|≥γ∣n0,n1\)\\displaystyle\\Pr\(\|d\_\{S\}\-d\_\{C\}\|\\geq\\gamma\\mid n\_\{0\},n\_\{1\}\)≤4​exp⁡\(−ln⁡\(4/δ\)\)\\displaystyle\\leq 4\\exp\(\-\\ln\(4/\\delta\)\)=δ\.\\displaystyle=\\delta\.Now assume\|dC\|≤ε−γ\|d\_\{C\}\|\\leq\\varepsilon\-\\gamma\. Whenever\|dS−dC\|<γ\|d\_\{S\}\-d\_\{C\}\|<\\gamma, the triangle inequality yields

\|dS\|≤\|dC\|\+\|dS−dC\|<\(ε−γ\)\+γ=ε\.\|d\_\{S\}\|\\leq\|d\_\{C\}\|\+\|d\_\{S\}\-d\_\{C\}\|<\(\\varepsilon\-\\gamma\)\+\\gamma=\\varepsilon\.Hence\{\|dS\|\>ε\}⊆\{\|dS−dC\|≥γ\}\\\{\|d\_\{S\}\|\>\\varepsilon\\\}\\subseteq\\\{\|d\_\{S\}\-d\_\{C\}\|\\geq\\gamma\\\}and therefore

Pr⁡\(\|dS\|\>ε∣n0,n1\)≤δ,\\Pr\(\|d\_\{S\}\|\>\\varepsilon\\mid n\_\{0\},n\_\{1\}\)\\leq\\delta,which is equivalent toPr⁡\(\|dS\|≤ε∣n0,n1\)≥1−δ\\Pr\(\|d\_\{S\}\|\\leq\\varepsilon\\mid n\_\{0\},n\_\{1\}\)\\geq 1\-\\delta\. ∎

We note that, since sampling occurs without replacement from the finite candidate setCC, these bounds can actually be tightened through a finite\-population correction\. For completeness, we detail this refinement in Appendix[D](https://arxiv.org/html/2608.04365#A4), while retaining the ordinary Hoeffding bound in the main text for simplicity and as a conservative worst\-case bound\.

## Appendix CIllustrative Extension with Equal Opportunity

The analysis of Theorem[1](https://arxiv.org/html/2608.04365#Thmtheorem1)relies on two properties of demographic parity: the audited metric is a difference between two empirical rates and the effect of a single output flip on this difference can be bounded\. The same argument applies to other group fairness metrics after identifying the appropriate conditional populations and single\-flip sensitivity\. We illustrate this adaptation for the equal opportunity metric\(hardt2016equality\), which quantifies differences in true positive rates across protected groups\.

Assume that eachx∈Cx\\in Cis associated with a binary ground\-truth labelY​\(x\)∈\{0,1\}Y\(x\)\\in\\\{0,1\\\}\. For each protected groupa∈\{0,1\}a\\in\\\{0,1\\\}, define

Ca\+:=\{x∈C:A​\(x\)=a,Y​\(x\)=1\},Na\+:=\|Ca\+\|,C\_\{a\}^\{\+\}:=\\\{x\\in C:A\(x\)=a,\\ Y\(x\)=1\\\},\\qquad N\_\{a\}^\{\+\}:=\|C\_\{a\}^\{\+\}\|,and similarly

Sa\+:=\{x∈S:A​\(x\)=a,Y​\(x\)=1\},na\+:=\|Sa\+\|\.S\_\{a\}^\{\+\}:=\\\{x\\in S:A\(x\)=a,\\ Y\(x\)=1\\\},\\qquad n\_\{a\}^\{\+\}:=\|S\_\{a\}^\{\+\}\|\.The true positive rate of groupaaonCCis

pa,CEO:=1Na\+​∑x∈Ca\+h​\(x\),p\_\{a,C\}^\{\\mathrm\{EO\}\}:=\\frac\{1\}\{N\_\{a\}^\{\+\}\}\\sum\_\{x\\in C\_\{a\}^\{\+\}\}h\(x\),and the equal opportunity gap onCCis

dCEO:=p1,CEO−p0,CEO\.d\_\{C\}^\{\\mathrm\{EO\}\}:=p\_\{1,C\}^\{\\mathrm\{EO\}\}\-p\_\{0,C\}^\{\\mathrm\{EO\}\}\.The quantitiespa,SEOp\_\{a,S\}^\{\\mathrm\{EO\}\}anddSEOd\_\{S\}^\{\\mathrm\{EO\}\}are defined analogously onSS\. As in Section[3\.1](https://arxiv.org/html/2608.04365#S3.SS1), we omit the classifierhhin notation since it is clear from context\. Finally, let

Nmin\+:=min\(N0\+,N1\+\),nmin\+:=min\(n0\+,n1\+\)\.N\_\{\\min\}^\{\+\}:=\\min\(N\_\{0\}^\{\+\},N\_\{1\}^\{\+\}\),\\qquad n\_\{\\min\}^\{\+\}:=\\min\(n\_\{0\}^\{\+\},n\_\{1\}^\{\+\}\)\.
###### Theorem 3\(respirmanipulation bound for equal opportunity\)\.

LetC⊂𝒳C\\subset\\mathcal\{X\}be the candidate set and letS⊂CS\\subset Cbe sampled uniformly at random without replacement\. Assume thatNa\+,na\+\>0N\_\{a\}^\{\+\},n\_\{a\}^\{\+\}\>0for eacha∈\{0,1\}a\\in\\\{0,1\\\}\. LetdC,trueEOd\_\{C,\\text\{true\}\}^\{\\mathrm\{EO\}\}denote the equal opportunity gap of the provider’s model onCCbefore manipulation, and letε\\varepsilonbe the audit threshold\.

Forδ∈\(0,1/2\]\\delta\\in\(0,1/2\], define

γEO​\(δ\):=2​ln⁡\(4/δ\)nmin\+\.\\gamma\_\{\\mathrm\{EO\}\}\(\\delta\):=\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}^\{\+\}\}\}\.If the post\-manipulation candidate\-set gap satisfies

\|dCEO\|≤ε−γEO​\(δ\),\|d\_\{C\}^\{\\mathrm\{EO\}\}\|\\leq\\varepsilon\-\\gamma\_\{\\mathrm\{EO\}\}\(\\delta\),then

Pr⁡\(\|dSEO\|≤ε\|n0\+,n1\+\)≥1−δ\.\\Pr\\\!\\left\(\|d\_\{S\}^\{\\mathrm\{EO\}\}\|\\leq\\varepsilon\\,\\middle\|\\,n\_\{0\}^\{\+\},n\_\{1\}^\{\+\}\\right\)\\geq 1\-\\delta\.
Consequently, assuming that the original \(non\-manipulated\) model would fail the equal opportunity audit,*i\.e\.*,

\|dC,trueEO\|\>ε,\|d\_\{C,\\text\{true\}\}^\{\\mathrm\{EO\}\}\|\>\\varepsilon,any set of output flips that enforces this sufficient condition must contain at least

mEO≥⌈\(\|dC,trueEO\|−ε\+γEO​\(δ\)\)​Nmin\+⌉m\_\{\\mathrm\{EO\}\}\\geq\\left\\lceil\\left\(\|d\_\{C,\\text\{true\}\}^\{\\mathrm\{EO\}\}\|\-\\varepsilon\+\\gamma\_\{\\mathrm\{EO\}\}\(\\delta\)\\right\)N\_\{\\min\}^\{\+\}\\right\\rceilflipped predictions on examples withY​\(x\)=1Y\(x\)=1\.

###### Proof\.

Fix a realization of\(n0\+,n1\+\)\(n\_\{0\}^\{\+\},n\_\{1\}^\{\+\}\)\. Conditional onna\+n\_\{a\}^\{\+\}, the setSa\+S\_\{a\}^\{\+\}is a uniformly random subset of sizena\+n\_\{a\}^\{\+\}ofCa\+C\_\{a\}^\{\+\}\. Thus,pa,SEOp\_\{a,S\}^\{\\mathrm\{EO\}\}is the average ofna\+n\_\{a\}^\{\+\}binary predictions sampled uniformly without replacement from theNa\+N\_\{a\}^\{\+\}predictions inCa\+C\_\{a\}^\{\+\}\.

Hoeffding’s inequality for sampling without replacement gives, for everyt\>0t\>0,

Pr⁡\(\|pa,SEO−pa,CEO\|≥t\|na\+\)≤2​exp⁡\(−2​na\+​t2\)\.\\Pr\\\!\\left\(\\left\|p\_\{a,S\}^\{\\mathrm\{EO\}\}\-p\_\{a,C\}^\{\\mathrm\{EO\}\}\\right\|\\geq t\\,\\middle\|\\,n\_\{a\}^\{\+\}\\right\)\\leq 2\\exp\(\-2n\_\{a\}^\{\+\}t^\{2\}\)\.Using

dSEO−dCEO=\(p1,SEO−p1,CEO\)−\(p0,SEO−p0,CEO\),d\_\{S\}^\{\\mathrm\{EO\}\}\-d\_\{C\}^\{\\mathrm\{EO\}\}=\\left\(p\_\{1,S\}^\{\\mathrm\{EO\}\}\-p\_\{1,C\}^\{\\mathrm\{EO\}\}\\right\)\-\\left\(p\_\{0,S\}^\{\\mathrm\{EO\}\}\-p\_\{0,C\}^\{\\mathrm\{EO\}\}\\right\),the triangle inequality and a union bound yield

Pr⁡\(\|dSEO−dCEO\|≥γ\|n0\+,n1\+\)≤4​exp⁡\(−γ22​nmin\+\)\.\\Pr\\\!\\left\(\\left\|d\_\{S\}^\{\\mathrm\{EO\}\}\-d\_\{C\}^\{\\mathrm\{EO\}\}\\right\|\\geq\\gamma\\,\\middle\|\\,n\_\{0\}^\{\+\},n\_\{1\}^\{\+\}\\right\)\\leq 4\\exp\\left\(\-\\frac\{\\gamma^\{2\}\}\{2\}n\_\{\\min\}^\{\+\}\\right\)\.Setting

γ=γEO​\(δ\)=2​ln⁡\(4/δ\)nmin\+\\gamma=\\gamma\_\{\\mathrm\{EO\}\}\(\\delta\)=\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}^\{\+\}\}\}makes the right\-hand side equal toδ\\delta\. Hence, if

\|dCEO\|≤ε−γEO​\(δ\),\|d\_\{C\}^\{\\mathrm\{EO\}\}\|\\leq\\varepsilon\-\\gamma\_\{\\mathrm\{EO\}\}\(\\delta\),then\|dSEO\|≤ε\|d\_\{S\}^\{\\mathrm\{EO\}\}\|\\leq\\varepsilonwith conditional probability at least1−δ1\-\\delta\.

We now bound the number of output flips required to enforce this condition\. Assume without loss of generality thatdC,trueEO\>0d\_\{C,\\text\{true\}\}^\{\\mathrm\{EO\}\}\>0\. Flipping a prediction for an example inC1\+C\_\{1\}^\{\+\}from11to0decreases the equal opportunity gap by1/N1\+1/N\_\{1\}^\{\+\}\. Similarly, flipping a prediction for an example inC0\+C\_\{0\}^\{\+\}from0to11decreases the gap by1/N0\+1/N\_\{0\}^\{\+\}\. In contrast, flips on examples withY​\(x\)=0Y\(x\)=0do not affect equal opportunity\. Therefore, a single output flip can decrease the gap by at most

max⁡\(1N0\+,1N1\+\)=1Nmin\+\.\\max\\left\(\\frac\{1\}\{N\_\{0\}^\{\+\}\},\\frac\{1\}\{N\_\{1\}^\{\+\}\}\\right\)=\\frac\{1\}\{N\_\{\\min\}^\{\+\}\}\.Reducing the initial gap to at mostε−γEO​\(δ\)\\varepsilon\-\\gamma\_\{\\mathrm\{EO\}\}\(\\delta\)thus requires at least

⌈\(\|dC,trueEO\|−ε\+γEO​\(δ\)\)​Nmin\+⌉\\left\\lceil\\left\(\|d\_\{C,\\text\{true\}\}^\{\\mathrm\{EO\}\}\|\-\\varepsilon\+\\gamma\_\{\\mathrm\{EO\}\}\(\\delta\)\\right\)N\_\{\\min\}^\{\+\}\\right\\rceiloutput flips, which proves the result\. ∎

This example illustrates the general adaptation of Theorem 1\. For a fairness metric expressed as a difference between conditional rates, the relevant group sizes are those of the conditioning strata while the manipulation bound is determined by the maximum change in the metric caused by a single output flip\. Metrics involving several simultaneous rate constraints, such as equalized odds, can be handled similarly by applying concentration bounds to each rate and combining them through an appropriate union bound\.

## Appendix DRefining the Bound through a Finite\-Population Correction

Theorems[1](https://arxiv.org/html/2608.04365#Thmtheorem1)and[2](https://arxiv.org/html/2608.04365#Thmtheorem2)apply a Hoeffding bound that is valid under sampling without replacement but does not exploit the finite population sizesN0N\_\{0\}andN1N\_\{1\}\. As a complementary result, we apply the finite\-population refinement of the Hoeffding–Serfling inequality proposed bybardenet2015concentration, which builds on and slightly improves the original bound ofserfling1974\.

For eacha∈\{0,1\}a\\in\\\{0,1\\\}, define

ρa:=\{1−na−1Na,if​na≤Na/2,\(1−naNa\)​\(1\+1na\),if​na\>Na/2,\\rho\_\{a\}:=\\begin\{cases\}1\-\\dfrac\{n\_\{a\}\-1\}\{N\_\{a\}\},&\\text\{if \}n\_\{a\}\\leq N\_\{a\}/2,\\\\\[6\.0pt\] \\left\(1\-\\dfrac\{n\_\{a\}\}\{N\_\{a\}\}\\right\)\\left\(1\+\\dfrac\{1\}\{n\_\{a\}\}\\right\),&\\text\{if \}n\_\{a\}\>N\_\{a\}/2,\\end\{cases\}and

γFPC​\(δ\):=ρ1​ln⁡\(4/δ\)2​n1\+ρ0​ln⁡\(4/δ\)2​n0\.\\gamma\_\{\\mathrm\{FPC\}\}\(\\delta\):=\\sqrt\{\\frac\{\\rho\_\{1\}\\ln\(4/\\delta\)\}\{2n\_\{1\}\}\}\+\\sqrt\{\\frac\{\\rho\_\{0\}\\ln\(4/\\delta\)\}\{2n\_\{0\}\}\}\.
###### Theorem 4\(Finite\-population refinement of Theorem 1\)\.

Consider the setting of Theorem 1 and fixδ∈\(0,1\)\\delta\\in\(0,1\)\. If the post\-manipulation candidate\-set gap satisfies

\|dC\|≤ε−γFPC​\(δ\),\|d\_\{C\}\|\\leq\\varepsilon\-\\gamma\_\{\\mathrm\{FPC\}\}\(\\delta\),then

Pr⁡\(\|dS\|≤ε\|n0,n1\)≥1−δ\.\\Pr\\\!\\left\(\|d\_\{S\}\|\\leq\\varepsilon\\,\\middle\|\\,n\_\{0\},n\_\{1\}\\right\)\\geq 1\-\\delta\.Moreover, enforcing this sufficient condition from an initial gapdC,trued\_\{C,\\text\{true\}\}requires at least

mFPC≥⌈\(\|dC,true\|−ε\+γFPC​\(δ\)\)​Nmin⌉m\_\{\\mathrm\{FPC\}\}\\geq\\left\\lceil\\left\(\|d\_\{C,\\text\{true\}\}\|\-\\varepsilon\+\\gamma\_\{\\mathrm\{FPC\}\}\(\\delta\)\\right\)N\_\{\\min\}\\right\\rceiloutput flips, whereNmin:=min⁡\(N0,N1\)N\_\{\\min\}:=\\min\(N\_\{0\},N\_\{1\}\)\.

###### Proof\.

Conditioning onnan\_\{a\}, applybardenet2015concentrationto the finite population ofNaN\_\{a\}binary predictions in groupaa\. In their notation, the population mean ispa,Cp\_\{a,C\}, the sample mean ispa,Sp\_\{a,S\}, the sample size isnan\_\{a\}, and the range satisfiesb−a=1b\-a=1\. Thus, with probability at least1−δ1\-\\delta,

pa,S−pa,C≤ρa​log⁡\(1/δ\)2​na\.p\_\{a,S\}\-p\_\{a,C\}\\leq\\sqrt\{\\frac\{\\rho\_\{a\}\\log\(1/\\delta\)\}\{2n\_\{a\}\}\}\.Equivalently, settingδ=exp⁡\(−2​na​t2/ρa\)\\delta=\\exp\(\-2n\_\{a\}t^\{2\}/\\rho\_\{a\}\)gives, for everyt\>0t\>0,

Pr⁡\(pa,S−pa,C\>t\|na\)≤exp⁡\(−2​na​t2ρa\)\.\\Pr\\\!\\left\(p\_\{a,S\}\-p\_\{a,C\}\>t\\,\\middle\|\\,n\_\{a\}\\right\)\\leq\\exp\\\!\\left\(\-\\frac\{2n\_\{a\}t^\{2\}\}\{\\rho\_\{a\}\}\\right\)\.The same bound applies to the opposite deviationpa,C−pa,Sp\_\{a,C\}\-p\_\{a,S\}\. A union bound over the two tails therefore yields

Pr⁡\(\|pa,S−pa,C\|≥t\|na\)≤2​exp⁡\(−2​na​t2ρa\)\.\\displaystyle\\Pr\\\!\\left\(\|p\_\{a,S\}\-p\_\{a,C\}\|\\geq t\\,\\middle\|\\,n\_\{a\}\\right\)\\leq 2\\exp\\\!\\left\(\-\\frac\{2n\_\{a\}t^\{2\}\}\{\\rho\_\{a\}\}\\right\)\.\(5\)
For eacha∈\{0,1\}a\\in\\\{0,1\\\}, set

ta:=ρa​ln⁡\(4/δ\)2​na\.t\_\{a\}:=\\sqrt\{\\frac\{\\rho\_\{a\}\\ln\(4/\\delta\)\}\{2n\_\{a\}\}\}\.Substitutingt=tat=t\_\{a\}into Equation \([5](https://arxiv.org/html/2608.04365#A4.E5)\) gives

Pr⁡\(\|pa,S−pa,C\|\>ta\|na\)≤2​exp⁡\(−ln⁡\(4/δ\)\)=δ2\.\\Pr\\\!\\left\(\|p\_\{a,S\}\-p\_\{a,C\}\|\>t\_\{a\}\\,\\middle\|\\,n\_\{a\}\\right\)\\leq 2\\exp\\\!\\left\(\-\\ln\(4/\\delta\)\\right\)=\\frac\{\\delta\}\{2\}\.A union bound over the two protected groups therefore shows that, with probability at least1−δ1\-\\delta,

\|p1,S−p1,C\|≤t1and\|p0,S−p0,C\|≤t0\.\|p\_\{1,S\}\-p\_\{1,C\}\|\\leq t\_\{1\}\\qquad\\text\{and\}\\qquad\|p\_\{0,S\}\-p\_\{0,C\}\|\\leq t\_\{0\}\.On this event,

\|dS−dC\|\\displaystyle\|d\_\{S\}\-d\_\{C\}\|=\|\(p1,S−p1,C\)−\(p0,S−p0,C\)\|\\displaystyle=\\left\|\(p\_\{1,S\}\-p\_\{1,C\}\)\-\(p\_\{0,S\}\-p\_\{0,C\}\)\\right\|≤\|p1,S−p1,C\|\+\|p0,S−p0,C\|\\displaystyle\\leq\|p\_\{1,S\}\-p\_\{1,C\}\|\+\|p\_\{0,S\}\-p\_\{0,C\}\|≤t1\+t0=γFPC​\(δ\)\.\\displaystyle\\leq t\_\{1\}\+t\_\{0\}=\\gamma\_\{\\mathrm\{FPC\}\}\(\\delta\)\.Consequently, if

\|dC\|≤ε−γFPC​\(δ\),\|d\_\{C\}\|\\leq\\varepsilon\-\\gamma\_\{\\mathrm\{FPC\}\}\(\\delta\),then

\|dS\|≤\|dC\|\+\|dS−dC\|≤ε\|d\_\{S\}\|\\leq\|d\_\{C\}\|\+\|d\_\{S\}\-d\_\{C\}\|\\leq\\varepsilonwith probability at least1−δ1\-\\delta\.

Finally, a single output flip changesdCd\_\{C\}by at most

max⁡\(1N0,1N1\)=1Nmin\.\\max\\left\(\\frac\{1\}\{N\_\{0\}\},\\frac\{1\}\{N\_\{1\}\}\\right\)=\\frac\{1\}\{N\_\{\\min\}\}\.Enforcing the sufficient condition above therefore requires reducing the candidate\-set gap by at least

\|dC,true\|−ε\+γFPC​\(δ\)\.\|d\_\{C,\\text\{true\}\}\|\-\\varepsilon\+\\gamma\_\{\\mathrm\{FPC\}\}\(\\delta\)\.It consequently requires at least

⌈\(\|dC,true\|−ε\+γFPC​\(δ\)\)​Nmin⌉\\left\\lceil\\left\(\|d\_\{C,\\text\{true\}\}\|\-\\varepsilon\+\\gamma\_\{\\mathrm\{FPC\}\}\(\\delta\)\\right\)N\_\{\\min\}\\right\\rceiloutput flips as claimed\. ∎

Sinceρa≤1\\rho\_\{a\}\\leq 1andna≥nminn\_\{a\}\\geq n\_\{\\min\}for eacha∈\{0,1\}a\\in\\\{0,1\\\},

γFPC​\(δ\)\\displaystyle\\gamma\_\{\\mathrm\{FPC\}\}\(\\delta\)=ρ1​ln⁡\(4/δ\)2​n1\+ρ0​ln⁡\(4/δ\)2​n0\\displaystyle=\\sqrt\{\\frac\{\\rho\_\{1\}\\ln\(4/\\delta\)\}\{2n\_\{1\}\}\}\+\\sqrt\{\\frac\{\\rho\_\{0\}\\ln\(4/\\delta\)\}\{2n\_\{0\}\}\}≤ln⁡\(4/δ\)2​n1\+ln⁡\(4/δ\)2​n0\\displaystyle\\leq\\sqrt\{\\frac\{\\ln\(4/\\delta\)\}\{2n\_\{1\}\}\}\+\\sqrt\{\\frac\{\\ln\(4/\\delta\)\}\{2n\_\{0\}\}\}≤2​ln⁡\(4/δ\)nmin\.\\displaystyle\\leq\\sqrt\{\\frac\{2\\ln\(4/\\delta\)\}\{n\_\{\\min\}\}\}\.The finite\-population correction thus yields a tighter concentration margin than the ordinary Hoeffding bound, particularly when a large fraction of either protected group is sampled\. This results in a less conservative sufficient threshold for the numbermFPCm\_\{\\mathrm\{FPC\}\}of output flips required for the platform to pass the audit with sufficiently high probability\.