{"id":"e2b7078a-65c0-4548-8849-7636d6ab8270","arxiv_id":"2506.07868","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Pure joint output/timing differential privacy is achievable in the unbounded setting with polynomially vanishing error when the input length is known to the RAM program, and that rate is essentially necessary.","lead":"This paper shows how differentially private programs can be made safe against timing attacks even when the dataset size itself is secret, using a RAM model where the length is known and random numbers can be drawn directly. The authors prove that in this model the unavoidable error shrinks polynomially with dataset size, while weaker models can only reach a constant error rate.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.5 is stated for ε-DP programs but its proof requires ε-JOT-DP; an ε-DP program whose runtime equals its input length is a counterexample to the stated hypothesis.","rationale":"The paper's central contribution is the model-dependent separation and the efficient conversion from upper-bounded to unbounded JOT-DP. The positive conversion is explicit and mostly checkable, and the lower-bound idea (support equality under pure JOT-DP, plus the model-dependent minimum sampleable probability) is sound in spirit. My stress-test pass focused on the exact hypothesis of the headline conversion theorem, since that is what a reader will rely on. I found that Theorem 4.5 as printed says 'ε-DP' but its proof and the composition lemma it invokes require the input program to be ε-JOT-DP. The difference is not cosmetic: a program whose runtime equals the length of its input is ε-DP (if its output is privatized) but not JOT-DP, and running Program 3 on it will leak the noisy count through runtime, giving disjoint runtime supports for adjacent lengths. Hence the stated theorem is false; the intended theorem is true with 'ε-JOT-DP' (or after a padding step). This is a fixable but load-bearing presentation error. I also noticed a boundary gap in Lemma 4.2's privacy proof (Case 2 divides by Geom(p,0) when y=n+1), but the ratio is in fact bounded, so I did not treat it as the primary concern. The reader's identified weakest assumption (unit-cost RAM with input length in a register) is a real modeling choice but is explicit and is the source of the model-dependence claim rather than a flaw. Therefore I recommend keeping the CONDITIONAL verdict, with the condition that Theorem 4.5's hypothesis be corrected and the proof aligned.","tokens_in":20398,"tokens_out":40200,"duration_ms":463837,"concrete_test":"Inspect the proof of Theorem 4.5: locate the clause 'the ε2-JOT-DP program P' and confirm it is assumed, not derived, in the composition. Then instantiate P as an ε-DP program whose runtime equals the length of its input (e.g., a loop over all records adding Laplace noise), apply Program 3, and compute the joint (output, runtime) distribution for adjacent datasets of size n and n+1. Show that the support of the runtime differs (Pr[T=n] > 0 for size n but 0 for size n+1 when n̂ ≥ n/2), violating the pure JOT-DP definition. This settles whether the stated ε-DP hypothesis is sufficient.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.5 states: 'For all ε > 0, ε′ > ε, and ε-DP RAM programs P : X × E → Y × E in the upper-bounded setting, there exists a ε′-JOT-DP RAM program P′...' Yet the proof of Theorem 4.5 explicitly refers to 'the ε2-JOT-DP program P' and composes it with P(line 3) via Lemma 2.4. Lemma 2.4 (sequential composition) only preserves JOT-DP when both components are JOT-DP. If P is merely ε-DP with data-dependent runtime, its runtime on the truncated dataset Truncate(x, 2n̂) can equal min(|x|, 2n̂), so the total runtime distribution of P′ has disjoint supports for datasets of length n and n+1 when n̂ differs, violating pure JOT-DP. Concretely, take P to be an ε-DP sum mechanism whose runtime equals its input length (it loops over all records). For adjacent datasets of length n and n+1, the event 'P′ runtime = n' has probability 1 under one input and 0 under the other after truncation with n̂ ≥ n/2, so pure ε′-JOT-DP fails for any finite ε′. Thus the theorem as stated is false; the hypothesis must be 'ε-JOT-DP' (or the construction must first make P JOT-DP by padding, as the paper's Section 1.2 suggests but does not build into Theorem 4.5). This also affects the abstract's claim of converting 'any pure DP program P in the upper-bounded setting' — that claim is only valid for programs that already have timing-private implementations.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":20701,"tokens_out":26479,"duration_ms":321898,"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":[{"comment":"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'.","section":"Theorem 4.5 (Section 4.1) and Section 1.2"},{"comment":"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.","section":"Theorem 4.5 vs Lemma 4.3"},{"comment":"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.","section":"Theorem 4.1 (Section 4)"}],"minor_comments":[{"comment":"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.","section":"Section 1.2"},{"comment":"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.","section":"Theorem 4.1"},{"comment":"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.","section":"Section 2 and Theorem 4.1"},{"comment":"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.","section":"Program 2, line 5"},{"comment":"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.","section":"Lemma 4.4"},{"comment":"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.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The false Theorem 4.5 statement appears to be a scope error rather than a deliberate result, since the proof and Program 3 already assume JOT-DP for the inner program. Nevertheless, the Introduction advertises conversion of 'any pure DP program', and the counterexample is direct, so the correction is not cosmetic. I recommend major revision rather than rejection: the constructions and the core privacy/accuracy arguments are otherwise coherent, and the corrected scope still resolves the paper's main technical question for timing-private upper-bounded programs."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The key result here is not quite what the abstract says. The paper claims to convert any pure ε-DP program in the upper-bounded setting to a pure JOT-DP program in the unbounded setting with polynomial error. Theorem 4.5 states exactly that. But the proof actually requires the input program to be ε-JOT-DP, not merely ε-DP. The sequential composition lemma (Lemma 2.4) only preserves JOT-DP when both components are JOT-DP, and the proof calls the program “ε2-JOT-DP.” Take an ε-DP program whose runtime equals its input length—looping over all records. After truncation, the total runtime for adjacent dataset lengths n and n+1 has different support for any estimate that exceeds n/2, so pure JOT-DP fails. The theorem as stated is false. This is not a minor presentation issue; it affects the abstract’s main claim. The fix is straightforward: change the hypothesis to ε-JOT-DP, which the authors themselves note is a mild restriction since padding achieves it. But as written, the central theorem does not do what the abstract promises.\n\nThat said, there is real substance here. The model-dependent lower bound (Theorem 4.1) is the interesting new idea: showing that the achievable error for pure JOT-DP in the unbounded setting depends on whether the model gives you constant-time access to n and random integers. The constant-error conversion (Theorem 3.4) is also new and explicitly efficient, resolving an open question from BDDNT23. The adaptive sampler in Program 2 is a clever construction: its runtime is a deterministic function of its output, so output-DP implies joint output/timing DP. Lemma 4.2’s proof checks out.\n\nThe smaller issues: Theorem 4.5 claims O(1/n^c) but Lemma 4.3 gives O(1/n^{c-1}); that is an off-by-one that reindexing c fixes. The lower bound proof moves from support equality to a quantitative probability bound using pt0(n); the step is plausible but could be spelled out. Neither is fatal.\n\nThis paper deserves a serious referee, but the authors must fix the statement and proof of Theorem 4.5 and temper the abstract. If they do, the core contributions stand. Worth engaging with for anyone in privacy theory.","headline":"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.","tokens_in":21278,"tokens_out":7618,"would_cite":false,"duration_ms":83015,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["joint output-timing privacy","unbounded differential privacy","timing attacks","RAM model of computation","random number generator","count estimation","pure JOT-DP","Laplace mechanism"],"falsifier":"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}$.","tokens_in":20125,"feed_emoji":"🕐","tokens_out":6116,"duration_ms":57152,"temperature":0.7,"pith_summary":"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.","feed_headline":"Timing-safe differential privacy can now vanish polynomially","feed_subtitle":"With dataset size in a register and one-step random draws, private programs keep timing-safe error to 1/n^c.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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)}."],"supporting_citations":[{"why":"Prior conversion to pure JOT-DP in the unbounded setting; incurs constant error, may be inefficient, and uses a coin-flip model; the paper's upper bounds improve on it and its Appendix extends the technique back to that model.","marker":"[BDDNT23]"},{"why":"Formalized joint output/timing privacy and supplied the sequential-composition and constant-time lemmas that the constructions rely on.","marker":"[RV24]"},{"why":"Introduced timing stability and the random-delay approach to timing privacy; the O(n)-runtime restriction of that approach is what the new truncation-based construction avoids.","marker":"[HPN11]"},{"why":"Proved that the censored Discrete Laplace (truncated geometric) mechanism is differentially private; this mechanism provides the private count in the constant-error construction.","marker":"[GRS12]"},{"why":"Gave constant-time implementations of sampling from censored Discrete Laplace distributions on finite computers, needed for those counts to be JOT-DP.","marker":"[BV19]"},{"why":"Supplies the smooth-sensitivity median algorithm, a superlinear-time DP program that motivates the need for timing privacy beyond O(n)-runtime programs.","marker":"[NRS07]"}],"fun_headline_variants":["Model access determines timing-safe privacy error","Polynomial timing-safe error when n is known","Random draws and known size shrink privacy error","Timing-safe privacy error: model-dependent, not DP-dependent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Model access determines timing-safe privacy error","Polynomial timing-safe error when n is known","Random draws and known size shrink privacy error","Timing-safe privacy error: model-dependent, not DP-dependent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000827,"raw_usage":{"total_tokens":3691,"prompt_tokens":1101,"completion_tokens":2590,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":717,"completion_tokens_details":{"reasoning_tokens":2531}},"tokens_in":717,"tokens_out":2590,"duration_ms":19885,"temperature":1.0,"reasoning_tokens":2531,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:27:33.784420+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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}$.","supporting_citations":[],"review_version":1}