Continual Learning With Participation Privacy: An Auditable Buffering-Aggregation Recipe T-H. Hubert Chan1
Elaine Shi2
Mengshi Zhao1
Mingxun Zhou3
1
The University of Hong Kong, Hong Kong, China 2 Carnegie Mellon University, Pittsburgh, USA 3 The Hong Kong University of Science and Technology, Hong Kong, China
arXiv:2607.07209v1 [cs.CR] 8 Jul 2026
Abstract Modern federated and streaming learning systems often release intermediate models, so privacy must hold for the full trajectory under adaptive interaction. Motivated by participation privacy, we study single-edit neighboring user streams, where one insertion/deletion shifts all subsequent updates and defeats standard Hamming-neighbor continual-release analyses. We give an auditable modular recipe. A randomized buffering wrapper emits bins of size [U, 2U ], reducing single-edit streams to a Hamming-style per-bin update stream with explicit backlog/delay guarantees, where U is calibrated by the privacy parameters (ε, δ). We then prove a certification theorem identifying when a non-adaptive Hamming-neighbor DP proof for a continual primitive lifts to adaptive inputs: the primitive must use fresh per-round randomness and have a stable one-round privacy profile under common adaptive context. Together, these ingredients yield trajectory-level (ε, δ)-DP for single-edit streams using standard primitives (e.g., tree prefix sums), with an explicit privacy–latency link via U .
1
Introduction
Modern federated and streaming learning systems release intermediate model snapshots throughout training, so an adversary may observe the entire trajectory (w(t) )t≥0 rather than only a final model. A canonical instance is streaming stochastic gradient descent (SGD): at step t, a user contributes a private loss function ft and the learner updates using a gradient step based on the current model [TS13, KMS+ 21]. Beyond protecting the data within each ft , some deployments also require participation privacy: a user may wish to ensure plausible deniability of whether they participated at all. This motivates single-edit (edit-distance) neighboring streams, where two user-update streams are neighbors if one can be obtained from the other by inserting or deleting a single user event. Continual release also makes the learning process intrinsically interactive: the released model (t) w influences what happens next, so the update stream can be adaptively generated in response to prior outputs. While classical continual-release primitives such as tree-based private prefix sums [DNPR10,CSS11] were originally analyzed under statically chosen (Hamming-neighbor) streams, recent work formalizes differential privacy against such adaptive interaction [JRSS23]. Our goal is to make this adaptive viewpoint compatible with the single-edit participation model above. The difficulty is that Hamming-style neighboring streams are not the right abstraction for participation privacy on a stream. Most continual DP analyses change the value at a single time index t0 while keeping all other positions aligned [Dwo06]. In contrast, a single insertion/deletion shifts the alignment of all subsequent positions, so an edit-neighbor pair can be far from Hammingneighboring. This also undermines deterministic batching: partitioning the stream into fixed contiguous blocks can cause one edit to shift many later batch boundaries, so standard Hammingneighbor continual DP guarantees do not directly transfer. To address this mismatch, we use a simple modular recipe: randomized buffering and an adaptive-safety certification for downstream continual primitives. We apply a randomized buffering wrapper [CCMS22, ZSCM23] that introduces random delay and releases user updates in bins of controlled size (e.g., in [U, 2U ]); here U is a privacy-implied systems cost, calibrated by the target (ε, δ) and inducing delay. We then invoke standard continual DP primitives (e.g., tree/prefix-sum) to privately aggregate the resulting vector updates, and prove a certification theorem showing when a non-adaptive Hamming-neighbor privacy proof remains valid under feedback. The certification requires fresh per-round randomness together with a stable-context condition: common adaptive updates may change the released statistic, but they must not change the privacy cost of the unique Hamming discrepancy.1 Contributions. • Edit-neighbor continual learning under feedback. We formalize participation privacy via single-edit neighboring user-update streams in a continual learning setting with intermediate releases. • Modular pipeline with an explicit privacy to latency link. We combine randomized buffering with standard continual DP primitives to obtain trajectory-level privacy for editneighbor streams; the target (ε, δ) determines the buffering level U , making induced delay explicit. • Certification theorem for adaptive safety of continual DP primitives. We give a checkable certification condition under which a non-adaptive Hamming-neighbor privacy 1
An earlier version [CSZZ26] stated the certification condition using independent decomposability alone. Here we use the slightly stronger stable-context condition, formalized in Appendix E as quantitative decomposability. This refinement makes the statement technically precise and is satisfied by the certified cores of the continual-release primitives used in our pipeline.
1
analysis carries over to the feedback/adaptive setting. The condition combines fresh perround randomness with a stable-context requirement, and certifies safe reuse of canonical primitives such as tree/prefix-sum mechanisms. Results and organization. Our end-to-end guarantee is trajectory-level (ε, δ)-DP for single-edit neighboring participation streams under feedback, obtained by composing randomized buffering with a continual-release DP aggregator (Theorem 3.1); the privacy target explicitly induces a buffering level U (ε, δ) and hence delay/staleness. A second ingredient is a reusable certification theorem showing that, for continual primitives satisfying our fresh-randomness and stable-context conditions, a standard non-adaptive privacy analysis lifts to the adaptive/feedback setting (Theorem 4.3). Section 2 formalizes the interactive model, edit adjacency, and metrics; Section 3 gives a high-level view of the pipeline and states the main theorem; Section 4 develops the two auditable ingredients (randomized buffering and certification) and combines them via modular composition; Section 5 instantiates the recipe with continual DP-SGD (tree/prefix-sum aggregation). Technical proofs are deferred to the appendix. The relevant experiments are given in [CSZZ26].
1.1
Related Work
Continual-Release DP. Canonical continual-release primitives for streaming aggregates include tree-based private prefix sums [DNPR10,CSS11] and closely related lower-triangular (matrix-style) mechanisms [DMR+ 22]. These mechanisms are typically analyzed for Hamming-neighboring update streams, where only one time index differs. In contrast, our participation model uses single-edit (insertion/deletion) neighboring streams, where alignment shifts after the edit; this gap is mild for static datasets [BEBP24] but is fundamental for streams. Sliding-window variants of private stream release have also been studied for window aggregate queries and graph streams [CXG+ 13, UUA21]. These works target recent-window utility, whereas our setting focuses on single-edit participation privacy, where one insertion/deletion shifts all subsequent stream positions and requires an edit-to-Hamming shielding interface. Adaptive Streams and Feedback. Continual learning is inherently interactive: released outputs can influence future updates. Recent work formalizes differential privacy against such adaptive interaction (e.g., left-or-right style games and verification viewpoints) [DMR+ 22,JRSS23]. Our certification result is complementary: it gives a checkable structural condition under which a standard non-adaptive Hamming-DP analysis of a continual primitive lifts directly to the adaptive setting. The condition is stronger than fresh prefix-causal randomness alone: it also requires that common adaptive context does not change the one-round privacy cost of the unique Hamming discrepancy. Privacy-Induced Delayed Reactions. [CLN+ 24] give a conceptually related delayed-reaction phenomenon for continual observation and online threshold queries. Their Appendix B delays threshold-type outputs on a directly observed online bit stream. Our delay has a different technical role: RandBin waits for future arrivals to form bins in [U, 2U ] so that a single insertion/deletion, which appears only in the neighboring-stream analysis, becomes a bounded Hamming-style perturbation while the full transcript, including timing and ⊥ outputs, remains protected. Randomized Buffering, RSC, and Obliviousness Lineage. Randomized buffering has appeared as infrastructure in oblivious data structures and related privacy modularity work [CCMS22, ZSCM23]. A closely related random-partition idea also appears in the Reorder-Slice-Compute (RSC) paradigm of [CLN+ 23], where random slicing is used to synchronize neighboring executions and avoid a one-edit domino effect. Our setting differs in that the continual streaming transcript exposes release timing itself: the adversary observes whether each step emits a real block or the dummy symbol ⊥. Thus, in our use, RandBin is an interactive interface that converts single-edit
2
participation streams into a sparse, Hamming-style per-bin update stream while also providing explicit backlog/delay guarantees calibrated by (ε, δ). Composition and Concurrency. Beyond classical (ε, δ)-DP [Dwo06], alternative formalisms (e.g., Rényi divergence and tradeoff-based views) can streamline composition reasoning [Mir17, DRS22, VZ23, ZZCS24], recovering familiar advanced composition bounds [DRV10, KOV15]. Concurrent composition in interactive settings has also been studied, including adaptively chosen privacy parameters [HST+ 23,HSV26]. These works typically assume each mechanism’s neighboring relation is defined on a single underlying (static or dynamic) database; in our pipeline, we additionally need to reason about neighbor-preserving transformations between components (edit-to-Hamming shielding), which motivates our modular composition viewpoint. Our modular composition theorem can be viewed as combining the refinement-pair reduction of NPDP to standard DP in [ZZCS24] with the interactive/concurrent composition framework of [HSV26]; for completeness and to match our power-function accounting, we give a self-contained proof in Appendix C.
2
Setting and Preliminaries
We now fix the interactive streaming-learning model underlying continual release: the adversary observes both the released model trajectory and the release timing, and may influence future user events. We also define edit-style (participation) adjacency and the utility–latency metrics used throughout. With these conventions in place, Section 3 summarizes our buffering–aggregation pipeline and main guarantee. Streaming Learning Loop and Transcript. At each discrete step t = 1, 2, . . ., an adaptive environment produces a user event ft (e.g., a private loss or update). The server maintains a model w(t) ∈ Rd and may release intermediate snapshots. To unify per-step and buffered releases, we include an observable timing bit vt ∈ {0, 1}: if vt = 1 the server incorporates available (buffered) events to form an update gt and publishes the new snapshot; if vt = 0 it holds w(t) = w(t−1) . The T adversary’s view up to horizon T is the transcript tr≤T := (vt , w(t) ) t=0 , and our privacy notion is defined with respect to this joint transcript (including timing). All privacy guarantees are required to hold for every horizon T , and thus apply to the full trajectory. Feedback/Adaptive Interaction. The environment (and thus the event stream) may depend on the past transcript: formally, ft may be chosen as an arbitrary (possibly randomized) function of tr<t . All guarantees quantify over such adaptive interaction. When we refer to a non-adaptive privacy analysis for a continual primitive, we mean its input stream is fixed in advance (independent of past releases). Participation Privacy via Single-Edit Adjacency. Let M denote the full interactive mechanism (e.g., buffering → aggregation → releases) mapping an event stream F = (f1 , f2 , . . .) to a transcript. We use single-edit adjacency: F ∼edit F ′ if F ′ is obtained from F by inserting or deleting exactly one event, shifting subsequent indices; equivalently, for some t0 , either (i) ft′ = ft for t < t0 and ft′ = ft+1 for all t ≥ t0 (deletion), or (ii) the reverse (insertion). The unit of privacy is one participation event; other units (e.g., a session spanning multiple events) reduce via grouping/composition (formal composition tools appear in Appendix A).
3
Differential Privacy (Under Adaptive Interaction). for all F ∼edit F ′ and all measurable transcript-sets S,
We say M is (ε, δ)-DP w.r.t. ∼edit if
Pr M(F ) ∈ S ≤ eε Pr M(F ′ ) ∈ S + δ, where the probability is over M’s internal randomness; the quantification over event-generation strategies is captured by the adaptive-interaction model above. Our appendix sometimes uses the equivalent tradeoff-/power-function viewpoint to streamline interactive composition; the main text states guarantees in (ε, δ)-DP; see Appendix A. Metrics. Utility: test accuracy / loss of the final released model by time T (e.g., w(T ) or the last release by T ). Systems: backlog Qt (pending, not-yet-incorporated events after time t) and inclusion delay D(i) := min{t ≥ i : fi is incorporated by time t} − i, measured in event arrivals. Extension: From One Edit to k Edits. If neighbors may differ by up to k insertions/deletions, standard group-privacy/composition yields a k-dependent degradation of (ε, δ); in our pipeline this correspondingly increases the required privacy budgets and thus the induced buffering/latency. Full statements are deferred to the appendix.
3
Overview
This section summarizes our buffering–aggregation pipeline (Fig. 1) and the resulting end-to-end guarantee: continual-release (ε, δ)-DP for single-edit participation streams under feedback, where the adversary observes the released trajectory (and timing). The required buffering level U (ε, δ) is privacy-implied and explicitly governs delay. feedback: future events may depend on w(t)
User-event stream f1 , f 2 , . . .
Randomized buffering
U (ε, δ)
Batches Bt ⊆ {fi }
|Bt | ∈ [U, 2U ]
Update Continual DP gt primitive
(certified)
bin contents / internal state hidden
Released models w(t) adversary observes w(t)
Figure 1: Pipeline overview. Randomized buffering (parameter U (ε, δ)) converts a single-edit stream into bins that are consumed (in the sense defined in Appendix B) by a certified continualrelease DP primitive, producing intermediate model releases. The adversary observes the released models; bin contents and internal states are hidden. We next give the recipe and state the end-to-end guarantee. Recipe (buffering → aggregation → releases). Given user-event stream (ft ), at each step t ≥ 1, buffering outputs Bt with |Bt | ∈ [U, 2U ] or ⊥. Let τ (1) < τ (2) < · · · be the (random) steps with Bτ (k) ̸= ⊥. 1. Buffer. Run randomized buffering with U (ε, δ) to obtain (Bt )t≥1 . 4
2. Update. For each k ≥ 1, form a clipped per-bin update gk := |B 1 | τ (k) o n G where ClipG (x) := x · min 1, ∥x∥2 .
P
f ∈Bτ (k) ClipG ∇f w
(τ (k)−1)
3. Aggregate + release. Feed (gk )k≥1 to a certified continual-release DP primitive and update only at bin times: output w(τ (k)) after processing gk , and hold w(t) = w(τ (k)) for τ (k) ≤ t < τ (k+1) (feedback allowed). Theorem 3.1 states the resulting end-to-end privacy. Theorem 3.1 (End-to-end continual-release DP for single-edit streams). Run the above recipe with target (ε, δ), allocating (εb , δb ) to buffering and (εa , δa ) to aggregation. Set U = privacy 1 1 Θ εb log δb , and plug in any continual-release DP primitive that is adaptively (εa , δa )-DP for Hamming-neighboring update streams. Then the released model trajectory (w(t) )t≥0 is (ε, δ)-DP with respect to single-edit neighboring event streams, even when future events are generated adaptively from past releases (feedback). Proof idea. Randomized buffering turns a single insertion/deletion on the event stream into a bounded Hamming-style perturbation on the emitted update stream; we then apply a certified continual-release DP primitive whose non-adaptive analysis remains valid under feedback, and conclude via modular composition (Appendix C). Certification preview (adaptive safety of continual primitives). We use a reusable certification for feedback: writing xt for the per-round input and x1:t for its prefix, a continual-release primitive is independently decomposable if at each release time t it samples fresh independent randomness Rt and outputs a deterministic function of (x1:t , Rt ). For such primitives, standard nonadaptive (ε, δ)-DP analyses remain valid under feedback. This covers tree/prefix-sum (Appendix F) and more general lower-triangular matrix mechanisms (Section 4.2). SGD instantiation and what we measure. We instantiate the pipeline with streaming SGD: each emitted bin Bτ (k) triggers one clipped mini-batch gradient update, privatized by a continualrelease DP aggregator (tree/prefix-sum in our experiments). The target (ε, δ) fixes U(ε, δ), yielding random batch sizes in [U, 2U ] and a backlog bound of order O ε1b log t (log t + log δ1b ) (Lemma 4.2). We report accuracy versus (ε, δ) together with empirical delay distributions implied by U (ε, δ). The theoretical convergence of various SGD variants under DP noise has already been extensively analyzed; we refer the reader to standard works [JKT12, SCS13, TS13, KMS+ 21, DMR+ 22]. Deferred details. Sections 4.1 and 4.2 formalize buffering and certification; the end-to-end proof of Theorem 3.1 (via modular composition) and additional instantiations/experiments appear in the appendix.
4
Auditable Ingredients: Randomized Buffering and AdaptiveSafe Continual-Release DP
This section isolates the two ingredients that make the pipeline in Fig. 1 auditable. First, we treat randomized buffering (RandBin) as an interface: it converts a single-edit event stream into a sparse per-bin update stream that admits a standard Hamming-neighbor DP analysis, while providing an
5
,
explicit backlog guarantee. Second, we give a reusable certification theorem for adaptive interaction (output-dependent updates): for independently decomposable (prefix-causal) continual-release mechanisms, a non-adaptive DP proof remains valid even when updates are chosen adaptively as a function of past releases. Separation of Roles. Randomized buffering is not needed for the certification theorem itself: Theorem 4.3 is a reusable adaptivity lift for independently decomposable continual mechanisms. In our pipeline, buffering serves a different role: it shields the downstream primitive from singleedit adjacency, where one insertion or deletion can shift many later batch boundaries. Thus, our modular proof separates an upstream edit-to-Hamming interface from a downstream adaptive-safety certificate. We do not claim that randomized buffering is the only possible route; alternatives would require either another edit-shielding interface or a direct native proof under edit adjacency.
4.1
Randomized Buffering Wrapper
RandBin Interface. We use RandBin as a lightweight wrapper that turns an incoming event stream into well-sized bins, while keeping the buffering backlog under control and enabling our edit-to-Hamming reduction downstream. The input is a stream of user events f1 , f2 , . . . (losses, gradients, or updates). At each step t ≥ 1, RandBin outputs a symbol Bt : either a concrete bin Bt containing some pending events among those arrived by time t, or ⊥ (no emission). Let τ (1) < τ (2) < · · · be the (random) emission times with Bτ (k) ̸= ⊥. When Bt = ⊥, nothing is sent to the downstream aggregator and the released model remains unchanged. We rely on three interface properties: (P1) Bin size. Whenever Bt ̸= ⊥, the bin size is controlled: |Bt | ∈ [U, 2U ]. (P2) Backlog control. The number of pending (unbinned) events Qt remains small for all t (formal bound below), yielding explicit delay guarantees. (P3) Edit-to-Hamming wrapper: neighbor-preserving (NP) DP. A single insertion/deletion in the input stream induces only a bounded Hamming-style perturbation in the emittedbin (and hence per-bin update) stream, in the sense needed to compose with a Hamming-DP continual primitive. The details are deferred to Appendix D. Input-Identifiability Convention. Lemma 4.1 uses the standard convention that events are identifiable, e.g., by unique IDs or metadata tags, so that after the first mismatch in an editneighbor pair the simulation can determine which stream contains the extra event. Anonymous streams with duplicate values require an extra disambiguation assumption; see Appendix D. Systems Metrics: Backlog and Delay. The buffering level U (εb , δb ) controls how aggressively RandBin batches the stream and thus the latency regime seen by learning. We track the backlog Qt , the number of pending (unbinned) events after time t. For an event fi , its inclusion delay D(i) is the number of subsequent arrivals until it is placed in an emitted bin. In particular, if Qt ≤ B(t) for all t ∈ [i, T ], then D(i) ≤ B(T ) (and sharper bounds follow from the trajectory of (Qt )). Interface Guarantees for Modular Composition. RandBin; proofs and constants appear in Appendix D.
6
We will use two interface properties of
Algorithm 1 RandBin (Interface-Level Skeleton) 1: Input: (εb , δb ); stream (ft )t≥1 2: Output: Bt ∈ {⊥} ∪ {bins of size in [U, 2U ]} 3: Set U = Θ(ε−1 b log(1/δb )) and a distribution D supported on [U, 2U ] 4: Maintain a FIFO buffer buf and a private randomized emission scheduler 5: for t = 1, 2, . . . do 6: Append ft to buf 7: if there is no scheduled emission then 8: Output ⊥ 9: else 10: Sample C ∈ [U, 2U ] from D 11: Pop C items from buf as Bt 12: Output Bt ; refresh scheduler 13: end if 14: end for
Lemma 4.1 (Edit-to-Hamming Wrapper (NPDP Contract)). For any single-edit neighboring input streams, RandBin admits a neighbor-preserving paired simulation (with refinement) such that the coupled emitted-bin/update streams differ in a bounded Hamming-style way at the interface required for modular composition with a Hamming-DP continual primitive. Intuition: randomized boundaries prevent one insertion/deletion from cascading into many downstream bin shifts; the paired simulation formalizes this stability under interaction. −1 Lemma 4.2 (Backlog Bound (Privacy-Implied Delay)). With U = Θ(εb log(1/δb )), for every time
t the backlog satisfies Qt = O ε1b log t · log t + log δ1b . This bound is obtained by implementing RandBin’s private emission scheduler via the streaming DP prefix-sum mechanism (Theorem F.1) and translating its additive-error guarantee into a worst-case queue bound. As a consequence, inclusion delay is controlled at the same order (up to constants) for events arriving by time t. Intuition: the noisy scheduling forces sufficiently frequent emissions to prevent sustained queue growth, while keeping bin sizes within [U, 2U ]. On the Horizon Dependence. The log t dependence in Lemma 4.2 is not merely an artifact of loose algebra. In our implementation, the emission scheduler is a continual private prefix-sum mechanism, and its additive error is translated directly into backlog. On a unit-rate stream, if Mt is the cumulative number of emitted items by time t, then Qt = t − Mt . Thus, within this scheduler family, improving the backlog bound would amount to improving the corresponding continual private counting error. Known continual-counting lower bounds suggest that logarithmic horizon dependence is intrinsic to this proof route [DNPR10, CLN+ 24], although we do not claim a minimax lower bound for all possible NPDP wrappers. Scope of the Approximate-DP Regime. The bounded-delay guarantee in Lemma 4.2 is tied to the approximate-DP implementation of RandBin: the proof uses bounded-support buffering noise and an always-valid prefix-sum error bound. For RandBin-style shift masking, pure DP would require unbounded-support noise, and therefore cannot give the same probability-one finite-delay guarantee.
7
Positioning. Randomized buffering is often used in oblivious data structures to hide access patterns [CCMS22, ZSCM23]. Our use is different in emphasis: RandBin serves as an infrastructure interface that (i) converts single-edit participation streams into a sparse, Hamming-style stream of per-bin updates and (ii) exposes explicit backlog guarantees. Once Lemmas 4.1–4.2 hold, the downstream component becomes plug-and-play: any continual primitive that passes our certification in Section 4.2 can be safely reused. Full pseudocode, the NPDP security game (paired simulation + refinement), and sharper tail bounds are deferred to Appendix D.
4.2
Certifying Feedback-Safe Continual-Release Primitives
Why Certification? Our pipeline treats the continual-release DP primitive as a plug-in component. To make this modularity auditable, we need a certification criterion showing when a standard non-adaptive Hamming-neighbor DP analysis continues to hold when per-round updates are chosen adaptively from past releases. Fresh independent randomness is necessary for this transfer, but not sufficient by itself; Appendix E.1 gives a two-round counterexample. The criterion below therefore combines fresh randomness with a quantitative decomposability condition that prevents adaptive common context from changing the one-round leakage profile. Certified Decomposability. Write xt for the input update at round t and x1:t := (x1 , . . . , xt ). The certification condition has two parts. First, the mechanism must use fresh independent randomness at each round: the release at time t is generated as yt = Mt (Rt , x1:t ), where Rt is independent of the randomness used at other rounds and Mt is deterministic given (Rt , x1:t ). Second, the privacy cost of a one-round release must be stable under common context. Informally, if two input histories differ in one update, then the effect of this discrepancy on the round-t release is determined only by the part of the round-t aggregate that contains the changed update. Common updates before or after the discrepancy may change the released statistic, but they are shared by both neighboring histories and therefore should not change the privacy cost of the discrepancy itself. The formal appendix condition, called quantitative decomposability, rules out this behavior by requiring the one-round privacy profile to depend only on the distance between the relevant aggregates after common aggregation context is removed. Importantly, after producing the output y1:t at time t, the mechanism may apply arbitrary postprocessing to (y1 , . . . , yt ) and output any derived value at time t; by closure under post-processing, this does not weaken the privacy guarantee proved for the underlying releases.
8
Checklist 1 (Certification Conditions). A continual-release primitive M passes certification if its core release process satisfies the following conditions: 1. Prefix dependence: the core release at time t depends only on the input prefix x1:t , not on future inputs. 2. Fresh randomness: the core release at time t uses randomness Rt that is independent of the randomness used in all other rounds. 3. Deterministic release map: given (Rt , x1:t ), the core release yt = Mt (Rt , x1:t ) is deterministic. 4. Stable one-round privacy cost: if two prefixes differ in one update, then common aggregation context in the two prefixes does not change the privacy cost of that discrepancy. The appendix formalizes this condition as quantitative decomposability in Definition E.3. 5. Post-processing only afterward: after the certified core releases are produced, the mechanism may output any function of the released transcript; this is post-processing and does not weaken the privacy guarantee. Consequence: any finite-horizon non-adaptive (ε, δ)-DP proof for Hamming-neighboring update streams lifts to adaptive interaction. Certification Theorem. The next theorem formalizes the consequence of Checklist 1 and serves as an audit tool for reusing continual DP primitives inside interactive learning loops. The formal appendix statement is given in terms of power functions; the version below states the resulting (ε, δ)-DP guarantee. Theorem 4.3 (Certification: Non-Adaptive DP Implies Feedback-Safe DP). Consider Hammingstyle neighboring update streams, where two equal-length streams differ in at most one position. Let M be a continual primitive satisfying Checklist 1. If M is non-adaptively (ε, δ)-DP for Hammingneighboring update streams for every finite horizon, then M is also (ε, δ)-DP against adaptive interaction for every finite horizon, where each xt may be chosen as an arbitrary function of past releases. Proof Sketch. (Full proof in Appendix E) The proof works in the paired-simulation game and proceeds by induction on the horizon. If the first input pair already contains the unique Hamming discrepancy, then all later paired inputs must be equal componentwise. Checklist 1 ensures that these later common inputs only add common context and do not change the one-round privacy cost of the discrepancy; the per-round privacy losses then tensorize exactly. If the first input pair is equal, we condition on the common first release, fix the first input as common context, and apply the induction hypothesis to the shifted mechanism on the remaining rounds. Fresh independent randomness is used to separate the per-round contributions, while the stable-context condition prevents adaptive common inputs from amplifying the leakage of the unique discrepancy. Mini-Audit 1: Tree / Prefix-Sum. For the tree mechanism, the certified core is the stream of newly revealed noisy tree-node values. Each such node value depends only on the updates in its interval and on its own fresh noise. If two update streams differ in one coordinate, then only the tree nodes whose intervals contain that coordinate see different sums; all other contributions are common to the two executions. Thus the one-round privacy cost is determined only by the changed update’s contribution to the affected node, not by the surrounding common updates. The 9
published prefix sum at time t is a deterministic function of the noisy node values revealed so far, hence post-processing. Therefore the usual non-adaptive Hamming-neighbor DP analysis for tree prefix sums carries over to adaptive update choices by Theorem 4.3. Mini-Audit 2: Lower-Triangular (Prefix) Linear Mechanisms. Many continual primitives can be written as a certified core followed by linear post-processing. Concretely, suppose the core releases noisy statistics zt = ⟨bt , x1:t ⟩ + ηt ,
supp(bt ) ⊆ {1, . . . , t},
where the noises ηt are fresh and independent across t. Each core release depends only on the input prefix x1:t and its own fresh noise. If two update streams differ in one coordinate, then the two linear statistics differ only through that coordinate’s contribution; all common updates contribute equally to both executions. Thus the one-round P privacy cost is stable under common context. Any published output of the form yt = s≤t At,s zs is a deterministic function of (z1 , . . . , zt ) and therefore post-processing. Hence any non-adaptive Hamming-neighbor DP bound for the core stream (zt ) remains valid under adaptive interaction, and the same holds for the released stream (yt ) by Theorem 4.3. For details, see Appendix F.1. Scope Boundary. Theorem 4.3 is a sufficient certification condition, not a characterization of adaptive privacy. Fresh randomness alone is not enough; Appendix E.1 gives a two-round separation. The missing ingredient is the stable-context condition in Checklist 1, which prevents adaptive common inputs from changing the leakage profile of an earlier Hamming discrepancy. Conversely, failure of Checklist 1 does not imply that adaptive privacy is false; it means that a separate interaction-aware proof is needed, as for RandBin in Appendix D.
4.3
Putting the Ingredients Together
We prove end-to-end privacy by a modular composition argument that composes two interactive mechanisms in series. Our general composition theorem (Appendix C) applies to any upstream wrapper that is (εb , δb )-NPDP and any downstream continual primitive that is (εa , δa )-DP for Hamming-neighboring update streams and is feedback-safe by certification. The pipeline in Fig. 1 is one instantiation, with RandBin as the wrapper and a continual DP aggregator as the downstream mechanism. Section 4.1 supplies the wrapper side: RandBin implements an edit-to-Hamming reduction, i.e., a single insertion/deletion in the event stream induces only a bounded Hamming-style change in the induced (per-bin) update stream (Lemma 4.1). Section 4.2 supplies the downstream side: for primitives that pass Checklist 1, a standard non-adaptive DP proof for Hamming-neighboring inputs remains valid when updates are chosen adaptively from past releases (Theorem 4.3). Modular Composition (Informal). View buffering as producing (i) a visible transcript (e.g., whether a bin is emitted) and (ii) a hidden interface stream of per-bin updates. The downstream continual primitive consumes this interface stream and releases the trajectory observed by the adversary. The end-to-end guarantee follows from two conditions: 1. Wrapper condition (NPDP). The wrapper is (εb , δb )-NPDP for single-edit neighboring event streams, and the induced interface streams can be aligned to be Hamming-neighboring (Lemma 4.1). 10
Algorithm 2 Continual DP-SGD Under Single-Edit User Streams 1: Input: Privacy target (ε, δ); public horizon Tmax , i.e., maximum number of steps/time indices and hence an upper bound on the number of emitted bins; allocation (εb , δb ) for buffering and (εa , δa ) for aggregation; initial model w(0) ; clip norm G; stepsizes (ηk )k≥1 2: Output: Released trajectory (w(t) )t≥0 and release timing 3: Set U = Θ(ε−1 b log(1/δb )) and initialize RandBin with level U 4: Initialize the continual DP prefix-sum mechanism PrivStreamSum with budget (εa , δa ) 5: k ← 0 6: for t = 1, 2, . . . , Tmax do 7: Receive user event ft 8: Bt ← RandBin(ft ) 9: if Bt = ⊥ then 10: w(t) ← w(t−1) 11: else 12: k ←k+1 P 13: gk ← |B1t | f ∈Bt ClipG ∇f w(t−1) 14: uk ← ηk gk ▷ stepsize-scaled update 15: Sk ← PrivStreamSum(uk ) ▷ private prefix sum 16: w(t) ← w(0) − Sk ▷ post-processing of Sk 17: end if 18: end for
2. Downstream condition (Hamming-DP + certification). The downstream primitive is (εa , δa )-DP for Hamming-neighboring update streams on its own input, and passes Checklist 1, hence remains DP under adaptive interaction (Theorem 4.3). Conclusion. Under these conditions, the composed pipeline is (εb +εa , δb +δa )-DP with respect to single-edit neighboring event streams, even under adaptive interaction. This is the only composition step used to derive Theorem 3.1; the formal NPDP definition, alignment/refinement machinery, and the general modular composition theorem are deferred to Appendix C. Takeaway. Sections 4.1–4.3 justify treating the pipeline as plug-and-play: once the wrapper and certification conditions hold, we can focus on the DP-SGD instantiation and evaluation.
5
Instantiation: Continual DP-SGD Pipeline
This section instantiates the buffering–aggregation recipe (Section 4) with streaming SGD (Algorithm 2). Each arriving user event ft is buffered by RandBin. When a bin is emitted, we form a clipped mini-batch gradient and pass a (stepsize-scaled) update to a continual-release DP aggregator. In our experiments, the aggregator PrivStreamSum is either (i) the standard tree-based prefix-sum mechanism [CSS10], or (ii) the lower-triangular matrix factorization prefix-sum mechanism [FHU23]. Their formal DP and error/consistency guarantees are summarized in Appendix F. As in Fig. 1, the adversary observes the released models and the release timing (i.e., whether Bt = ⊥ at each step), while bin contents and internal states are hidden. Fixed vs. Tuned Parameters. The privacy target (ε, δ) and its allocation into (εb , δb ) and (εa , δa ) determine (i) the buffering level U (εb , δb ) and (ii) the aggregation budget for PrivStreamSum. Given a learning task, the remaining choices follow standard DP-SGD practice: the clipping norm G and stepsize schedule (ηk ) are tuned for utility. The release schedule is induced by RandBin: bins are emitted at random times, and satisfy |Bt | ∈ [U, 2U ] whenever Bt ̸= ⊥. The aggregator 11
PrivStreamSum is used as a plug-in, subject to: (i) (εa , δa )-DP for Hamming-neighboring update streams on its own input, and (ii) passing Checklist 1 so its non-adaptive DP analysis remains valid under adaptive interaction (Section 4.2). Privacy-Budget Split. We use a symmetric 50/50 split between buffering and aggregation as a simple default. Since privacy composes as (ε, δ) = (εb + εa , δb + δa ) and latency scales as U = Θ(ε−1 b log(1/δb )), any fixed split εb = cε, εa = (1 − c)ε with c ∈ (0, 1) changes the asymptotic guarantees only by constant factors; assigning constant fractions of δ changes log(1/δb ) only by an additive O(1) term. The best finite-sample split can be chosen empirically by sweeping c and measuring the latency–accuracy tradeoff. Mini-BatchPView. When a bin is emitted, the gradient estimate uses the standard mini-batch average |B1t | f ∈Bt ∇f (w). Since RandBin enforces |Bt | ∈ [U, 2U ], the batch size is controlled and varies by at most a factor of 2. Implementation Notes and Measured Latency. The server maintains (a) the current released model w(t) , (b) the FIFO buffer state of RandBin, and (c) the internal state of PrivStreamSum (e.g., the tree nodes). The model is updated only on emission times and is held fixed otherwise, yielding a piecewise-constant released trajectory. To quantify privacy-implied latency, we log the backlog Qt (pending events after time t). For an event fi , its inclusion delay is D(i) := min{t ≥ i : fi ∈ Bt } − i, which can be computed directly from the same FIFO queue evolution underlying (Qt ); we report summary statistics and empirical CDFs in the experiments. Other Optimizers. The same template applies to streaming optimizers whose per-bin updates can be encoded as a clipped, sensitivity-bounded stream for the certified continual-release aggregator: replace gk = Clip(·) and uk by the desired update encoding, while keeping RandBin as the editto-Hamming wrapper and PrivStreamSum as the aggregation primitive. Variants with additional state, such as momentum or adaptive preconditioning, require a separate audit of Theorem 4.3’s conditions; falling outside the theorem does not by itself imply failure of adaptive privacy.
6
Conclusion
We studied continual learning under adaptive interaction when privacy is defined over edit-style (single-insertion/deletion) user streams, where naive continual-release analyses do not directly apply. Our main recipe composes a randomized buffering wrapper RandBin, which reduces single-edit neighbors to a Hamming-style per-bin update interface with explicit backlog guarantees, with a certified continual-release DP primitive (tree-based prefix sums in our experiments), and then invokes modular composition to obtain end-to-end (ε, δ)-DP.
12
References [BEBP24] Jeremiah Birrell, Reza Ebrahimi, Rouzbeh Behnia, and Jason Pacheco. Differentially private stochastic gradient descent with fixed-size minibatches: Tighter RDP guarantees with or without replacement. In NeurIPS, 2024. [CCMS22] T.-H. Hubert Chan, Kai-Min Chung, Bruce M. Maggs, and Elaine Shi. Foundations of differentially oblivious algorithms. J. ACM, 69(4):27:1–27:49, 2022. [CLN+ 23] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Optimal differentially private learning of thresholds and quasi-concave optimization. In STOC, pages 472–482. ACM, 2023. [CLN+ 24] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In COLT, Proceedings of Machine Learning Research, pages 1200–1222. PMLR, 2024. [CSS10]
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. In ICALP (2), volume 6199 of Lecture Notes in Computer Science, pages 405–417. Springer, 2010.
[CSS11]
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, 2011.
[CSZZ26]
T-H. Hubert Chan, Elaine Shi, Mengshi Zhao, and Mingxun Zhou. Continual learning with participation privacy: An auditable buffering-aggregation recipe. In ICML, Proceedings of Machine Learning Research. PMLR / OpenReview.net, 2026.
[CX25]
T.-H. Hubert Chan and Quan Xue. Unraveling universally closest refinements via symmetric density decomposition and Fisher market equilibrium. In ITCS, volume 325 of LIPIcs, pages 35:1–35:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[CXG+ 13] Jianneng Cao, Qian Xiao, Gabriel Ghinita, Ninghui Li, Elisa Bertino, and Kian-Lee Tan. Efficient and accurate strategies for differentially-private sliding window queries. In EDBT, pages 191–202. ACM, 2013. [DMR+ 22] Sergey Denisov, H. Brendan McMahan, John Rush, Adam D. Smith, and Abhradeep Guha Thakurta. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In NeurIPS, 2022. [DNPR10] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In STOC, pages 715–724. ACM, 2010. [DRS22]
Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 2022.
[DRV10]
Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. Boosting and differential privacy. In FOCS, pages 51–60. IEEE Computer Society, 2010.
[Dwo06]
Cynthia Dwork. Differential privacy. In ICALP (2), volume 4052 of Lecture Notes in Computer Science, pages 1–12. Springer, 2006.
13
[FHU23]
Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 10072–10092. PMLR, 2023.
[HST+ 23] Samuel Haney, Michael Shoemate, Grace Tian, Salil P. Vadhan, Andrew Vyrros, Vicki Xu, and Wanrong Zhang. Concurrent composition for interactive differential privacy with adaptive privacy-loss parameters. In CCS, pages 1949–1963. ACM, 2023. [HSV26]
Monika Henzinger, Roodabeh Safavi, and Salil Vadhan. Concurrent composition for differentially private continual mechanisms. In PODS, 2026.
[JKT12]
Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. Differentially private online learning. In COLT, volume 23 of JMLR Proceedings, pages 24.1–24.34. JMLR.org, 2012.
[JRSS23]
Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. The price of differential privacy under continual observation. In ICML, volume 202 of Proceedings of Machine Learning Research, pages 14654–14678. PMLR, 2023.
[Kad68]
Joseph B Kadane. Discrete search and the Neyman-Pearson lemma. Journal of Mathematical Analysis and Applications, 22(1):156–171, 1968.
[KMS+ 21] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In ICML, volume 139 of Proceedings of Machine Learning Research, pages 5213–5225. PMLR, 2021. [KOV15]
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In ICML, volume 37 of JMLR Workshop and Conference Proceedings, pages 1376–1385. JMLR.org, 2015.
[Mir17]
Ilya Mironov. Renyi differential privacy. In Computer Security Foundations Symposium (CSF), 2017 IEEE 30th, pages 263–275. IEEE, 2017.
[SCS13]
Shuang Song, Kamalika Chaudhuri, and Anand D. Sarwate. Stochastic gradient descent with differentially private updates. In GlobalSIP, pages 245–248. IEEE, 2013.
[TS13]
Abhradeep Guha Thakurta and Adam D. Smith. (Nearly) optimal algorithms for private online learning in full-information and bandit settings. In NIPS, pages 2733–2741, 2013.
[UUA21]
Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. Differentially private analysis on graph streams. In AISTATS, Proceedings of Machine Learning Research, pages 1171–1179. PMLR, 2021.
[VZ23]
Salil P. Vadhan and Wanrong Zhang. Concurrent composition theorems for differential privacy. In STOC, pages 507–519. ACM, 2023.
[ZSCM23] Mingxun Zhou, Elaine Shi, T.-H. Hubert Chan, and Shir Maimon. A theory of composition for differential obliviousness. In EUROCRYPT (3), volume 14006 of Lecture Notes in Computer Science, pages 3–34. Springer, 2023.
14
[ZZCS24]
Mingxun Zhou, Mengshi Zhao, T.-H. Hubert Chan, and Elaine Shi. Advanced composition theorems for differential obliviousness. In ITCS, volume 287 of LIPIcs, pages 103:1–103:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
Appendix A
Detailed Preliminaries
We formalize the setting as outlined in the introduction. We first describe the concept of an abstract interactive mechanism, from which we will derive other forms of interactive mechanisms later. Abstract Interactive Mechanism. We use U to denote the collection of all valid messages, where {⊥, halt} ⊆ U . We use R to denote the collection of random seeds. In this work, we focus on the case that both U and R are finite. An interactive mechanism M is specified by a distribution RM on R and a transition function M : R × U ∗ → U, where U ∗ := ∪i∈N U i , with the convention that U 0 is the identity under Cartesian product, i.e., R × U 0 = R. Note that we sometimes overload the notation such that M denotes both the mechanism and the corresponding transition function. Here is the functionality of an interactive mechanism. 1. The mechanism M samples a (secret) random seed r ∈ R according to the distribution RM . 2. At time step t = 0, the mechanism outputs M(r) ∈ U . If the mechanism is supposed to wait for the first input message, we use the convention that M(r) = ⊥. 3. At time step t ≥ 1, suppose a message xt ∈ U (which may be chosen depending on the history before time t) is sent to the mechanism. We use x[1..t] := (x1 , x2 , . . . , xt ) ∈ U t to denote the messages received by the mechanism from the previous time steps up to t. Then, at this time step, the mechanism outputs M(r; x[1..t]) ∈ U. 4. If, for some t, M(r; x[1..t]) = halt, then the mechanism halts at time step t.
Instantiation: Mapping the Abstract Interaction to Our Transcript. The abstract interaction formalism above subsumes the continual-learning setting of Section 2. Concretely, we instantiate the mechanism’s input messages as the user-side stream xt := ft (or, when modeling a subcomponent, xt may represent an emitted bin Bt or a per-bin update gt ), and we instantiate the mechanism’s outputs as the released observations yt := (vt , w(t) ), so that the induced transcript is tr≤T = ((vt , w(t) ))Tt=0 . The adversary’s view function νA reveals exactly the observable portion of each release—the timing bit and model snapshot—matching the trajectory-and-timing threat model in Section 2. Bounded Termination. In addition to finite R and U, we consider mechanisms that always terminate in a bounded number of steps. Specifically, for each mechanism M, there exists TM ∈ Z such that M always terminates in at most TM steps. This is without loss of generality, because any privacy notion defined for mechanisms with bounded termination can be extended naturally to unbounded mechanisms. We simply require that, for any T ∈ Z+ , the truncated mechanism obtained by running the (unbounded) mechanism for T steps will satisfy the privacy notion defined for bounded mechanisms. This matches the “for every horizon T ” convention in Section 2. 15
Mechanism View. The view observed by a mechanism M up to time step t consists of its generated random seed r and its received input messages x[1..t] up to time t. Remark A.1. Since M can recover its own output sequence from its random seed and input sequence, it suffices to include the latter two in its view. Similarity Between Mechanisms. To formalize privacy notions later, we need a way to quantify the similarity between two mechanisms. Since we consider randomized mechanisms, we will use power functions to compare how different two distributions are. It is known that power functions are general enough to capture all divergences satisfying the data processing inequality. Recall that in this work, we focus on finite sample spaces. Definition A.2 (Data Processing Inequality). A divergence measure is a function D that takes two distributions P and Q on the same space such that D(P ∥Q) ≥ 0, where equality holds iff the distributions P = Q are identical. A divergence D satisfies the data processing inequality if, for any stochastic transformation (or channel) T that maps the original space to another space, the following inequality holds: D(T (P )∥T (Q)) ≤ D(P ∥Q), where T (P ) and T (Q) are the resulting distributions after applying the transformation T to P and Q, respectively. Definition A.3 (Power Function as Fractional Knapsack Problem [Kad68]). Suppose P and Q are distributions on the same finite sample space Ω, i.e., P and Q are vectors in RΩ ≥0 whose coordinates sum to 1. The power function Pow(P ∥Q) : [0, 1] → [0, 1] can be defined in terms of the fractional knapsack problem. Given a collection Ω of items, suppose ω ∈ Ω has weight P (ω) and value Q(ω). Then, given α ∈ [0, 1], Pow(P ∥Q)(α) is the maximum value attained with weight capacity constraint α, where items may be taken fractionally. Intuition. When two distributions P and Q are the same, it is clear that given any capacity constraint α, the maximum reward is also α; this means the power function is exactly the identity function. However, if the two distributions are very different, this means that there are items whose reward-to-weight ratios are large; hence, in this case, the power function can initially grow faster than the identity function. Partial Order on Power Functions. Pointwise comparison naturally induces a partial order on power functions. We denote f1 ≤ f2 if for all α ∈ [0, 1], f1 (α) ≤ f2 (α), where a larger f2 indicates that the two distributions are more different. Fact A.4 (Properties of Power Functions). For any two distributions P and Q on the same sample space, Pow(P ∥Q) ≥ Id, where Id : [0, 1] → [0, 1] is the identity function, and equality holds iff the distributions P = Q are identical. Moreover, power functions satisfy the data processing inequality, i.e., for any stochastic transformation (or channel) T that maps the original space to another space, the following inequality holds: Pow(T (P )∥T (Q)) ≤ Pow(P ∥Q). Differential Privacy in Terms of Power Function. Given ε ≥ 0 and 0 ≤ δ ≤ 1, the power function DPε,δ : [0, 1] → [0, 1] can be described as follows (see Figure 2): 16
1.0
DP , Identity
power
0.8 0.6 0.4 0.2 0.0 0.0
intercept= 0.2
0.4
0.6
0.8
1.0
Figure 2: Power function DPε,δ for ε = 1 and δ = 0.3. 1. In the xy-plane, starting at (0, δ), the function increases linearly with slope eε until it touches 1−δ eε +δ the line y = 1 − x at ( 1+e ε , 1+eε ). 2. After touching the line y = 1 − x, the slope changes to e−ε , until the line segment reaches (1 − δ, 1), where the curve remains horizontally till the end (1, 1) is reached. In other words, 1−δ ε for 0 ≤ α ≤ 1+e ε; δ + e · α, 1−δ −ε −ε DPε,δ (α) = 1 − e (1 − δ) + e α, for 1+eε < α ≤ 1 − δ; 1, for 1 − δ < α ≤ 1. Below are some facts on power functions that we will use, which are usually equivalently stated in the literature in terms of the tradeoff function T(P ∥Q)(α) := 1 − Pow(P ∥Q)(α). Fact A.5 (DP in Terms of Power Function [DRS22]). Given two distributions P and Q on the same sample space Ω, Pow(P ∥Q) ≤ DPε,δ is equivalent to the statement that for all S ⊆ Ω, P (S) ≤ eε · Q(S) + δ and Q(S) ≤ eε · P (S) + δ. Fact A.6. ( Triangle Inequality for Power Functions)[Theorem 2.14 in [DRS22]] Suppose X, Y , Z are distributions on the same sample space such that Pow(X∥Y ) ≤ g1 and Pow(Y ∥Z) ≤ g2 . Then, Pow(X∥Z) ≤ g2 ◦ g1 , where the composition is defined as (g2 ◦ g1 )(x) := g2 (g1 (x)). In other words, Pow(X∥Z) ≤ Pow(Y ∥Z) ◦ Pow(X∥Y ). Example. Consider g = DPε,δ . Then, g ◦ g ≤ DP2ε,δ(1+eε ) . As we shall see, this is relevant to the scenario of multi-hop neighbors – aka group DP in the literature. Definition A.7 (Supremum of Power Functions). Given a collection S of power functions, its supremum sup(S) = supf ∈S f is the least power function fb such that for all f ∈ S, f ≤ fb. Formally, for each α ∈ [0, 1], fb(α) := sup{λ · f1 (α1 ) + (1 − λ) · f2 (α2 ) | f1 , f2 ∈ S; α1 , α2 , λ ∈ [0, 1] : α = λα1 + (1 − λ)α2 }. Definition A.8 (Tensor Product of Power Functions). Suppose f and g are power functions that are attained by the corresponding distributions in Pow(P1 ∥P2 ) = f and g = Pow(Q1 ∥Q2 ). Then, their corresponding tensor product f ⊗ g = Pow(P1 × Q1 ∥P2 × Q2 ) is defined in terms of the corresponding product distributions. Fact A.9 (Joint Convexity [DRS22]). Suppose Λ is an indexing set and f is a power function such that for each λ ∈ Λ, a pair (P (λ), Q(λ)) of distributions satisfy Pow(P (λ)∥Q(λ)) ≤ f . Then, for any distribution L on Λ, Pow(P (L)∥Q(L)) ≤ f . 17
Fact A.10 (Composition Rule of Power Functions [DRS22]). Suppose P and P ′ are distributions on the sample space Ω. For each ω ∈ Ω, Q(ω) and Q′ (ω) are distributions on sample space Ω′ . If Pow(P ∥P ′ ) ≤ f and Pow(Q(ω)∥Q′ (ω)) ≤ g for all ω ∈ Ω, then Pow((P, Q(P ))∥(P ′ , Q′ (P ′ ))) ≤ f ⊗g. Distinguishing between Interactive Mechanisms. Suppose we wish to compare the behavior of two mechanisms M0 and M1 , to which we only have oracle accesses. An adversary A : R × U ∗ → U is also an interactive mechanism. The adversary has some view function νA : U → U that specifies what information it can gather from the output of the mechanism. However, later when we instantiate from the abstract mechanism, we will use the structure of the message space to clarify what the adversary can observe. We next define the interaction A ↔ M between the two mechanisms. The adversary A repeatedly sends messages to M. At each time step, the adversary determines the next message to be sent to M, based on the history of prior interactions. This process repeats iteratively, until the mechanism M outputs halt in some time step. Formally, it is captured by the following description. 1. The mechanisms A and M sample the random seeds rA and rM , respectively. 2. At time step t = 0, M outputs y0 ← M(rM ) ∈ U. A observes v0 := νA (y0 ). 3. At time step t ≥ 1, (a) A generates xt ← A(rA ; v[0..t − 1]) and sends to M. (b) M responds yt ← M(rM ; x[1..t]); A observes vt := νA (yt ). The process terminates as soon as either xt or yt is halt; otherwise, the process continues for the next time step. Definition A.11 (Adversary View). Suppose the interaction A ↔ M terminates at time step t (which may be a random quantity). Then, the adversary view is defined as: view(A ↔ M) := (rA ; v[0..t]). Terminology (“non-adaptive”). In this paper, when we say “non-adaptive” for a continual mechanism’s privacy analysis, we mean the mechanism’s input stream is fixed in advance (equivalently, the environment/adversary that provides inputs does not condition on past outputs). Definition A.12 (Non-Adaptive Adversary). An adversary transition function A : R × U ∗ → U is non-adaptive, if there exists a transition function of the form Ab : R × Z → U such that for any b t). length-t sequence v[0..t − 1], A(r; v[0..t − 1]) = A(r; We can next define a distance notion between two mechanisms based on power functions. Intuitively, it quantifies the difficulty of distinguishing between two mechanisms. Definition A.13 (Power Function between Mechanisms). Given two interactive mechanisms M0 and M1 , we overload the notation and denote Pow (M0 ∥M1 ) ≤ f , for some power function f , if for all adversaries A, Pow (view(A ↔ M0 )∥view(A ↔ M1 )) ≤ f. If we have the weaker requirement that the inequality holds for just non-adaptive adversaries, we denote: PowNA (M0 ∥M1 ) ≤ f . 18
Simulation of Two Close Interactive Mechanisms with Close Random Seeds. The following result from [VZ23] states that if two mechanisms are close in the sense of Definition A.13, then it is possible to simulate either one of them exactly with the same mechanism transition function that initially takes a random seed generated from one of the two appropriate distributions. Because the proof uses induction and Cartesian products of sample spaces, only the special case of finite sample and message spaces and mechanisms with bounded termination is considered. It is plausible that the result could be generalized to unbounded spaces, but that would likely require the Axiom of Choice, which often falls outside the scope of the computer science community. This is a very useful lemma in proving privacy composition results, because instead of interacting with two potentially different mechanisms in every time step, we can view the adversary as interacting with the same mechanism transition function but with initial random seeds drawn from two different distributions. One useful analogy is that after a sensitive database is anonymized with appropriate noise, then it can be queried unlimited number of times without privacy degradation because of data post-processing. Lemma A.14 (Exact Simulation of Two Close Interactive Mechanisms [VZ23], Theorem 1.5). Suppose M0 and M1 : R × U ∗ → U are two interactive mechanisms with bounded termination, and f is a power function such that Pow(M0 ∥M1 ) ≤ f in the sense of Definition A.13. Then, there exist two distributions N0 and N1 on some sample space Ω and a transition function P : Ω × U ∗ → U such that Pow(N0 ∥N1 ) ≤ f , and, for all adversaries A, the following holds for both b ∈ {0, 1}: view(A ↔ Mb ) ≡ view(A ↔ P(Nb )), where P(N ) is the interactive mechanism that uses the specified transition function P with a random seed drawn from the distribution N .
B
Modular Composition of Interactive Mechanisms with Hidden Outputs
Interactive Mechanism with Hidden Output. We next consider a special form of interactive mechanism with a transition function of the form M : R × X ∗ → V × Y. Here, we use X to denote the input space. In each time step, the mechanism produces (v, y) ∈ V × Y, where the adversary can observe v from the view space V and the output y from the output space Y is potentially hidden from the adversary, which may be passed to another interactive mechanism (that could however possibly leak information about y). If an adversary only interacts with M, then it can be described by a transition function with the form A : R × V ∗ → X . Neighboring Input Sequences. Similar to the conventional differential privacy, we need a neighboring notion for input sequences such that intuitively the behaviors of a mechanism on two neighboring input sequences should be similar. Assumption B.1 (Prefix-Closed Neighboring Relation). We assume there is a neighboring relation ∼X ∗ (or just ∼ for succinctness) that satisfies the property that if two sequences x[1..t] ∼ x′ [1..t′ ] are neighboring, then the following holds: (i) They have the same length, i.e., t = t′ . (ii) All their corresponding prefixes are neighboring, i.e., for all 1 ≤ τ < t, x[1..τ ] ∼ x′ [1..τ ]. Privacy for Interactive Mechanisms. Since the inputs for an interactive mechanism in later time steps can be influenced by its earlier behavior, one cannot formally define its privacy just based on neighboring input sequences. In the literature, adaptive differential privacy [JRSS23] is based on a construction that we call paired simulation. 19
Definition B.2 (Paired Simulation). Suppose an interactive mechanism is given by the transition function M : R × X ∗ → V × Y and the random seed distribution RM , where a neighboring relation is defined on X ∗ . pair Then, the paired simulation consists of a canonical pair of interactive mechanisms (Mpair 0 , M1 ) : R × (X 2 )∗ → V × Y. such that for each b ∈ {0, 1}, the transition function has the form Mpair b Moreover, in the paired simulation, an adversary with transition function A : R×V ∗ → X 2 interacts with Mpair as follows. b The interaction between an adversary A and Mpair b : 1. A and M sample the hidden random seeds rA and rM from their own distributions, respectively. 2. At time step t = 0, the simulation calls (v0 , y0 ) ← M(rM ). If M is supposed to wait for the first input message, (v0 , y0 ) = (⊥, ⊥). (0)
(1)
3. At time step t ≥ 1, A constructs a pair (xt , xt ) ← A(rA ; v[0..t − 1]) ∈ X 2 and sends to the simulation. If the sequences x(0) [1..t] and x(1) [1..t] generated so far are not neighboring, the whole simulation terminates. Otherwise, (vt , yt ) ← M(rM ; x(b) [1..t]), and A observes vt . If either A or M decides to halt, then the whole simulation terminates. The adversarial view is denoted as view(A ↔ Mpair b ). If the simulation does not terminate before time step t, then the view up to time t includes the random seed rA and v[0..t]. Definition B.3 (Differentially Private (DP) View). Given an interactive mechanism M, suppose pair (Mpair 0 , M1 ) is the paired simulation as in Definition B.2. For a power function f , the mechanism M is adaptively f -differentially private (DP) if pair Pow(Mpair 0 ∥M1 ) ≤ f , for all adaptive adversaries in the sense of Definition A.13. Similarly, pair non-adaptively f -DP is defined by PowNA (Mpair 0 ∥M1 ) ≤ f . Multi-Hop Neighboring Notion. In the literature, group DP or multi-hop neighbors can be generalized to sequences readily. Definition B.4 (k-Hop Neighboring Sequences). For k = 1, 1-hop neighboring is the same as that in Assumption B.1. For k ≥ 2, two sequences x and x′ are k-hop neighboring if there exist x1 , . . . , xk−1 such that for 0 ≤ i < k, xi and xi+1 are 1-hop neighboring, where x0 = x and xk = x′ . We also generalize Definition B.2 to multi-hop neighboring simulation. Definition B.5 (k-Hop Neighboring Simulation). Generalizing the description in Definition B.2, (0) (1) (k) in each time step t, the adversary generates a tuple (xt , xt , . . . , xt ) such that for each 0 ≤ i < k, x(i) [1..t] and x(i+1) [1..t] are neighboring sequences. (b) Moreover, for b ∈ [0..k], Mhop is a simulation of M that takes the b-th component xt at each b step t.
20
Fact B.6 (Adaptive DP for Multi-Hop Neighboring Sequences). Suppose M is adaptively f -DP as in Definition B.3. Then, in a k-hop neighboring simulation as in Definition B.5, we have: hop ◦k Pow(Mhop 0 ∥Mk ) ≤ f , ◦1 where f = f and f ◦(i+1) = f ◦i ◦ f . Proof. This follows from Definition B.3 and Fact A.6. Modular Composition of Interactive Mechanisms. As mentioned above, the hidden output of one mechanism may be fed as the input of another mechanism. To this end, we define a specific form of composition that we call modular composition. The adversary only directly supplies an input to the “head” mechanism of the list, where each intermediate mechanism receives its input from the (hidden) output from the previous mechanism. Modular composition is an interactive mechanism with a transition function of the form (M → N ) : R1 × R2 × X ∗ → V × W × Z described as follows. 1. The mechanisms A, M and N sample the hidden random seeds rA , rM , rN from their own distributions, respectively. 2. At time step t = 0, call the subroutine (v0 , y0 ) ← M(rM ) and (w0 , z0 ) ← N (rN ). The adversary observes (v0 , w0 ). 3. At time step t ≥ 1, (a) the adversary generates xt ← A(rA ; v[0..t − 1], w[0..t − 1]), and sends it to the head mechanism of the modular composition (M → N ). (b) call the subroutine (vt , yt ) ← M(rM ; x[1..t]) and pass the hidden output yt to the next mechanism N ; (c) call the subroutine (wt , zt ) ← N (rN ; y[1..t]); (d) the adversary observes (vt , wt ). The whole process terminates as soon as one of A, M and N terminates. Otherwise, the process continues for the next time step. If the process terminates at time step t, the view of the adversary consists of its random seed rA , v[0..t] and w[0..t]. Definition B.7 (Modular Composition). Suppose two interactive mechanisms are given by the transition functions M : R1 × X ∗ → V × Y and N : R2 × Y ∗ → W × Z, with random seed distributions RM and RN , respectively. Then, an adversary with transition function A : R × (V × W)∗ → X interacts with the modular composition M → N as above. Neighbor-Preserving Paired Simulation. To consider composition of differentially oblivious mechanisms [CCMS22], the framework neighbor-preserving differential obliviousness (NPDO) [ZSCM23, ZZCS24] has been introduced to formalize the condition that if neighboring inputs are submitted to a mechanism, then the corresponding outputs would somehow be neighboring for a subsequent mechanism. To generalize this to interactive mechanisms, we will need to introduce neighborpreserving paired simulation. In addition to neighboring input sequences in X ∗ for mechanism N ,
21
we assume that there is a similar notion of neighboring sequences in Y ∗ (satisfying Assumption B.1) for mechanism N . Definition B.8 (Neighbor-Preserving Paired Simulation (NPP)). Given an interactive mechanism with transition function M : R × X ∗ → V × Y and random seed distribution RM , a neighbornpp preserving paired simulation (which might not be unique) is a pair (Mnpp 0 , M1 ) of interactive mechanisms such that the following holds. ′ 1. There exists possibly another collection R′ of random seeds and an appropriate distribution RM such that for each b ∈ {0, 1}, the corresponding mechanism has a transition function of the form Mnpp : R × R′ × (X 2 )∗ → V × Y 2 , where the random seed distribution on R still follows RM , and b ′ . the random seed from R′ is sampled from RM
In other words, in addition to a random seed in R, an extra random seed in R′ may be taken. Just like paired simulation in Definition B.2, a sequence of input pairs are also taken. However, the transition function returns a tuple in V × Y 2 , i.e., in addition to v ∈ V, a pair (y0 , y1 ) ∈ Y 2 is returned. 2. For each b ∈ {0, 1}, r ∈ R, r′ ∈ R′ , x(0) [1..t] and x(1) [1..t] ∈ X ∗ , ′ (0) (1) if x(0) [1..t] and x(1) [1..t] are not neighboring sequences, then Mnpp b (r, r ; x [1..t], x [1..t]) = ⊥, and the whole simulation terminates at time step t.
Otherwise, the pair (y (0) [1..t], y (1) [1..t]) of output sequences produced in the first t time steps are neighboring in Y ∗ . ′ (0) (1) (b) 3. If for some (v, y0 , y1 ) ∈ V × Y 2 , Mnpp b (r, r ; x [1..t], x [1..t]) = (v, y0 , y1 ), then M(r; x [1..t]) = (v, yb ).
In other words, we require consistency between Mnpp and Mpair (from Definition B.2). Specifically, b b npp pair the projection of Mb ’s output onto Mb ’s range must match the behavior of Mpair b . However, unlike paired simulation Mpair whose behavior is totally determined by the given M, in b the tuple (v, y0 , y1 ) returned above by Mnpp b , the value yb (where b ̸= b) can depend on all the input parameters in a manner that is not specified by M. 4. Augmented Adversary View. When an adversary interacts with Mnpp b , the adversarial view 2 ∗ consists of its randomness and the sequence in (V × Y ) produced until termination. Definition B.9 (NPDP Interactive Mechanisms). Given a power function f , an interactive mechanism M is said to be adaptively f -neighbor-preserving differentially private (NPDP), if there npp npp npp exists a neighbor-preserving paired simulation (Mnpp 0 , M1 ) such that Pow(M0 ∥M1 ) ≤ f , in the sense of Definition A.13. Remark B.10 (Construction of Neighbor-Preserving Paired Simulation). Observe that if one wishes to prove that a mechanism is NPDP as in Definition B.9, there is potentially some freedom to construct an appropriate NPP simulation. On the contrary, for non-interactive mechanisms (that only run for one time step), the recent result on universally closest distribution refinements [CX25] implies that a “best possible” NPP simulation may be used. Unfortunately, this does not seem to generalize to interactive mechanisms. The high level reason is that there may be no closest distribution refinements on two random sequences of length t + 1 such that its prefix projection would give a closest distribution refinement for the corresponding prefixes of length t. In other words, if one constructs the “best possible” NPP up to time step t, it may not result in the best NPP if the process enters step t + 1. 22
C
Modular Composition Theorem for Adaptively Differentially Private Interactive Mechanisms
We next describe a modular composition theorem for interactive mechanisms. At a high level, the theorem states that if the first stage is neighbor-preserving (NPDP) with privacy profile f , and the second stage is (adaptive) DP with profile g on the intermediate stream, then the end-to-end interactive pipeline is (adaptive) DP with profile f ⊗ g. How this theorem relates to existing composition frameworks. Our theorem can be viewed as a direct consequence of two existing ideas, once NPDP is interpreted through paired simulation. First, it is shown [ZZCS24] that neighbor-preserving notions (including differential obliviousness/NPDO) admit an equivalent characterization in terms of a paired simulation that outputs a refinement pair. Informally, in the standard secret-bit distinguishing game, an adversary provides (0) (1) at each time step a neighboring pair (xt , xt ), and a secret bit b ∈ {0, 1} selects which component is the “real” input. A mechanism is DP if the adversary’s views under b = 0 and b = 1 are close. The refinement-pair view resolves the usual obstacle in modular composition: even if the real world uses x(b) and produces a real intermediate output y (b) , one also needs a synthetic neighbor y (1−b) so that the next stage can be analyzed in a paired simulation. The NPDP guarantee precisely asserts the existence of such a paired simulator that, for each b, produces a pair (y (0) , y (1) ) whose b-marginal matches the real execution, and such that the two resulting pair-distributions (for b = 0 vs. b = 1) are close. Second, a general framework for adaptive privacy of continual mechanisms [HSV26] is developed to prove concurrent composition theorems under interactive adversaries. In particular, once a mechanism is expressed in the standard secret-bit game (and the controller only interacts with downstream submechanisms through their privatized outputs), privacy of the overall system follows from standard interactive composition and post-processing. Under the paired-simulation perspective, our two-stage pipeline M → N fits this template: the NPDP stage can be viewed as a (0) (1) mechanism that, on secret bit b, outputs a paired intermediate stream (yt , yt ) (together with visible outputs vt ), and the DP stage N is then run on y (b) . Thus, one may reduce modular composition to ordinary interactive composition: compose the lifted NPDP mechanism (as DP-on-the-bit with profile f ) with the second-stage DP mechanism (profile g), and finally apply post-processing to remove the extra synthetic transcript. While this reduction gives a useful conceptual guide and could be formalized by instantiating the conditions of [HSV26] together with the refinement-pair characterization of [ZZCS24], we include below a self-contained proof tailored to our setting and our power-function accounting. In particular, a more general concurrent setting (multiple submechanisms with interleaving calls) is studied in [HSV26], whereas we only need the serial modular composition used by our buffering– aggregation pipeline. Providing a direct proof also makes explicit how the privacy profile tensor f ⊗ g arises in our notation, and it cleanly interfaces with the certification arguments in other sections. Theorem C.1. Suppose an interactive mechanism with transition function M : R1 × X ∗ → V × Y is adaptively f -NPDP (as in Definition B.9). Suppose another interactive mechanism N : R2 × Y ∗ → W × Z is adaptively g-DP (as in Definition B.3). Then, the modular composition (as in Definition B.7) M → N : R1 × R2 × X ∗ → V × W × Z is adaptively f ⊗ g-DP.
23
The augmented adversary Ab interacts with Lbb , for each b ∈ {0, 1}, as follows. npp pair pair ′ 1. The mechanisms A, (Mnpp 0 , M1 ) and (N0 , N1 ), sample the random seeds rA , (rM , rM ), rN from the appropriate distributions, respectively. (0)
(1)
′ 2. At time step t = 0, call the subroutines (v0 , y0 , y0 ) ← Mnpp b (rM , rM ) and (w0 , z0 ) ← Nbpair (rN ).
Ab observes (v0 , w0 ). 3. At time step t ≥ 1, (0)
(1)
(a) Ab generates (xt , xt ) ← A(rA ; v[0..t − 1], w[0..t − 1]), and sends it to Lbb . (0)
(1)
′ (0) (1) (b) (vt , yt , yt ) ← Mnpp b (rM , rM ; x [1..t], x [1..t]) and pass the hidden output pair (0) (1) (yt , yt ) to the next mechanism Nbpair ;
(c) (wt , zt ) ← Nbpair (rN ; y (0) [1..t], y (1) [1..t]); (d) Ab observes (vt , wt ). and Nbpair terminates. Otherwise, The whole process terminates as soon as one of A, Mnpp b the process continues for the next time step. If the process terminates at time step t, the view of the adversary consists of its random seed rA , v[0..t] and w[0..t]. Proof. We denote the resulting interactive mechanism from the modular composition by L := pair M → N . In view of Theorem B.3, we consider the paired simulation (Lpair 0 , L1 ) as described in Theorem B.2. Specifically, our goal is to show that for any adversary A, the two distributions pair view(A ↔ Lpair 0 ) and view(A ↔ L1 ) are “close” in the sense quantified by the power function f ⊗ g. Our proof strategy is to construct an augmented pair (Lb0 , Lb1 ) of interactive mechanisms and pair an augmented adversary Ab whose views have the same distributions as those from (Lpair 0 , L1 ) and A. pair We next use Fact A.14 to show that instead of considering the pair (Lpair 0 , L1 ) with the same random seed distribution, we can equivalently simulate the pair with some common transition function, but using two different random seed distributions. By the data processing inequality, it suffices to analyze the alternative simulation and the power function of the two random seed npp distributions. Because M is f -NPDP, let (Mnpp 0 , M1 ) be the corresponding NPP simulation as npp guaranteed by Theorem B.9 such that Pow(M0 ∥Mnpp 1 ) ≤ f . By Fact A.14, there exist some interactive mechanism P and two random seed distributions F0 and F1 such that Pow(F0 ∥F1 ) ≤ f and for each b ∈ {0, 1}, P(Fb ) is an exact simulation of Mnpp (with the appropriate random seed b ′ ) for any adversary. Specifically, for each b, Mnpp (R ′ distribution RM × RM M × RM ) and P(Fb ) b are equivalent. Similarly, since N is g-DP, the paired simulation (N0pair , N1pair ) satisfies Pow(N0pair ∥N1pair ) ≤ g. Again, by Fact A.14, there exist some interactive mechanism Q and two random seed distributions G0 and G1 such that Pow(G0 ∥G1 ) ≤ g and for each b ∈ {0, 1}, Q(Gb ) is an exact simulation of Nbpair (with the appropriate random seed distribution RN ) for any adversary. Specifically, for
24
each b, Nbpair (RN ) and Q(Gb ) are equivalent. Given an adversary A that interacts with Lpair for b ∈ {0, 1}, we describe how an augmented b b b adversary A interacts with Lb in the above colored box. Because we follow exactly the same structure as in Definition B.7, after comparing the two descriptions line-by-line, it follows that b b view(A ↔ Lpair b ) has the same distribution as view(A ↔ Lb ). ′ As above, we use Fact A.14, for each b ∈ {0, 1}, we can equivalently replace Mnpp b (RM , RM ) with P(Fb ), and Nbpair (RN ) with Q(Gb ) in the above description. Hence, the first inequality below follows from the data processing inequality: pair b b b b Pow view(A ↔ Lpair 0 ) view(A ↔ L1 ) = Pow view(A ↔ L0 ) view(A ↔ L1 ) ≤ Pow(F0 × G0 ∥ F1 × G1 ) ≤ f ⊗ g, where the second inequality follows from the data processing inequality and the exact simulations, and the last inequality follows from Fact A.10.
D
RandBin: Achieving Privacy for Edit-Style Neighboring Inputs
In the literature, neighboring streams are typically defined in the Hamming sense. Specifically, given a collection O of objects, an (infinite) input stream is x : Z≥1 → O. In our applications, each object in O captures the characteristics of a user. Hamming-Style Neighboring Two streams x ∼H x′ are neighboring in the Hamming sense if there exists some t ∈ Z such that σ(τ ) = σ ′ (τ ) for all τ ̸= t. Edit-Style Neighboring. We are interested in the neighboring notion when an element may be inserted or deleted from a stream. Definition D.1 (Neighboring in the Edit Sense). Given a stream x and t ∈ Z, we use Delete(x; t) to denote the stream x′ such that for all τ < t, x′ [τ ] = x[τ ] and for all τ ≥ t, x′ [τ ] = x[τ + 1]; in other words, the element at time t is deleted in stream x to produce x′ . Two streams x ∼E x′ are neighboring in the edit sense if one stream can be obtained from the other by such a deletion operation. Two finite sequences of the same length are neighboring (in the edit sense) if they are prefixes of such neighboring streams.
D.1
Motivating Example: Private Prefix-Sum for Edit-Style Neighboring Streams
The input for the prefix-sum problem is a stream σ : Z P>0 → Z of integers, and the (accurate) output is a vector c of prefix-sums, i.e., for t ≥ 1, c[t] = ti=1 σ[i]. The well-known private prefixsum mechanism [DNPR10, CSS11] based on the binary tree structure is designed for neighboring streams in the Hamming sense. At the step t0 at which the two streams differ, the difference must be bounded, for instance |σ(t0 ) − σ ′ (t0 )| ≤ 1. Hamming-style neighboring captures the scenario when a user wants some protection on its data contents. However, whether a user has participated in the process may be regarded as sensitive information. This is captured by a neighboring notion in the edit sense. However, deleting one element from a stream can change the element for every step. For instance, if we delete the first element from the stream σ = (1, 0, 1, 0, . . .), the resulting stream σ ′ = (0, 1, 0, 1, . . .) will have every position flipped! This is as far away from being Hamming-neighboring as one can get, and 25
indeed the DP mechanism based on binary trees is not designed to provide good privacy guarantees for these two streams. Specifically, for all odd time steps t, the adversary can observe the noisy σ[t] + Nt , where Nt is independently generated noise centered at 0. Therefore, by averaging over these numbers for odd time steps, the adversary can distinguish between σ and σ ′ almost for certain. Instead of re-designing the DP prefix-sum mechanism to cater for edit-style neighboring streams, our goal is to design a pre-processing mechanism RandBin that somehow transforms edit-style neighboring streams into Hamming-style neighboring streams. Then, using the modular composition framework, we pass the processed stream to the tree-based DP prefix-sum mechanism. Random Buffer to the Rescue. Edit-style neighboring notion has been considered in the context of oblivious data structures [CCMS22,ZSCM23], and the high-level idea is to use a buffering technique to introduce random delays into the streams in the hope of eventually aligning the elements from the two edit-style neighboring streams. We give a simplified view of the procedure that processes a stream σ of elements. It maintains a buffer queue that is initially empty. At each step t, the element σ[t] enters the end of the queue. The procedure then makes two random decisions: (i) whether to remove any element from the head of the queue; (ii) if yes, then remove a random number of elements from the head of the queue and return their sum in the output stream. Consider applying this random procedure to two edit-style neighboring streams, where we use alphabets to label bits at different position: σ = [a, b, c, d, e, f ] = [1, 0, 1, 0, 1, 0] and σ ′ = [b, c, d, e, f, g] = [0, 1, 0, 1, 0, 1]. Below are possible outcomes of the random batching process for each stream, where we sum up the bits in each non-empty batch.
σ:
[⊥, ⊥, {a, b}, ⊥, ⊥, {c, d, e}] →[⊥, ⊥, 1, ⊥, ⊥, 2]
′
[⊥, ⊥, {b}, ⊥, ⊥, {c, d, e}] →[⊥, ⊥, 0, ⊥, ⊥, 2]
σ :
Note that at the end of step 6, the queue contains {f } for the case of σ and contains {f, g} for the case of σ ′ . In this particular lucky scenario, we see that the RandBin procedure has converted edit-style neighboring streams to Hamming-style neighboring streams. However, observe that these two outcomes from the two scenarios do not occur with exactly the same probability, but similar probabilities if the RandBin procedure is designed carefully. Moreover, for easy illustration, we give an oversimplified description of Hamming-style neighboring streams. We next give the formal and technical details.
D.2
Technical Description of RandBin
We use the following Hamming-style neighboring notion on bin sequences, which are suitable for private mechanisms that are designed expecting Hamming-style neighboring streams. Definition D.2 (Neighboring Bin Sequences). We use B to denote the collection of concrete bins, where a concrete bin contains an array of objects with some specified maximum array length. In our usage, a concrete bin is non-empty and is typically opaque in the sense that the adversary cannot observe its contents. A bin sequence of length T is denoted by B : [1..T ] → B ∪ {⊥}, where ⊥ means that no concrete bin is returned in that time step. Adjacent concrete bins with indices i < j in a sequence B mean that for i < t < j, B[t] = ⊥. Two bin sequences B ∼B B ′ of the same length T are neighboring if the following holds. 1. For all t ∈ [1..T ], B[t] = ⊥ iff B ′ [t] = ⊥. 26
2. Except for at most 2 indices t in [1..T ], B[t] = B ′ [t]. (a) If B and B ′ differ in exactly one index, the corresponding index refers to the last concrete bin in both sequences. Moreover, the two bin contents must have the following form. There exist elements w and u and (possibly empty) element arrays σ1 and σ2 such that the two differing bins from B and B ′ contain the arrays: [σ1 , w, σ2 ] and [σ1 , σ2 , u]. (b) If B and B ′ differ in exactly two indices i < j, then the two indices correspond to adjacent concrete bins in both sequences. Moreover, there exist elements w and u and element arrays σ1 , σ2 and σ3 such that two adjacent concrete bins from each bin sequence are illustrated as follows: • [σ1 , w, σ2 ], ⊥, . . . , ⊥, [u, σ3 ] • [σ1 , σ2 , u], ⊥, . . . , ⊥, [σ3 ] Observe that if each of two neighboring bin sequences are concatenated, two resulting item sequences will have lengths differ by at most 1, in which case deleting one element from the longer item sequence results in the shorter item sequence. We need the following primitives to describe the RandBin mechanism. Definition D.3 (Symmetric Geometric Distribution). Let α > 1. The symmetric geometric disα−1 tribution Geom(α) takes integer values such that the probability mass function at k is α+1 · α−|k| . It is known that using Geom(eε ) as additive noise can mask two integers differing by 1 with (ε, 0)-DP. However, if we want the noise to have bounded support, then we truncate the noise and get only (ε, δ)-DP. Definition D.4 (Truncated Geometric Distribution). Let ε > 0, δ ∈ (0, 1). Let U be the smallest even positive integer such that Pr |Geom(eε )| ≥ U2 ≤ δ, where U = O( 1ε log 1δ ). The truncated geometric distribution G(ε, δ) has support [− U2 , U2 ], and is obtained by first sampling r from Geom(eε ) and then truncating r within [− U2 , U2 ], i.e., return min(max(− U2 , r), U2 ). Differentially Private Streaming Prefix Sum with Always Error Bounds. We use the (ε, δ)-DP interactive mechanism from Theorem F.1, denoted as StreamSumε,δ . Observe that StreamSumε,δ is not necessarily private against adaptive adversaries. Even though we will prove that RandBin is adaptively NPDP, we do not need the adaptive property from StreamSumε,δ , but rather that the additive error from all time steps t be bounded by some function E(t) with probability 1. Mechanism Intuition. In Algorithm 3, we reinterpret RandBin (which was introduced in [CCMS22, ZSCM23]) as an interactive mechanism. On a high level, the mechanism maintains an internal buffer that is a subarray. In each time step t, the mechanism takes an element x[t] from the input stream and appends it to the end of the buffer. The mechanism decides according to some rules if a new bin should be created from a prefix of the buffer contents. If yes, a prefix from the buffer is removed to form a new bin that is returned in this step; otherwise, nothing is returned in this step and we denote the output by ⊥.
27
Algorithm 3 Interactive RandBin Mechanism 1: Input: ε > 0, δ ∈ (0, 1); a stream x : Z≥1 → O of items 2: Output: A bin sequence Z≥1 → B ∪ {⊥}; an adversary can only observe whether a concrete bin or ⊥ is output in each step 3: Denote ε1 = ε2 = 2ε and δ1 = δ2 = 2δ 4: Let G(ε1 , δ1 ) be the truncated geometric distribution, and let U := O ε1 log δ1 1 1
be the value
defined in Definition Theorem D.4 3U 5: Denote the distribution G := 3U 2 + G(ε1 , δ1 ), whose mean is 2 and whose support is [U..2U ] 6: Initialize an instance of the interactive mechanism StreamSumε2 ,δ2 , as in Theorem F.1, that takes elements in [U..2U ] 7: Moreover, with probability 1, the additive error for the length-i prefix sum is strictly less than 1 1 E[i] := O · log i · log i + log ε2 δ2 8: Initialize an empty FIFO queue Buf ← ∅ 9: Set Index ← 0, C[0] ← 0, and S[0] ← 0 10: for each time step t ≥ 1 at which element x[t] is received do
Append x[t] to the end of the queue Buf if t < S[Index] + E[Index] + 2U then 13: Output ⊥ in step t 14: else 15: Remove the first C[Index] elements from the queue Buf to form Bin[Index] 16: ▷ Bin[Index] ̸= ⊥ is a concrete bin ⇔ C[Index] > 0 ⇔ Index > 0 17: Output Bin[Index] in step t 18: Update Index ← Index + 1 19: Sample C[Index] independently from G 20: S[Index] ← StreamSumε2 ,δ2 (C[Index]) 21: end if 22: end for 11: 12:
Theorem D.5 (Utility Guarantee of RandBin). At the end of every step t, with probability 1, the concatenation of the concrete bins that have been output so far is a prefix of the input stream with length at least t − O( 1ε · log t · (log t + log 1δ )). Proof. Observe that because the additive error of StreamSumε,δ holds with probability 1, the Buf will never run into underflow in line 15. Actually, to ensure no underflow, it suffices to have t < S[Index] + E[Index] in line 12; we shall see that the extra term 2U is crucial to argue that RandBin is private against adaptive adversaries. Note that at the end of time step t, we have the invariant that t < S[Index] + E[Index] + 2U ; this holds because S[Index + 1] − S[Index] ≥ U ≥ 1 and E[Index + 1] ≥ E[Index]. Moreover, at this moment, the number of elements in the queue Buf is
t−
Index−1 X
C[j] < (S[Index] + E[Index] + 2U ) − (S[Index − 1] − E[Index − 1])
j=1
1 1 ≤4U + E[Index] + E[Index − 1] = O( · log t · (log t + log )), ε δ 28
using the crude bound Index ≤ t.
D.3
Adaptive Privacy Analysis
Privacy of RandBin. Observe that in each step, the view of the adversary just consists of one bit of information: whether a concrete bin or ⊥ is returned. Moreover, the distribution of the view is always the same, regardless of what the input stream is. However, as noted in [ZSCM23], when a mechanism has hidden outputs that will be passed to another mechanism, one needs to consider the joint distribution of the view and the output, which is why NPDO was defined, which we have extended to interactive mechanisms in Definition B.9. Construction of Neighbor-Preserving Paired (NPP) Simulation for RandBin. The proofs in [ZSCM23] already contain an implicit description of how an NPP simulation for RandBin is constructed, but we will make it explicit here. Recall that the adversary will generate two input sequences (x(0) , x(1) ) in an NPP simulation in Definition B.8. For b ∈ {0, 1}, the mechanism Mnpp b will do two things in each step t. 1. Simulate the behavior of the original mechanism M on the sequence x(b) [1..t] to produce the corresponding view v[t] and output y (b) [t]. 2. Generate another output y (b) [t] such that the output sequences y (b) [1..t] and y (b) [1..t] are neighboring. The counter-intuitive point is that y (b) [1..t] is not necessarily the simulation of the original M on the other input sequence x(b) . In fact, it is possible that y (b) [1..t] may not even be in the support of M on x(b) . In general, extra randomness other than that used in the original M may be needed to generate y (b) [t]. However, for RandBin, no extra randomness is needed. Technical Assumption on Input Pair. Note that in Definition B.8, the adversary needs to ensure that at every time step t, the pair (x(0) [1..t], x(1) [1..t]) of input sequences generated so far are neighboring (in the edit sense). For instance, for t = 4, the pair ([0, 1, 0, 1], [1, 0, 1, 0]) of sequences are neighboring in the edit sense, but the issue is that we do not know which stream has an element deleted. If next input pair at t = 5 is (0, a), then we know that in the two streams (x(0) , x(1) ), the first element from x(0) is deleted to produce x(1) ; on the other hand, if the next input pair at t = 5 is (a, 1), then the opposite is true. However, in the construction of RandBinnpp b , we would need to know whether an element is deleted from x(0) or x(1) . Observe that this issue will not arise if a stream contains only distinct elements. In practice, this is a valid assumption because an item is typically tagged with unique metadata. Hence, in the proof, we assume that if the adversary first generates x(0) [t] ̸= x(1) [t] at step t, then when we receive a pair at the beginning of step t + 1, we will know from which stream an element is deleted. This will not be too late, because the additive error for the prefix-sum S[Index] is at most E[Index], we can ensure that the Buf queue will never be empty, i.e., an element arriving at step t will never be returned in a concrete bin in the same step t. npp npp Definition D.6 (Description of (RandBinnpp 0 , RandBin1 )). We focus on the description of RandBin0 (because the behavior of RandBinnpp is symmetric); recall that the adversary generates a pair of 1 (0) (1) time sequences (x , x ).
29
The first component simulates RandBin from Algorithm 3 on the sequence x(0) ; in every step t, it will output y (0) [t] that is either a concrete bin or ⊥. We describe the second component more carefully, which is how y (1) [t] is constructed in each step t. Note that since the two output sequences must be neighboring as in Definition D.2, we will make sure y (0) [t] = ⊥ iff y (1) [t] = ⊥. Moreover, we need to ensure that at most two adjacent concrete bins are different in a specific way. We consider two cases. 1. Suppose an element x(0) [t] = w is deleted from x(0) to produce the stream x(1) . In the output sequence y (0) , we focus on two adjacent concrete bins that contains the deleted item w and the next concrete bin: [σ1 , w, σ2 ], ⊥, . . . , ⊥, [u, σ3 ], where σ1 , σ2 and σ3 are (potentially empty) subarrays. Then, in the output sequence y (1) , those two concrete bins are modified to: [σ1 , σ2 , u], ⊥, . . . , ⊥, [σ3 ]. Note that the bin y (0) [τ ] = [σ1 , w, σ2 ] is returned in the output sequence y (0) in some step τ > t; observe that at the end of step τ , in the remaining Buf queue, u should be the first element. Moreover, u should have already appeared in the input pair together with the last is able to produce y (1) [τ ] = [σ1 , σ2 , u]. element of σ. Hence, RandBinnpp 0 Moreover, note that if [u, σ3 ] contains exactly U elements, then [σ3 ] will not be in the support of simulating the actual RandBin. 2. Suppose an element x(1) [t] = w is deleted from x(1) to produce the stream x(0) . Again, we focus on two adjacent concrete bins from the output sequence y (0) : [σ1 , σ2 , u], ⊥, . . . , ⊥, [σ3 ], where [σ1 , σ2 , u] is the bin that contains the element x(0) [t], which is also the first element in the subarray [σ2 , u]. Note that in the case that σ2 is empty, then u = x(0) [t]. Then, in the output sequence y (1) , those two concrete bins are modified to: [σ1 , w, σ2 ], ⊥, . . . , ⊥, [u, σ3 ] Note that if [σ3 ] contains 2U elements, then [u, σ3 ] will not appear in the support of simulating the actual RandBin. From construction, the two output bin sequences y (0) and y (1) are neighboring as in Definition D.2. With the formal terminology in place, we can formally restate the result in [ZSCM23]. Fact D.7 (RandBin is NPDP Against Non-Adaptive Adversary). The interactive mechanism in Algorithm 3 is non-adaptively (ε, δ)-NPDP. Specifically, in terms of power function, the NPP simulanpp npp NA tion (RandBinnpp (RandBinnpp 0 , RandBin1 ) in Definition D.6 satisfies: Pow 0 ∥RandBin1 ) ≤ DPε,δ . Lemma D.8. Suppose for some power function f , the interactive mechanism RandBin in Algorithm 3 is non-adaptively f -NPDP (with respect to input neighboring notion in Definition D.1 and output neighboring notion in Definition D.2). Then, RandBin is also adaptively f -NPDP; specifinpp cally, the NPP simulation (RandBinnpp 0 , RandBin1 ) in Definition D.6 satisfies: npp npp Pow(RandBin0 ∥RandBin1 ) ≤ f .
30
Proof. By joint convexity in Fact A.9, we assume a deterministic adversary A that interacts with npp (RandBinnpp 0 , RandBin1 ). Moreover, without loss of generality, to simplify the notation, we assume that there is a canonical sequence x(t) := t. (0) (1) Then, for some initial steps t, the default action of the adversary is to generate a pair (xt , xt ) (0) (1) satisfying xt = xt = t until some critical step tc in which the adversary decides (based on its observation) to deviate from the default behavior. It can either: (0) (1) (i) delete from x(0) , i.e., for t ≥ tc , xt = t + 1 and xt = t, or (0) (1) (ii) delete from x(1) , i.e., for t ≥ tc , xt = t and xt = t + 1. Observe that before step tc , the two input sequences x(0) and x(1) are identical. Hence, the single decision made by the adversary is at which time step tc it wants to deviate from the default behavior, and it does not really matter whether it deletes from x(0) or x(1) . Augmented View. We assume a more powerful adversary that can observe, in addition to its normal view (which consists of the contents of both bins y (0) [t] and y (1) [t])), the noisy prefix-sums S[·] once they are created. We note that the proof in [ZSCM23] also allows the (non-adaptive) adversary to have this augmented view. However, it is important when the adversary learns about these noisy prefix-sums. Default Distribution. Suppose the canonical sequence x is used in both of (x(0) , x(1) ). Then, the npp behaviors of both interactive mechanisms (RandBinnpp 0 , RandBin1 ) are identical. We use Ω to denote the space of views, and P to denote the corresponding distribution of views. Each ω ∈ Ω consists of the view and output of every time step t ≥ 1. Decision of Adversary A. Because we have assumed that A is deterministic, for each ω ∈ Ω, either (i) A will never deviate from the default behavior, or (ii) A will deviate at the beginning of some step t, in which case the resulting view will be different from ω starting from step t onwards. We use Ωt ⊆ Ω to denote the collection of view in which the adversary deviates at the beginning of step t. Consider some ω ∈ Ωt . As explained above, this means that the adversary decides to deviate at the beginning of step t, after observing the information in ω up to step t − 1. This means it will generate a pair (x(0) [t], x(1) [t]) of different inputs, and as a result the distributions of outputs npp for (RandBinnpp 0 , RandBin1 ) from step t onwards may be different. For such ω ∈ Ωt , we use gω := (0) (1) Pow(Vω ∥Vω ) to denote the power function between the corresponding two view distributions (0) (1) Vω and Vω starting from step t. Key Insight. We next show that for ω ∈ Ωt , the decision of A to deviate the beginning of step t is npp equivalent to a randomized non-adaptive adversary that interacts with (RandBinnpp 0 , RandBin1 ). Suppose i is the index of concrete bins such that S[i − 1] + E[i − 1] + 2U < t ≤ S[i] + E[i] + 2U . First, analyze what information the adversary has gathered till the beginning of step t: 1. At the end of step S[i − 1] + E[i − 1] + 2U , the adversary learns the exact count C[i − 1] (and also C[i − 2], . . . , C[1]), because so far the two output sequences are identical. Moreover, it Pi also learns the noisy prefix-sum S[i] that is an estimate of j=1 C[j]. 2. At the beginning of step t, it knows the exact number of elements in the Buf queue, which is larger than 2U . Hence, the input pair of elements generated at time t will definitely not go into the concrete bin with index i. This is why we need the term 2U in line 12. The crucial observation is that at this moment, the number C[i + 1] of elements in the (i + 1)-st concrete bin has not been sampled yet. 3. Hence, if the adversary A decides to deviate P at the beginning of step t, it will know that the element at step t will be the Nω := (t − ij=1 C[j])-th element in the Buf queue. 31
The adversary does not know C[i], but based on the knowledge of S[i], S[i − 1], . . . , S[1] and C[i − 1], . . . , C[1], it knows the conditional distribution of C[i], and hence, can derive the distribution of Nω . Conclusion. For ω ∈ Ωt , the adversary A deciding to deviate at the beginning of step t will be equivalent to another instance where a randomized non-adaptive adversary decides upfront to deviate at some step according to the distribution Nω . From the hypothesis, we conclude that the (0) (1) power function satisfies gω = Pow(Vω ∥Vω ) ≤ f . Then, the whole proof concludes because: (0)
(1)
npp Pow(view(A ↔ RandBinnpp 0 )∥view(A ↔ RandBin1 )) = Pow((P, VP )∥(P, VP ))
≤Pow(P∥P) ⊗ f = f, where the inequality follows from the composition rule of power functions in Fact A.10. Fact D.7 and Lemma D.8 immediately give the following corollary. Corollary D.9. The interactive mechanism RandBin in Algorithm 3 is adaptively (ε, δ)-NPDP with input neighboring notion ∼E and output neighboring notion ∼B .
E
Adaptive Differential Privacy for Independently Decomposable Mechanisms
This section proves the adaptive-safety certification used in the modular pipeline. The goal is to identify structural conditions under which an ordinary non-adaptive privacy analysis of a continual mechanism already implies privacy against adaptive adversaries. The result applies to Hammingstyle neighboring input streams and is stated in the power-function language used throughout the appendix. The first condition is a fresh-randomness, prefix-causality condition. At round t, the mechanism may depend on the entire input prefix x[1..t], but the only randomness used for the round-t output is a fresh seed ωt independent of all other rounds. This rules out hidden cross-round correlations introduced by reused noise, while still allowing the release at time t to be an arbitrary deterministic function of the input prefix. Definition E.1 (Independently Decomposable Mechanisms). An (abstract) interactive mechanism with transition function M : R × U ∗ → U is independently decomposable if the following properties hold. • Each random seed r ∈ R takes the form r = (ω1 , ω2 , . . .) ∈ ΩN . Moreover, the mechanism samples ωt independently from some distribution Rt in time step t. • For each t ≥ 1, there exists a deterministic function Mt such that the output yt ← Mt (ωt ; x[1..t]) ∈ U depends only on x[1..t] and the randomness ωt sampled in step t. Quantitatively Decomposable Mechanisms. Independent decomposability alone records where the randomness enters, but does not quantify how much a change in the input prefix can affect a one-round release. We therefore add a quantitative condition. The condition says that, for each round t, the power function between the two possible round-t output laws is determined exactly by the distance between two aggregates of selected input coordinates. The invariant-pair condition below ensures that common aggregation context can be ignored: only the part of the aggregate containing the Hamming discrepancy contributes to the distance. 32
Definition E.2 (Invariant Pair). Let d : U × U → R≥0 be a metric, and let (U , ⊕, 0⊕ ) be a monoid. We say that (d, ⊕) is an invariant pair (under common aggregation context) if for all a, b, u, u′ ∈ U, d(a ⊕ u ⊕ b, a ⊕ u′ ⊕ b) = d(u, u′ ). Notation. For an index set I = {τ1 < τ2 < · · · < τk } ⊆ [1..t] and an input history x[1..t] ∈ U t , define M x[τ ] := x[τ1 ] ⊕ x[τ2 ] ⊕ · · · ⊕ x[τk ]. τ ∈I
L For I = ∅, we use the convention τ ∈I x[τ ] := 0⊕ . Since ⊕ is associative and the elements are aggregated in increasing index order, this expression is well-defined without requiring commutativity. Definition E.3 (Quantitatively Decomposable Mechanism). An interactive mechanism M : R × U ∗ → U is quantitatively decomposable with respect to an invariant pair (d, ⊕) in the sense of Definition E.2 if it is independently decomposable in the sense of Definition E.1, and there exist a sequence of index sets {It }t≥1 with It ⊆ [1..t] and, for every t ≥ 1 and θ ≥ 0, a power function gt (θ) : [0, 1] → [0, 1] such that the following hold. • For every t ≥ 1, gt (θ) ≤ gt (θ′ ) whenever 0 ≤ θ ≤ θ′ . • For every t ≥ 1 and every pair of input histories x[1..t], x′ [1..t] ∈ U t , !! M M x′ [τ ] . x[τ ], Pow Mt (Rt ; x[1..t])∥Mt (Rt ; x′ [1..t]) = gt d τ ∈It
τ ∈It
Here, Mt (Rt ; x[1..t]) denotes the distribution of Mt (ωt ; x[1..t]) when ωt is sampled from Rt . We can now state the certification theorem. The only-if direction is immediate, since nonadaptive adversaries are a special case of adaptive adversaries. The content is the converse: for quantitatively decomposable mechanisms, adaptivity does not increase the worst-case powerfunction profile. Thus any finite-horizon non-adaptive f -DP proof automatically lifts to the pairedsimulation adaptive game. Theorem E.4 (Adaptive Safety of Quantitatively Decomposable Mechanisms). Consider the Hammingstyle neighboring relation on equal-length input sequences in U , where two sequences are neighboring if they differ in at most one position. Let f be a power function. Suppose M : R × U ∗ → U is quantitatively decomposable in the sense of Definition E.3. If M is non-adaptively f -DP in the paired-simulation sense of Definition B.3, for every finite horizon, then M is adaptively f -DP in the same sense, for every finite horizon. Proof. We prove the following finite-horizon statement by induction on T : for every power function f , if M is non-adaptively f -DP up to horizon T , then M is adaptively f -DP up to horizon T . This implies the theorem because the theorem assumes the non-adaptive guarantee for every finite horizon. We first reduce to deterministic adversaries. A randomized adversary can be viewed as first sampling its random seed and then running a deterministic adversary. For every fixed seed, the deterministic-adversary case gives the desired power-function bound. Taking the mixture over the same seed distribution under the two secret bits preserves the bound by the joint convexity property in Fact A.9. Hence it suffices to consider deterministic adaptive adversaries. We also assume, without loss of generality, that the adversary observes the entire output of M in each round. If the real adversary observes only a view of the output, the real view is obtained from 33
the full-output transcript by post-processing, and the desired bound follows from data processing. If the mechanism has an initial output before the adversary sends any input, this initial output has the same distribution under the two secret bits; it may be included as an additional common first observation and does not affect the privacy bound. Thus we count rounds from the first adversarial input. pair Let A be a deterministic adaptive adversary in the paired simulation (Mpair 0 , M1 ). We pad terminated executions with a fixed halt symbol, so all transcripts have length T . This padding is post-processing and does not change the privacy claim. We must prove pair Pow view(A ↔ Mpair )∥view(A ↔ M ) ≤ f. 0 1 The base case T = 1 is immediate. With only one input round, the adversary has no previous mechanism output on which to adapt, so the adaptive and non-adaptive paired simulations coincide. Assume the statement holds for horizon T − 1, and consider horizon T > 1. Let (x(0) [1], x(1) [1]) be the first pair of inputs produced by A. Since A is deterministic, this pair is fixed. Let U (b) := M1 (R1 ; x(b) [1]) be the first-round output distribution under secret bit b. We split into two cases. Case 1: the first round is the challenge round. Assume x(0) [1] ̸= x(1) [1], and write ∆ := d(x(0) [1], x(1) [1]). Because the paired simulation only allows Hamming-neighboring prefixes, once the first inputs differ, every later input pair produced by the adversary must have equal components. That is, on every non-terminated transcript prefix and for every t ≥ 2, the adversary must output a pair of the form (xt , xt ). We use the finite-horizon convention that terminated executions are padded with a fixed halt symbol; the padded rounds have identical outputs under the two secret bits and hence contribute the identity power function. For each round t, define ( gt (∆), if 1 ∈ It , ht := Id, if 1 ∈ / It . We first show that, at every round t and every transcript prefix that can arise before round t, the conditional next-output distributions under the two secret bits have power function exactly ht . Fix such a transcript prefix. Since the adversary is deterministic, conditioning on this common prefix fixes all input pairs generated so far. As argued above, the two input histories entering round t differ only in the first coordinate. If 1 ∈ / It , then the two aggregates M M x(0) [τ ] and x(1) [τ ] τ ∈It
τ ∈It
are identical. Hence their distance is zero. Applying Definition E.3 to identical histories gives gt (0) = Id, and therefore the one-round power function is exactly Id. If 1 ∈ It , then the two aggregates have the form x(0) [1] ⊕ c
and 34
x(1) [1] ⊕ c
for the same common suffix aggregate c over the remaining indices in It . By the invariant-pair property, d(x(0) [1] ⊕ c, x(1) [1] ⊕ c) = d(x(0) [1], x(1) [1]) = ∆. Hence Definition E.3 gives the exact one-round identity Pow Mt (Rt ; x(0) [1..t])∥Mt (Rt ; x(1) [1..t]) = gt (∆) = ht . Thus the one-round power function is exactly ht , and ht depends only on t, not on the transcript prefix. We now justify that these exact one-round identities tensorize to an exact identity for the whole adaptive transcript in this case. Let Pb be the distribution of the full length-T transcript under b be the conditional distribution of y secret bit b. For a transcript prefix s = y[1..t − 1], let Kt,s t b is generated using the fresh given the prefix s under bit b. By independent decomposability, Kt,s seed Rt , which is independent of the previous seeds. From the preceding paragraph, 0 1 Pow(Kt,s ∥Kt,s ) = ht
for every prefix s that can arise. We use the following finite-experiment characterization of power functions. For two finite distributions P and Q, the power function Pow(P ∥Q) is determined by the decreasing rearrangement of the likelihood ratio Q(ω)/P (ω) under ω ∼ P ; equivalently, two pairs of finite distributions with the same power function have the same likelihood ratio distribution under their first distribution, up to the usual splitting of atoms. Moreover, tensor product of power functions corresponds to taking the product of independent likelihood ratios. Apply this characterization to the conditional kernels. For each prefix s, the likelihood ratio 1 (y ) Kt,s t Lt,s (yt ) := 0 Kt,s (yt ) 0 , the likelihood-ratio distribution determined by h . This distribution is the has, under yt ∼ Kt,s t same for every prefix s. Since Rt is fresh and independent of the previous seeds, the conditional likelihood-ratio increment at round t is independent of the past after conditioning on the prefix, and its distribution is determined only by ht . For a full transcript y[1..T ], the likelihood ratio between P1 and P0 factors as 1 T P1 (y[1..T ]) Y Kt,y[1..t−1] (yt ) = . 0 P0 (y[1..T ]) Kt,y[1..t−1] (yt ) t=1
Under P0 , the factors in this product have the same joint distribution as independent likelihoodratio variables whose one-step power functions are h1 , . . . , hT . Therefore the power function of the full adaptive transcript pair is exactly the tensor product: Pow(P0 ∥P1 ) =
T O
ht =
t=1
O
gt (∆),
t∈[1..T ] 1∈It
where the second equality uses Id ⊗ q = q for every power function q. Finally, consider any non-adaptive adversary that submits the fixed first pair x(0) [1], x(1) [1] and then submits identical inputs in every later round. The later common inputs may be chosen 35
arbitrarily. By the invariant pair property, they only contribute common aggregation context and therefore do not change the one-step power labels ht . For this non-adaptive input pair, the same tensor product is the power function of the transcript pair: O gt (∆). t∈[1..T ] 1∈It
Since M is non-adaptively f -DP up to horizon T , this tensor product is at most f . Hence pair Pow view(A ↔ Mpair )∥view(A ↔ M ) ≤f 0 1 in Case 1. Case 2: the first round is not the challenge round. Assume x(0) [1] = x(1) [1]. Denote this common value by c. Then U (0) = U (1) as distributions, and hence Pow(U (0) ∥U (1) ) = Id. We now define a shifted mechanism for the remaining T − 1 rounds after the common first input c has been fixed. Let M(c) be the mechanism whose round-s output, for 1 ≤ s ≤ T − 1, is M(c) s (Rs+1 ; z[1..s]) := Ms+1 (Rs+1 ; c, z[1..s]). This mechanism uses the independent seeds R2 , . . . , RT , so it is independently decomposable. It is also quantitatively decomposable. Indeed, for round s define Is(c) := {τ − 1 : τ ∈ Is+1 , τ ≥ 2} ⊆ [1..s]. (c)
If 1 ∈ / Is+1 , then the aggregate used by Ms+1 is exactly the aggregate over Is in the suffix history. If 1 ∈ Is+1 , then the aggregate has the common left context c, and the invariant-pair property removes this common context. Therefore, for every two suffix histories z[1..s] and z ′ [1..s], M M (c) ′ Pow M(c) z[ρ], z ′ [ρ] . s (Rs+1 ; z[1..s])∥Ms (Rs+1 ; z [1..s]) = gs+1 d (c)
ρ∈Is
(c)
ρ∈Is
Thus M(c) satisfies the same structural assumptions as M, with the time indices shifted by one. Let Λ be the set of all Hamming-neighboring pairs of suffix histories of length T − 1. For λ = (z (0) [1..T − 1], z (1) [1..T − 1]) ∈ Λ, (b)
let Vλ be the distribution of the length-(T − 1) transcript generated by M(c) on the fixed suffix input z (b) [1..T − 1]. Define (0)
(1)
gλ := Pow(Vλ ∥Vλ )
and
g := sup gλ . λ∈Λ
By definition of the supremum of power functions, g is a power function. We claim that M(c) is non-adaptively g-DP up to horizon T − 1. For deterministic nonadaptive suffix adversaries this is immediate from the definition of g. Randomized non-adaptive suffix adversaries are mixtures of deterministic ones, and the same bound follows from Fact A.9. 36
Moreover, g ≤ f . To see this, fix any λ ∈ Λ and consider the non-adaptive length-T adversary for M that submits the common first input c in both branches and then submits the suffix pair λ. The first-round output has the same distribution under the two secret bits, and the remaining (b) transcript has law Vλ under bit b. Hence the power function of this full non-adaptive transcript pair is Id ⊗ gλ = gλ . The non-adaptive f -DP assumption for M gives gλ ≤ f for every λ ∈ Λ. Taking the supremum over λ gives g ≤ f . Now condition on a possible first-round output u in the support of U (0) = U (1) . After observing u, the original deterministic adaptive adversary A induces a deterministic adaptive suffix adversary Au for the shifted mechanism M(c) : it continues exactly as A would continue after the first transcript symbol u. Let W (b) (u) := view(Au ↔ (M(c) )pair b ) be the distribution of the remaining transcript under secret bit b, and write hu := Pow(W (0) (u)∥W (1) (u)). Since M(c) is quantitatively decomposable and non-adaptively g-DP up to horizon T − 1, the induction hypothesis gives hu ≤ g for every such first-round output u. Finally, the full transcript under secret bit b has the same distribution as (U, W (b) (U )), where U ∼ U (0) = U (1) . The first coordinate has identical distribution under the two secret bits, and, conditional on U = u, the continuation distributions have power function at most g. Applying Fact A.10 with first-stage profile Id and second-stage profile g yields pair Pow view(A ↔ Mpair 0 )∥view(A ↔ M1 ) ≤ Id ⊗ g = g ≤ f. This proves Case 2. The two cases complete the induction step. Hence the finite-horizon adaptive f -DP guarantee holds for every deterministic adaptive adversary. As argued at the beginning, joint convexity then extends the same guarantee to randomized adaptive adversaries. Therefore M is adaptively f -DP for every finite horizon. Remark E.5 (Vector-Valued Aggregates). Definition E.3 states quantitative decomposability using a scalar distance parameter. This is sufficient for the theorem as used in the main text. Some standard vector-valued mechanisms, however, have an exact one-round power profile that depends on the full difference vector rather than only on its norm. For example, for coordinate-wise Laplace noise on Rk , the exact profile of u + η versus u′ + η may depend on the vector u − u′ . The theorem and proof extend verbatim to this setting by replacing the scalar distance d(u, u′ ) with an invariant difference map ∆(u, u′ ) taking values in some parameter space, such as ∆(u, u′ ) = u − u′ ∈ Rk , and replacing gt (θ) by a family gt (v) indexed by this difference parameter. The only property needed in the proof is invariance under common aggregation context: ∆(a ⊕ u ⊕ b, a ⊕ u′ ⊕ b) = ∆(u, u′ ). 37
Under this vector-indexed variant, the binary-tree prefix-sum mechanism with coordinate-wise Laplace noise is covered exactly for vector updates in Rk . In the main text, we state the simpler scalar version because the usual (ε, δ) consequences can also be obtained by upper-bounding the vector-indexed profile in terms of a norm, such as ∥u − u′ ∥1 for coordinate-wise Laplace noise.
E.1
Why Independent Decomposability Alone Is Insufficient
The certification theorem in Section E requires quantitative decomposability, not merely independent decomposability. The following example shows why the stronger condition is needed. Even when each round uses fresh independent randomness and the round-t output is a deterministic function of the input prefix and the fresh seed, a non-adaptive approximate-DP guarantee need not lift to adaptive adversaries. The obstruction is that the one-round leakage can depend on the adaptive common context, rather than only on the location and magnitude of the Hamming discrepancy. Counterexample with Fresh Independent Randomness. Consider a two-round mechanism with input and output alphabets {0, 1}. Write x1 = b and x2 = q. Using independent fresh randomness in the two rounds, the mechanism outputs Y1 , Y2 ∈ {0, 1} with Pr[Y1 = 1 | b = 0] = 0.68,
Pr[Y1 = 1 | b = 1] = 0.65,
and q=0 q=1 b = 0 Pr[Y2 = 1] = 0.28 Pr[Y2 = 1] = 0.20 b = 1 Pr[Y2 = 1] = 0.19 Pr[Y2 = 1] = 0.28. Since each output is a deterministic function of the current prefix and a fresh independent seed, the mechanism is independently decomposable in the sense of Definition E.1. For every fixed input stream (b, q), the transcript distribution is the product distribution of Y1 and Y2 . Since two-sided (0, δ)-DP is equivalent to total variation distance at most δ, it suffices to check the four Hamming-neighboring pairs: Fixed neighboring streams Total variation distance (0, 0) and (1, 0) 0.09 (0, 1) and (1, 1) 0.08 (0, 0) and (0, 1) 0.08 (1, 0) and (1, 1) 0.09. Hence the mechanism is non-adaptively (0, 0.09)-DP. (0) Now consider the deterministic adaptive adversary that chooses the challenge pair x1 = 0 and (1) (0) (1) x1 = 1 at round 1, and, after observing Y1 = y, submits the common second input x2 = x2 = y. This is a valid adaptive Hamming-neighbor adversary: the two submitted streams differ only at coordinate 1, but their common second input depends on the first release. The resulting transcript distributions are: (Y1 , Y2 ) World 0 World 1 (0, 0) 0.2304 0.2835 (0, 1) 0.0896 0.0665 (1, 0) 0.5440 0.4680 (1, 1) 0.1360 0.1820. 38
For S = {(0, 1), (1, 0)}, we have Pr[S] − Pr[S] = 0.6336 − 0.5345 = 0.0991 > 0.09. 0
1
Therefore, TV(View0 , View1 ) = 0.0991, so the mechanism is not adaptively (0, 0.09)-DP. This does not contradict Theorem E.4, because the theorem assumes quantitative decomposability. The example shows that fresh independent randomness alone is not enough: the adaptive adversary can choose a common later input that changes how the earlier Hamming discrepancy is revealed. Quantitative decomposability rules out precisely this behavior by forcing the one-round power function to depend only on the distance between the relevant aggregates, with common aggregation context removed by the invariant-pair property.
F
Streaming Prefix-Sum Mechanism
There have been numerous works on differentially private prefix-sum algorithms since the binary tree mechanism [CSS10, CSS11] was proposed. We state the properties of the variant that are needed for our applications and briefly outline how they can be achieved from existing works. Problem Setting. For each time step t ≥ 1, an input stream has some integer xt ∈ X = [a..b] from some known range that is passed to the interactive Pta value Pt mechanism StreamSum that returns St that is supposed to be an estimation of the sum τ =1 xτ . The additive error is |St − τ =1 xτ |. The adversary observes St . Neighboring Notion. Two input streams are neighboring if they differ in at most one time step, and the corresponding two values differ by 1. As aforementioned, a mechanism with unbounded termination satisfies (ε, δ)-DP if for every T > 0, the truncated mechanism run for T steps is (ε, δ)-DP. Theorem F.1 (Stream Sum with Bounded Error and Consistency). For any ε > 0, δ ∈ (0, 1) and an interval [a..b] ⊆ Z of integers, there exists an (ε, δ)-differentially private interactive mechanism StreamSumε,δ , such that given a stream {xt } of integers in [a..b], the algorithm outputs a number St in each time step t such that the following hold. • Bounded Error: With probability 1, at each time step t, the output has additive error at most E(t) := O 1ε · log t · (log t + log 1δ ) . • Consistency: With probability 1, for each time step t, the increment St − St−1 ∈ [a..b] is in the above range. As in [CCMS22], we start with a pure ε-DP prefix sum algorithm that has high probability guarantee on the additive error. Fact F.2 (Pure DP Stream Sum [CSS11]). For any ε > 0, there exists an (ε, 0)-differentially private interactive mechanism HybridStreamSumε that takes an input stream {xt } of integers and output St at each time step t with the following properties. • Bounded Error: Fix any 0 < δ < 1. With probability 1 − δ, for every time step t, the output at time t has an additive error of at most O( 1ε log t(log t + log 1δ )). 39
• Structure: In eachP time step t, the mechanism actually allows the adversary to observe noisy counts of the form i∈I xi masked with independent noise, where the index interval has the form I = [c..t]. The output St can be constructed deterministically from the noisy counts released so far. Proof of Theorem F.1. Fix ε and δ. Starting from the mechanism HybridStreamSumε in Fact F.2, we modify it step by step to achieve the desired properties. P Pt xi + E(t), return ti=1 xi + 1. Always Error Bound. If the output St is too Ptlarge, i.e., St > i=1 P E(t); if the output is too small, i.e., St < i=1 xi − E(t), return ti=1 xi − E(t). The argument in Theorem 3.2 of [CCMS22] shows this can turn a high probability additive error bound into an additive error bound with probability 1, at the cost of getting (ε, δ)-DP. 2. Consistency. The argument in Lemma 5.2 of [CSS11] shows that a further truncation operation can achieve consistency without increasing the additive error bound.
Corollary F.3. The interactive mechanism HybridStreamSumε in Fact F.2 is adaptively (ε, 0)-DP, and can be made to be consistent. Proof. The structure property in Fact F.2 implies that noisy counts obey the independent decomposability property in Definition E.1. Adaptability follows from Theorem E.4. Consistency can be achieved, because the modification can be done deterministically from the released noisy counts only. Remark F.4. It is not clear whether the “Always Error Bound” can be achieved under the independent decomposability framework, because the truncation needs to refer back to the private inputs, in addition to the released noisy counts.
F.1
Prefix Sums via Lower-Triangular Matrix Factorizations
We briefly restate the prefix-sum workload in the language of the matrix mechanism. Fix a horizon T and write the stream as a vector x ∈ RT . The prefix sums are the linear workload Mcount x ∈ RT ,
Mcount [t, i] = 1[t ≥ i],
Pt
i.e., (Mcount x)t = i=1 xi . We use the event-level neighboring notion: x ∼ x′ iff x − x′ = ±∆ei for some coordinate i ∈ [T ], where ∆ > 0 is the sensitivity unit (in the above we take ∆ = 1). Privacy Notions: Renyi DP (RDP) and zCDP. Let P, Q be distributions with densities p, q w.r.t. a common base measure. For α > 1, the (order-α) Renyi divergence is Z 1 Dα (P ∥Q) := log p(y)α q(y)1−α dy. α−1 An interactive mechanism M is (α, ε)-RDP if for all neighboring x ∼ x′ , Dα M(x) ∥ M(x′ ) ≤ ε. It is ρ-zCDP if for all α > 1 and all neighboring x ∼ x′ , Dα M(x) ∥ M(x′ ) ≤ ρ α. Equivalently, ρ-zCDP means (α, ρα)-RDP holds simultaneously for every α > 1. 40
Converting RDP to (ε, δ)-DP. If M satisfies (α, εα )-RDP for some α > 1, then for every δ ∈ (0, 1) it satisfies (ε, δ)-DP with log(1/δ) . α−1
ε = εα +
One may optimize over α > 1 to get the tightest (ε, δ) bound: log(1/δ) ε(δ) = inf εα + . α>1 α−1 Lower-Triangular Factorization Mechanism. Let Mcount = LR be a (possibly rectangular) factorization where R ∈ Rm×T and L ∈ RT ×m are lower-triangular in time (i.e., causal: the t-th output depends only on x[1..t] through R and L). Define the column-sensitivity of R by s(R) := max ∥Rei ∥2 = ∥R∥1→2 . i∈[T ]
Consider the Gaussian matrix mechanism ML,R,σ (x) := L Rx + z , z ∼ N (0, σ 2 Im ) with independent coordinates. Since L(·) is post-processing, privacy is governed entirely by the Gaussian release of Rx. Lemma F.5 (Exact zCDP/RDP Constants for L(Rx + z)). For neighboring x ∼ x′ with x − x′ = ±∆ei , we have ∥R(x − x′ )∥2 ≤ ∆ s(R). Hence the mechanism ML,R,σ satisfies: • zCDP: ρ-zCDP with ρ =
∆2 s(R)2 . 2σ 2
• RDP: for every order α > 1, (α, εα )-RDP with εα = αρ =
α ∆2 s(R)2 . 2σ 2
Binary Tree Mechanism as a Factorization. Assume first T = 2h for an integer h ≥ 0 (otherwise pad to the next power of two, which only changes constants by replacing h with ⌈log2 T ⌉). Index the nodes of the complete binary tree over [T ] by dyadic intervals; let q ∈ Rm be the vector of all dyadic-interval sums, so that q = Rtree x where Rtree is a 0/1 incidence matrix (leaf i contributes to exactly its h + 1 ancestors). Each prefix [1..t] has a canonical dyadic partition of size at most h + 1, so there is a reconstruction matrix Ltree with Mcount = Ltree Rtree . Proposition F.6 (Exact Privacy Constant for the Binary Tree Factorization). For T = 2h , every column of Rtree has exactly h + 1 ones, hence s(Rtree )2 = ∥Rtree ∥21→2 = h + 1. Therefore, the Gaussian tree mechanism Ltree (Rtree x + z) with z ∼ N (0, σ 2 Im ) is ρtree -zCDP with ρtree =
∆2 (h + 1) , 2σ 2
and for every α > 1 it is (α, εα,tree )-RDP with α ∆2 (h + 1) . 2σ 2 For general T , the same holds with h := ⌈log2 T ⌉. εα,tree =
41
A Smooth Lower-Triangular Factorization [FHU23]. Fichtenberger et al. give an explicit Toeplitz lower-triangular factorization Mcount = LR with L = R defined by a scalar sequence f (·): f (0) = 1,
f (k) =
2k − 1 2k
f (k − 1) (k ≥ 1),
L[t, i] = R[t, i] = f (t − i) (t ≥ i),
and 0 otherwise. Let γ be the Euler–Mascheroni constant and define Ψ(T ) := 1 −
1 − γ ln T 2 + + . π π T
Proposition F.7 (Exact Privacy Constant for the Fichtenberger–Henzinger–Upadhyay Factorization). Let L, R be the above factorization. Then Mcount = LR and s(R)2 = ∥R∥21→2 = ∥L∥22→∞ ≤ Ψ(T ). Consequently, the mechanism L(Rx + z) with z ∼ N (0, σ 2 IT ) is ρFHU -zCDP with ρFHU =
∆2 Ψ(T ) ∆2 ∥R∥21→2 ≤ , 2 2σ 2σ 2
and for every α > 1 it is (α, εα,FHU )-RDP with εα,FHU =
α ∆2 Ψ(T ) α ∆2 ∥R∥21→2 ≤ . 2σ 2 2σ 2
Takeaway. Both mechanisms fit the same template L(Rx + z), but yield different (exact) privacy constants through the column ℓ2 sensitivity s(R): the binary tree gives s(R)2 = Θ(log2 T ), while ln T 2 the smooth Toeplitz factorization satisfies s(R)2 ≤ 1 − 1−γ π + π + T.
G
Other Related Work
As the most relevant related works have already been covered in the introduction, we will elaborate further on some related aspects. Choices of Privacy Measure. The central idea in differential privacy [Dwo06] is that if V0 and V1 are two distributions of outputs produced by a mechanism from two neighboring inputs, then those two distributions should be close. The classical (ε, δ)-DP notion uses two parameters to quantify closeness, where a smaller value in each parameter means that the two distributions are closer. However, since distributions are inherently complex objects, some information on the two distributions will be inevitably lost when they are compared using just two parameters. When the same Gaussian noise is used to mask two different vectors, researchers have discovered that the Rényi divergence [Mir17] can capture the variance of the Gaussian distribution perfectly, and hence, can quantify the closeness of two such distributions (with the same variance but different means). In general, any useful way to quantify privacy guarantees must satisfy the property that if the output satisfies certain privacy requirement, then any further processing of the output cannot violate that specific requirement. This can be formally formulated by requiring that the divergence – used for measuring how different two distributions are – must satisfy the data processing inequality; it is worth noting that some common distance notion such as the ℓ2 -norm does not satisfy this property.
42
Instead of just using a few parameters to capture the closeness of two distributions, tradeoff functions [DRS22] have been proposed to define differential privacy, because a tradeoff function can capture all the essential information about how two distributions differ in the sense that any divergence satisfying the data processing inequality can be recovered from the tradeoff function. Indeed, tradeoff functions offer a powerful tool to describe the composition of private mechanisms. However, one notational inconvenience is that a larger tradeoff (measured by pointwise comparison) means that the two distributions are closer, which has the opposite interpretation from other divergence parameters such as ε and δ. In fact, an ad hoc concept of generalized probability distance has been defined in [VZ23] to reverse the direction of the inequalities such that it will be consistent with the notion of distance. On the other hand, a simpler way to achieve this notation consistency is to replace a tradeoff function with its complement that is known as a power function, which naturally preserves all the equivalent mathematical properties. As we shall see in Definition A.3, a power function also has an intuitive description using the fractional knapsack problem. As illustrated in [VZ23, ZZCS24], if one uses such a powerful tool to define any new notion of differential privacy, then a single composition theorem (such as our Theorem C.1) will be sufficient to recover any composition result from the classical notion to the new notion of privacy. Therefore, it would not be necessary to reconstruct individual advanced composition theorems [DRV10,KOV15]. Hamming vs Edit Neighboring Notions. In [BEBP24], two neighboring notions are considered for static databases: • Hamming-style. Two databases have the same number of elements, and they differ in at most one element. • Edit-style. One element from one database is deleted to form the other database. They considered fixed-size mini-batches, which may be sampled in two ways: with or without replacement. Since they considered sampling from static databases, the difference between Hammingvs edit-style neighboring static databases would not have such a stark contrast as streams, as deleting the first element of a stream can cause it to change in every position. Other Recent Works on Concurrent Composition. A more general notion of concurrent composition is considered in [HST+ 23], where the privacy parameters of mechanisms can be adaptively chosen. However, as in [VZ23], each interactive mechanism is associated with a single static database on which its neighboring relation is defined; the adversary may interact adaptively with the mechanism, but neighboring inputs differ only in this underlying database, not in a dynamic stream of updates. Concurrent composition for mechanisms with adaptively chosen privacy parameters are also considered in [HSV26], but for neighboring dynamic databases. They also give a formulation based on adaptive DP [DMR+ 22], expressed via a left-or-right style distinguishing game with a verification function, which is essentially the same as our paired simulation in Definition B.2. Note that both works consider composition where each mechanism has a single neighboring relation on its dataset (static or dynamic). In order to capture modular composition in which neighboring notions are defined separately on both the input and the output of a mechanism—and to reason about neighbor-preserving transformations that change the neighboring structure—we need a more refined notion of neighbor-preserving paired simulation, given in Definition B.8.
43