Securing Unbounded Differential Privacy Against Timing Attacks
Zachary Ratliff, Salil Vadhan · 2025
Read Securing Unbounded Differential Privacy Against Timing Attacks by Zachary Ratliff, Salil Vadhan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07868.txt.
Introduction
Zachary Ratliff and Salil Vadhan protect private data systems against a subtle leak: how long a program runs, in a 2025 paper. A program that answers questions about a data set can reveal facts through its running time, even when its answers are safe.
The strong form of protection they study guards both the output and the runtime. Earlier fixes for the unbounded case, where data set size itself is secret, added fixed error or slowed programs down. Ratliff and Vadhan show the needed error depends on the computing model. With random numbers available at unit cost, the error can shrink as data grows. With only coin flips, some fixed error is unavoidable. Their conversions keep programs efficient.
Catalog record
| CREATOR | Zachary Ratliff, Salil Vadhan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 70 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-07868
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Securing Unbounded Differential Privacy Against Timing Attacks Zachary Ratliff, Salil Vadhan Abstract Recent works [ BDDNT23 , RV24 ] have started to theoretically investigate how we can protect differentially private programs against timing attacks, by making the joint distribution the output and the runtime differentially private (JOT-DP). However, the existing approaches to JOT-DP have some limitations, particularly in the setting of unbounded DP (which protects the size of the dataset and applies to arbitrarily large datasets). First, the known conversion of pure DP programs to pure JOT-DP programs in the unbounded setting [ BDDNT23 ] (a) incurs a constant additive increase in error probability (and thus does not provide vanishing error as n → ∞ n\to\infty ) (b) produces JOT-DP programs that fail to preserve the computational efficiency of the original pure DP program and (c) is analyzed in a toy computational model in which the runtime is defined to be the number of coin flips. For approximate JOT-DP, an efficient conversion with vanishing error in the RAM model is known [ HPN11 , RV24 ] , but only applies to programs that run in O ( n ) O(n) time on datasets of size n n , as linear runtime is implied by “timing stability,” the timing analogue of global sensitivity. In this work, we overcome these limitations. Specifically: 1. We show that the error required for pure JOT-DP in the unbounded setting depends on the model of computation. • In a randomized RAM model where the dataset size n n is given (or can be computed in constant time) and we can generate random numbers (not just random bits) in constant time, polynomially small error probability is necessary and sufficient. • If n n is not given or we only have a random-bit generator, an (arbitrarily small) constant error probability is necessary and sufficient. 2. The aforementioned positive results are proven by efficient procedures to convert any pure JOT-DP program P P in the upper-bounded setting to a pure JOT-DP program P ′ P^{\prime} in the unbounded setting, such that the output distribution of P ′ P^{\prime} is γ \gamma -close in total variation distance to that of P P , where γ \gamma is either an arbitrarily small constant or polynomially small, depending on the model of computation. 1 Introduction Timing side-channel attacks , in which an attacker measures the runtime of an algorithm to infer otherwise private information, have proven to be a highly effective method for breaking modern cryptographic systems. These attacks have been used to extract signing keys from cryptographic processors [ Koc96 ] , recover private keys from remote TLS servers [ BB05 , BT11 , AFP13 , AP16 ] , and leak sensitive information from hidden hardware states (e.g., Spectre [ KHF+20 ] and Meltdown [ LSG+18 ] ). Early research on timing attacks focused on identifying and mitigating timing side-channels in cryptographic implementations. However, the growing adoption of differential privacy (DP) [ DMNS06 ] —an influential framework for privacy-preserving data analysis, used in applications such as analyzing user behavior [ MDH+20 , G+16 ] and releasing aggregate statistics [ Abo18 , ABC+20 ] —has introduced new avenues for timing attacks. Differential privacy achieves its protections by adding carefully calibrated noise to computations, ensuring that the output of a query is not too sensitive to the addition or removal of a single data point. However, researchers have already identified that the runtime of user-defined queries [ HPN11 , AKM+15 ] and noise samplers [ JMRO21 ] can severely violate the promises of differential privacy. Thus, recent research has begun to theoretically investigate timing-private DP programs, which ensure that the joint distribution of the output and runtime satisfies differential privacy [ BDDNT23 , RV24 ] . Definition 1.1 ( (\varepsilon,\delta) -Joint Output/Timing Privacy [ BDDNT23 , RV24 ] ) . Let \mathcal{X} be a dataset space with an adjacency relation, \mathcal{E} be a set of execution environments for a computational model, \mathcal{Y} be an output space, \mathcal{T}\subseteq\mathbb{R}^{\geq 0} a set of possible runtimes in the model, and P:\mathcal{X}\times\mathcal{E}\rightarrow\mathcal{Y}\times\mathcal{E} a randomized program in the model. Then we say that P is (\varepsilon,\delta) - jointly output/timing-private (JOT-DP) if for all adjacent x,x^{\prime}\in\mathcal{X} , all pairs of input-compatible execution environments \mathtt{env},\mathtt{env}^{\prime}\in\mathcal{E} , and all S\subseteq\mathcal{Y}\times\mathcal{T} \displaystyle\Pr[(Y,T)\in S]\leq e^{\varepsilon}\cdot\Pr[(Y^{\prime},T^{\prime})\in S]+\delta where Y=\mathtt{out}(P(x,\mathtt{env})) and T_{\scriptscriptstyle P}(x,\mathtt{env}) denote the output and runtime of P respectively (and defined similarly for Y^{\prime} and T^{\prime} ). When \delta=0 , we say that P achieves pure JOT-DP, and when \delta>0 , we say that P achieves approximate JOT-DP. The dataset space \mathcal{X} and its adjacency relation determine whether the program achieves JOT-DP in the bounded (the number of records n=|x| in a dataset x\in\mathcal{X} is fixed and publicly known), unbounded ( |x| can be arbitrarily large and is intended to remain private), or upper-bounded (upper bound on |x| is publicly known, but |x| should remain private subject to the upper bound) settings. The above notion of timing privacy requires that the joint distribution of the program P ’s output and runtime when executed in the environment \mathtt{env} satisfies the standard definition of differential privacy. Informally, the execution environment represents the state of the computer before execution, for example, the contents of memory. We give further background on execution environments in Section 2 . Beyond its role in data analysis, DP has recently emerged as a valuable tool for designing more practical and efficient cryptographic systems. For instance, metadata-private messaging systems have leveraged weaker DP guarantees to improve performance over purely cryptographic approaches [ LGZ18 , VDHLZZ15 ] . Similarly, the concept of differential obliviousness , which extends DP-like guarantees to the memory access patterns of a process, has been proposed as a lightweight alternative to oblivious RAM [ CCMS22 ] . Apple has even adopted DP in their implementation of enhanced visual search as a more efficient method of anonymizing user queries [ App24 , ABG+24 ] . Thus, there is a pressing need to understand the extent to which DP implementations can be protected from timing attacks. 1.1 Limitations of Prior Approaches One general technique suggested by Haeberlen, Pierce, and Narayan [ HPN11 ] and formalized and generalized by Ratliff and Vadhan [ RV24 ] , for constructing JOT-DP programs involve first establishing a bound on the program’s timing stability , which is the timing equivalent of global sensitivity. Once this bound is established, the output release is delayed by an amount sampled from a distribution, scaled according to the timing stability and the desired privacy level. However, this technique seems to inherently result in approximate privacy (\delta>0) because it can only add non-negative “noise” to the program’s runtime. It is possible to achieve pure (\delta=0) JOT-DP in the bounded-DP (or upper-bounded DP) setting, where the maximum size of the input is known and public, by padding execution to the worst case runtime. However, in the unbounded DP setting, where the size of the program’s input is unknown and must be protected by differential privacy, achieving JOT-DP for non-trivial programs introduces several interesting challenges. First, Ben Dov, David, Naor, and Tzalik [ BDDNT23 ] show that pure DP programs in the unbounded setting can be converted into JOT-DP programs, but the