pith. sign in

arxiv: 2605.21185 · v1 · pith:KOJS2O7Znew · submitted 2026-05-20 · 💻 cs.CR · cs.IT· math.IT

Information Leakage Envelopes

Sara Saeidian (1 , 2) , Carlos Pinz\'on (2 , 3) , Catuscia Palamidessi (2 , 3) ((1) KTH Royal Institute of Technology , (2) Inria Saclay , (3) \'Ecole Polytechnique) This is my paper

Pith reviewed 2026-05-21 03:55 UTC · model grok-4.3

classification 💻 cs.CR cs.ITmath.IT
keywords pointwise maximal leakagePML envelopepost-processingprivacy guaranteesinformation leakagefailure probabilityrandomized response
0
0 comments X

The pith

The PML envelope measures the largest leakage about a secret after any post-processing and bounds the probability that leakage exceeds a threshold.

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

This paper seeks a privacy guarantee in the pointwise maximal leakage framework that remains valid after the output is transformed by any further processing. Two candidate definitions drawn from approximate differential privacy each fail to satisfy both robustness under post-processing and an upper bound on the probability of excessive leakage. The PML envelope is introduced as the quantity that captures the worst-case leakage possible after arbitrary post-processing; by construction it meets both requirements at once. This construction matters because real privacy systems routinely apply additional transformations to released data, so guarantees that break under such steps have limited operational value. The paper then records monotonicity, general bounds, and explicit values for two standard mechanisms.

Core claim

The PML envelope is defined as the largest amount of information leakage about a secret that can occur after arbitrary post-processing of a mechanism's output. By this definition it is robust under post-processing and supplies an upper bound on the probability that leakage exceeds any chosen threshold. Structural properties such as monotonicity are established, general upper and lower bounds are derived, and the envelope is computed exactly for PML-extremal mechanisms in the high-privacy regime and for randomized response.

What carries the argument

The PML envelope, which quantifies the largest amount of information leakage about a secret after arbitrary post-processing of a mechanism's output.

If this is right

  • The envelope is monotonic with respect to the underlying leakage measure.
  • General upper and lower bounds on the envelope can be stated for any mechanism.
  • Explicit closed-form expressions exist for the envelope of PML-extremal mechanisms in the high-privacy regime.
  • Explicit values of the envelope are obtained for the randomized-response mechanism.
  • Any privacy guarantee expressed via the envelope is automatically preserved under arbitrary downstream transformations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The envelope could be used to certify privacy for entire data pipelines that include unknown future analyses.
  • It offers a leakage-based alternative when differential privacy's additive guarantees become too loose after composition.
  • Numerical computation of the envelope for a given mechanism might serve as a practical auditing tool before release.

Load-bearing premise

The pointwise maximal leakage framework permits a well-defined quantification of the largest leakage after arbitrary post-processing without additional constraints on the mechanism or secret distribution.

What would settle it

A concrete mechanism and post-processing function for which the observed probability that leakage exceeds the envelope's threshold is strictly larger than the envelope predicts.

Figures

Figures reproduced from arXiv: 2605.21185 by 2), (2) Inria Saclay, 3), 3) ((1) KTH Royal Institute of Technology, (3) \'Ecole Polytechnique), Carlos Pinz\'on (2, Catuscia Palamidessi (2, Sara Saeidian (1.

Figure 1
Figure 1. Figure 1: An example of the CDF CY (t) together with εY (δ) and ε¯Y (δ) at δ = 0.1. Since CY is not strictly increasing, there is a gap between εY (δ) and ε¯Y (δ). Observe that the mapping δ 7→ ε¯Z(δ) is non-increasing and left-continuous. Heuristically, the difference between ε¯Z(δ) and εZ(δ) can be understood as follows: εZ(δ) is the smallest upper bound on the worst-case PML over all the “good” sets of outputs (i… view at source ↗
Figure 2
Figure 2. Figure 2: PML envelope upper bounds (UBs), lower bounds (LBs), [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
read the original abstract

We study privacy guarantees in the framework of pointwise maximal leakage (PML) that satisfy two requirements: they are robust under post-processing and upper bound the failure probability, i.e., the probability that the information leakage exceeds a given threshold. We first examine two candidate definitions inspired by (approximate) differential privacy and show that neither one satisfies both requirements simultaneously. We then introduce the notion of the PML envelope, which quantifies the largest amount of information leakage about a secret after arbitrary post-processing of a mechanism's output. By construction, the PML envelope satisfies both requirements. We discuss basic structural properties of the envelope, such as monotonicity, and derive general upper and lower bounds. We further analyze the envelope for two widely used privacy mechanisms: the PML-extremal mechanisms in the high-privacy regime and randomized response. Overall, this work establishes the PML envelope as a natural and operationally meaningful definition for providing privacy guarantees that are preserved under arbitrary downstream transformations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper studies privacy guarantees in the pointwise maximal leakage (PML) framework that are robust under post-processing and upper-bound the probability that information leakage exceeds a given threshold. It shows that two candidate definitions inspired by approximate differential privacy fail to satisfy both requirements simultaneously. The authors then introduce the PML envelope, defined as the supremum of PML leakage over arbitrary post-processings of a mechanism's output. By construction, this envelope satisfies both requirements. The manuscript discusses basic structural properties such as monotonicity, derives general upper and lower bounds, and analyzes the envelope for PML-extremal mechanisms in the high-privacy regime and for randomized response.

Significance. If the envelope is rigorously shown to be finite and well-defined, the construction provides an operationally meaningful privacy measure within the PML framework that directly addresses post-processing robustness without the limitations of the examined candidates. The explicit evaluation on standard mechanisms adds practical value, and the by-construction satisfaction of the two requirements is a conceptual strength.

major comments (1)
  1. [Section defining the PML envelope] The central definition of the PML envelope (as the supremum of PML after arbitrary post-processing) is load-bearing for the claim that it is well-defined, finite, and upper-bounds the failure probability. For mechanisms with continuous or countably infinite output alphabets, or when the class of post-processing functions is unrestricted, it is not immediate that the supremum exists or is finite rather than infinite or trivial; the manuscript provides no explicit conditions, proof of attainment, or finiteness argument to support this.
minor comments (2)
  1. [Abstract] The abstract would benefit from briefly indicating the sections containing the bounds and the mechanism-specific analyses.
  2. [Introduction] Notation for the envelope (e.g., how the threshold and secret distribution are parameterized) could be introduced earlier for readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and for identifying this important technical point regarding the definition of the PML envelope. We address the comment in detail below and will revise the manuscript to incorporate additional justification.

read point-by-point responses

  1. Referee: The central definition of the PML envelope (as the supremum of PML after arbitrary post-processing) is load-bearing for the claim that it is well-defined, finite, and upper-bounds the failure probability. For mechanisms with continuous or countably infinite output alphabets, or when the class of post-processing functions is unrestricted, it is not immediate that the supremum exists or is finite rather than infinite or trivial; the manuscript provides no explicit conditions, proof of attainment, or finiteness argument to support this.

    Authors: We agree that a rigorous argument for the existence and finiteness of the supremum is necessary to support the claims. The manuscript focuses on mechanisms with finite output alphabets (including the PML-extremal mechanisms and randomized response analyzed in the paper), for which the output space is discrete and finite. In this setting, the collection of possible post-processing functions yields only finitely many distinct PML values, so the supremum is attained and finite. We will add an explicit lemma and short proof in the section defining the PML envelope establishing that, under the finite-alphabet assumption used throughout the work, the envelope is always well-defined, finite, and attained. For countably infinite or continuous alphabets the referee correctly notes that additional regularity conditions would be required; we will include a brief remark clarifying that such cases lie outside the scope of the present paper, which targets standard discrete mechanisms common in the PML literature. This addresses the concern without altering the core construction or results. revision: yes

Circularity Check

0 steps flagged

PML envelope defined from prior PML framework; satisfaction of requirements follows directly from supremum construction with no reduction to fitted values or self-referential equations

full rationale

The paper defines the PML envelope explicitly as the largest PML value over arbitrary post-processings of the mechanism output and states that it satisfies the two requirements by construction. This is a standard definitional move that builds a new object on the existing PML framework rather than a circular reduction where an output is forced to equal its input by construction. No equations are shown to collapse into each other, no parameters are fitted to data and then relabeled as predictions, and no load-bearing uniqueness theorem or ansatz is imported solely via self-citation. The analysis of specific mechanisms (PML-extremal and randomized response) and derivation of bounds appear to rest on independent properties of PML. The paper is therefore self-contained against external benchmarks with only minor potential self-citation of the base PML definition.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The contribution rests on the pre-existing pointwise maximal leakage framework and the modeling choice of arbitrary post-processing; no free parameters or new physical entities are introduced.

axioms (1)
  • domain assumption Pointwise maximal leakage (PML) framework as defined in prior literature
    The paper builds all subsequent definitions and properties on this established framework.
invented entities (1)
  • PML envelope no independent evidence
    purpose: Quantifies the largest information leakage about a secret after arbitrary post-processing
    Newly defined construct introduced to satisfy the two stated privacy requirements simultaneously.

pith-pipeline@v0.9.0 · 5738 in / 1157 out tokens · 36673 ms · 2026-05-21T03:55:42.031915+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Calibrating Noise to Sensitivity in Private Data Analysis,

    C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” inTheory of cryptography conference, Springer, 2006, pp. 265–284.DOI: 10.1007/11681878 14

    work page doi:10.1007/11681878 2006

  2. [2]

    2014.The Algorithmic Foundations of Differential Privacy

    C. Dwork and A. Roth, “The Algorithmic Foundations of Differential Privacy,”Found. Trends Theor. Comput. Sci., vol. 9, no. 3-4, pp. 211– 407, Aug. 2014,ISSN: 1551-305X.DOI: 10.1561/0400000042

    work page doi:10.1561/0400000042 2014

  3. [3]

    Privacy: Theory meets practice on the map,

    A. Machanavajjhala, D. Kifer, J. Abowd, J. Gehrke, and L. Vilhuber, “Privacy: Theory meets practice on the map,” in2008 IEEE 24th in- ternational conference on data engineering, IEEE, 2008, pp. 277–286

    work page 2008

  4. [4]

    An axiomatic view of statistical privacy and utility,

    D. Kifer and B.-R. Lin, “An axiomatic view of statistical privacy and utility,”Journal of Privacy and Confidentiality, vol. 4, no. 1, 2012

    work page 2012

  5. [5]

    Boosting and Differential Privacy,

    C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and Differential Privacy,” in2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, NV , USA: IEEE, Oct. 2010, pp. 51–60, ISBN: 978-1-4244-8525-3.DOI: 10.1109/FOCS.2010.12

    work page doi:10.1109/focs.2010.12 2010

  6. [6]

    Approximate and probabilistic differential privacy defini- tions,

    S. Meiser, “Approximate and probabilistic differential privacy defini- tions,”Cryptology ePrint Archive, 2018. [Online]. Available: https : //eprint.iacr.org/2018/277

    work page 2018

  7. [7]

    Pointwise maximal leakage,

    S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Pointwise maximal leakage,”IEEE Transactions on Information Theory, vol. 69, no. 12, pp. 8054–8080, 2023.DOI: 10.1109/TIT.2023.3304378

    work page doi:10.1109/tit.2023.3304378 2023

  8. [8]

    Rethinking disclosure prevention with pointwise maximal leakage,

    S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Rethinking disclosure prevention with pointwise maximal leakage,”Journal of Privacy and Confidentiality, vol. 15, no. 1, Mar. 2025.DOI: 10.29012/ jpc.893

    work page 2025

  9. [9]

    Additive and multiplicative notions of leakage, and their capacities,

    M. S. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi, and G. Smith, “Additive and multiplicative notions of leakage, and their capacities,” in2014 IEEE 27th Computer Security Foundations Symposium, 2014, pp. 308–322.DOI: 10.1109/CSF.2014. 29

    work page doi:10.1109/csf.2014 2014

  10. [10]

    An operational approach to information leakage,

    I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,”IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1625–1657, 2019.DOI: 10.1109/TIT.2023.3341148

    work page doi:10.1109/tit.2023.3341148 2019

  11. [11]

    M. S. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi, and G. Smith,The Science of Quantitative Information Flow. Springer Cham, 2020

    work page 2020

  12. [12]

    Extremal Mechanisms for Pointwise Maximal Leakage,

    L. Grosse, S. Saeidian, and T. J. Oechtering, “Extremal Mechanisms for Pointwise Maximal Leakage,”IEEE Transactions on Information Forensics and Security, vol. 19, pp. 7952–7967, 2024,ISSN: 1556- 6021.DOI: 10.1109/TIFS.2024.3449556

    work page doi:10.1109/tifs.2024.3449556 2024

  13. [13]

    Randomized Response: A Survey Technique for Elim- inating Evasive Answer Bias,

    S. L. Warner, “Randomized Response: A Survey Technique for Elim- inating Evasive Answer Bias,”Journal of the American Statistical Association, vol. 60, no. 309, pp. 63–69, 1965,ISSN: 0162-1459.DOI: 10.2307/2283137 JSTOR: 2283137

    work page doi:10.2307/2283137 1965

  14. [14]

    Extremal mechanisms for local differential privacy,

    P. Kairouz, S. Oh, and P. Viswanath, “Extremal mechanisms for local differential privacy,”Journal of Machine Learning Research, vol. 17, no. 1, pp. 492–542, Jan. 2016,ISSN: 1532-4435

    work page 2016

  15. [15]

    What can we learn privately?

    S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?” In49th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 531–540

    work page 2008

  16. [16]

    Local privacy and statistical minimax rates,

    J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” inIEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 429–438

    work page 2013

  17. [17]

    Our data, ourselves: Privacy via distributed noise generation,

    C. Dwork, K. Kenthapadi, F. McSherry, I. Mironov, and M. Naor, “Our data, ourselves: Privacy via distributed noise generation,” inProceed- ings of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 4004, Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 486–503. DOI: 10.1007/11761679 29

    work page doi:10.1007/11761679 2006

  18. [18]

    Privacy amplification by subsampling: Tight analyses via couplings and divergences,

    B. Balle, G. Barthe, and M. Gaboardi, “Privacy amplification by subsampling: Tight analyses via couplings and divergences,” inPro- ceedings of the 32nd International Conference on Neural Information Processing Systems, ser. NIPS’18, Red Hook, NY , USA: Curran Associates Inc., 2018, pp. 6280–6290

    work page 2018

  19. [19]

    The Discrete Gaussian for Differential Privacy,

    C. L. Canonne, G. Kamath, and T. Steinke, “The Discrete Gaussian for Differential Privacy,”Journal of Privacy and Confidentiality, vol. 12, no. 1, 2022.DOI: 10.29012/jpc.784

    work page doi:10.29012/jpc.784 2022

  20. [20]

    On the ’Semantics’ of Dif- ferential Privacy: A Bayesian Formulation,

    S. P. Kasiviswanathan and A. Smith, “On the ’Semantics’ of Dif- ferential Privacy: A Bayesian Formulation,”Journal of Privacy and Confidentiality, vol. 6, no. 1, 2014,ISSN: 2575-8527.DOI: 10.29012/ jpc.v6i1.634

    work page 2014

  21. [21]

    Jonany,Correcting (ϵ,δ) misconception in differential privacy, 2022

    S. Jonany,Correcting (ϵ,δ) misconception in differential privacy, 2022. [Online]. Available: https://medium.com/@sjonany/correcting-%CF% B5-%CE%B4-misconception-in-differential-privacy-e830dbdce0ab

    work page 2022

  22. [22]

    An Axiomatic View of Statistical Privacy and Utility,

    D. Kifer and B.-R. Lin, “An Axiomatic View of Statistical Privacy and Utility,”Journal of Privacy and Confidentiality, vol. 4, no. 1, Jul. 2012,ISSN: 2575-8527.DOI: 10.29012/jpc.v4i1.610

    work page doi:10.29012/jpc.v4i1.610 2012

  23. [23]

    A note on generalized inverses,

    P. Embrechts and M. Hofert, “A note on generalized inverses,”Mathe- matical Methods of Operations Research, vol. 77, no. 3, pp. 423–432, 2013

    work page 2013

  24. [24]

    Distribution and quantile functions,

    J.-M. Dufour, “Distribution and quantile functions,”McGill University Report, 1995

    work page 1995

  25. [25]

    Privacy Profiles and Amplifica- tion by Subsampling,

    B. Balle, G. Barthe, and M. Gaboardi, “Privacy Profiles and Amplifica- tion by Subsampling,”Journal of Privacy and Confidentiality, vol. 10, no. 1, 2020.DOI: 10.29012/jpc.726

    work page doi:10.29012/jpc.726 2020

  26. [26]

    R ´enyi Differential Privacy,

    I. Mironov, “R ´enyi Differential Privacy,” in2017 IEEE 30th Computer Security Foundations Symposium (CSF), IEEE Computer Society, Aug. 2017, pp. 263–275,ISBN: 978-1-5386-3217-8.DOI: 10 . 1109 / CSF. 2017.11

    work page 2017

  27. [27]

    Concentrated Differential Privacy: Simplifica- tions, Extensions, and Lower Bounds,

    M. Bun and T. Steinke, “Concentrated Differential Privacy: Simplifica- tions, Extensions, and Lower Bounds,” inProceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 9985, Berlin, Heidelberg: Springer-Verlag, Oct. 2016, pp. 635–658, ISBN: 978-3-662-53640-7.DOI: 10.1007/978-3-662-53641-4 24

    work page doi:10.1007/978-3-662-53641-4 2016

  28. [28]

    Gaussian Differential Privacy,

    J. Dong, A. Roth, and W. J. Su, “Gaussian Differential Privacy,”Jour- nal of the Royal Statistical Society Series B: Statistical Methodology, vol. 84, no. 1, pp. 3–37, Feb. 2022,ISSN: 1369-7412.DOI: 10.1111/ rssb.12454

    work page 2022

  29. [29]

    Abstract Channels and Their Robust Information-Leakage Ordering,

    A. McIver, C. Morgan, G. Smith, B. Espinoza, and L. Meinicke, “Abstract Channels and Their Robust Information-Leakage Ordering,” inPrinciples of Security and Trust, Berlin, Heidelberg: Springer, 2014, pp. 83–102,ISBN: 978-3-642-54792-8.DOI: 10 . 1007 / 978 - 3 - 642 - 54792-8 5

    work page 2014