Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity

arXiv:2602.15815 · cs.CR, cs.DS · Submitted 2026-02-17 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Privacy Filters are Captured by Residues".

Elias: Here's the gist of the paper. Privacy filters are captured by residues: A characterization of free natural filters and the cost of adaptivity<ref:2602.15815#pg2>.

Nadia: This paper develops a general theory to characterize the worst-case privacy loss of an interaction involving an analyst that respects restrictions on query issuance, leading to residue filters which unify existing privacy filters<ref:2602.15815#pg5>.

Elias: The work introduces the Gaussian DP (GDP) residue filter, showing it strictly improves upon the naïve GDP filter and captures the natural filter under certain conditions<ref:2602.15815#pg5>.

Nadia: Theoretical Framework for Privacy Accounting The paper establishes a framework using privacy loss distributions (PLDs) to characterize privacy characteristics, where PLDs are defined based on likelihood ratios between mechanisms<ref:2602.15815#pg4>.

Paper summary: Nadia: We just touched on how this paper sets up a general theory to characterize the worst-case privacy loss for an analyst who respects restrictions on query issuance, leading to residue filters which unify existing privacy filters, as it’s laid out on page five of this work <ref:2602.15815#pg3>.

Elias: Exactly. The authors develop a framework using privacy loss distributions or PLDs to define these characteristics based on likelihood ratios between mechanisms, and they show that these PLDs form a partially-ordered commutative monoid under convolution, which is crucial for analyzing adaptive composition, as you can see on page five <ref:2602.15815#pg3>.

Priya: That sounds mathematically dense. Can you translate what that means for us in terms of the actual data we are looking at? What is the big picture here?

Nadia: It means they are building a general theory to characterize the worst-case privacy loss of an interaction involving an analyst that respects some restrictions on what queries they may issue, leading to residue filters which unify existing privacy filters, as it’s laid out on page five of this work <ref:2602.15815#pg3>.

Elias: The authors apply this theory to develop residue filters, which perform exact accounting under a residual update condition, and they introduce the Gaussian DP residue filter specifically to improve upon the standard GDP filter by searching for the largest valid residual GDP budget, as seen on page thirteen of this work.

Priya: So instead of just using a simple parameter like epsilon or delta, they are looking at how the privacy loss accumulates across multiple queries in a way that respects these update conditions, right?

Nadia: Right. And they show that this approach captures the natural filter under certain conditions, which is significant because the natural filter promises greater utility by leveraging exact accounting techniques instead of just simple parameters like Rényi-DP or GDP parameters.

Elias: That’s what page one states: "Natural filters account for the entire privacy profile of every query, promising more efficient use of a given privacy budget," which is on page one.

Priya: So when you look at the numbers and caveats, are we talking about a method that gives us tighter bounds than standard approximate DP methods?

Nadia: They prove that natural filters are not free in general by showing counterexamples where they fail for certain queries and budgets, which is on page thirty-one of this work.

Priya: So it’s not perfect protection, but it's not completely useless either if we know what to look for in terms of the query structure.

Nadia: It depends entirely on the structure of the queries; they show that universal freeness only holds for queries that are closed under composition and totally-ordered, as they explain on page thirty-five.

Elias: That condition links the mathematical properties of how queries can be combined to whether we get a free natural filter, which is a core theoretical finding here.

Conclusion: Nadia: So we’ve walked through how this paper develops a general theory to characterize the worst-case privacy loss for an analyst, leading to residue filters that unify existing ones, as outlined in the title of this work.

Elias: And they’ve shown that by introducing things like the Gaussian DP residue filter, they can strictly improve upon older methods like the standard GDP filter by finding a larger valid residual budget.

Priya: What does all this mean for us moving forward? If we apply these concepts, what is the practical implication for how we think about building privacy accounting systems?

Nadia: It means that residue filters capture all existing privacy filters, including Rényi and GDP forms, which provides a unified way to handle different types of DP mechanisms.

Elias: And they provide concrete conditions—being closed under composition and totally-ordered—for when the natural filter becomes universally free, which is on page thirty-five.

Priya: So if we take this theory seriously, it suggests that for specific types of queries and budgets, we can leverage exact accounting techniques to get better privacy guarantees than what's currently available with simpler methods.

Nadia: Exactly. It suggests that when the query structure is right, you can get more efficient use of your budget by leveraging the natural filter’s ability to account for the entire profile of every query.

Elias: The authors show that post-processing can achieve a bound on epsilon delta l star that is better than what we might expect from additive methods, as they detail on page thirty-one.

Priya: So in the end, it’s about moving towards a framework where we aren't just looking at one type of privacy filter, but one that can handle the whole family under specific structural constraints.

University of Waterloo · University of British Columbia · Google Research

cs.CR, cs.DS

Submitted: 2026-02-17

Updated: 2026-11-06

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 99/100

The gist: Privacy filters are captured by residues: A characterization of free natural filters and the cost of adaptivity<ref:2602.15815#pg2>.

Key concepts

Privacy Loss Distributions (PLDs)
These distributions quantify privacy loss by looking at likelihood ratios between different mechanisms. They form a mathematical structure that helps characterize how privacy degrades when information is queried adaptively.
Residue Filters
'Residue filters' are a new framework designed to capture all existing privacy filters, including pure DP and GDP filters. They provide a general way to characterize the worst-case privacy loss resulting from an interaction involving an analyst respecting query restrictions.
Natural Filter
A natural filter is a type of privacy mechanism that arises from specific query structures. The paper characterizes when these filters are 'free' (meaning they don't incur excessive loss) based on the structure and composition of the queries being made.

Terminology

Summary

Privacy filters are captured by residues: A characterization of free natural filters and the cost of adaptivity<ref:2602. p. 0

Where the paper says it

Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity∗ Matthew Regehr† Bingshan Hu‡ Ethan Leeman§ Pasin Manurangsi¶ Pierre Tholoniat‖ Mathias Lécuyer∗∗ April 17, 2026 Abstract We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We develop a general theory that characterizes the worst-case privacy loss of an interaction involving an analyst that respects some restrictions on what queries they may issue.

15815#pg2>. This paper develops a general theory to characterize the worst-case privacy loss of an interaction involving an analyst that respects restrictions on query issuance, leading to residue filters which unify existing privacy filters<ref:2602. p. 0
Where the paper says it

We develop a general theory that characterizes the worst-case privacy loss of an interaction involving an analyst that respects some restrictions on what queries they may issue. We apply this theory to develop residue filters, which unifies existing privacy filters.

15815#pg5>. The work introduces the Gaussian DP (GDP) residue filter, showing it strictly improves upon the naïve GDP filter and captures the natural filter under certain conditions<ref:2602. p. 0
Where the paper says it

We develop the Gaussian DP (GDP) residue filter, which strictly improves upon the naïve GDP filter. We also show that residue filters capture the natural filter, which promises greater utility by leveraging exact privacy accounting techniques.

15815#pg5>.

Theoretical Framework for Privacy Accounting

The paper establishes a framework using privacy loss distributions (PLDs) to characterize privacy characteristics, where PLDs are defined based on likelihood ratios between mechanisms<ref:2602.15815#pg4>. It defines the Blackwell order on pairs of distributions and shows that PLDs form a partially-ordered commutative monoid under convolution, which is crucial for analyzing adaptive composition<ref:2602. p. 4

Where the paper says it

It is straightforward to show that this order is well-defined regardless of the underlying representations (P, Q) and (P ′ , Q′ ). When equipped with the Blackwell order, PLDs also form a partially-ordered commutative monoid under convolution.

15815#pg5>. The paper also introduces hockey-stick curves as a generalization of (ε, δ)-DP that captures adaptive composition naturally<ref:2602. p. 5
Where the paper says it

For convenience, we will sometimes write hL to denote the unique hockey-stick curve associated to a PLD L, namely hL(x) := EZ∼L[(1 − xe−Z)+]. Moreover, like PLDs, hockey-stick curves also capture adaptive composition in a natural way.

15815#pg7>.

Characterization of Free Natural Filters

The central theoretical contribution is the characterization of when a family of private queries admits free natural filters for a given budget, specifically showing that only families totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget<ref:2602.15815#pg5>. The paper proves that the natural filter is universally free for any budget only for queries that are closed under composition and totally-ordered, in which case the natural filter is captured by a residue filter<ref:2602. p. 2

Where the paper says it

• In §5 we apply our theory of constrained adversaries to calculate the exact privacy cost of an interaction with the natural filter. We show that the natural filter is universally free for any budget only for queries that are closed under composition and totally-ordered, in which case the natural filter is captured by a residue filter.

15815#pg5>.

Residue Filters and Their Scope

Residue filters are developed to capture all existing privacy filters, including the pure DP filter, Rényi filter, and GDP filter<ref:2602.15815#pg11>. A key result is Theorem 1 that states that for an update rule U satisfying a natural residue condition (⋆), the resulting update filter Algorithm 1 is free<ref:2602. p. 9

Where the paper says it

Now, notice that Algorithm 1 can be captured succinctly by the recursive privacy rule UpdateU,B(λ) := {L ∈ L : L ⪯ B} UpdateU,B |L1 := UpdateU,U(B,L1) . Our key result is that privacy filters derived from budget updates are valid as long as the updates satisfy a natural residue condition.

15815#pg10>. The GDP residue filter is introduced, which strictly improves upon the standard GDP filter by searching for the largest valid residual GDP budget<ref:2602. p. 0
Where the paper says it

We apply this theory to develop residue filters, which unifies existing privacy filters. We develop the Gaussian DP (GDP) residue filter, which strictly improves upon the naïve GDP filter.

15815#pg13>.

Failure Modes and Bounds

The paper demonstrates that natural filters are not free in general, showing counterexamples where they fail for certain queries and budgets<ref:2602.15815#pg31>. However, it proves that the natural approximate-DP filter cannot fail too badly; the output remains approximate-DP with parameters at most poly-logarithmically worse than intended privacy parameters<ref:2602. p. 0

Where the paper says it

In particular, only families of privacy mechanisms that are totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget. Finally, we show that, while the natural approximate-DP filter can fail in the presence of adaptive adversary, it cannot fail too badly: the output remains approximate-DP with parameters at most poly-logarithmically worse than the intended privacy parameters.

15815#pg8>. The upper bound for the natural (ε, δ)-DP PLD filter is shown to be Rχ·(ε+1), χ = O(log k + log 1 + 1/ε · log(1/δ))<ref:2602. p. 3
Where the paper says it

Let P and Q be distributions on Ω. The PLD of (P, Q), denoted PLD(P ∥ Q), is the distribution over R := R ∪ {±∞} of log( dP dQ (ω)), ω ∼ P.

15815#pg31>.

Universal Freeness Conditions

The paper identifies specific query families that admit universally free natural filters, including GDP queries and (0, δ)-DP queries<ref:2602.15815#pg38>. Corollary 6 shows that the natural filter for (0, δ)-DP queries is universally free for every budget B in Lall<ref:2602. p. 2

Where the paper says it

• In §5 we apply our theory of constrained adversaries to calculate the exact privacy cost of an interaction with the natural filter. We show that the natural filter is universally free for any budget only for queries that are closed under composition and totally-ordered, in which case the natural filter is captured by a residue filter.

15815#pg38>. The main result is that query families closed under composition and totally-ordered admit universally free natural filters<ref:2602. p. 0
Where the paper says it

We present a characterization of when a family of private queries admits free natural filters for a given budget. In particular, only families of privacy mechanisms that are totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget.

15815#pg35>.

Post-Processing as a Privacy Guarantee

The analysis of the additive discretized PL profile filter shows that it is less strict than the natural (ε, δ)-DP PLD filter<ref:2602.15815#pg31>. Theorem 15 proves that PLD Discretekε,l∗⪯ Rχ·(ε+1),χ·δ<ref:2602. p. 0

Where the paper says it

lecuyer@ubc. ca 1 arXiv:2602.

15815#pg31>. This is achieved by showing that the output distribution is a post-processing of randomized response answers with high probability<ref:2602.15815#pg31>. The final result shows that the PLD Discretekε,l∗⪯ Rε′,δ'<ref:2602.15815#pg31>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved Privacy Accounting through Residue Filters: The system can utilize residue filters to unify existing privacy filters, such as pure DP, Rényi-DP, and GDP filters, by monitoring a remaining privacy budget according to the condition that every budget encountered during the interaction dominates the privacy cost of the next budget plus the cost of the next query.

  2. Enhanced Budget Management for Adaptive Interactions: The system can implement an update filter based on a residue condition, ensuring that if an analyst issues queries with constrained per-query privacy costs, the resulting interaction provably satisfies a meaningful privacy guarantee, which is formalized by Theorem 1.

  3. Superior Gaussian DP Filter: A new GDP residue filter can be developed that strictly improves upon the naïve GDP filter, specifically showing that for non-Gaussian queries, the residual GDP budget, when composed with the query, is very close to the starting budget.

  4. Characterization of Free Natural Filters: The system can determine when a family of private queries admits free natural filters by checking if the queries are closed under composition and totally-ordered, as this condition is necessary for the filter to be universally free against an arbitrary privacy budget.

  5. Robust Guarantees for (Epsilon, Delta)-DP Filters: When using the natural (epsilon, delta)-DP filter on symmetric queries, the system can guarantee a stronger privacy level of chi times epsilon plus one, chi times delta, where chi is bounded by a value logarithmic in the number of rounds and inverse epsilon.

  6. Efficient Approximation via Additive Discretized Profile Filter: The system can employ an additive discretized privacy loss profile filter to approximate the natural (epsilon, delta)-DP filter with a privacy loss distribution bounded by Rchi times epsilon plus one, where chi is determined by k and 1/delta.

Abstract

We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We show that the worst-case privacy loss of interacting with any privacy filter is characterized by a Bellman equation. We apply this theory to develop residue filters, which unify existing privacy filters. We develop the Gaussian DP (GDP) residue filter, which strictly improves upon the naïve GDP filter. We show that, in the average case, this new filter asymptotically permits as many pure DP queries as in the non-adaptive case and a factor π/2 more pure DP queries than the naïve GDP filter. We also show that residue filters capture the natural filter, which promises greater utility by leveraging exact privacy accounting techniques. Earlier privacy filters consider only simple privacy parameters such as Rényi-DP or GDP parameters. Natural filters account for the entire privacy profile of every query, promising more efficient use of a given privacy budget. We show that, contrary to other forms of DP, natural privacy filters are not free in general. We present a characterization of when a family of private queries admits free natural filters for a given budget. In particular, only families of privacy mechanisms that are totally-ordered when composed admit free natural privacy filters with respect to an arbitrary privacy budget. Finally, we show that, while the natural approximate-DP filter can fail in the presence of an adaptive adversary, it cannot fail too badly: the output remains approximate-DP with parameters at most poly-logarithmically worse than the intended privacy parameters.

Sources

Related papers