Pith. sign in

REVIEW 3 major objections 6 minor 26 references

Securing Unbounded Differential Privacy Against Timing Attacks

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that the error a timing-private program must tolerate is a property of the machine model, not of differential privacy itself, and that in a RAM model with constant-time access to the dataset size and to random numbers…

desk verdict Theorem 4.5 as stated overclaims—the construction only works for programs that are already JOT-DP—but the model-dependent lower bound and the efficient conversion for JOT-DP programs are real contributions. read the letter →

arxiv 2506.07868 v1 pith:HAMNDQQH submitted 2025-06-09 cs.CR

Zachary Ratliff , Salil Vadhan This is my paper
classification cs.CR
keywords jointoutput-timingprivacyunboundeddifferentialtimingattacksRAMmodelofcomputationrandomnumbergeneratorcountestimationpureJOT-DPLaplacemechanism
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether programs that satisfy differential privacy can also be protected against timing attacks—attacks that infer private information from how long a computation takes—when the size of the dataset itself is private. In the strongest 'unbounded' setting, previous conversions of private programs into jointly output/timing-private (JOT-DP) programs were forced to accept a constant probability of large error. The paper shows that this constant error is not a law of nature: in a randomized RAM model where the dataset size is available in constant time and random numbers can be generated in one instruction, one can convert any pure differentially private program into a pure JOT-DP program whose error probability decays polynomially in the dataset size, and this decay is essentially the best possible. If the program does not know its input length or only has random bits, the same argument shows that constant error is unavoidable. The constructions run in linear time with high probability and preserve the original program's accuracy up to the stated polynomial loss.

What carries the argument

The load-bearing object is the adaptive coin-flipping counter (Program 2): a program whose output is the number of flips until first success, where success on the i-th flip has probability 1/(n-i+k)^c (capped at 1/k^c), so that success gets harder as the output grows. Its key property is that runtime is a deterministic function of output, so proving the output is ε-DP automatically proves the joint (output, runtime) pair is ε-DP. A calculation with PMF ratios shows the output is ε-DP for ε = 2c ln((k+1)/(k-1)), and the probability of underestimating n by a factor of two is O(1/$n^{{c-1}}$). The construction composes this estimator with a truncation step and the original upper-bounded JOT-DP program, using the estimate as a private upper bound on dataset size. For the constant-error version (Theorem 3.4), the machinery is a censored Discrete Laplace count inside a doubling-threshold loop.

What would settle it

A pure ε-JOT-DP RAM program that estimates its own input length and fails with probability decaying faster than any inverse polynomial as n→∞ would refute Theorem 4.1; the simplest concrete check is to implement the adaptive sampler on a machine where RAND(B) takes time proportional to log B and measure whether the failure probability still decays polynomially on inputs of length $10^{6}$, $10^{7}$, and $10^{8}$.

Watch

Extended reading notes

Core claim

The central discovery is that achievable utility for pure JOT-DP in the unbounded setting is a property of the computational model, not of differential privacy itself. Theorem 4.5 constructs, for any ε-DP RAM program in the upper-bounded setting, an ε'-JOT-DP program in the unbounded setting whose output distribution is O(1/n^c)-close in total variation distance, for any desired c ≥ 2, with linear runtime with high probability; Corollary 4.6 applies this to the Laplace mechanism for sums, giving error O(log n/ε) with probability 1 - O(1/n^c). The matching lower bound, Theorem 4.1, shows that any pure JOT-DP program that estimates its own input length must fail with probability at least the smallest nonzero Bernoulli probability sampleable in constant time on the empty input. In the RAM model with constant-time access to n this smallest probability decays polynomially; with only coin flips, or without access to n, it stays constant.

Load-bearing premise

The whole argument runs in an idealized unit-cost RAM model where the input length n sits in a register and a single instruction can sample uniformly from a range of size up to n^c; if those operations are not constant-time, the polynomial error guarantee collapses to constant error.

Editorial extensions

If this is right

  • Any pure ε-DP program in the upper-bounded setting—not just count queries—can be converted to pure JOT-DP in the unbounded setting with O(1/n^c) total-variation distance, so timing-private versions of superlinear-time algorithms such as the smooth-sensitivity median are no longer ruled out by the O(n) runtime ceiling of the delay-based approach.
  • The pure JOT-DP Laplace mechanism for sums releases with error O(log n/ε) and failure probability O(1/n^c), matching the accuracy of the standard Laplace mechanism up to the polynomial failure term.
  • In the coin-flip-only model (the one used by earlier work), constant error probability is necessary and sufficient, so the earlier conversion is optimal for that model.
  • The lower bound establishes that any pure JOT-DP count estimator must have failure probability at least the smallest nonzero Bernoulli probability sampleable in the model's constant time; in the RAM model that quantity decays as n^{-Θ(1)}.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the unit-cost RAND assumption is replaced by a logarithmic-cost random number generator, the paper's own lower-bound argument suggests the achievable failure probability degrades to constant, so practical instantiations on real hardware may sit between the two regimes.
  • The adaptive sampler's runtime being a deterministic function of its output is a template for other privacy mechanisms: any DP mechanism whose output determines its runtime can be lifted to JOT-DP without extra privacy cost.
  • The truncation-plus-private-count pattern suggests a general compiler: for any DP mechanism with a public upper-bounded version, one can privatize dataset size at the cost of a polynomial failure probability, which may also apply to settings like streaming or distributed DP.
  • A natural testable extension is to close the gap between the n^{-c} upper bound and the lower bound's constant-factor slack, or to determine whether approximate (δ>0) JOT-DP can achieve exponential decay in this model.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. This paper studies joint output/timing privacy (JOT-DP) in the unbounded differentially private setting, where the dataset size is itself private. It presents two conversions from upper-bounded programs to unbounded JOT-DP programs: Program 1, which uses censored Discrete Laplace counts to estimate the input length and achieves arbitrarily small constant total-variation error (Theorem 3.4), and Programs 2–3, an adaptive coin-flipping estimator exploiting knowledge of n and a RAND instruction, which claims inverse-polynomial total-variation error (Theorem 4.5). The paper also proves a model-dependent lower bound (Theorem 4.1) and extends the constant-error construction to the coin-flip RAM_BDDNT model via a dyadic symmetric geometric mechanism (Appendix A). The stated goal is to resolve an open question of Ben Dov et al. and to show that achievable error depends on whether the model provides the input length and random integers.

Significance. If the theorem statements are corrected as proposed below, this is a solid contribution. The constructions are explicit, the privacy analysis of Program 2 is a genuine ratio calculation rather than a fitted argument, and the paper does not reverse-engineer its assumptions from its conclusions. The model distinction between RAM models with and without direct access to the input length is a real insight, and the appendix gives a clean dyadic sampler for the BDDNT model. The main caveat is that the advertised conversion of 'any pure DP program' is not delivered by the proofs: Theorem 4.5 as written is false, and the correct hypothesis is that the input program is already JOT-DP. Once that scope is fixed, the paper still makes a meaningful contribution for the natural class of programs that already have timing-private implementations in the upper-bounded setting.

major comments (3)
  1. [Theorem 4.5 (Section 4.1) and Section 1.2] The stated hypothesis 'ε-DP RAM programs' is contradicted by the proof, which requires P to be ε2-JOT-DP (Program 3, line 4; proof of Theorem 4.5). Lemma 2.4 only composes JOT-DP programs, and the runtime of P is part of P′'s joint output. This is load-bearing: take P to be an ε-DP sum mechanism whose runtime equals its input length. In Program 3 the total runtime is L·n̂+O(1)+min(|x|,2n̂) with L=7+2(c−1)≥7; for inputs of length n and n+1 and large n̂, the attainable total runtimes are L n̂+O(1)+n and L n̂+O(1)+n+1, which are disjoint, so an event of the form {T=t} in the tail has probability zero for length n and positive for length n+1. Hence the constructed P′ is not ε′-JOT-DP for any finite ε′. Restate Theorem 4.5 with P assumed ε-JOT-DP (or explicitly pad P to a timing-private implementation, with the corresponding efficiency cost), and correct the Section 1.2 sentence that claims conversion of 'any pure DP program'.
  2. [Theorem 4.5 vs Lemma 4.3] The theorem states total-variation error O(1/n^c) for all c≥2, but Lemma 4.3 gives Pr[estimate < n/2] = O(1/n^{c-1}), and the proof of Theorem 4.5 uses exactly this bound after doubling the estimate. The stated O(1/n^c) therefore does not follow from the written proof; one must instantiate Program 2 with parameter c+1, or state the theorem as O(1/n^{c-1}). Please fix the exponent consistently in the theorem, proof, and Corollary 4.6.
  3. [Theorem 4.1 (Section 4)] The lower bound is not fully formal as written. The quantity p_t0(n) is defined as 'the smallest non-zero probability such that Z∼Bernoulli(p_t0(n)) can be sampled in time 2·t0 when P is executed...', which mixes a Bernoulli-sampling statement with events in P's own execution and does not, by itself, imply that the event {out(P(x))∈S, T_P(x)≤2t0} has probability at least p_t0(n). A supporting lemma should define p_t0(n) as the minimum nonzero probability of any output/time event of P on n-record inputs within 2t0 steps, or equivalently bound that minimum via the maximum RAND range along each path, and then show the event used in the proof is such an event. Without this, the claimed model-dependent separation between polynomial and constant failure probability is plausible but not rigorously established.
minor comments (6)
  1. [Section 1.2] The sentence 'construct an efficient procedure for converting any pure DP program P in the upper-bounded setting...' overstates the theorem, which requires ε-JOT-DP; see major comment 1.
  2. [Theorem 4.1] The proof sets c=max S and concludes |y−n|≥n−c, but the theorem requires |y−n|>n^{−c}; this needs n>c (or c+1 in the statement) and a short justification that n−c>n^{−c} for large n.
  3. [Section 2 and Theorem 4.1] The proof that S is finite relies on the standing assumption that programs are output/runtime independent of the execution environment; this assumption should be stated explicitly as a hypothesis of the theorems, since the current text makes it only informally in Section 2.
  4. [Program 2, line 5] The note about rounding negative numbers to 0 should make clear that only the variable v is clamped, while count continues increasing; otherwise the tail of the distribution (the geometric part) is not immediate.
  5. [Lemma 4.4] The bound 'Pr[out(P)>2n] ≤ Geom(p,n)' is written as a comparison with a PMF; replace it with the explicit tail probability (1−1/k^c)^n.
  6. [Section 4] The displayed bound 'pt0(n) ≥ n^{-2^{2t0}}' is garbled in the text (it appears as n−22·t0); please fix the superscript notation and state t0's role in the lower-bound statement clearly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the conversions are direct constructions and the lower bound is an independent runtime-support argument; the ε-DP vs JOT-DP mismatch in Theorem 4.5 is a correctness gap, not a circular reduction.

full rationale

The paper's main claims are constructions and a lower bound, not empirical predictions. Theorem 3.4 and Theorem 4.5 build P' by (a) privately estimating input length, (b) truncating, and (c) running the upper-bounded program on the truncated input; the output-closeness bound is obtained by union-bounding the probability that truncation changes the input (Lemmas 3.3 and 4.3), so the utility guarantee is derived from the construction's failure probability rather than assumed. Lemmas 2.3, 2.4, and 2.7 are cited from the authors' prior work, but they are elementary composition/constant-time-sampling statements with hypotheses that do not include the target theorems; they are building blocks, not uniqueness claims or fitted parameters, so they do not make the argument circular. Theorem 4.1 is a genuine lower bound: it uses pure JOT-DP to force identical output supports within a fixed runtime budget on all inputs, then counts the finite support to conclude large error with probability at least the smallest samplable Bernoulli probability; it does not assume the upper bound. The one load-bearing defect I found is not circular: Theorem 4.5 is stated for 'ε-DP RAM programs' but its proof refers to 'the ε2-JOT-DP program P' and applies Lemma 2.4, which requires both components to be JOT-DP; an ε-DP program with data-dependent runtime is not covered by the proof as written. This is an omitted hypothesis/justification (a correctness risk), not an equivalence-by-construction, and it can be repaired by the paper's own padding observation in Section 1.2. Accordingly, there is no significant circularity.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

No new entities are introduced. The central results rest on the unit-cost RAM model, on pure-DP support transfer, and on known constant-time discrete Laplace samplers. The adaptive geometric sampler introduces constants c and k chosen by hand, not fitted to data.

free parameters (2)
  • c (accuracy exponent) = any integer >= 2, user-chosen
    Controls the polynomial tail in Programs 2 and 3 and in Corollary 4.6. It is chosen by the theorem user, not fitted to data.
  • k (geometric base) = O(c / epsilon)
    Sets the base probability 1/k^c in the adaptive sampler; chosen by hand so that epsilon = 2c ln((k+1)/(k-1)) meets the target privacy parameter.
assumptions (3)
  • standard math Pure differential privacy transfers support: with finite epsilon, any output/runtime event with positive probability on one dataset has positive probability on every adjacent dataset, and hence across the connected input space.
    Used in Theorem 4.1 to move the output support S from the empty dataset to all dataset sizes; valid because delta = 0 and the adjacency graph is connected.
  • domain assumption The idealized RAM model has unit-cost arithmetic, a built-in input_len register, and a unit-cost RAND(B) instruction.
    Stated in Section 2. All upper and lower bounds are relative to this model; if n is not available in constant time or RAND(B) is costly, the paper's polynomial-vs-constant classification changes.
  • domain assumption Constant-time samplers for censored discrete Laplace distributions exist in the RAM model.
    Invoked via Lemma 2.7 as a building block in Program 1; the paper relies on prior literature (BV19, RV24) rather than proving this from scratch.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Securing Unbounded Differential Privacy Against Timing Attacks." pith.science (2026). https://pith.science/paper/HAMNDQQH

@misc{pith2026250607868,
  author       = {Pith},
  title        = {Pith review of: Securing Unbounded Differential Privacy Against Timing Attacks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HAMNDQQH}},
  note         = {Machine review of arXiv:2506.07868}
}
abstract

Recent works 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 (a) incurs a constant additive increase in error probability (and thus does not provide vanishing error as $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. In this work, we overcome these limitations. Specifically, 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$ 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$ is not given or we only have a random-bit generator, an (arbitrarily small) constant error probability is necessary and sufficient. The aforementioned positive results are proven by efficient procedures to convert any pure JOT-DP program $P$ in the upper-bounded setting to a pure JOT-DP program $P'$ in the unbounded setting, such that the output distribution of $P'$ is $\gamma$-close in total variation distance to that of $P$, where $\gamma$ is either an arbitrarily small constant or polynomially small, depending on the model of computation.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

26 extracted references · 22 canonical work pages

  1. [1]

    Google covid-19 community mobility reports: anonymization process description (version 1.1)

    Ahmet Aktay, Shailesh Bavadekar, Gwen Cossoul, John Davis, Damien Desfontaines, Alex Fabrikant, Evgeniy Gabrilovich, Krishna Gadepalli, Bryant Gipson, Miguel Guevara, et al. Google covid-19 community mobility reports: anonymization process description (version 1.1). arXiv preprint arXiv:2004.04145 , 2020

    arXiv 2004

  2. [2]

    Scalable private search with wally

    Hilal Asi, Fabian Boemer, Nicholas Genise, Muhammad Haris Mughees, Tabitha Ogilvie, Rehan Rishi, Guy N Rothblum, Kunal Talwar, Karl Tarbe, Ruiyu Zhu, et al. Scalable private search with wally. arXiv preprint arXiv:2406.06761 , 2024

    arXiv 2024

  3. [3]

    The us census bureau adopts differential privacy

    John M Abowd. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining , pages 2867--2867, 2018

    work page 2018

  4. [4]

    Lucky thirteen: Breaking the tls and dtls record protocols

    Nadhem J Al Fardan and Kenneth G Paterson. Lucky thirteen: Breaking the tls and dtls record protocols. In 2013 IEEE symposium on security and privacy , pages 526--540. IEEE, 2013

    work page 2013

  5. [5]

    On subnormal floating point and abnormal timing

    Marc Andrysco, David Kohlbrenner, Keaton Mowery, Ranjit Jhala, Sorin Lerner, and Hovav Shacham. On subnormal floating point and abnormal timing. In 2015 IEEE Symposium on Security and Privacy , pages 623--639. IEEE, 2015

    work page 2015

  6. [6]

    Lucky microseconds: A timing attack on amazon’s s2n implementation of tls

    Martin R Albrecht and Kenneth G Paterson. Lucky microseconds: A timing attack on amazon’s s2n implementation of tls. In Advances in Cryptology--EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I 35 , pages 622--643. Springer, 2016

    work page 2016

  7. [7]

    Privacy-preserving machine learning with homomorphic encryption

    Apple. Privacy-preserving machine learning with homomorphic encryption. https://machinelearning.apple.com/research/homomorphic-encryption, 2024. Accessed: 2025-01-19

    work page 2024

  8. [8]

    Remote timing attacks are practical

    David Brumley and Dan Boneh. Remote timing attacks are practical. Computer Networks , 48(5):701--716, 2005

    work page 2005

Show all 26 references
  1. [9]

    Resistance to timing attacks for sampling and privacy preserving schemes

    Yoav Ben Dov, Liron David, Moni Naor, and Elad Tzalik. Resistance to timing attacks for sampling and privacy preserving schemes. In 4th Symposium on Foundations of Responsible Computing (FORC 2023) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2023

    2023

  2. [10]

    Remote timing attacks are still practical

    Billy Bob Brumley and Nicola Tuveri. Remote timing attacks are still practical. In European Symposium on Research in Computer Security , pages 355--371. Springer, 2011

    2011

  3. [11]

    Differential privacy on finite computers

    Victor Balcer and Salil Vadhan. Differential privacy on finite computers. Journal of Privacy and Confidentiality , 9:2, 2019

    2019

  4. [12]

    Foundations of differentially oblivious algorithms

    T-H Hubert Chan, Kai-Min Chung, Bruce Maggs, and Elaine Shi. Foundations of differentially oblivious algorithms. ACM Journal of the ACM (JACM) , 69(4):1--49, 2022

    2022

  5. [13]

    Lower bounds for sampling algorithms for estimating the average

    Ran Canetti, Guy Even, and Oded Goldreich. Lower bounds for sampling algorithms for estimating the average. Information Processing Letters , 53(1):17--25, 1995

    1995

  6. [14]

    Calibrating noise to sensitivity in private data analysis

    Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3 , pages 265--284. Springer, 2006

    2006

  7. [15]

    differential privacy

    Andy Greenberg et al. Apple’s “differential privacy” is about collecting your data--but not your data. Wired, June , 13(1), 2016

    2016

  8. [16]

    Universally utility-maximizing privacy mechanisms

    Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan. Universally utility-maximizing privacy mechanisms. SIAM Journal on Computing , 41(6):1673--1693, 2012

    2012

  9. [17]

    Differential privacy under fire

    Andreas Haeberlen, Benjamin C Pierce, and Arjun Narayan. Differential privacy under fire. In 20th USENIX Security Symposium (USENIX Security 11) , 2011

    2011

  10. [18]

    Are we there yet? timing and floating-point attacks on differential privacy systems

    Jiankai Jin, Eleanor McMurtry, Benjamin IP Rubinstein, and Olga Ohrimenko. Are we there yet? timing and floating-point attacks on differential privacy systems. arXiv preprint arXiv:2112.05307 , 2021

    2021 arXiv

  11. [19]

    Spectre attacks: Exploiting speculative execution

    Paul Kocher, Jann Horn, Anders Fogh, Daniel Genkin, Daniel Gruss, Werner Haas, Mike Hamburg, Moritz Lipp, Stefan Mangard, Thomas Prescher, et al. Spectre attacks: Exploiting speculative execution. Communications of the ACM , 63(7):93--101, 2020

    2020

  12. [20]

    Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems

    Paul C Kocher. Timing attacks on implementations of diffie-hellman, rsa, dss, and other systems. In Advances in Cryptology—CRYPTO’96: 16th Annual International Cryptology Conference Santa Barbara, California, USA August 18--22, 1996 Proceedings 16 , pages 104--113. Springer, 1996

    1996

  13. [21]

    Karaoke: Distributed private messaging immune to passive traffic analysis

    David Lazar, Yossi Gilad, and Nickolai Zeldovich. Karaoke: Distributed private messaging immune to passive traffic analysis. In 13th \ USENIX \ Symposium on Operating Systems Design and Implementation ( \ OSDI \ 18) , pages 711--725, 2018

    2018

  14. [22]

    Meltdown

    Moritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher, Werner Haas, Stefan Mangard, Paul Kocher, Daniel Genkin, Yuval Yarom, and Mike Hamburg. Meltdown. arXiv preprint arXiv:1801.01207 , 2018

    2018 arXiv

  15. [23]

    Facebook Privacy-Protected Full URLs Data Set , 2020

    Solomon Messing, Christina DeGregorio, Bennett Hillenbrand, Gary King, Saurav Mahanti, Zagreb Mukerjee, Chaya Nayak, Nate Persily, Bogdan State, and Arjun Wilkins. Facebook Privacy-Protected Full URLs Data Set , 2020

    2020

  16. [24]

    Smooth sensitivity and sampling in private data analysis

    Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pages 75--84, 2007

    2007

  17. [25]

    A framework for differential privacy against timing attacks

    Zachary Ratliff and Salil Vadhan. A framework for differential privacy against timing attacks. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security , pages 3615--3629, 2024

    2024

  18. [26]

    Vuvuzela: Scalable private messaging resistant to traffic analysis

    Jelle Van Den Hooff, David Lazar, Matei Zaharia, and Nickolai Zeldovich. Vuvuzela: Scalable private messaging resistant to traffic analysis. In Proceedings of the 25th Symposium on Operating Systems Principles , pages 137--152, 2015

    2015

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.