{"id":"48c75709-edd1-4250-a560-50361a970190","arxiv_id":"2608.04365","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A PIR-based audit protocol forces deceptive model providers to flip many more predictions to hide unfairness, increasing detection probability.","lead":"This paper presents R²esPIR, an audit protocol that uses private information retrieval to hide the exact audit queries from a model provider, forcing the provider to manipulate a much larger set of predictions to fake fairness. It could give regulators a practical way to detect when companies are gaming declared fairness audits.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's 'must falsify' bound is derived from a sufficient condition and depends on the realized random n_min; the paper never proves necessity, so the abstract's central claim overstates what is established.","rationale":"The reader's weakest assumption identifies the main logical gap: Theorem 1 proves a sufficient condition for passing with high probability and then treats the flips needed for that sufficient condition as the flips that are 'must' be performed. The paper's abstract and contribution list lean on this necessity claim, so the overstatement is load-bearing for the headline contribution. The protocol's qualitative insight remains plausible—hiding S does force manipulation to occur at the scale of C rather than S—and the concentration calculations themselves appear correct, which is why the appropriate outcome is a conditional accept with revision rather than rejection. The additional dependence on the realized random n_min reinforces the same concern: the stated bound is not a fixed flip count a provider can commit to before S is sampled, and the paper's own experimental section acknowledges that the realized n_min is not known in advance. The reader's CONDITIONAL verdict is therefore appropriate; I would keep it and require the authors to either prove a genuine lower bound (e.g., using the converse tail to show that |d_C| > ε + γ implies failure with probability at least 1 − δ) or soften the abstract and theorem statements from 'must falsify' to 'it is sufficient to flip' plus an explicit conditioning statement.","tokens_in":21868,"tokens_out":13234,"duration_ms":137706,"concrete_test":"Use a small synthetic finite population (e.g., N = 12, N_min = 3, n = 6) with d_C,true = 0.2, ε = 0.1, δ = 0.05. Exhaustively enumerate all flip subsets of C of size m and all audit subsets S of size n to compute the exact minimal m achieving Pr(|d_S| ≤ ε) ≥ 1 − δ; compare this to Theorem 1's expression evaluated at the realized n_min. If the exact minimal m is smaller than the theorem's value, the 'must falsify' lower bound is concretely false. Also check whether any fixed flip set of the theorem's size achieves the claimed unconditional 1 − δ guarantee across all S, given that n_min varies.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that R²esPIR forces a provider to falsify at least ceil((|d_C,true| − ε + sqrt(2 ln(4/δ)/n_min)) N_min) responses is not supported by the proof. Theorem 2 (Section 4.3) gives only a sufficient condition: if |d_C| ≤ ε − γ, then Pr(|d_S| ≤ ε | n_0, n_1) ≥ 1 − δ. Theorem 1 then counts flips needed to reach this sufficient condition, but never shows that a provider failing this sufficient condition cannot pass with probability at least 1 − δ. The concentration bound has slack: a provider whose post-manipulation candidate-set gap lies in (ε − γ, ε + γ] may still pass with the required probability, so the abstract's 'must falsify' is not a proven lower bound. A second issue is that the bound depends on n_min, the realized smallest protected-group size in the random audit set S; the provider must commit to flips before S is drawn, so the stated number is not a well-defined deterministic strategy guarantee unless the theorem also supplies a high-probability lower bound on n_min, which it does not. Both issues are located in Section 4.3, Theorem 1 and its proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes R²esPIR, an audit protocol that hides the actual audit set S inside a larger candidate set C using private information retrieval. The provider is required to label all of C, while the auditor later retrieves labels on a uniformly random subset S and tests demographic parity. The authors claim that this forces a deceptive provider to flip substantially more predictions than in a vanilla black-box audit, and they support this claim with a concentration-based analysis (Theorems 1 and 2), a finite-population refinement (Theorem 4), an extension to equal opportunity (Theorem 3), and experiments on CCD, COMPAS, and HateDay using a VeriSimplePIR implementation.","tokens_in":22084,"tokens_out":7529,"duration_ms":71810,"significance":"If the central claim were fully established, the paper would make a useful contribution: it offers a practical, model-agnostic mechanism for increasing the cost and detectability of audit manipulation, it integrates verifiable stateful PIR with known performance characteristics, and it is accompanied by public code. The concentration derivation in Theorem 2 is correct and uses standard bounds, and the extension to equal opportunity is clean. However, the headline 'must falsify' claim is currently supported only for a sufficient condition, and the flip lower bound depends on a random quantity that is unavailable to the provider when it commits its flips; these are substantive gaps that require additional work rather than mere polishing.","major_comments":[{"comment":"The abstract's central claim that a deceptive provider under R²esPIR 'must falsify a significantly larger number of responses' is not established by the proof of Theorem 1. Theorem 2, which the proof invokes, provides only a sufficient condition for passing: if |d_C| ≤ ε − γ then Pr(|d_S| ≤ ε | n0, n1) ≥ 1 − δ. Theorem 1 counts the flips needed to reach this sufficient condition, but no converse is proved: a provider whose post-manipulation candidate-set gap lies in (ε − γ, ε + γ] may still pass with probability at least 1 − δ because the Hoeffding/Serfling bound is not tight. Therefore the quantity in Eq. (4) is a lower bound on flips needed to satisfy a sufficient condition, not a lower bound on flips needed to pass the audit. The manuscript should either prove a matching necessity direction (e.g., via an anti-concentration argument) or consistently phrase the result as a guarantee relative to the sufficient condition rather than as a 'must falsify' lower bound.","section":"Section 4.3, Theorem 1"},{"comment":"The lower bound in Eq. (4) depends on n_min, the realized smallest protected-group size of the randomly sampled audit set S. Under the protocol in Algorithm 2, the provider commits to labels on all of C before S is sampled, so n_min is not known to the provider when it chooses its flips. Consequently, Eq. (4) does not describe a deterministic strategy guarantee; different realizations of S yield different claimed thresholds. The paper itself acknowledges in Section 5 that the bound depends on 'the realized value of n_min,' but the theorem statement does not supply the required high-probability lower bound on n_min. To make the claim operational, the authors should add a concentration argument for n_min under uniform sampling without replacement (or use a worst-case lower bound derived from N_min, N, and n) and state Theorem 1 unconditionally in terms of that bound.","section":"Section 4.3, Theorem 1"},{"comment":"Table 3 labels m_vanilla and m_R²esPIR as the 'number of output flips required' and the surrounding text repeatedly states that R²esPIR increases the number of required output flips. Because Proposition 1 is a genuine deterministic lower bound but Theorem 1 is only a lower bound on flips needed to meet a sufficient condition, the comparison in Table 3 is not a comparison of minimal manipulation costs. The experimental conclusions remain meaningful as an illustration of the sufficient-condition-based bound, but as written the 'required' language goes beyond what the theorems prove. Please either add the missing converse or relabel the experimental quantity, for example as 'flips needed to reach the sufficient condition of Theorem 1.'","section":"Section 5, Table 3"}],"minor_comments":[{"comment":"Algorithm 1 and Algorithm 2 test 'd_S < ε' while the surrounding text and Theorem 2 use '|d_S| ≤ ε'; these should be aligned to avoid ambiguity about boundary behavior.","section":"Algorithms 1 and 2"},{"comment":"The statement 'it suffices for the provider to flip at least [m]' is logically inverted: the proof shows that reaching the sufficient condition requires at least m flips, not that flipping at least m arbitrary predictions suffices to pass. The statement should be reworded accordingly.","section":"Section 4.3, Theorem 1 statement"},{"comment":"The role of q in Eq. (3) is unclear: the text says that conditional on being effectively present a canary is modified with probability m/n, but the formula includes the factor q m/n. The generative model for q and for canary inclusion should be stated explicitly so that Eq. (3) follows from the definition.","section":"Section 3.2, Eq. (3)"},{"comment":"The phrase 'Algorithm 2, algorithm 2' appears twice in the step descriptions and seems to be a typo; it likely refers to specific lines of Algorithm 2 and should be corrected.","section":"Section 4.1"}],"recommendation":"major_revision","confidential_remarks":"The paper's core theorem is currently a sufficient-condition guarantee, so the headline claim in the abstract is overstated. I do not recommend rejection: the protocol idea is sound, and the missing converse may be provable with additional concentration/anti-concentration arguments, while the n_min issue can likely be repaired with a high-probability lower bound. However, as submitted, the central 'must falsify' claim needs substantive additional work, and the experiments should be carefully relabeled to avoid asserting a stronger statement than Theorem 1 proves."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, what you should know: the protocol is a genuine new idea — hiding the audit set inside a larger candidate set via PIR — and the concentration argument in Theorem 2 is correct. But the headline claim in the abstract, 'must falsify a significantly larger number of responses,' is not proven. Theorem 1 only shows that flipping at least m flips gets the provider into a sufficient condition for passing; it never shows that fewer flips cannot also pass with probability ≥1−δ. A provider whose post-manipulation gap lands between ε−γ and ε+γ may still pass due to slack in the Hoeffding bound. So the 'must' is an overclaim.\n\nThe second, related problem: the bound depends on n_min, the realized smallest group size in the audit set S, which the provider must commit to before S is drawn. The authors acknowledge this in Section 5, calling the theorem an analytical characterization rather than an operational recipe, but the abstract doesn't carry that caveat. Without a high-probability lower bound on n_min, the provider cannot actually use the number as a strategy guarantee.\n\nWhat the paper does well: R²esPIR is clearly specified, the flip-sensitivity argument for demographic parity is valid, and the positioning against prior work (Garcia Bourrée et al., cryptographic audit protocols) is honest. The extension to equal opportunity and the finite-population refinement in Appendix D are real additions. The writing is clear and the protocol is practicable under reasonable assumptions.\n\nThe experiments are the weakest empirical part: they evaluate the formulas rather than simulate an actual attack, and the code link in the abstract has a typo (space instead of a hyphen). The PIR timing table (Table 1) lacks setup details like hardware and parameter choices.\n\nBottom line: the core insight is good and the math is largely sound, but the central claim needs to be restated as a sufficient-condition cost, not a necessity lower bound. If the authors fix that and soften the abstract, this becomes a solid contribution. I'd send it to peer review — the idea deserves referee time — but I'd expect heavy revision.","headline":"Clever protocol idea, but the 'must falsify' claim outruns the proof; worth reviewing after the necessity gap is fixed.","tokens_in":22638,"tokens_out":2511,"would_cite":true,"duration_ms":23100,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A PIR-based audit protocol hides which queries count, forcing a deceptive provider to falsify a large fraction of the candidate set rather than a small known audit set.","keywords":["algorithmic auditing","fairness auditing","demographic parity","audit manipulation","private information retrieval","manipulation detection","oblivious querying","model governance"],"falsifier":"For a small concrete candidate set and audit size, enumerate every subset the auditor could draw and every strategy in which the provider flips exactly $m_{\\mathrm{R^2esPIR}}-1$ predictions chosen to minimize the candidate gap; if any such strategy passes with probability at least $1-\\delta$, then Theorem 1's claimed lower bound is false.","tokens_in":21637,"feed_emoji":"⚖️","tokens_out":10877,"duration_ms":103476,"temperature":0.7,"pith_summary":"The paper tries to make algorithmic fairness audits harder to game when the audited company can see which queries count. It introduces R²esPIR, a protocol in which the provider labels a large candidate set and the auditor uses Private Information Retrieval to obtain labels for a hidden audit subset, so the provider never knows which points are actually scored. The central result is a lower bound on manipulation effort: to pass a demographic-parity audit with probability at least 1−δ, a provider whose model is unfair on the candidate set must falsify a number of predictions that scales with the candidate set's smallest protected group, not the small audit set's. This raises both the cost and the detectability of manipulation, and the reported experiments on credit, recidivism, and hate-speech datasets show detection probabilities roughly doubling for the same number of verification queries.","feed_headline":"Hiding the audit set makes faking fairness far costlier","feed_subtitle":"A PIR-based protocol forces providers to patch a large candidate set, roughly doubling detection odds.","key_machinery":"The load-bearing object is the hidden audit set. R²esPIR (Robust Research audit APIs enabled by Private Information Retrieval) works in three steps: both parties agree on a candidate set $C$; the provider privately labels every point in $C$ and commits to that label database; the auditor samples an audit set $S\\subseteq C$ uniformly and retrieves $h(S)$ through VeriSimplePIR, a verifiable PIR scheme that prevents the provider from changing labels after commitment. Two mathematical ingredients convert this hiding into a manipulation cost: a concentration inequality for sampling without replacement, which bounds $|d_S-d_C|$ by $\\sqrt{2\\ln(4/\\delta)/n_{\\min}}$ with probability at least $1-\\delta$, and the sensitivity bound that a single output flip changes $d_C$ by at most $1/N_{\\min}$. Together they imply that the provider must make the whole candidate set look fair rather than patch the known audit set.","core_discovery":"The paper's central claim is that hiding the audit set inside a larger candidate set converts a local patching problem into a global one. Theorem 1 states that a provider who would fail on the candidate set with gap $d_{C,\\mathrm{true}}$ must flip at least $\\left\\lceil \\left(|d_{C,\\mathrm{true}}|-\\varepsilon + \\sqrt{2\\ln(4/\\delta)/n_{\\min}}\\right) N_{\\min}\\right\\rceil$ predictions in $C$ to pass with probability at least $1-\\delta$, versus the $\\lceil(|d_{\\mathrm{true}}|-\\varepsilon)n_{\\min}\\rceil$ flips needed when the audit set is known. The extra square-root term comes from concentration of the sampled audit-set gap around the candidate-set gap, so the provider must push the candidate gap down to $\\varepsilon$ minus that margin. The proof combines a bound on how much one output flip can change the gap, namely at most $1/N_{\\min}$, with a sufficient condition relating the candidate-set gap to the observed audit-set gap.","pith_inferences":["The protocol's logic suggests that candidate-set design, not just cryptography, carries the guarantee: an auditor should negotiate a large and group-balanced $C$, because the manipulation cost scales with $N_{\\min}$ while the detection margin scales with $n_{\\min}$.","The same hidden-set recipe should transfer to any audited quantity that is a difference of two empirical rates with bounded one-flip sensitivity, such as equalized odds or predictive parity; the paper sketches equal opportunity, but the general pattern is to replace the protected-group sizes with the relevant conditioning-stratum sizes.","An empirical next step would be to measure the canary indistinguishability parameter $q$ directly on deployed APIs, since the detection probability formula makes $q$ the main unknown between the theoretical guarantee and real-world detection.","Because VeriSimplePIR commits the provider to a label database before the audit set is drawn, R²esPIR effectively turns an interactive audit into a pre-registered commitment, which suggests hybrid designs where the provider commits first and the auditor later randomizes the audit subset without the provider observing it."],"forward_implications":["Faking fairness under R²esPIR requires altering a number of predictions that scales with the candidate set's smallest protected group, so enlarging and rebalancing $C$ directly multiplies the attacker's cost.","For a fixed number of verification canaries, the detection probability rises as the required flip count grows, and the reported experiments show detection probabilities roughly doubling compared with a vanilla black-box audit.","The auditor's added cost stays small: a single lightweight PIR query per audited point, with measured online times on the order of milliseconds for small databases and seconds for an 8 GiB label database.","The protocol leaves the provider's model and inference pipeline untouched; the provider's only obligation is to label the candidate set and answer PIR queries.","A finite-population refinement of the bound gives a smaller required margin when the audit set covers a large share of a protected group, so the overhead of the protocol shrinks as the audit becomes more thorough."],"supporting_citations":[{"why":"Introduces private information retrieval, the primitive that lets the auditor retrieve labels without revealing which points are being queried.","marker":"Chor et al. 1998"},{"why":"Supplies SimplePIR, the efficient single-server PIR construction whose online query and answer phases the protocol uses.","marker":"Henzinger et al. 2023"},{"why":"Provides VeriSimplePIR, which commits the provider to a label database and lets the auditor verify that queries hit that committed database.","marker":"de Castro and Lee 2024"},{"why":"Gives the concentration inequality for averages of bounded random variables that drives the bound relating the audit-set gap to the candidate-set gap.","marker":"Hoeffding 1963"},{"why":"Supplies the sharper sampling-without-replacement concentration bound used in the finite-population refinement of the manipulation-cost theorem.","marker":"Serfling 1974"},{"why":"Provides the lattice-based encryption scheme that gives SimplePIR its query privacy and underpins the protocol's security.","marker":"Regev 2009"}],"fun_headline_variants":["Blind audits make faking fairness far costlier","Hiding audit set forces providers to flip more outcomes","Oblivious audits increase detection odds for cheating","Manipulation-proof audits: hiding queries raises costs","Hiding audit queries deters model providers from gaming"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower bound assumes that meeting the paper's sufficient condition is the only way for a provider to pass with high probability; if a provider whose hidden-set fairness gap is slightly above that threshold can still pass, the 'must flip this many' conclusion is too strong.","fun_headline_variants_meta":{"raw":{"variants":["Blind audits make faking fairness far costlier","Hiding audit set forces providers to flip more outcomes","Oblivious audits increase detection odds for cheating","Manipulation-proof audits: hiding queries raises costs","Hiding audit queries deters model providers from gaming"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000193,"raw_usage":{"total_tokens":1376,"prompt_tokens":996,"completion_tokens":380,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":304}},"tokens_in":612,"tokens_out":380,"duration_ms":4495,"temperature":1.0,"reasoning_tokens":304,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T18:57:16.708063+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a small concrete candidate set and audit size, enumerate every subset the auditor could draw and every strategy in which the provider flips exactly $m_{\\mathrm{R^2esPIR}}-1$ predictions chosen to minimize the candidate gap; if any such strategy passes with probability at least $1-\\delta$, then Theorem 1's claimed lower bound is false.","supporting_citations":[{"cited_title":"Journal of the","cited_arxiv_id":null,"evidence_quote":"Introduces private information retrieval, the primitive that lets the auditor retrieve labels without revealing which points are being queried."},{"cited_title":", title =","cited_arxiv_id":null,"evidence_quote":"Supplies the sharper sampling-without-replacement concentration bound used in the finite-population refinement of the manipulation-cost theorem."}],"review_version":1}