Manipulation-Proof Oblivious Audits against Deceptive Model Providers

Manipulation-Proof Oblivious Audits against Deceptive Model Providers Augustin Godinot1 , Sofiane Azogagh2 , Julien Ferry3 , Sébastien Gambs4 1

INRIA Centre de l’Université de Rennes, France 2 EURECOM, Sophia Antipolis, France 3 CIRRELT & SCALE-AI Chair in Data-Driven Supply Chains, Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Canada 4 Université du Québec à Montréal, Canada augustin.godinot@inria.fr, sofiane.azogagh@eurecom.fr, julien.ferry@polymtl.ca, gambs.sebastien@uqam.ca

arXiv:2608.04365v1 [cs.LG] 5 Aug 2026

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

1

Introduction

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 (Chandrasekaran et al. 2021). A central pillar of this governance is algorithmic auditing, which allows independent evaluators to scrutinize model behavior (Metaxa et al. 2021; Costanza-Chock, Raji, and Buolamwini 2022). 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 (Birhane et al. 2024). While several mechanisms attempt to bridge this transparency gap—such as dedicated research APIs (Entrena-

Serrano et al. 2025), academic partnerships (Social Science One 2019) and legally mandated data access—they often face practical limitations and remain vulnerable to provider interference (Bourrée et al. 2023). 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 (Horwitz 2025). 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 (Fukuchi, Hara, and Maehara 2020; Garcia Bourrée et al. 2025). 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 (Garcia Bourrée et al. 2025), but a few modifications of the outputs on the audit set can have a dramatic impact on the audit conclusions (see Proposition 1). 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 Section 6.1 how it extends to other settings. Our main contributions are as follows: • We introduce R2 esPIR, an audit protocol designed to mitigate audit manipulations. The core idea is to hide the actual audit set S within a larger candidate set C, provably making manipulation harder for a deceptive provider. The only prerequisite for this protocol is that the audited provider must label a candidate set C larger than the actual audit set S. • We prove that R2 esPIR forces a deceptive provider to modify its answers on a substantially larger number of points in the candidate set C in order to fake the same level of demographic parity (Theorem 1). This results in an increased probability of manipulation detection by the auditor. • We characterize how large the candidate set C must be, relative to the audit set S, 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 Section 2 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 Section 3 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 Section 4 an oblivious auditing protocol based on PIR, which we call R2 esPIR. We then establish the protocol’s theoretical guarantees in terms of manipulation effort and detectability, and evaluate it experimentally in Section 5. Finally, we conclude in Section 6 with a discussion regarding our framework’s applicability, the main design principles for hidden-audit-set protocols, and directions for future work.

2 2.1

Background & Related Work

Audits and Manipulations

Audits and regulation. Independent audits are a key mechanism for holding model providers accountable and fostering healthier algorithmic ecosystems (Metaxa et al. 2021; Vecchione, Levy, and Barocas 2021; Costanza-Chock, Raji, and Buolamwini 2022). This view has been adopted by recent regulations: the EU AI Act (Reg 2024), DSA (Reg 2022b), DMA (Reg 2022a) 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 (Ribeiro 2024). In others, promised (or required) data access was repeatedly delayed (Social Science One 2019) or simply not provided (European Commission 2025). Finally, when data or models are eventually shared, they may contain errors that undermine published academic

work (Timberg 2021) or fail to reflect the reality experienced by users (Entrena-Serrano et al. 2025; Pearson et al. 2024). 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 (Fukuchi, Hara, and Maehara 2020). Model explanations can be fairwashed to conceal discriminatory behavior (Aı̈vodji et al. 2019; Anders et al. 2020; Shamsabadi et al. 2022; Fokkema, de Heide, and van Erven 2023). Model outputs themselves can be selectively altered to deceive blackbox auditors (Bourrée et al. 2023; Garcia Bourrée et al. 2025). And more broadly, fairness metrics are susceptible to gaming when providers can anticipate the evaluation procedure (Hutchinson et al. 2022; Thomas and Uminsky 2022).

2.2

Related 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. Yan and Zhang (2022) study active fairness auditing, where the auditor adaptively selects queries to efficiently estimate fairness violations. Yadav, Moshkovitz, and Chaudhuri (2024) provide a theoretical framework for auditing with explanations. Most closely related to our work, Garcia Bourrée et al. (2025) formally 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. Shamsabadi et al. (2023) propose zero-knowledge proofs of fair training for decision trees. Waiwitlikhit et al. (2024) design a protocol based on zero-knowledge proofs that enables trustless audits without revealing models or data. Franzese et al. (2025) introduce online fairness certificates via a scalable zero-knowledge proof protocol that verifies fairness with respect to data received during deployment. Pentyala et al. (2022) develop 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 (Park, Kim, and Lim 2022). While promising, these approaches require trust in the hardware manufacturer and physical deployment constraints, which limit their applicability in many regulatory contexts.

2.3

Private 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 (Chor et al. 1998). 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 (Olumofin and Goldberg 2011). Other approaches rely on trusted hardware (Smith and Safford 2001) but the most promising ones are homomorphic encryption schemes based on lattice problems such as Learning With Errors (LWE) (Melchor et al. 2016; Angel et al. 2018; Ali et al. 2021; Ahmad et al. 2021; Mughees, Chen, and Ren 2021; Menon and Wu 2022; Davidson, Pestana, and Celi 2023; Henzinger et al. 2023). 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 (Corrigan-Gibbs and Kogan 2020; Kogan and Corrigan-Gibbs 2021; Shi et al. 2021; Mughees, Chen, and Ren 2021; Corrigan-Gibbs, Henzinger, and Kogan 2022). 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 (Henzinger et al. 2023; Davidson, Pestana, and Celi 2023). A prominent example is SimplePIR (Henzinger et al. 2023), which relies on Regev’s LWE-based encryption scheme (Regev 2009). 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). Furthermore, De Castro and Lee (de Castro and Lee 2024) 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.

3

The 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.1

Black-Box Fairness Auditing

Let X be the input space, and let h : X → {0, 1} denote the provider’s (binary) prediction function. Each query x ∈ X is associated with a binary protected attribute A(x) ∈ {0, 1}, which partitions the population into two protected groups (those with A = 1 and those with A = 0). The demographic parity gap of h quantifies how differently h assigns 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 group A = 1 and the corresponding probability for individuals in group A = 0: dD (h) := PX∼D (h(X) = 1|A(X) = 1) − PX∼D (h(X) = 1|A(X) = 0) , in which D denotes the underlying data distribution. In practice, since D is typically unknown, this quantity is estimated on a finite sample set S ⊂ X . For a ∈ {0, 1}, let na = {x ∈ S : A(x) = a} and define the empirical positive prediction rate over protected group a as 1 X pa,S (h) := h(x). na x∈Sa

The demographic parity gap of h on S is then dS (h) := p1,S (h) − p0,S (h). When the classifier h is clear from the context, we omit it from the notation and simply write pa,S and dS . Given a tolerance ε ≥ 0, we say that h satisfies the demographic parity constraint on S if |dS | ≤ ε,

(1)

in which ε is a chosen tolerance threshold. The objective of the auditor is to verify whether Constraint (1) holds for a given audit set S. More precisely, if |dS | ≤ ε, the ML provider passes the test while otherwise, if |dS | > ε, the provider is flagged as unfair by the auditor. However, a key challenge is that the auditor often does not have access to the model h itself, nor to its training data, code or documentation. To estimate the demographic parity gap on an audit set S, the auditor must therefore resort to black-box access

and query h on a set of inputs S ⊂ X that they collect. The resulting predictions are then used to compute dS . This black-box audit procedure is described in Algorithm 1. In the next subsection, we show how this framework is vulnerable to provider manipulation.

3.2

Manipulating Black-box Audit

One important limitation of typical demographic parity audits conducted as described in Section 3.1 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 label h(x) that differs from the underlying model’s true output. To quantify how easy such manipulation is, Proposition 1 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). Let S ⊂ X be the audit set (with |S| = n), let dtrue denote the demographic parity gap of the provider’s model on S (in the absence of manipulation), let nmin = min(n0 , n1 ) be the size of the smallest protected group in S, and let ε be the audit threshold. Assuming the model would fail the audit, i.e., |dtrue | > ε, the minimum number mvanilla of predictions that the provider must flip in order to pass the audit satisfies
mvanilla ≥ ⌈ |dtrue | − ε nmin ⌉. (2) Proof. Assume without loss of generality that dtrue > 0. Flipping a prediction h(x) from 1 to 0 for an example with A(x) = 1 decreases p1,S , and hence the gap on S, by at most 1/n1 . Similarly, flipping a prediction from 0 to 1 for an example with A(x) = 0 increases p0,S and decreases the gap by at most 1/n0 . Since a single flip affects only one group rate, the gap can decrease by at most   1 1 1 max , = n0 n1 nmin per modification. Therefore, reducing the gap from dtrue to at most ε requires at least (dtrue − ε) nmin modifications, hence at least ⌈(dtrue − ε) nmin ⌉ since mvanilla is an integer. Proposition 1 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 of 0.01 (i.e., dtrue − ε = 0.01) with a balanced audit set of n = 400 queries, 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 of k queries (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 set S, we assume that the canaries are included in S by construction. Therefore, the canary effectiveness can be modeled through a single catch-all parameter q ∈ [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). Let n := |S| denote the size of the audit set, and let m denote 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 probability m/n, and the probability that manipulation is detected satisfies
k P(manipulation detected) = 1 − 1 − q m/n . (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 manipulations m and the size k of the verification set: small k provides limited guarantees when only a few outputs are modified, whereas detection quickly becomes likely as either m or k increases. While increasing the number of canaries k is 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 number m of output modifications, which increases the cost of manipulation and its detectability.

4 4.1

Oblivious Auditing

R2 esPIR Protocol

Based on the observation that hiding unfairness over a known finite set is easily achieved, we propose a new audit protocol coined Robust Research audit APIs enabled by Private Information Retrieval (R2 esPIR). To mitigate audit manipulations, R2 esPIR forces the provider to find a strategy to optimize its manipulations on a significantly larger candidate set C rather than on the particular audit set S drawn by the auditor. The cryptographic primitive that prevents the provider from knowing which sample is used in the audit is the PIR (cf. Section 2.3). The audit protocol consists of three steps, described in Algorithm 2: • Step 1 (Algorithm 2, algorithm 2). The provider and the auditor agree on a (large) candidate set C. 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 for C can 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 (Algorithm 2, algorithm 2) The auditor samples an audit set S ⊂ C among the candidate set and runs it

Algorithm 1: Black-Box audit procedure

Algorithm 2: The R2 esPIR audit procedure

Require: X , h 1: Auditor gathers or generate an audit dataset S ⊂ X

Require: X , h 1: Provider and auditor agree on a large candidate set C ⊂ X 2: Provider privately labels all examples in C, creating D = {(x, h(x)) : x ∈ C}

2: For each example x ∈ S, the auditor queries the provider for h(x) 3: The auditor computes the parity gap dS 4: if dS < ε then 5: return Pass 6: else 7: return Fail

3: Auditor interacts with D to retrieve outputs on an audit set S ⊂ D using the Private Information Retrieval (PIR) primitive 4: if dS < ε then 5: return Pass 6: else 7: return Fail

through the PIR mechanism. The PIR mechanism guarantees that 1) the provider cannot infer the exact audit queries used in S and 2) the auditor cannot use the interaction to gather more information about the output of h other than what is given by h(S). Thus, the PIR properties effectively exclude any manipulation during the interaction between the auditor and the provider at step 2. • Step 3 (Algorithm 2, algorithm 2) Using the answers of the provider h(S) gathered during the PIR phase, the auditor produces an estimate dS 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 ≤ ε) when it should not have passed (i.e., dtrue > ε). We further highlight the following design properties. First, the candidate set C is constructed to be representative of the (unknown) data distribution D. Consequently, when the audit set S ⊆ C is sampled uniformly at random and is sufficiently large, it is expected to closely reflect D. While S could be sampled from C in 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 predictiondependent design since the auditor sees features in C but not the model’s outputs, and (iii) enables a clean probabilistic derivation of manipulation lower bounds (Theorem 1). Moreover, planting a small number k of verification queries (canaries) into S does not materially affect this representativeness when k ≪ |S|. As a result, it is reasonable to require the provider to pass the fairness verification (i.e., to exhibit unfairness of at most ε) on S. Second, although the provider is required to label a potentially large candidate set C, the amount of information revealed to the auditor is the same as in the traditional blackbox auditing setup described in Section 3.1, since the sampled audit set S need 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 a PIR scheme 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 Section 4.3, we provide a probabilistic analysis showing that this substantially increases both the cost and detectability of manipulation.

4.2

VeriSimplePIR Applied to an Audit Set

Let S denote the audit set and h the provider’s prediction function. The primary advantage of using a PIR protocol for auditing, as opposed to sending an encrypted version of the audit set S, lies in its efficiency as PIR is considerably faster than evaluating the model on S via homomorphic encryption. For example, if h is a neural network, running x ∈ S through h with 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 per x ∈ S. While a detailed description of the interaction during the PIR between the auditor and the provider is provided in Figure 3 in Appendix A, 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 set S, the provider applies its prediction function h to label the samples, resulting in a database h(S). , These labels are then packed into a small matrix D ∈ Zℓ×µ p with the parameters ℓ, p, and µ specified 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 D. The protocol then proceeds through four main functions: Commitment, Query, Answer and Recovery. During the offline phase, the provider performs the Commitment function by generating a cryptographic digest of the matrix D and a “hint” sent to the auditor to verify that 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 π that will later be used to verify that queries are performed on the committed database (see Construction 5.1 in (de Castro and Lee 2024) for more details about this proof). In the online phase, the auditor executes the Query function by selecting an index i = (ir , ic ) and sending an encryption of the one-hot encoding of ic to the provider using the Regev’s LWE encryption scheme (Regev 2009). The provider then performs the Answer function by com-

Table 1: Performance of VeriSimplePIR (de Castro and Lee 2024) on the online phase for different database sizes.

|dC | ≤ ε − γ.

Database size 128 KiB

128 MiB

1 GiB

4 GiB

8 GiB

Query size Answer size

0.375 KiB 7.812 KiB

13.16 KiB 276.6 KiB

37.76 KiB 816.8 KiB

77.85 KiB 1.644 MiB

110.1 KiB 2.325 MiB

Bandwidth usage

8.187 KiB

289.8 KiB

854.6 KiB

1.722 MiB

2.435 MiB

Query time Answer time Recovery time

0.5024 ms 0.0221 ms 0.574 ms

1.9587 ms 12.9588 ms 13.247 ms

5.3174 ms 69.1425 ms 42.825 ms

10.5765 ms 1447.86 ms 169.721 ms

15.3573 ms 2816.19 ms 807.623 ms

Total online time

1.09 ms

28.16 ms

117.28 ms

1628.15 ms

3639.17 ms

puting a matrix-vector multiplication between the D and the encrypted query. Finally, the auditor executes the Recovery function 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 π (see (de Castro and Lee 2024) for more details about this proof). To demonstrate how the protocol performs in practice, Table 1 reports timing measurements for the online phase (query, answer and recovery steps) along the bandwidth usage, across various sizes of h(S), in which h is a binary classifier. The given results are an average of 10 runs. When ∀y ∈ h(S), log2 (y) < log2 (p), multiple labels y can be encoded within a single element in Zp , so each entry in D can store several labels. As a result, the matrix D can be considerably smaller than the raw set of labels h(S). The results reported shows that the PIR protocol maintains practical efficiency even when handling large audit sets.

4.3

audit with probability at least 1 − δ (conditional on n0 , n1 ) is that the (post-manipulation) candidate-set gap satisfies

Manipulation Difficulty Analysis

We now establish probabilistic guarantees that hiding the audit set through R2 esPIR increases 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 (R2 esPIR audit manipulation). Let C ⊂ X be the candidate set (with |C| = N ) and let S ⊂ C be the audit set (with |S| = n), sampled uniformly at random without replacement from C. Let dC,true denote the demographic parity gap of the provider’s model on C (in the absence of manipulation), let nmin = min(n0 , n1 ) be the size of the smallest protected group in S, let Nmin = min(N0 , N1 ) be the size of the smallest protected group in C, and let ε be the audit threshold. For δ ∈ (0, 12 ], assuming the model would fail the audit, i.e., |dC,true | > ε, it suffices for the provider to flip at least    s 2 ln(4/δ)   Nmin  mR2 esPIR ≥    |dC,true | − ε + nmin   (4) predictions in C in order to pass the audit with probability at least 1 − δ. q Proof. Let γ := 2 ln(4/δ) nmin . By Theorem 2 (provided hereafter in Section 4.3), a sufficient condition for passing the

Thus, it suffices for the provider to modify predictions on C so as to reduce the initial gap |dC,true | down to at most ε − γ. We now bound the number of prediction flips required to achieve such a reduction on C. Assume without loss of generality that dC,true > 0 (otherwise apply the same argument to −dC,true ). Consider a single flip of one prediction on C. If the flipped example belongs to group A = 1, then p1,C changes by at most 1/N1 , hence dC changes by at most 1/N1 . If it belongs to group A = 0, then p0,C changes by at most 1/N0 , hence dC changes by at most 1/N0 . Therefore, a single flip can change dC by at most   1 1 1 max , = . N0 N1 Nmin To reach dC ≤ ε − γ, the provider must decrease the gap by at least dC,true − (ε − γ) = |dC,true | − ε + γ. Since each flip can reduce dC by at most 1/Nmin , it suffices to flip at least ⌈(|dC,true | − ε + γ) Nmin ⌉ predictions in C, as claimed. The manipulation resistance of R2 esPIR (Theorem 1) improves on that of a “vanilla” black-box audit (Proposition 1) in two complementary ways. First, R2 esPIR enforces a stricter effective target on the provider’s underlying disparity p because of the sampling uncertainty term 2 ln(4/δ)/nmin . This term materializes the fact that under uniform random sampling from C, audits sets S might exhibit unfairness dS slightly lower or higher due to the sampling process. Nevertheless, as long as they are representative of the underlying distribution (which is the case unless n = |S| is pathologically small), the provider’s model is expected to behave fairly on them as well. In other words, to ensure unfairness does not exceed ε on the sampled S with high probability, the provider must over-correct unfairness over the candidate set. Second, R2 esPIR increases the scale at which modifications must be performed. In a vanilla black-box audit, the provider may concentrate changes on the audited set S, so the best-case manipulation complexity scales with nmin . Under R2 esPIR, the provider must instead improve fairness across the entire candidate set C to pass for an unknown random S, implying a manipulation complexity that scales with Nmin , the size of the smaller protected group in C. Since typically Nmin ≫ nmin , 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 of k canaries (drawn from C and externally labeled), the probability of detection increases with the manipulated fraction m/N (according to (3), in which we substitute n by N to model the

102

Lower bound on # flips m

Lower bound on # flips m

Vanilla black-box audit (Prop. 3.1) R²esPIR audit (Thm. 4.1)

101

100

102

101 Vanilla black-box audit (Prop. 3.1) R²esPIR audit (Thm. 4.1)

100 0.00

0.02 0.04 0.06 0.08 Excess demographic parity gap to hide

0.10

0.00

0.02 0.04 0.06 0.08 Excess demographic parity gap to hide

0.10

(a) Lower bounds on the number of output flips m required to hide unfairness, for the unbalanced setting (left) and the balanced setting (right). Vanilla, k=1 Vanilla, k=3 Vanilla, k=5

0.4

0.5

R²esPIR, k=1 R²esPIR, k=3 R²esPIR, k=5

Detection probability (Eq. 3)

Detection probability (Eq. 3)

0.5

0.3 0.2 0.1 0.0

0.00

0.02 0.04 0.06 0.08 Excess demographic parity gap to hide

0.10

Vanilla, k=1 Vanilla, k=3 Vanilla, k=5

0.4

R²esPIR, k=1 R²esPIR, k=3 R²esPIR, k=5

0.3 0.2 0.1 0.0

0.00

0.02 0.04 0.06 0.08 Excess demographic parity gap to hide

0.10

(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 for R2 esPIR. We consider audit sets of size |S| = 400 and k ∈ {1, 3, 5} canaries, each detected with effectiveness probability q = 0.8. For R2 esPIR, we use a candidate set of size |C| = 2,000 and target passing probability 1 − δ = 0.95. We compare two protected group-composition regimes: an unbalanced regime where the minority group represents 10% of S (and of C for R2 esPIR) and a balanced regime with equal group sizes. The horizontal axis varies the amount of unfairness above the tolerance ε. probability that a canary’s output is modified). Moreover, when k is small compared to the audit size n, the auditor can include these canaries alongside the sampled audit set S without materially affecting the fairness estimation guarantees derived above.

mate dS . When S is sampled uniformly at random from C, dS concentrates around dC , with deviations controlled p at scale ln(1/δ)/nmin . Consequently, to pass with high probability, the provider must keep its candidate-set gap at least this far below the fairness threshold.

Illustrative Example The manipulation difficulty of both the vanilla black-box audit and our proposed R2 esPIR audit is illustrated in Figure 1 for a representative parameter setting. In particular, Figure 1a reports the number of output flips the provider must perform as a function of the amount of unfairness to hide, while Figure 1b shows the corresponding probability that the auditor detects such manipulation for different numbers of canaries included in the audit set S. 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 ε. In both regimes, R2 esPIR notably increases the required number of flips m and, consequently, the probability of manipulation detection.

Theorem 2 (R2 esPIR audit: Sufficient candidate set condition for high-probability passing). Let nmin := min(n0 , n1 ) and fix δ ∈ (0, 1). If the provider’s candidate set gap satisfies s 2 ln(4/δ) , |dC | ≤ ε − nmin

Intermediate Concentration Result Theorem 1 follows from Theorem 2, which formalizes the fact that the audit only observes the disparity through the sample-based esti-

then the provider passes the audit with probability at least 1 − δ: Pr(|dS | ≤ ε | n0 , n1 ) ≥ 1 − δ. Proof. Conditioning on (n0 , n1 ), we apply finite-population Hoeffding/Serfling bounds (Hoeffding 1963; Serfling 1974) to each group rate pa,S , and then use the triangle inequality and a union bound to obtain  2  γ Pr(|dS − dC | ≥ γ | n0 , n1 ) ≤ 4 exp − nmin . 2

CCD marriage COMPAS race

5

Experimental Evaluation

To illustrate and empirically validate our results, we selected three datasets spanning tabular and text domains: Default of Credit Card Clients (CCD) (Yeh and hui Lien 2009), COMPAS (Larson et al. 2016), and HateDay (Tonneau et al. 2025). We extracted numerical features from the HateDay text data using an off-the-shelf sentence transformer1 . For a fixed protected attribute, each dataset was randomly split 70/30 into 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 the skrub library2 . We tuned the learning rate, number of leaf nodes and number of estimators via random search with 5-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 repository3 , which includes all scripts and datasets required to reproduce our experiments and results, as well as our PIR-based auditing framework implemented as a userfriendly module. Table 2 summarizes the main characteristics of each dataset. Specifically, for each dataset we report the model accuracy (Acc) and the demographic parity gap (|dC,true |) before any manipulation, both measured on the candidate set C. We also report the candidate set size N , the audit set size n as well as the size of the smallest protected group in each set (respectively Nmin and nmin ). As shown in the last column, some setups are highly imbalanced. For example, in HateDay the smallest protected group represents only about 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. We leverage Proposition 1 and Theorem 1 to compute the number of output modifications required to hide this amount of unfairness against a traditional (“vanilla”) black-box audit and against a R2 esPIR-based audit. For R2 esPIR, the provider targets passing probability 1 − δ = 80%. Finally, we plug these modification counts into Equation (3) to obtain the corresponding probability of manipulation detection in a setting where the auditor has a verification set of k ∈ {5, 10, 20, 50} canaries (see Section 4.3). Note that Theorem 1 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 1 huggingface.co/sentence-transformers/distiluse-basemultilingual-cased-v2 2 skrub-data.org/stable/reference/generated/skrub. tabular pipeline.html 3 github.com/sofianeazogagh/oblivious audit

Detection probability (%)

p With γ = 2 ln(4/δ)/nmin , this probability is at most δ. Hence, if |dC | ≤ ε − γ, then |dS | ≤ ε with probability at least 1 − δ. See Appendix B for the detailed proof.

Respir Vanilla

80 60 40 20 0

5 10

20 Number of canaries (k)

50

Figure 2: Probability of manipulation detection for a subset of our experiments, as a function of the number of canaries k, for vanilla audits and for our proposed R2 esPIR audit framework. quantities not known in advance to the platform, such as the realized value of nmin . The results are summarized in Table 3, and displayed in Figure 2 for a subset of our experiments. As expected, the number of output manipulations required to hide unfairness increases substantially under R2 esPIR compared 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 size 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, 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 with k = 50 canaries. 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, the number of canaries owned by the auditor remains a crucial parameter, strongly influencing manipulation detectability for both methods. It is also worth noting that when the tolerance ε is close to q zero, and in particular when it is smaller than γ = 2 ln(4/δ) (which can occur, for instance, when nmin is nmin small), the sufficient target s 2 ln(4/δ) |dC | ≤ ε − nmin for passing with probability at least 1 − δ might become unattainable, since |dC | ≥ 0. In our experiments, such cases arise for some configurations in which |dC,true | is already

Table 2: Overview of the characteristics of the considered datasets. Dataset CCD COMPAS hateday

Protected Attribute gender education marriage age gender race language

Dataset Size 30,000 6,172 81,000

Acc

|dC,true |

0.823 0.82 0.821 0.82 0.66 0.67 0.95

0.028 0.044 0.009 0.027 0.148 0.164 0.008

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 under R2 esPIR, together with the resulting detection probabilities for different numbers of canaries k. Protected mvanilla m 2 k R esPIR Attribute 5 10 CCD gender 38 152 20 50 5 10 CCD education 27 107 20 50 5 10 CCD marriage 14 56 20 50 5 10 CCD age 34 134 20 50 5 10 COMPAS gender 20 79 20 50 5 10 COMPAS race 39 156 20 50 5 10 hateday language 7 26 20 50 Dataset

N

n

13,500

6,750

2,778

1,389

36,450

18,225

Nmin

nmin

Nmin N

5,350 2,417 6,147 4,956 529 947 3,038

2,675 1,209 3,073 2,478 264 473 1,519

0.396 0.179 0.455 0.367 0.19 0.341 0.083

fraction of the candidate set, thereby increasing the effort required to hide unfairness and substantially improving the probability of detecting such manipulation.

6

Limitations, Discussion and Conclusion

Pdetect Pdetect (vanilla) (R2 esPIR)

6.1

2.23% 4.41% 8.63% 20.20% 1.59% 3.15% 6.21% 14.81% 0.83% 1.65% 3.27% 7.97% 2.00% 3.96% 7.76% 18.28% 5.63% 10.94% 20.68% 43.97% 10.74% 20.32% 36.51% 67.89% 0.15% 0.31% 0.61% 1.52%

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 and Theorem 1, holding for any input-output mapping) would remain valid but potentially conservative.

4.42% 8.65% 16.55% 36.39% 3.13% 6.16% 11.95% 27.24% 1.65% 3.27% 6.43% 15.31% 3.91% 7.66% 14.74% 32.88% 10.87% 20.56% 36.89% 68.36% 20.53% 36.85% 60.12% 89.96% 0.28% 0.57% 1.14% 2.81%

very small. In these regimes, the provider may be unable to reach the desired passing confidence level 1 − δ for the R2 esPIR audit. Nevertheless, we still report its best-effort manipulation, namely the number of output modifications required to achieve |dC | = 0, which, as reflected in our results, still tends to make manipulation more detectable by the auditor. Overall, these findings confirm the purpose of R2 esPIR. By hiding the audited set S through PIR, our protocol forces malicious providers to spread manipulations over a larger

Applicability of the Proposed Approach

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 and Theorem 1 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. 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 and Theorem 1), 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.2

Discussion

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 is R2 esPIR, 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, R2 esPIR increases 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 Section 4.3 and their empirical evaluation in Section 5 highlight three main design principles: 1. Large and representative candidate sets. As the best-case manipulation cost scales with min(N0 , N1 ), the candidate set should be large and should contain nontrivial representation of each protected group. 2. Balanced auditing. Since detection power scales with min(n0 , n1 ), the auditor should sample S using a rule that avoids severe group imbalance; stratified sampling from C is a natural option. 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 exactly S, as in Proposition 1). However, our guarantees rely on the candidate set capturing a meaningful portion of the provider’s operational domain. If C is not representative, then passing the audit may not translate into improved fairness outside C. Limitations. We view R2 esPIR as 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 set S, but must instead commit to outputs over a larger candidate set C. This makes manipulation more costly and, when combined with external verification queries, more detectable. Nonetheless, R2 esPIR also has inherent limitations. First, because the candidate set C is 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 over C so 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 (Gilad-Bachrach et al. 2016; Brutzkus, Gilad-Bachrach, and Elisha 2019; Juvekar, Vaikuntanathan, and Chandrakasan 2018; Mishra et al. 2020; Gong et al. 2024), 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 set C, 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 of R2 esPIR; otherwise, the iterative structure itself could reveal information that the platform may exploit strategically.

6.3

Conclusion

Overall, R2 esPIR is 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, deploying R2 esPIR in 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 2022a. Regulation (EU) 2022/1925 of the European Parliament and of the Council of 14 September 2022 on Contestable and Fair Markets in the Digital Sector and Amending Directives (EU) 2019/1937 and (EU) 2020/1828 (Digital Markets Act) (Text with EEA Relevance). 2022b. Regulation (EU) 2022/2065 of the European Parliament and of the Council of 19 October 2022 on a Single Market For Digital Services and Amending Directive 2000/31/EC (Digital Services Act) (Text with EEA Relevance). 2024. Regulation (EU) 2024/1689 of the European Parliament and of the Council of 13 June 2024 Laying down Harmonised Rules on Artificial Intelligence and Amending Regulations (EC) No 300/2008, (EU) No 167/2013, (EU) No 168/2013, (EU) 2018/858, (EU) 2018/1139 and (EU) 2019/2144 and Directives 2014/90/EU, (EU) 2016/797 and (EU) 2020/1828 (Artificial Intelligence Act) (Text with EEA Relevance). Ahmad, I.; Yang, Y.; Agrawal, D.; El Abbadi, A.; and Gupta, T. 2021. Addra: Metadata-private voice communication over fully untrusted infrastructure. In Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation, OSDI, 313–329. Aı̈vodji, U.; Arai, H.; Fortineau, O.; Gambs, S.; Hara, S.; and Tapp, A. 2019. Fairwashing: the risk of rationalization. In Proceedings of the 36th International Conference on Machine Learning, ICML, 161–170. Ali, A.; Lepoint, T.; Patel, S.; Raykova, M.; Schoppmann, P.; Seth, K.; and Yeo, K. 2021. Communication–Computation trade-offs in PIR. In Proceedings of the 30th USENIX Security Symposium, 1811–1828. Anders, C. J.; Pasliev, P.; Dombrowski, A.; Müller, K.; and Kessel, P. 2020. Fairwashing explanations with off-manifold detergent. In Proceedings of the 37th International Conference on Machine Learning, ICML, 314–323. Angel, S.; Chen, H.; Laine, K.; and Setty, S. 2018. PIR with compressed queries and amortized query processing. In Proceedings of the 2018 IEEE Symposium on Security and Privacy, SP, 962–979. Bardenet, R.; and Maillard, O.-A. 2015. Concentration Inequalities for Sampling without Replacement. Bernoulli, 21(3): 1361–1385. Birhane, A.; Steed, R.; Ojewale, V.; Vecchione, B.; and Raji, I. D. 2024. AI auditing: The Broken Bus on the Road to AI

Accountability. In Proceedings of the IEEE Conference on Secure and Trustworthy Machine Learning, SaTML, 612– 643. Bourrée, J. G.; Merrer, E. L.; Trédan, G.; and Rottembourg, B. 2023. On the relevance of APIs facing fairwashed audits. arXiv preprint arXiv:2305.13883. Brutzkus, A.; Gilad-Bachrach, R.; and Elisha, O. 2019. Low Latency Privacy Preserving Inference. In Proceedings of the 36th International Conference on Machine Learning, ICML, 812–821. Chandrasekaran, V.; Jia, H.; Thudi, A.; Travers, A.; Yaghini, M.; and Papernot, N. 2021. SoK: Machine Learning Governance. arXiv preprint arXiv:2109.10870. Chor, B.; Kushilevitz, E.; Goldreich, O.; and Sudan, M. 1998. Private Information Retrieval. Journal of the ACM, 45(6): 965–981. Corrigan-Gibbs, H.; Henzinger, A.; and Kogan, D. 2022. Single-server private information retrieval with sublinear amortized time. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, 3–33. Corrigan-Gibbs, H.; and Kogan, D. 2020. Private information retrieval with sublinear online time. In Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, 44–75. Costanza-Chock, S.; Raji, I. D.; and Buolamwini, J. 2022. Who Audits the Auditors? Recommendations from a field scan of the algorithmic auditing ecosystem. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT, 1571–1583. Davidson, A.; Pestana, G.; and Celi, S. 2023. Frodopir: Simple, scalable, single-server private information retrieval. Proceedings on Privacy Enhancing Technologies. de Castro, L.; and Lee, K. 2024. VeriSimplePIR: Verifiability in SimplePIR at No Online Cost for Honest Servers. In Proceedings of the 33rd USENIX Security Symposium, 5931–5948. Entrena-Serrano, C.; Degeling, M.; Romano, S.; and Çetin, R. B. 2025. TikTok’s Research API: Problems Without Explanations. arXiv preprint arXiv:2506.09746. European Commission. 2025. Commission fines X C120 million under the digital services act. Fokkema, H.; de Heide, R.; and van Erven, T. 2023. Attribution-based Explanations that Provide Recourse Cannot be Robust. Journal of Machine Learning Research, 24: 360:1–360:37. Franzese, O.; Shamsabadi, A. S.; Luck, C.; and Haddadi, H. 2025. Secure and Confidential Certificates of Online Fairness. In Proceedings of the 39th Annual Conference on Neural Information Processing Systems, NeurIPS. Fukuchi, K.; Hara, S.; and Maehara, T. 2020. Faking Fairness via Stealthily Biased Sampling. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI, 412– 419. Garcia Bourrée, J.; Godinot, A.; Biswas, S.; Kermarrec, A.M.; Le Merrer, E.; Tredan, G.; Vos, M. D.; and Vujasinovic,

M. 2025. Robust ML Auditing Using Prior Knowledge. In Proceedings of the 42nd International Conference on Machine Learning, ICML, 18794–18810. Gilad-Bachrach, R.; Dowlin, N.; Laine, K.; Lauter, K.; Naehrig, M.; and Wernsing, J. 2016. CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy. In Proceedings of the 33rd International Conference on Machine Learning, ICML, 201–210. Gong, Y.; Chang, X.; Mišić, J.; Mišić, V. B.; Wang, J.; et al. 2024. Practical solutions in fully homomorphic encryption: a survey analyzing existing acceleration methods. Cybersecurity, 7(5). Hardt, M.; Price, E.; and Srebro, N. 2016. Equality of opportunity in supervised learning. In Proceedings of the 30th Annual Conference on Neural Information Processing Systems, NIPS. Henzinger, A.; Hong, M. M.; Corrigan-Gibbs, H.; Meiklejohn, S.; and Vaikuntanathan, V. 2023. One server for the price of two: Simple and fast Single-Server private information retrieval. In Proceedings of the 32nd USENIX Security Symposium, 3889–3905. Hoeffding, W. 1963. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association, 58(301): 13–30. Horwitz, J. 2025. Meta Created ‘Playbook’ to Fend off Pressure to Crack down on Scammers, Documents Show. Reuters. Hutchinson, B.; Rostamzadeh, N.; Greer, C.; Heller, K.; and Prabhakaran, V. 2022. Evaluation gaps in machine learning practice. In Proceedings of the 2022 ACM conference on fairness, accountability, and transparency, FAccT, 1859– 1876. Juvekar, C.; Vaikuntanathan, V.; and Chandrakasan, A. 2018. GAZELLE: A Low Latency Framework for Secure Neural Network Inference. In Proceedings of the 27th USENIX Security Symposium, 1651–1669. Kogan, D.; and Corrigan-Gibbs, H. 2021. Private blocklist lookups with checklist. In Proceedings of the 30th USENIX Security Symposium, 875–892. Larson, J.; Mattu, S.; Kirchner, L.; and Angwin, J. 2016. How We Analyzed the COMPAS Recidivism Algorithm. ProPublica. Melchor, C. A.; Barrier, J.; Fousse, L.; and Killijian, M. 2016. XPIR : Private Information Retrieval for Everyone. Proceedings on Privacy Enhancing Technologies, 155–174. Menon, S. J.; and Wu, D. J. 2022. Spiral: Fast, high-rate single-server PIR via FHE composition. In Proceedings of the 2022 IEEE Symposium on Security and Privacy, SP, 930–947. Metaxa, D.; Park, J. S.; Robertson, R. E.; Karahalios, K.; Wilson, C.; Hancock, J. T.; and Sandvig, C. 2021. Auditing Algorithms: Understanding Algorithmic Systems from the Outside In. Foundations and Trends® in Human–Computer Interaction, 14(4): 272–344.

Mishra, P.; Lehmkuhl, R.; Srinivasan, A.; Zheng, W.; and Popa, R. A. 2020. Delphi: A Cryptographic Inference Service for Neural Networks. In Proceedings of the 29th USENIX Security Symposium, 2505–2522. Mughees, M. H.; Chen, H.; and Ren, L. 2021. OnionPIR: Response efficient single-server PIR. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 2292–2306. Olumofin, F. G.; and Goldberg, I. 2011. Revisiting the Computational Practicality of Private Information Retrieval. In Proceedings of the 15th International Conference on Financial Cryptography and Data Security, FC, 158–172. Park, S.; Kim, S.; and Lim, Y.-s. 2022. Fairness audit of machine learning models with confidential computing. In Proceedings of the ACM Web Conference 2022, 3488–3499. Pearson, G. D.; Silver, N. A.; Robinson, J. Y.; Azadi, M.; Schillo, B. A.; and Kreslake, J. M. 2024. Beyond the margin of error: a systematic and replicable audit of the TikTok research API. Information, Communication & Society, 28(3): 452–470. Pentyala, S.; Melanson, D.; Cock, M. D.; and Farnadi, G. 2022. PrivFair: a Library for Privacy-Preserving Fairness Auditing. arXiv preprint arXiv:2202.04058. Regev, O. 2009. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM, 56(6): 1–40. Ribeiro, M. H. 2024. Is Facebook “Standard” Algorithm Polarizing? https://doomscrollingbabel.manoel.xyz/p/isfacebook-standard-algorithm-polarizing. Serfling, R. J. 1974. Probability Inequalities for the Sum in Sampling without Replacement. The Annals of Statistics, 2(1): 39–48. Shamsabadi, A. S.; Wyllie, S. C.; Franzese, N.; Dullerud, N.; Gambs, S.; Papernot, N.; Wang, X.; and Weller, A. 2023. Confidential-PROFITT: Confidential PROof of FaIr Training of Trees. In Proceedings of the 11th International Conference on Learning Representations, ICLR. Shamsabadi, A. S.; Yaghini, M.; Dullerud, N.; Wyllie, S. C.; Aı̈vodji, U.; Alaagib, A.; Gambs, S.; and Papernot, N. 2022. Washing The Unwashable : On The (Im)possibility of Fairwashing Detection. In Proceedings of the 36th Annual Conference on Neural Information Processing Systems, NeurIPS. Shi, E.; Aqeel, W.; Chandrasekaran, B.; and Maggs, B. 2021. Puncturable pseudorandom sets and private information retrieval with near-optimal online bandwidth and time. In Proceedings of the Annual International Cryptology Conference, 641–669. Smith, S. W.; and Safford, D. 2001. Practical server privacy with secure coprocessors. IBM Systems Journal, 40(3): 683– 695. The European Advisory Committee Social Science One. 2019. Public Statement from the Co-Chairs and European Advisory Committee of Social Science One. Thomas, R. L.; and Uminsky, D. 2022. Reliance on metrics is a fundamental challenge for AI. Patterns, 3(5).

Timberg, C. 2021. Facebook made big mistake in data it provided to researchers, undermining academic work. Tonneau, M.; Liu, D.; Malhotra, N.; Hale, S. A.; Fraiberger, S.; Orozco-Olvera, V.; and Röttger, P. 2025. HateDay: Insights from a Global Hate Speech Dataset Representative of a Day on Twitter. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics, 2297– 2321. Vecchione, B.; Levy, K.; and Barocas, S. 2021. Algorithmic auditing and social justice: Lessons from the history of audit studies. In Proceedings of the 1st ACM Conference on Equity and Access in Algorithms, Mechanisms, and Optimization, 1–9. Waiwitlikhit, S.; Stoica, I.; Sun, Y.; Hashimoto, T.; and Kang, D. 2024. Trustless Audits without Revealing Data or Models. In Proceedings of the 41st International Conference on Machine Learning, ICML, 49808–49821. Yadav, C.; Moshkovitz, M.; and Chaudhuri, K. 2024. XAudit : A Learning-Theoretic Look at Auditing with Explanations. Transactions on Machine Learning Research. Yan, T.; and Zhang, C. 2022. Active fairness auditing. In Proceedings of the 39th International Conference on Machine Learning, ICML, 24929–24962. Yeh, I.-C.; and hui Lien, C. 2009. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert Systems with Applications, 36: 2473–2480.

A

Interactions during the PIR

Figure 3 provides a detailed description of the interaction during the PIR between the auditor and the provider using VeriSimplePIR (de Castro and Lee 2024). Auditor

Provider

Request an audit Offline Commitment D ∈ Zℓ×µ p Uniformly sample A ∈ Zµ×n q H ←D·A C ← Hash(A, H) A,H,Z

←−−−−−−−−−−−

Z ←C ·D

C ← Hash(A, H) Return Fail if ||Z||∞ > p · ℓ or ZA ̸= CH Query Choose an index i = (ir , ic ) ∈ Zℓ × Zµ bic ← OneHot(ic ) ▷ Regev’s Encryption using the generated A during the commitment Sample a uniform secret s ∈ Zn q Sample an error vector e ∈ χµ Jbic K = As + e + ⌊ pq ⌋ · bic Jbi K

−−−−−−c−−−−→

Answer

←−−−−−−−−− JrK

v ← D × Jbic K

Recover r̃ ← v[ir ] − ⟨H[ir ], s⟩ r ← ⌊ p·r̃ ⌉ q

Figure 3: The interaction between the auditor and the provider based on the SimplePIR protocol (Henzinger et al. 2023) and using the commitment to the database from VeriSimplePIR (de Castro and Lee 2024). More details can be found in (de Castro and Lee 2024) (Construction 5.1) to verify the integrity of the queries.

B

Proof of Theorem 2

Proof. Fix a realization of (n0 , n1 ) and let nmin := min(n0 , n1 ). Recall that dC = p1,C − p0,C and dS = p1,S − p0,S , in which pa,C (resp. pa,S ) denotes the protected group-a positive prediction rate on C (resp. on S). Conditioning on na , the quantity pa,S is the average of na binary values in [0, 1] obtained by sampling na elements uniformly without replacement from the Na elements of C in group a. For i.i.d. sampling with replacement, Hoeffding’s inequality for bounded random variables yields, for any t > 0, Pr(|pa,S − pa,C | ≥ t | na ) ≤ 2 exp(−2na t2 ). The same exponential bound remains valid under uniform sampling without replacement (Hoeffding 1963), so we use it here.

Using the decomposition dS − dC = (p1,S − p1,C ) − (p0,S − p0,C ), and the triangle inequality, |dS − dC | ≤ |p1,S − p1,C | + |p0,S − p0,C |, we obtain the event inclusion (as at least one of the two terms must be greater than γ/2 for their sum to be greater than γ): {|dS − dC | ≥ γ} ⊆ {|p1,S − p1,C | ≥ γ/2} ∪ {|p0,S − p0,C | ≥ γ/2}. Applying the union bound and the concentration inequality above gives Pr(|dS − dC | ≥ γ | n0 , n1 ) ≤ Pr(|p1,S − p1,C | ≥ γ/2 | n1 ) + Pr(|p0,S − p0,C | ≥ γ/2 | n0 )
≤ 2 exp −2n1 (γ/2)2
+ 2 exp −2n0 (γ/2)2   2 γ ≤ 4 exp − nmin . 2 Set γ :=

q

2 ln(4/δ) nmin . Then

Pr(|dS − dC | ≥ γ | n0 , n1 ) ≤ 4 exp(− ln(4/δ)) = δ. Now assume |dC | ≤ ε − γ. Whenever |dS − dC | < γ, the triangle inequality yields |dS | ≤ |dC | + |dS − dC | < (ε − γ) + γ = ε. Hence {|dS | > ε} ⊆ {|dS − dC | ≥ γ} and therefore Pr(|dS | > ε | n0 , n1 ) ≤ δ, which is equivalent to Pr(|dS | ≤ ε | n0 , n1 ) ≥ 1 − δ. We note that, since sampling occurs without replacement from the finite candidate set C, these bounds can actually be tightened through a finite-population correction. For completeness, we detail this refinement in Appendix D, while retaining the ordinary Hoeffding bound in the main text for simplicity and as a conservative worst-case bound.

C

Illustrative Extension with Equal Opportunity

The analysis of Theorem 1 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 (Hardt, Price, and Srebro 2016), which quantifies differences in true positive rates across protected groups. Assume that each x ∈ C is associated with a binary ground-truth label Y (x) ∈ {0, 1}. For each protected group a ∈ {0, 1}, define Ca+ := {x ∈ C : A(x) = a, Y (x) = 1}, Na+ := |Ca+ |, and similarly Sa+ := {x ∈ S : A(x) = a, Y (x) = 1},

+ n+ a := |Sa |.

The true positive rate of group a on C is pEO a,C :=

1 X h(x), Na+ + x∈Ca

and the equal opportunity gap on C is EO EO dEO C := p1,C − p0,C . EO The quantities pEO a,S and dS are defined analogously on S. As in Section 3.1, we omit the classifier h in notation since it is clear from context. Finally, let + + + Nmin := min(N0+ , N1+ ), n+ min := min(n0 , n1 ).

Theorem 3 (R2 esPIR manipulation bound for equal opportunity). Let C ⊂ X be the candidate set and let S ⊂ C be EO sampled uniformly at random without replacement. Assume that Na+ , n+ a > 0 for each a ∈ {0, 1}. Let dC,true denote the equal opportunity gap of the provider’s model on C before manipulation, and let ε be the audit threshold. For δ ∈ (0, 1/2], define s γEO (δ) :=

2 ln(4/δ) . n+ min

If the post-manipulation candidate-set gap satisfies |dEO C | ≤ ε − γEO (δ), then

+ + Pr |dEO S | ≤ ε n0 , n1 ≥ 1 − δ. Consequently, assuming that the original (non-manipulated) model would fail the equal opportunity audit, i.e., |dEO C,true | > ε,

any set of output flips that enforces this sufficient condition must contain at least 
+  mEO ≥ |dEO C,true | − ε + γEO (δ) Nmin flipped predictions on examples with Y (x) = 1. + + + + + EO Proof. Fix a realization of (n+ 0 , n1 ). Conditional on na , the set Sa is a uniformly random subset of size na of Ca . Thus, pa,S + + is the average of n+ a binary predictions sampled uniformly without replacement from the Na predictions in Ca . Hoeffding’s inequality for sampling without replacement gives, for every t > 0,
+ + 2 EO Pr pEO a,S − pa,C ≥ t na ≤ 2 exp(−2na t ).

Using

EO EO EO EO EO dEO S − dC = p1,S − p1,C − p0,S − p0,C , the triangle inequality and a union bound yield   2
γ + + + EO n . Pr dEO − d ≥ γ n , n ≤ 4 exp − S C 0 1 2 min Setting s γ = γEO (δ) =

2 ln(4/δ) n+ min

makes the right-hand side equal to δ. Hence, if |dEO C | ≤ ε − γEO (δ), EO then |dS | ≤ ε with conditional probability at least 1 − δ. We now bound the number of output flips required to enforce this condition. Assume without loss of generality that dEO C,true > 0. Flipping a prediction for an example in C1+ from 1 to 0 decreases the equal opportunity gap by 1/N1+ . Similarly, flipping a prediction for an example in C0+ from 0 to 1 decreases the gap by 1/N0+ . In contrast, flips on examples with Y (x) = 0 do not affect equal opportunity. Therefore, a single output flip can decrease the gap by at most   1 1 1 max = + . +, + N0 N1 Nmin Reducing the initial gap to at most ε − γEO (δ) thus requires at least  EO
+  |dC,true | − ε + γEO (δ) Nmin output 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.

D

Refining the Bound through a Finite-Population Correction

Theorems 1 and 2 apply a Hoeffding bound that is valid under sampling without replacement but does not exploit the finite population sizes N0 and N1 . As a complementary result, we apply the finite-population refinement of the Hoeffding–Serfling inequality proposed by Bardenet and Maillard (2015, Theorem 2.4 and Corollary 2.5), which builds on and slightly improves the original bound of Serfling (1974). For each a ∈ {0, 1}, define  na − 1   , if na ≤ Na /2, 1 − Na    ρa :=  1 na   1+ , if na > Na /2,  1− Na na and s s ρ1 ln(4/δ) ρ0 ln(4/δ) γFPC (δ) := + . 2n1 2n0 Theorem 4 (Finite-population refinement of Theorem 1). Consider the setting of Theorem 1 and fix δ ∈ (0, 1). If the postmanipulation candidate-set gap satisfies |dC | ≤ ε − γFPC (δ), then Pr(|dS | ≤ ε | n0 , n1 ) ≥ 1 − δ. Moreover, enforcing this sufficient condition from an initial gap dC,true requires at least mFPC ≥ ⌈(|dC,true | − ε + γFPC (δ)) Nmin ⌉ output flips, where Nmin := min(N0 , N1 ). Proof. Conditioning on na , apply Bardenet and Maillard (2015, Corollary 2.5) to the finite population of Na binary predictions in group a. In their notation, the population mean is pa,C , the sample mean is pa,S , the sample size is na , and the range satisfies b − a = 1. Thus, with probability at least 1 − δ, s ρa log(1/δ) pa,S − pa,C ≤ . 2na Equivalently, setting δ = exp(−2na t2 /ρa ) gives, for every t > 0,   2na t2 Pr(pa,S − pa,C > t | na ) ≤ exp − . ρa The same bound applies to the opposite deviation pa,C − pa,S . A union bound over the two tails therefore yields   2na t2 Pr(|pa,S − pa,C | ≥ t | na ) ≤ 2 exp − . ρa For each a ∈ {0, 1}, set s ta :=

ρa ln(4/δ) . 2na

Substituting t = ta into Equation (5) gives Pr(|pa,S − pa,C | > ta | na ) ≤ 2 exp(− ln(4/δ)) =

δ . 2

A union bound over the two protected groups therefore shows that, with probability at least 1 − δ, |p1,S − p1,C | ≤ t1

and

|p0,S − p0,C | ≤ t0 .

On this event, |dS − dC | = |(p1,S − p1,C ) − (p0,S − p0,C )| ≤ |p1,S − p1,C | + |p0,S − p0,C | ≤ t1 + t0 = γFPC (δ).

(5)

Consequently, if |dC | ≤ ε − γFPC (δ), then |dS | ≤ |dC | + |dS − dC | ≤ ε with probability at least 1 − δ. Finally, a single output flip changes dC by at most  max

1 1 , N0 N1

 =

1 . Nmin

Enforcing the sufficient condition above therefore requires reducing the candidate-set gap by at least |dC,true | − ε + γFPC (δ). It consequently requires at least ⌈(|dC,true | − ε + γFPC (δ)) Nmin ⌉ output flips as claimed. Since ρa ≤ 1 and na ≥ nmin for each a ∈ {0, 1}, s

s ρ1 ln(4/δ) ρ0 ln(4/δ) γFPC (δ) = + 2n1 2n0 s s ln(4/δ) ln(4/δ) ≤ + 2n1 2n0 s 2 ln(4/δ) ≤ . nmin 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 number mFPC of output flips required for the platform to pass the audit with sufficiently high probability.

Related documents

• Model Inversion Attacks that Exploit Confidence Information and Basic Countermeasures#6672
• Onyx: Cost-Efficient Disk-Oblivious ANN Search#123957
• Tamper-Proofing with Self-Modifying Code#13022
• Fact-Checks Can Help Inoculate LLMs Against Disinformation#16360
• Cryptography and Cryptanalysis#67183