1 Introduction↩︎

Whistleblowers are a crucial safeguard against organizational wrongdoing [1], from misconduct in private organizations [2], [3] to national governments [4]. Employees, who account for a significant fraction of whistleblower reports [2], frequently face retaliation from the organizations they expose [5]. This is a major deterrent to whistleblowing: perceived threat of retaliation is negatively associated with the intention to blow the whistle [6]–[8].

For this reason, confidentiality and anonymity are widely treated as central to effective whistleblower protection [9]–[11]. This is also reflected in recent legal frameworks: the EU Whistleblower Protection Directive requires confidential reporting channels and protection from retaliation [12], and the EU AI Act extends these protections to reports of AI Act infringements [13]. Yet these regimes typically specify confidentiality at the level of the reporting channel. They do not provide a formal guarantee about what an organization may infer from the auditor’s subsequent actions.

This distinction matters because anonymity can fail even when reports are submitted confidentially. Suppose an employee reports a concern to an independent auditor, and the auditor soon afterwards investigates the employee’s organization. The organization may not observe the report itself, but it observes the audit. If only a few employees had access to the relevant information, the audit can reveal who likely reported. Thus, the central privacy question is not only whether a reporting channel hides names, but whether the observable audit transcript preserves plausible deniability for each individual report.

This problem is particularly acute in AI governance. Many risks from advanced AI systems are likely to be observed first by employees and contractors inside the organizations developing them, before they are visible to external auditors, regulators, or the public. Recent proposals for frontier-AI regulation, responsible reporting, and end-to-end algorithmic auditing all rely on insider information as an important signal [14]–[16]. For such systems to be credible, a developer should not be able to infer from the timing or target of a model evaluation, compliance review, or safety audit that a particular employee filed a report.

The key insight to ensure this is that audit decisions need not be deterministic functions of report counts. If the auditor introduces randomness into the organizations selected for audit, the organization cannot be sure whether an audit was triggered by a report or by the auditor’s randomization. This gives whistleblowers plausible deniability: the ability to deny responsibility due to other alternative possibilities. More specifically, we study the design of randomized audit policies that provide a quantifiable deniability guarantee. At each timestep, an auditor receives whistleblower report and selects an audit target for follow-up. The resulting sequence of audit decisions is observable to the audited organizations. Ideally, the mechanism should protect any single report while still allowing useful audit decisions, and should impose no bound on the number of reports received between audits.

One classic approach to achieve plausible deniability is using randomized response [17]: the mechanism sometimes follows the true signal and sometimes outputs a random response. Prior work [10] adapts this idea to whistleblowing. Unfortunately, privacy pins randomized response to near-uniform auditing: at any fixed privacy level, it must select almost at random already at the first audit decision, regardless of the horizon.

Our contributions:↩︎

• Formalization (Sections 2–3). We formalize whistleblower auditing as per-report \((0, \delta)\)-differential privacy on the transcript of audit selection decisions, under a strong-adversary threat model in which the audited organization itself is the adversary. To our knowledge, no prior work targets this exact granularity — per-report adjacency, per-decision observable, fixed horizon — under this threat model.

• Negative result for randomized response (Section 4, Theorem 2). We prove that randomized response applied at the selection step — the canonical adaptation of Warner’s [17] primitive used in the economics literature on whistleblowing [10] — can never outperform uniform random auditing by more than \(\delta\) at any horizons.

• Generic reduction (Section 5, Proposition 3). We give a mechanism that reduces private auditing to private continual counting: any \((0, \delta)\)-DP continual counter plugs in by post-processing, and the audit transcript inherits the same per-report guarantee. Future improvements in continual counting can be incorporated easily.

• Concrete instantiation and utility analysis (Sections 6 and 7). We instantiate the reduction with the Toeplitz-factorization counter of [18], which was recently shown to be near-optimal for continual counting by [19]. This obtains per-report \((0, \delta)\)-DP with noise scaling as \(O(\sqrt{\log T})\). A utility theorem (Theorem 5) shows the error decays whenever the noisy report-count gap between the organization with the most reports and the runner-up organization grows faster than \(\sqrt{\log T}\) — an asymptotic improvement over randomized response.

• Empirical validation (Section 8). Simulations show that the resulting mechanism substantially outperforms randomized response in both a static gap sweep and a dynamic online auditing setting.

2 An Auditing Framework↩︎

We propose the following auditing setup. Fix an audit horizon \(T \in \mathbb{N}\) and a number of audit targets \(C \in \mathbb{N}\).¹ At each timestep \(t \in [T]\), the auditor collects any new whistleblower reports and selects an audit target. The collected reports form a report stream \({\mathbf{R}}_T = ({\mathbf{r}}_1, \ldots, {\mathbf{r}}_T) \in \mathbb{N}_0^{C \times T}\), where the \(c\)-th entry of \({\mathbf{r}}_t\), denoted \(r_{t,c}\), counts the number of new reports about audit target \(c\) at time \(t\). The sequence of audit decisions forms the audit transcript \({\mathbf{a}}_T = (a_1, \ldots, a_T) \in [C]^T\). For \(t \le T\), we write \({\mathbf{R}}_t\) and \({\mathbf{a}}_t\) for the length-\(t\) prefixes. We write \({\mathcal{R}}_T := \mathbb{N}_0^{C \times T}\) for the space of report streams and \({\mathcal{A}}_T := [C]^T\) for the space of audit transcripts.

The auditing setup must satisfy the following conditions.

We formalize Condition 1 using the following definitions of adjacency and privacy:

For the special case of \((0,\delta)\)-DP, we can demand equivalently: \(d_{\mathrm{TV}}({\mathcal{M}}({\mathbf{R}}_T),{\mathcal{M}}({\mathbf{R}}_T')) \le \delta\) for every adjacent pair (a standard fact proven in Proposition 6).

Audits based on whistleblower reports are often costly [20] so it is reasonable for an auditor to audit less frequently than whistleblowers can issue reports, motivating the following practical condition:

This condition reflects the interpretation of an audit as resolving the currently pending concerns about that audit target. Thus, at time \(t\), the relevant count for target \(c\) is not the cumulative number of reports over the entire horizon, but the number of active reports: reports received since the most recent audit of \(c\), or since \(t=1\) if \(c\) has not yet been audited.

3 A Threat Model↩︎

3.0.0.1 The adversary.

Following the strong-adversary threat model of [21], we take the natural adversary in our setting to be the audit target itself: an entity with near-complete knowledge of its internal state and reporting history. The adversary has an incentive to identify whistleblowers in order to retaliate, knows the auditing mechanism \({\mathcal{M}}\) including all parameters, and observes the realized audit transcript \({\mathbf{a}}_T\).

We instantiate the strong-adversary model as a binary adjacent-stream distinguishing game. Let \({\mathbf{R}}_T \sim {\mathbf{R}}'_T\) be two adjacent report streams that differ only in whether one report at \((t^*,c^*)\) was filed. The adversary’s task is to distinguish the two worlds \[\begin{align} H_1:{\mathbf{a}}_T \sim {\mathcal{M}}({\mathbf{R}}_T) \qquad \text{vs.} \qquad H_0:{\mathbf{a}}_T \sim {\mathcal{M}}({\mathbf{R}}'_T). \end{align}\] This captures the relevant privacy question of whether observing the audit transcript lets the audit target infer that a particular report was filed. Because the adversary is assumed to have near-complete background knowledge, bounding its distinguishing power also bounds the power of weaker adversaries.

3.0.0.2 Tests, error rates, and the prior-free guarantee.

A test for the distinguishing game above is a decision rule \(\varphi : \mathcal{A}_T \to [0,1]\), where \(\varphi({\mathbf{a}}_T)\) is the probability with which the adversary, having observed the transcript \({\mathbf{a}}_T\), rejects \(H_0\) and concludes that the additional report was filed; deterministic rules correspond to \(\varphi({\mathbf{a}}_T) \in \{0,1\}\). Its true- and false-positive rates, \[\begin{align} \mathrm{TPR}(\varphi) \mathrel{\vcenter{:}}= \mathbb{E}_{{\mathbf{a}}_T \sim {\mathcal{M}}({\mathbf{R}}_T)}\bigl[\varphi({\mathbf{a}}_T)\bigr], \qquad \mathrm{FPR}(\varphi) \mathrel{\vcenter{:}}= \mathbb{E}_{{\mathbf{a}}_T \sim {\mathcal{M}}({\mathbf{R}}'_T)}\bigl[\varphi({\mathbf{a}}_T)\bigr], \end{align}\] are the power and the size of the test \(\varphi\). By the total-variation characterization of \((0,\delta)\)-DP (Proposition 6), the privacy guarantee is equivalent to the following prior-free statement: \[\mathrm{TPR}(\varphi) \;\le\; \mathrm{FPR}(\varphi) + \delta \qquad \text{for every adjacent pair {\mathbf{R}}_T \sim {\mathbf{R}}'_T and every rule \varphi.} \label{eq:prior-free}\tag{1}\] This becomes clear after plugging in the indicator function: \(\varphi = \mathbb{1}_A\), which recovers Definition 2 with \(\epsilon = 0\), and conversely \(\mathrm{TPR}(\varphi) - \mathrm{FPR}(\varphi) \le d_{\mathrm{TV}}\bigl({\mathcal{M}}({\mathbf{R}}_T), {\mathcal{M}}({\mathbf{R}}'_T)\bigr) \le \delta\) for every \([0,1]\)-valued \(\varphi\). The corresponding interpretation thus is: no test on the transcript can detect the report at a rate exceeding its false-alarm rate by more than \(\delta\).

3.0.0.3 The advantage of the adversary.

Following the baseline-aware perspective of [21], we translate equation 1 into a statement about the adversary’s decisions by placing a weight on the two hypotheses. Fix \(\pi \in [0,1]\) and let \(W \sim \mathrm{Bern}(\pi)\) select the true hypothesis: the mechanism runs on \({\mathbf{R}}_T\) if \(W = 1\) (hypothesis \(H_1\)) and on \({\mathbf{R}}'_T\) if \(W = 0\) (hypothesis \(H_0\)), and the adversary — who knows \({\mathcal{M}}\), both streams, and \(\pi\) — observes \({\mathbf{a}}_T\) and guesses \(W\). The success of a rule \(\varphi\) is its probability of guessing correctly in this experiment; by the law of total probability, \[\begin{align} \mathrm{succ}_{\pi,{\mathbf{R}}_T,{\mathbf{R}}'_T}(\varphi;{\mathcal{M}}) \mathrel{\vcenter{:}}= \Pr[\text{guess} = W] = \pi\,\mathrm{TPR}(\varphi) + (1-\pi)\bigl(1 - \mathrm{FPR}(\varphi)\bigr). \end{align}\] The weight \(\pi\) may be read either as the adversary’s prior belief that the report was filed, or as the frequency of the reporting event across the scenarios the guarantee must cover; all bounds below hold uniformly in \(\pi\), so no assumption on \(\pi\) is made. Without observing \({\mathbf{a}}_T\), the best achievable success is that of the better constant rule (\(\varphi \equiv 1\) or \(\varphi \equiv 0\)): \[\begin{align} \mathrm{base}_{\pi} \mathrel{\vcenter{:}}= \max\{\pi, 1-\pi\}. \end{align}\] The additive advantage of \(\varphi\) is its improvement over this baseline, \[\begin{align} \mathrm{adv}_{\pi,{\mathbf{R}}_T,{\mathbf{R}}'_T}(\varphi;{\mathcal{M}}) \mathrel{\vcenter{:}}= \mathrm{succ}_{\pi,{\mathbf{R}}_T,{\mathbf{R}}'_T}(\varphi;{\mathcal{M}}) - \mathrm{base}_{\pi}, \end{align}\] so that any rule which ignores the transcript has advantage at most zero. The mechanism’s advantage at weight \(\pi\) is the largest such improvement over all adjacent streams and decision rules: \[\begin{align} \mathrm{adv}_{\pi}({\mathcal{M}}) \mathrel{\vcenter{:}}= \sup_{{\mathbf{R}}_T \sim {\mathbf{R}}'_T}\, \sup_{\varphi}\, \mathrm{adv}_{\pi,{\mathbf{R}}_T,{\mathbf{R}}'_T}(\varphi;{\mathcal{M}}). \end{align}\]

We adopt \((0,\delta)\)-DP as the operational privacy definition for the rest of the paper. By Theorem 1, no strong adversary — including the audit target itself — can improve its probability of correctly determining whether a single report was filed by more than \(\delta/2\), whichever prior it holds.

3.0.0.4 Why this threat model is different.

Our setting differs from prior work in two ways. First, the privacy unit is a single report, but the public observable is the entire sequence of audit decisions in \([C]\), rather than a noisy count vector or histogram. Second, prior whistleblower mechanisms [10], [17] randomize each report at submission time under an untrusted-auditor model. We instead trust the auditor with the reports but treat the audit transcript as public and observed by a powerful insider adversary. Thus privacy must hold for a report’s effect on the full audit transcript over horizon \(T\), not merely for a privatized message.

3.0.0.5 Utility.

If privacy were not a concern, we assume the auditor would like to select the audit target with the largest number of whistleblower reports to audit next. To quantify this, we define the error of an auditing mechanism \({\mathcal{M}}\) as the probability it does not select the audit target with the current largest number of reports.

We now have a concrete way to compare mechanisms. For any mechanism \({\mathcal{M}}\) that satisfies Conditions 1 and 2, the auditor offers a fixed per-report DP parameter \(\delta\), which implies a baseline-independent additive-advantage bound of \(\delta/2\) (Theorem 1). For this privacy level, a better mechanism has strictly lower error, as defined in Definition 4. The next natural questions are what guarantees exist for existing mechanisms, and whether we can do better.

4 Randomized Response as a Natural Baseline↩︎

A natural baseline is to apply randomized response at the audit-selection step [17]: with some probability \(p_{\mathrm{rand}}\) the auditor ignores the reports and selects an audit target uniformly at random, and otherwise selects the target with the largest current report count. Prior work has applied this to whistleblowing [10]. The mechanism is described in Algorithm 6.

Randomized response satisfies \((0,\, 1 - p_{\mathrm{rand}}^{\,T})\)-DP at horizon \(T\) (Proposition 11), and its one-step error is at most \(\frac{C-1}{C}\,p_{\mathrm{rand}}\), with equality whenever the current maximizer is unique (Proposition 12). Calibrating through Proposition 11 requires \(p_{\mathrm{rand}} \ge (1-\delta)^{1/T}\), which tends to \(1\) as the horizon grows; this is the calibration we use for the experimental baseline in Section 8. However, a smaller exploration probability also cannot reconcile a fixed privacy level with informative audit selection: the privacy requirement pins randomized response to within \(\delta\) of uniform random auditing, already at the first audit decision. The following theorem shows this:

5 A Generic Reduction to Private Continual Counting↩︎

Randomized response solves the privacy problem at the selection step; however, by Theorem 2 this pins its error within \(\delta\) of uniform random auditing, however large the report gap. Using continual counting mechanisms, we instead privatize the report counts, so that a growing gap can outrun the noise. These mechanisms take a stream of non-negative counts and output noisy running totals at each step:

5.1 A Generic Private Auditing Algorithm↩︎

We now give a generic reduction from private continual counting to private auditing (Algorithm 2). Given any continual-counting mechanism \({\mathcal{C}}\), the auditing mechanism \(\mathcal{M}_{{\mathcal{C}}}\) maintains, for each audit target, an independent noisy counter for the number of reports received since that target was last audited. At each time step, the auditor observes the noisy pending counts and audits a target with maximum noisy count. The mechanism implements Condition 2 (Report Reset) by restarting an audit target’s counter after that target is audited.

The privacy argument then reduces to the privacy of the affected continual counter, with target selection and the audit transcript obtained from the noisy counter outputs.

5.2 Privacy Guarantee↩︎

6 Concrete Continual-Counting Instantiation↩︎

We now construct a continual-counting mechanism calibrated for \((0,\delta)\)-DP.

6.1 Gaussian Matrix-Mechanism Counter↩︎

Let \({\mathbf{A}}^{(T)}\in\{0,1\}^{T\times T}\) denote the lower-triangular all-ones prefix-sum matrix, i.e. \({\mathbf{A}}^{(T)}_{i,j} = \mathbf{1}[i\ge j]\). Thus the exact vector of prefix sums of \({\mathbf{x}}\in\mathbb{N}_0^T\) is \({\mathbf{A}}^{(T)}{\mathbf{x}}\). Suppose we are given matrices \({\mathbf{B}}^{(T)},{\mathbf{C}}^{(T)}\in\mathbb{R}^{T\times T}\) such that \({\mathbf{B}}^{(T)}{\mathbf{C}}^{(T)} = {\mathbf{A}}^{(T)}\). We define the associated Gaussian matrix-mechanism counter by \[\label{eq:generic-counter} {\mathcal{C}}({\mathbf{x}}) := {\mathbf{B}}^{(T)}\!\bigl({\mathbf{C}}^{(T)}{\mathbf{x}}+{\mathbf{z}}\bigr), \; {\mathbf{z}}\sim \mathcal{N}(0,\sigma^2 {\mathbf{I}}_T).\tag{2}\]

For privacy, the key quantity is the largest column norm of the encoder: \[\label{eq:definition95mt} M_T \;:=\; \max_{j\in[T]} \|{\mathbf{C}}^{(T)}{\mathbf{e}}_j\|_2\tag{3}\]

The proof (Appendix 16) follows by applying Lemma 3 to the encoded shift \({\mathbf{C}}^{(T)}{\mathbf{e}}_{j^*}\), whose norm is at most \(M_T\), and post-processing through \({\mathbf{B}}^{(T)}\).

6.2 Concrete Instantiation via Toeplitz Factorization↩︎

To maximize utility, we use the Toeplitz factorization of [18] and [19], which is near-optimal for continual counting.

We define the \(T \times T\) lower-triangular Toeplitz matrices \({\mathbf{C}}^{(T)}\) (encoder) and \({\mathbf{B}}^{(T)}\) (decoder) by \[\label{eq:def95toeplitz95matrices} {\mathbf{C}}^{(T)}_{i,j} = {\mathbf{B}}^{(T)}_{i,j} := \begin{cases} f_{i-j} & \text{if } i \ge j, \\ 0 & \text{if } i < j. \end{cases}\tag{4}\] where the sequence \((f_k)_{k \ge 0}\) is given by \[f_0 = 1, \qquad f_k = \Bigl(1 - \frac{1}{2k}\Bigr)f_{k-1} \quad\text{for } k \ge 1\]

The convolution properties of this sequence yields \({\mathbf{B}}^{(T)}{\mathbf{C}}^{(T)}={\mathbf{A}}^{(T)}\) (Lemma 1 & 2 [18]).

Instantiating Algorithm 2 with this Toeplitz-based counter – running one independent copy per organization and restarting after each audit – yields our final mechanism, which satisfies \((0,\delta)\)-DP. This factorization was shown to be optimal among lower-triangular Toeplitz factorizations for continual counting [19]. We use this instantiation throughout the remainder of the paper.

7 Utility Guarantee↩︎

We now derive a utility guarantee (Definition 4) for the above mechanism. To begin, define the noise history of the mechanism.

7.1 Utility Theorem↩︎

For a proof, see Appendix 17.

7.2 Remarks↩︎

8 Experiments↩︎

We compare Toeplitz Continual Auditing (TCA), with Randomized Response [17], uniformly random auditing, and non-private (greedy) auditing in two simulation studies. All private mechanisms are calibrated to the same per-report \((0, \delta)\)-DP guarantee over the relevant horizon; full details can be found in Appendix 18.

8.0.0.1 Experiment 1: Static gap sweep.

Theorem 5 predicts that TCA’s error should decrease as the effective gap between the true leader and its challengers grows, with noise scale governed by \(M_T=\mathcal{O}(\sqrt{\log T})\). To isolate this effect, we consider a single audit decision with one leading organization \(c_0\) having active count \(n_0=\Delta\) and all other organizations having active count \(n_c=0\). We vary \(\Delta\) and estimate the mis-selection probability \(\Pr[a \neq c_0]\). Figure 3 (a) shows the expected qualitative pattern: TCA’s error decreases rapidly as the gap grows, while randomized response is essentially insensitive to the gap. The advantage increases with the number of audited organizations (Appendix Figures 7–9).

Experiment 2: Dynamic auditing. The static experiment isolates a single decision, but real auditing is online: each audit resets the selected organization’s active count, so different mechanisms induce different future states. We therefore simulate a streaming report process over a fixed horizon \(T\) and measure the active count deficit: \(d_t^{\mathcal{M}} := \max_{c} n^{\mathcal{M}}_{t,c} - n^{\mathcal{M}}_{t, a_t}\), computed before the reset at time \(t\) — the regret of \({\mathcal{M}}\)’s selection against the best available active count. Figure 3 (b) shows that TCA remains close to the greedy auditor, while randomized response accumulates much larger deficits.

9 Limitations↩︎

First, the per-whistleblower guarantee degrades linearly in the number of reports \(k\) under group privacy (Lemma 2, Corollary 1). Second, the threat model assumes that the auditor is a trusted entity that will not leak the private report counts. While this is a standard threat model assumption in centralized differential privacy, it may be worth strengthening the threat model by omitting a trusted auditor. Mechanisms that satisfy local differential privacy [23] such as the randomized response approach described in Section 4 would likely be sufficient to guarantee privacy under this threat model. Third, we were unable to obtain any data from a real-world auditing setup. An evaluation with real-world data could expose additional practical considerations that may have been missed in this work.

10 Related Work↩︎

10.0.0.1 Whistleblower mechanisms in economics and computer science.

The economics literature has long studied the design of intervention rules that protect informants from retaliation [10], [24], with randomized response [17] supplying the canonical garbling primitive. Empirical auditing work confirms that whistleblower reports causally affect downstream audit intensity [20]. On the systems side, deployed pipelines such as SecureDrop and academic designs Dissent and Riposte [25] target sender-anonymity using mix-nets, DC-nets, or PIR. Recent cryptographic work establishes that anonymous transfer without trusted parties is fundamentally hard [26], [27], motivating our information-theoretic, DP-based approach in which deniability is provided by the auditor’s randomized policy rather than by network-level anonymity.

10.0.0.2 Differential privacy under continual observation.

Our mechanism builds on the model introduced by [28] and refined by [29], which gives polylogarithmic-error counters and top-\(k\) extensions. Recent matrix-factorization mechanisms achieve near-optimal constants [18], [30] and admit efficient streaming implementations [19], [31]. We instantiate our generic counter-and-reset scheme with a Toeplitz factorization to obtain \(O(\sqrt{\log T})\) noise.

10.0.0.3 Private selection and online decision making.

At each audit step we solve a private argmax over noisy counters, a problem whose canonical solutions are the exponential mechanism [32], Report-Noisy-Max [22], and Permute-and-Flip [33]. When candidate scores are themselves DP outputs, [34] and [35] give general selection frameworks. Closest in structure to our work are differentially private multi-armed bandit algorithms that maintain per-arm tree-counters [36]. However, they differ on three concrete axes: 1.  their adjacency unit is a single pull or reward (vs. a single report on our transcript); 2.  their objective is cumulative regret over an exploration horizon (vs. count-leader identification at every step under a fixed \((0, \delta)\) constraint); and 3.  their feedback model uses stochastic rewards after each pull to update arm estimates (vs. direct report counts with no reward channel from the audit). Bandit regret bounds therefore do not transfer to deniability guarantees, and our utility theorem (Theorem 5) has no analogue in the bandit literature.

10.0.0.4 Privacy semantics and AI governance auditing.

Translating \((\epsilon,\delta)\)-DP into operational deniability guarantees has recently been unified across re-identification, attribute-inference, and reconstruction risks via \(f\)-DP [21]; this is also the framework that links DP to GDPR-style “singling out” [37]. Empirical auditing of DP claims complements this view [38]. In AI governance, calls for external scrutiny of frontier systems [15], [16], responsible reporting frameworks [16], and end-to-end algorithmic-audit processes [14] all envision insider information as a key signal. Our work supplies the missing technical primitive: an auditor policy whose randomization gives whistleblowers a quantifiable deniability guarantee even after many rounds of audits—he setting in which randomized response is provably pinned within \(\delta\) of uniform auditing at any horizon.

11 Conclusion↩︎

We formalized an auditing setup for whistleblower anonymity and showed that the canonical primitive, randomized response, cannot improve on uniform random auditing by more than \(\delta\) at any fixed \((0,\delta)\)-level, at any horizon. We then proposed a generic counter-and-restart mechanism whose privacy is inherited by post-processing from any \((0,\delta)\)-DP continual-counting mechanism, and instantiated it with the Toeplitz factorization of [18] and [19], yielding per-report \((0,\delta)\)-DP with noise calibrated by \(M_T = \mathcal{O}(\sqrt{\log T})\). Our utility theorem shows that the error decays whenever the effective leader–challenger gap grows faster than \(\sqrt{\log T}\). Natural extensions include tightening the per-whistleblower guarantee for multiple reports beyond group privacy, and empirical evaluation on real audit pipelines. While this mechanism is intended to make reporting channels more credible by limiting what audit transcripts reveal about individual reports, the guarantee applies only under the stated threat model and should not be taken to protect against operational failures such as access-log leaks, non-anonymous reporting channels, overly narrow audit scopes, or retaliation based on side information.

Acknowledgments↩︎

This research was enabled by support provided by Mila – Québec AI Institute and by École Polytechnique de Montréal. LR acknowledges support from the Engineering and Physical Sciences Research Council with grant number EP/S021566/1. MJK is supported through the Canada CIFAR AI Chair program and by a grant from the IVADO R10 cluster.

12 Threat Model Notation↩︎

Table 1 summarizes how the record-level DP objects of [21] instantiate in our whistleblower-auditing setting; see Remark 8 for the formal correspondence.

13 Additional Proofs↩︎

14 Baselines↩︎

14.1 Greedy Auditing↩︎

The proof follows by construction.

14.2 Uniformly Random Auditing↩︎

14.3 Randomized Response↩︎

We first show the following sufficient condition for \((0, \delta)\)-DP:

We further want to prove the following statement on the error bound.

14.3.1 Proof of Theorem 2 (Privacy of Randomized Response↩︎

We now prove the main result of section 4:

15 Proof of Proposition 3 (Privacy of Algorithm 2)↩︎

We give the full proof of Proposition 3; the sketch appears in Section 5.2.

16 Proof of Proposition 4↩︎

Before proving Proposition 4 we state a useful textbook Lemma.

17 Proof of Theorem 5 (Utility)↩︎

The proof of Theorem 5 in Section 7.1 relies on the following Lemma.

18 Experimental Details↩︎

All experiments were run on a standard laptop/CPU machine; no GPU was used. The full experiment suite completes in under 10 minutes.

18.1 Experiment 1 – Mis-selection over gap↩︎

The goal of this set of experiments is to show that TCA’s mis-selection rate decays sharply with the gap \(\Delta\) between the leader and the runner-up, while RR is essentially gap-independent and saturates near \((C-1)/C\). The sweep over the number of audit targets \(C\) sweep demonstrates that the qualitative picture is robust across pool sizes spanning 1.5 orders of magnitude; the gap required to suppress mis-selection grows only mildly with \(C\) (roughly like \(\sigma\sqrt{2\ln C}\), the scale of the maximum of \(C-1\) Gaussians).

18.1.0.1 Setup.

We fix a single-shot configuration: each audit target has been observed for exactly \(L\) steps since its last reset, and the pending counts are \(n_0 = \Delta\) for the leader (audit target \(c_0)\) and \(n_c = 0\) for all other audit targets.

For each \((L, \delta, \Delta)\) we run \(S = 1000\) Monte-Carlo trials and estimate \(\Pr[a \neq 0]\). For TCA we exploit that the total noise on each audit target at run length \(L\) is Gaussian with variance \(\sigma^2 \sum_{k=0}^{L-1} f_k^2\), drawn independently per audit target. Greedy and uniform-random mis-selection probabilities are computed in closed form (0 if \(\Delta>0\), \((C-1)/C\) if \(\Delta=0\) for greedy; \((C-1)/C\) always for uniform).

18.1.0.2 Hyperparameters.

Calibrated noise scales are independent of \(C\): TCA’s \(\sigma\) depends only on \(L\) and \(\delta\), and likewise \(p_{\mathrm{rand}}\) for RR.

18.2 Experiment 2 – Dynamic Utility Auditing↩︎

We evaluate the mechanisms in an online report stream with report resets. The goal of this experiment is to measure how much utility is lost over time when using a private auditing mechanism rather than the non-private greedy baseline.

18.2.0.1 Mechanisms.

We compare four auditing mechanisms:

1. Toeplitz Counter Auditing (TCA). Each audit target runs an independent Toeplitz continual-counting instance. At each timestep the mechanism audits the audit target with the largest noisy active-count estimate. After an audit, the selected audit target’s active count and private counter instance are reset with fresh independent randomness.

2. Randomized response auditing (RR). With probability \(p_{\mathrm{rand}}=(1-\delta)^{1/T}\), the mechanism audits a uniformly random audit target. With probability \(1-p_{\mathrm{rand}}\), it audits an audit target with maximal active count, with ties broken uniformly at random. After the audit, the selected audit target’s active count is reset. This reset step is important: RR is evaluated under the same active-report auditing semantics as TCA and Greedy.

3. Greedy auditing. The mechanism audits an audit target with maximal active count, with ties broken uniformly at random. After the audit, the selected audit target’s active count is reset. This is a non-private upper baseline.

4. Uniform random auditing. The mechanism audits a uniformly random audit target, ignoring reports. After the audit, the selected audit target’s active count is reset. This is a privacy-only lower baseline.

18.2.0.2 Privacy calibration.

For each run, the private mechanisms are calibrated to the same transcript-level privacy guarantee \((0,\delta)\) over the same certified horizon \(T\). TCA uses the Gaussian Toeplitz calibration \[\sigma = \frac{M_T}{2\Phi^{-1}((1+\delta)/2)},\] where \(M_T\) is the Toeplitz encoder sensitivity. Randomized response uses \[p_{\mathrm{rand}} = (1-\delta)^{1/T}.\] Thus both private mechanisms are compared under the same fixed-horizon privacy requirement.

18.2.0.3 Report stream.

We generate reports from an independent Poisson model. At each timestep \(t\), audit target \(0\) receives reports \[x_{t,0} \sim \mathrm{Poisson}(\lambda_{\mathrm{lead}}),\] and each other audit target \(c\in\{1,\ldots,C-1\}\) receives reports \[x_{t,c} \sim \mathrm{Poisson}(\lambda_{\mathrm{other}}).\] All draws are independent across timesteps and audit targets. Although audit target \(0\) has the highest arrival rate in expectation, the audit target with maximal active count need not be audit target \(0\) at a given timestep, because audits reset active reports.

18.2.0.4 Mechanism-specific active counts.

Each mechanism \(\mathcal{M}\) maintains its own active-count vector \[n_t^{\mathcal{M}} = (n_{t, 1}^{\mathcal{M}},\ldots,n_{t, C}^{\mathcal{M}}),\] because different mechanisms audit different audit targets and therefore induce different reset histories. At each timestep \(t\), the new report vector \(x_t\) is added to that mechanism’s active counts. The mechanism then selects an audited audit target \(a_t^{\mathcal{M}}\). All utility metrics are computed before applying the reset. Finally, the selected audit target is reset: \[n_{t,a_t^{\mathcal{M}}}^{\mathcal{M}} \leftarrow 0.\] For TCA, the selected audit target’s private counter instance is also restarted.

18.2.0.5 Metrics.

Our primary metric is the active-count deficit \[d_t^{\mathcal{M}} := \max_{c\in[C]} n_{t,c}^{\mathcal{M}} - n_{t,a_t^{\mathcal{M}}}^{\mathcal{M}}.\] This measures how many fewer active reports are resolved by \(\mathcal{M}\)’s selected audit than by the best available audit under the same reset history. We report the running average deficit \[\bar d_t^{\mathcal{M}} := \frac{1}{t}\sum_{s=1}^t d_s^{\mathcal{M}}.\] We also compute a normalized deficit, \[\eta_t^{\mathcal{M}} := \frac{d_t^{\mathcal{M}}}{\max_{c\in[C]} n_{t,c}^{\mathcal{M}}+1},\] and its running average \[\bar\eta_t^{\mathcal{M}} := \frac{1}{t}\sum_{s=1}^t \eta_s^{\mathcal{M}}.\] The normalized version is useful for comparing regimes with different report volumes. Finally, we record the number of reports resolved by the selected audit, \[u_t^{\mathcal{M}} := n_{t, a_t^{\mathcal{M}}}^{\mathcal{M}},\] and its running average \[\bar u_t^{\mathcal{M}} := \frac{1}{t}\sum_{s=1}^t u_s^{\mathcal{M}}.\] Lower values of \(\bar d_t^{\mathcal{M}}\) and \(\bar\eta_t^{\mathcal{M}}\) indicate better performance, while higher values of \(\bar u_t^{\mathcal{M}}\) indicate that audits are resolving more active reports.

18.2.0.6 Implementation details.

Unless otherwise stated, we use \[C=50,\qquad T=1000,\qquad \delta=0.10,\qquad \lambda_{\mathrm{lead}}=1.0,\qquad \lambda_{\mathrm{other}}=0.2.\] We average over \(100\) independent random seeds. For each seed, the same generated report stream is fed to each mechanism, but each mechanism maintains its own active counts and reset history. We plot the mean running metric across seeds with.

18.2.0.7 Interpretation.

Greedy auditing has zero active-count deficit by construction. Uniform random auditing ignores reports and therefore provides a lower utility baseline. Randomized response is expected to behave close to uniform random auditing in long horizons, because the fixed-horizon privacy calibration makes \(p_{\mathrm{rand}}\) close to one. TCA should accumulate substantially less active-count deficit when the active-count gaps are large relative to the calibrated counter noise.

19 Additional Results↩︎

19.1 Experiment 1 with \(C \in \{20,50,200\}\)↩︎

We vary the number of audit targets in the setup of Experiment 1 and show the results in Figures 7-9. TCA curves move closer to uniform random auditing, but still have low mis-selection rates as the report gap grows.

20 Operationalization↩︎

Our framework is defined by a small number of operational choices regarding the audit targets \(c \in [C]\), the audit horizon \(T\) and the target per-report deniability level \(\delta\). We describe these choices in a frontier-AI auditing setting, where confidential reports from employees or contractors may inform follow-up audits, model evaluations, or compliance reviews.

In this setting, the auditor may be a public authority, an AI-safety institute, or a trusted third-party evaluator. The adversary is the audited developer, which observes the audit transcript and may know substantial internal context

The utility theorem can also be read operationally. If the true leading audit target has effective gap at least \(g\) over every challenger, then Theorem 5 implies \[\begin{align} \Pr[a_t \neq c_t^* \mid \mathcal{H}_{t-1}] \leq (C-1)\Phi\!\left(-\frac{g}{\sqrt{2}\sigma}\right). \end{align}\] Thus, the main implementation trade-offs are explicit: larger \(C\) requires distinguishing the leader from more challengers; smaller \(\delta\) gives stronger deniability but increases noise; and larger \(T\) has only a logarithmic effect on the noise scale.

References↩︎

---

1. The audit unit \(c\) need not be an entire legal organization. It can denote a sub-team, product line, safety process, or other regulator-chosen unit.↩︎