Information Leakage Envelopes

Computer Science > Cryptography and Security [Submitted on 20 May 2026] Information Leakage Envelopes Sara Saeidian (1 and 2), Carlos Pinzón (2 and 3), Catuscia Palamidessi (2 and 3) ((1) KTH Royal Institute of Technology, (2) Inria Saclay, (3) École Polytechnique) 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. Comments: Accepted to CSF2026 Subjects: Cryptography and Security (cs.CR); Information Theory (cs.IT) Cite as: arXiv:2605.21185 [cs.CR]   (or arXiv:2605.21185v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2605.21185 Focus to learn more Submission history From: Sara Saeidian [view email] [v1] Wed, 20 May 2026 13:50:26 UTC (1,213 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-05 Change to browse by: cs cs.IT math math.IT References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)