Manipulation-Proof Oblivious Audits against Deceptive Model Providers

AI summary

Overview

Research area: Algorithmic governance and trustworthy machine learning, at the intersection of fairness auditing (demographic parity in binary classifiers), adversarial manipulation of audit results, and applied cryptography (Private Information Retrieval, lattice-based homomorphic encryption).

Technical level: Advanced. The paper combines cryptographic primitives (LWE-based PIR, VeriSimplePIR, commitment digests), probabilistic concentration arguments (Hoeffding/Serfling bounds), and a formal adversary model for fairness auditing. Readers need comfort with probability bounds and basic cryptography; the high-level argument is accessible, but the guarantees are stated mathematically.

Scope (1 sentence): The paper proposes and analyzes a protocol, called respir, that hides the auditor's actual audit set inside a larger candidate set via Private Information Retrieval, forcing a deceptive model provider to falsify far more predictions (and thus become far more detectable) in order to fake demographic parity.

What This Paper Is About

External fairness audits of machine learning models are usually run as declared, black-box query procedures, which means the model provider can see or infer exactly which inputs are being audited and can strategically flip a small number of those outputs to appear fair while leaving the deployed model unchanged. The paper's goal is an audit protocol in which the provider must label a large candidate set without learning which subset the auditor will actually use, so that passing the audit requires genuine fairness across the whole candidate set rather than surgical patching of a known evaluation subset. The paper formalizes this as a regulator-versus-malicious-provider game and proves that the new protocol increases both the number of flips required and the probability of detecting them, without modifying the audited model, its training, or its inference pipeline.

Key Contributions

1. The respir audit protocol. A manipulation-mitigating audit protocol that hides the true audit set S inside a larger candidate set C using a Private Information Retrieval mechanism. Its only prerequisite is that the provider must label a candidate set C larger than the actual audit set S.

2. A manipulation-difficulty theorem. Theorem 1 proves that under respir, a deceptive provider must modify a substantially larger number of points in the candidate set C in order to fake the same level of demographic parity, compared to the number required under a vanilla black-box audit (Proposition 1), thereby increasing the probability of detection.

3. Characterization of the required candidate-set size. The paper derives how large C must be relative to S to achieve a desired level of manipulation detection (Theorem 1 and the intermediate concentration result, Theorem 2), while showing the protocol does not incur prohibitive computational overhead.

4. A practical instantiation and efficiency evidence. The protocol is built on VeriSimplePIR, an extension of SimplePIR that adds verifiability at no additional online cost, letting the auditor verify that the database queried is exactly the one used to generate the digest, preventing the provider from relabeling during the audit. Timing measurements for the online phase are reported across database sizes from 128 KiB to 8 GiB.

Main Findings

• A vanilla black-box audit is easy to subvert. Proposition 1 gives the lower bound m_vanilla ≥ ⌈(|d_true| − ε) · n_min⌉ on the number of predictions a provider must flip to pass a failing audit, where n_min is the size of the smallest protected group in the audit set and ε is the fairness tolerance. The paper's illustrative case: to hide a disparity of 0.01 with a balanced audit set of n = 400 queries, the provider only has to modify two predictions.

• Unbalanced audit sets make manipulation even easier. The bound scales with n_min, so audit sets with a small minority group greatly facilitate manipulation.

• Detection depends on both the number of manipulations and the number of canaries. The paper models detection via a verification set of k externally labeled queries (canaries) present in S, with a catch-all parameter q ∈ [0,1] (the probability a canary remains indistinguishable to the provider). The detection probability is ℙ(manipulation detected) = 1 − (1 − q·m/n)^k, where m is the number of modified audit-set outputs. Small k provides limited guarantees when only a few outputs are modified.

• respir raises the manipulation cost, in two ways. Theorem 1 states that it suffices for the provider to flip at least m_respir ≥ ⌈(|d_{C,true}| − ε + sqrt(2 ln(4/δ)/n_min)) · N_min⌉ predictions in C to pass with probability at least 1 − δ, where N_min is the smallest protected group in the candidate set C. First, the sampling-uncertainty term sqrt(2 ln(4/δ)/n_min) forces the provider to over-correct unfairness on C. Second, the scaling changes from n_min (audit-set scale) to N_min (candidate-set scale), and since typically N_min ≫ n_min, the manipulation cost grows substantially.

• A sufficient condition for high-probability passing. Theorem 2: if |d_C| ≤ ε − sqrt(2 ln(4/δ)/n_min), the provider passes with probability at least 1 − δ. The proof applies finite-population Hoeffding/Serfling bounds to each group rate and uses the triangle inequality plus a union bound, giving Pr(|d_S − d_C| ≥ γ | n_0, n_1) ≤ 4 exp(−γ²n_min/2), with γ = sqrt(2 ln(4/δ)/n_min).

• The protocol is information-economical. Although the provider must label the large candidate set C, the amount of information revealed to the auditor is the same as in the traditional black-box setup, since the sampled audit set S need not be larger. This protects proprietary models.

• PIR is efficient compared to homomorphic-encryption evaluation. For a neural network h, running x ∈ S through h under homomorphic encryption would require as many matrix-vector multiplications as there are network layers, whereas the PIR protocol reduces this to a single lightweight matrix-vector multiplication per x ∈ S.

• Measured online performance (VeriSimplePIR, average of 10 runs). Total online time is 1.09 ms for a 128 KiB database, 28.16 ms for 128 MiB, 117.28 ms for 1 GiB, 1628.15 ms for 4 GiB, and 3639.17 ms for 8 GiB. Corresponding query sizes run from 0.375 KiB (128 KiB database) to 110.1 KiB (8 GiB); answer sizes from 7.812 KiB to 2.325 MiB; bandwidth usage from 8.187 KiB to 2.435 MiB. Query time ranges from 0.5024 ms to 15.3573 ms; answer time from 0.0221 ms to 2816.19 ms; recovery time from 0.574 ms to 807.623 ms. Because labels y with log2(y) < log2(p) can be packed multiple per element of Z_p, the matrix D can be considerably smaller than the raw label set h(S).

• Illustrative bounds setting. Figure 1 uses |S| = 400, canaries k ∈ {1, 3, 5} each with detection effectiveness q = 0.8, candidate set |C| = 2,000, target passing probability 1 − δ = 0.95, and compares an unbalanced regime (minority group = 10% of S, and of C for respir) against a balanced regime with equal group sizes. In both regimes, respir increases the required number of flips m and, consequently, the probability of detection.

• Two protocols are presented. Algorithm 1 is the standard black-box audit procedure (gather S, query h on S, compute d_S, pass if d_S < ε); Algorithm 2 is the respir procedure (agree on C, provider privately labels all of C into D = {(x, h(x)) : x ∈ C}, auditor uses PIR to retrieve outputs on S ⊂ D, then decides pass/fail).

Methodology in Plain English

The authors first define the standard audit: the auditor collects a set of examples, queries the provider's model on each, and computes the demographic parity gap — the difference in positive-prediction rates between two protected groups — checking whether it falls within a tolerance ε. They then show mathematically how few output flips are needed to drag that measured gap below ε, which is the vulnerability they target.

Their fix changes what the provider sees. Rather than auditing a set the provider knows in advance, the auditor and provider first agree on a much larger candidate set C. The provider labels every example in C, producing a database of features and labels. The auditor then picks a smaller audit set S from inside C and uses Private Information Retrieval to fetch only those labels: the provider answers an encrypted query and learns nothing about which records were retrieved, while the auditor learns nothing beyond the labels it asked for. The query is a lightweight encrypted matrix-vector multiplication, and VeriSimplePIR's commitment digest lets the auditor confirm afterwards that the database queried is the one that was committed, so labels cannot be switched mid-audit.

Because S is a uniform random sample of C, the provider cannot target its edits. To pass with high probability, it must make the model look fair across the whole candidate set, which requires falsifying many more outputs — and each falsified output is a chance for a planted canary to expose the manipulation. The authors back this up with concentration inequalities (Hoeffding/Serfling) that bound how far the sampled audit gap d_S can deviate from the candidate-set gap d_C, and they benchmark the PIR online phase on databases from 128 KiB to 8 GiB.

Note on the provided content: the paper's abstract states that experimental results across representative audit scenarios confirm effectiveness and practicality, but the concrete experimental section (beyond Table 1's PIR timings and Figure 1's theoretical illustration) is not present in the supplied text, and Table 2 ("Overview of the characteristics of the considered datasets") appears only as empty column headers. Specific dataset names, dataset sizes, and per-scenario experimental numbers are therefore not reported here.

Why This Matters

Impact on research. The work adds a cryptographic lever to the small literature on manipulation-proof auditing. Prior approaches rely on the auditor holding private prior knowledge (Garcia Bourrée et al. 2025), on heavy zero-knowledge-proof protocols requiring the provider's active cooperation, or on trusted hardware. respir instead uses lightweight PIR and requires no modification to the audited model, its training procedure, or its inference pipeline, and it relaxes the private-prior assumption by cryptographically hiding the auditor's queries.

Real-world applications:

• Regulatory AI audits. The EU AI Act, DSA, and DMA increasingly mandate external assessments of high-risk AI systems; respir gives regulators a protocol that survives provider interference.
• Advertising and content-moderation transparency. The paper's motivating incident is the Meta Ad Library: a 2025 Reuters report found Meta monitored the specific keywords and celebrity names Japanese regulators used to investigate scam ads, then re-ran those exact searches to preemptively delete the targeted ads. Hiding the query set removes this reactive-curation channel.
• Fairness evaluation of proprietary prediction APIs. Lending, hiring, insurance, or benefits-allocation models exposed only through black-box APIs can be audited for demographic parity without disclosing the audit sample or the proprietary model.
• Third-party and academic model access. Where research APIs or academic partnerships exist but are vulnerable to provider interference (undisclosed model changes, delayed data access), oblivious querying makes compliance claims harder to stage.

Industry relevance. The protocol requires the provider to label the candidate set C but imposes minimal overhead on the auditor, and its measured online cost stays in the millisecond-to-second range across databases up to 8 GiB. That makes it a plausible compliance mechanism rather than a research prototype, and it does not require the provider to reveal model architecture, weights, or training data.

Future Directions

1. Beyond demographic parity in binary classifiers. The paper states that its framework is model- and metric-agnostic but restricts the presentation to demographic parity in binary classifiers, and defers discussion of extensions to other settings. Scaling the guarantees to other fairness metrics and multi-class or non-classification outputs remains open.

2. Choosing and negotiating the candidate set. C can be proposed by the auditor (for example from a large public dataset) or by the provider, and selection can be iterative, with either party asking for additions or deletions to improve representativeness. How to make that negotiation itself manipulation-resistant is a design question the paper flags but does not fully resolve.

3. Canary design and sampling alternatives. The detection analysis collapses canary effectiveness into a single parameter q, and uniform sampling of S from C is justified by representativeness, ease of provider acceptance, prediction-independence, and a clean probabilistic derivation of the bounds. How alternative sampling schemes or richer verification sets change the guarantees is left open.

4. Deployment and verifiability in practice. The protocol relies on VeriSimplePIR's proof that the queried database matches the committed digest; practical questions of integrating this into real regulatory workflows, along with the design principles for hidden-audit-set protocols more generally, are listed as directions for future work in the concluding discussion.

Target Audience

Researchers and practitioners in trustworthy ML and algorithmic governance — especially those working on fairness auditing, audit manipulation, and regulatory compliance tooling. It also suits applied cryptographers interested in PIR deployments, and policy or regulatory technologists who need to understand what formal guarantees an audit can and cannot provide. Some mathematical fluency is required to follow the theorems, but the framing, the black-box audit game, and the manipulation-detection formula are readable by a broader audience.

Authors’ 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.