Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917412634361856 |
|---|---|
| author | Regehr, Matthew Hu, Bingshan Leeman, Ethan Manurangsi, Pasin Tholoniat, Pierre Lécuyer, Mathias |
| author_facet | Regehr, Matthew Hu, Bingshan Leeman, Ethan Manurangsi, Pasin Tholoniat, Pierre Lécuyer, Mathias |
| contents | 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. 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. 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 adaptive adversary, it cannot fail too badly: the output remains approximate-DP with parameters at most poly-logarithmically worse than the intended privacy parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_15815 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity Regehr, Matthew Hu, Bingshan Leeman, Ethan Manurangsi, Pasin Tholoniat, Pierre Lécuyer, Mathias Cryptography and Security Data Structures and Algorithms 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. 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. 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 adaptive adversary, it cannot fail too badly: the output remains approximate-DP with parameters at most poly-logarithmically worse than the intended privacy parameters. |
| title | Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity |
| topic | Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.15815 |