Technical Summary: Plausible Deniability Guarantees for Whistleblowers

Problem Statement

Whistleblowers serve as a critical safeguard against organizational misconduct, yet the fear of retaliation significantly deters reporting. While existing legal frameworks (e.g., the EU Whistleblower Protection Directive) mandate confidential reporting channels, they fail to provide formal guarantees regarding what an organization can infer from an auditor's subsequent actions.

The core privacy challenge arises when an organization, acting as a "strong adversary," observes the sequence of audit decisions (the audit transcript) but not the reports themselves. If an auditor investigates an organization shortly after a report is filed, and only a few employees had access to the relevant information, the organization can infer the identity of the whistleblower. The paper formalizes the need for plausible deniability: ensuring that the observable audit transcript does not allow an adversary to distinguish between a world where a specific report was filed and a world where it was not, beyond a negligible advantage.

Existing approaches, such as Randomized Response (adapting Warner's 1965 mechanism to whistleblowing), suffer from a fundamental utility-privacy trade-off. They force the auditor to select audit targets nearly uniformly at random to satisfy privacy constraints, rendering the audit process unresponsive to the actual volume of reports. Furthermore, standard differential privacy (DP) mechanisms often do not directly target the specific threat model where the audited entity itself is the adversary observing the full sequence of decisions.

Methodology

Formal Framework

The authors propose an auditing framework defined over a horizon $T$ with $C$ audit targets.

• Input: A stream of report counts $R_T = (r_1, \dots, r_T)$, where $r_{t,c}$ is the number of new reports for target $c$ at time $t$.
• Output: An audit transcript $a_T = (a_1, \dots, a_T)$, where $a_t \in [C]$ is the target selected for audit at time $t$.
• Privacy Definition: The paper adopts (0, $\delta$)-Differential Privacy (DP) with respect to per-report adjacency. Two report streams are adjacent if they differ by exactly one report at a specific time and target.
• Threat Model: The adversary is the audit target itself, possessing near-complete internal knowledge and observing the full transcript $a_T$. The goal is to bound the adversary's advantage in distinguishing whether a specific report was filed.
• Utility Metric: The error is defined as the probability that the mechanism fails to select the target with the highest active count (reports received since the last audit of that target).

The Negative Result: Randomized Response

The paper proves that applying Randomized Response (RR) at the selection step—where the auditor ignores reports with probability $p_{rand}$ and audits a random target, otherwise auditing the target with the highest count—cannot outperform uniform random auditing by more than $\delta$.

• Theorem 2: For any horizon $T$, if RR satisfies $(0, \delta)$-DP, the probability of selecting the wrong target (when a unique maximizer exists) is bounded below by $\frac{C-1}{C} - \delta$.
• Implication: RR is "gap-insensitive." Even if the report gap between the leader and the runner-up is massive, the error remains high because the privacy requirement forces the mechanism to explore (audit randomly) almost always.

The Proposed Solution: Reduction to Private Continual Counting

To overcome the limitations of RR, the authors propose a generic reduction from private auditing to private continual counting.

1. Mechanism Design (Algorithm 1):
   • For each audit target $c$, maintain an independent instance of a $(0, \delta)$-DP continual counter.
   • At each timestep, feed the new report counts for each target into its respective counter.
   • Select the target with the highest noisy count (the counter's output).
   • Reset Condition: Upon auditing a target, restart its counter instance and reset its active count to zero. This ensures the privacy of past reports is not compromised by future decisions.
2. Privacy Guarantee: The audit transcript is a post-processing of the counter outputs. Since the counters satisfy $(0, \delta)$-DP and the reset mechanism ensures that a single report affects only one active counter instance, the entire transcript inherits the $(0, \delta)$-DP guarantee.
3. Concrete Instantiation: The authors instantiate this framework using the Toeplitz-factorization counter (Fichtenberger et al., 2023; Dvijotham et al., 2024). This mechanism achieves noise scaling of $O(\sqrt{\log T})$, which is near-optimal for continual counting.

Utility Analysis

The paper derives a utility theorem (Theorem 6) showing that the selection error decays as the effective gap between the true leader and challengers grows.

• The effective gap includes the true report count difference plus the accumulated noise difference.
• Unlike RR, the error of the proposed mechanism vanishes whenever the noisy report gap grows faster than $\sqrt{\log T}$. This allows the mechanism to be highly responsive to report volumes while maintaining strict privacy.

Key Contributions

1. Formalization: The paper formalizes whistleblower auditing as per-report $(0, \delta)$-DP on the audit transcript under a strong-adversary model where the target is the adversary.
2. Negative Result for RR: It proves that Randomized Response is fundamentally limited, being pinned to near-uniform auditing regardless of the horizon or report gap.
3. Generic Reduction: It establishes a reduction from private auditing to private continual counting, allowing any $(0, \delta)$-DP counter to be used as a plug-in component.
4. Concrete Mechanism (TCA): By instantiating the reduction with Toeplitz factorization, the authors create a mechanism (Toeplitz Continual Auditing, TCA) that achieves $(0, \delta)$-DP with noise scaling $O(\sqrt{\log T})$.
5. Utility Theorem: It provides a theoretical bound showing that selection error decays as the report gap increases, a significant improvement over the constant error of RR.

Results

• Theoretical: The utility theorem demonstrates that the proposed mechanism's error approaches zero as the gap between the leading organization and its competitors grows, whereas RR's error remains constant and high.
• Empirical: Simulations in both static (gap sweep) and dynamic (online auditing) settings confirm the theoretical findings:
  • Static: TCA's mis-selection rate drops rapidly as the report gap increases, while RR remains insensitive to the gap.
  • Dynamic: In an online setting with report resets, TCA maintains a significantly lower "active-count deficit" (regret) compared to RR and uniform random auditing, approaching the performance of a non-private greedy baseline.

Significance and Claims

The paper claims to provide the first formal, quantifiable deniability guarantee for whistleblowers that operates effectively over long horizons without sacrificing utility.

• Credibility: By ensuring that audit decisions cannot be deterministically linked to specific reports, the mechanism makes reporting channels more credible to potential whistleblowers who fear retaliation.
• AI Governance: The work is particularly motivated by the need for credible internal reporting in AI governance, where insider information is a key signal for safety audits. The mechanism ensures that a developer cannot infer that a specific employee filed a report based on the timing or target of a model evaluation.
• Limitations: The authors modestly note that the per-whistleblower guarantee degrades linearly with the number of reports filed ($k\delta$) and that the model assumes a trusted auditor who does not leak private counts. They acknowledge that real-world operational failures (e.g., access log leaks) are outside the scope of this cryptographic/algorithmic guarantee.

In summary, the paper argues that while Randomized Response is a canonical privacy primitive, it is insufficient for high-stakes auditing where utility is paramount. By leveraging advances in continual counting, it is possible to construct auditing policies that offer strong, formal plausible deniability while remaining highly responsive to the data they are designed to protect.