Pith. sign in

REVIEW 3 major objections 5 minor 87 references

Statistic Maximal Leakage

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Statistic maximal leakage measures the worst-case gain in one-try guessing of a known secret, composes additively, and reduces to a min-cost flow for deterministic mechanisms.

desk verdict Useful measure and a clean min-cost flow result, but the adaptive composition proof has a real gap that needs fixing. read the letter →

arxiv 2411.18531 v1 pith:XZILRI6C submitted 2024-11-27 cs.IT math.IT

Shuaiqi Wang , Zinan Lin , Giulia Fanti This is my paper · ORCID
classification cs.ITmath.IT MSC 94A1768P2790C35
keywords statisticmaximalleakageprivacycompositionpost-processingmin-costflowquantizationmechanismrandomizedresponse
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Data holders often want to hide one known statistic—say the fraction of records in a category—rather than everything about the data. This paper introduces statistic maximal leakage, a privacy measure that quantifies the worst-case multiplicative increase in an adversary's chance of guessing that known secret correctly after seeing a mechanism's output, relative to their best guess without it. The measure is secret-aware and needs no prior over the data beyond the support, and the paper proves it composes additively across sequential releases and is preserved under post-processing. It also shows that for deterministic release mechanisms the measure can be computed in polynomial time by solving a minimum-cost flow problem, even though it is NP-hard in general. On tabular categorical data the paper argues that a quantization mechanism beats randomized response at the same privacy level, making secret-specific protection considerably cheaper in utility.

What carries the argument

The object carrying the argument is the SML functional together with a structural simplification: Proposition 1 shows that the supremum can be restricted to priors with $P_{\Theta|G}\in\{0,1\}$, so each secret value points to a single parameter $\theta_g$. For deterministic mechanisms this reduces to a min-cost flow on a graph with a source, G-nodes, $\Theta$-nodes, $\Theta'$-nodes, and a sink: unit capacities enforce the single-$\theta_g$ and single-secret-per-output constraints, and edge costs $-P_{\Theta'|\Theta}(\theta'|\theta)$ make the total cost equal to the sum inside the logarithm in Proposition 1. That reduction is what turns SML into a poly-time audit for deterministic releases and, via a modified edge-cost flow, shows that the general case is NP-hard.

What would settle it

On a finite instance with, say, three possible parameters and two secrets, enumerate every deterministic mechanism, compute SML by exhaustive maximization over $\{0,1\}$-valued conditional priors, and compare to the min-cost flow value from Algorithm 1; a mismatch would refute Proposition 2.

Watch

Extended reading notes

Core claim

Statistic maximal leakage fixes a known secret $G=g(\Theta)$ and a mechanism $M$, and defines the leakage as $\Pi_{M,g} = \sup_{P_\Theta, P_{\hat G|\Theta'}} \log \frac{P(\hat G=G)}{\sup_{g\in G} P_G(g)}$. The paper establishes that this quantity is prior-independent in a worst-case-prior sense, satisfies adaptive composition (the SML of a sequential composition is at most the sum of the individual SMLs), and is non-increasing under post-processing. The central algorithmic discovery is that when $M$ is deterministic, $\Pi_{M,g}$ equals the negative logarithm of the minimum cost of a unit-capacity flow in a three-layer network, which yields polynomial-time auditing; for general mechanisms the computation is NP-hard. The paper then derives closed-form SML and distortion formulas for randomized response and the quantization mechanism, and shows that at equal non-trivial SML budgets the quantization mechanism's worst-case total-variation distortion is asymptotically no worse than randomized response's.

Load-bearing premise

The load-bearing premise is that the parameter space is finite (a categorical histogram at fixed precision $\tau$) and that privacy risk is measured by the multiplicative increase in exact one-try guessing of a known secret under a worst-case prior.

Editorial extensions

If this is right

  • Any deterministic release can be audited for SML in time polynomial in $|\Theta|\cdot|\Theta'|$, enabling practical privacy accounting for such mechanisms.
  • Sequential, adaptively chosen releases of the same data have SML at most the sum of the individual SMLs, so privacy budgets compose linearly.
  • Post-processing a released output can only decrease SML, so arbitrary downstream transformations preserve the guarantee.
  • For tabular categorical data with a category-fraction secret, a quantization mechanism can match randomized response's SML with asymptotically lower worst-case distortion as precision $\tau$ grows.
  • Because SML is secret-specific, it can certify protection of a target statistic with less perturbation than a secret-agnostic maximal-leakage baseline.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The min-cost flow formulation suggests a natural extension: approximate SML for randomized mechanisms by sampling or discretizing the output distribution and solving the same flow, with error that vanishes as the discretization refines; the paper does not pursue this.
  • SML's worst-case-prior definition makes it a capacity-style quantity, so it could be paired with an actual prior to give an empirical weak-leakage estimate rather than only a hard guarantee.
  • Because SML only tracks one-try exact guessing of the most likely secret, adversarially useful partial information (such as narrowing the secret to a small set) is invisible; a gain-function variant would close that gap.
  • The quantization-over-randomized-response comparison is proven for a category-fraction secret at large precision; testing other secret functions is a direct way to see how far the comparison generalizes.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces statistic maximal leakage (SML), a privacy measure that quantifies the worst-case multiplicative increase in one-try guessing of a known secret g(Θ) after release of Θ′. The measure is defined in Eq. (2) by a supremum over priors and attack strategies, and Proposition 1 reduces it to a finite max-over-secrets form. The paper claims three properties: prior-independence, secret-awareness, and adaptive composition with post-processing. It proves post-processing, gives an NP-hardness result for general mechanisms, gives a polynomial-time minimum-cost-flow algorithm for deterministic mechanisms, and derives closed-form privacy and distortion guarantees for randomized response and the quantization mechanism, with an empirical comparison on Census data. The central weakness is the proof of the adaptive composition theorem in Appendix D, which contains an invalid equality and an undefined notion of per-step SML for adaptive mechanisms.

Significance. If the main claims were fully established, SML would be a useful addition to the literature: it is operationally defined, does not require a prior, is explicitly secret-specific, and the deterministic-mechanism flow formulation gives a concrete auditing tool. The paper also contains several genuinely valuable components that are not affected by the composition-proof gap: Proposition 1, the NP-hardness reduction, the RR and QM closed forms, and the empirical study are all derived from the definitions without fitted parameters or circular assumptions. The quantization-versus-randomized-response comparison is a substantive contribution. However, the adaptive composition theorem is advertised as a core property in the abstract and introduction, and the current proof does not establish it; this is a load-bearing issue that must be fixed before the paper can be accepted.

major comments (3)
  1. [App. D (Theorem 2)] The final equality in the proof of Theorem 2 is false. The term Q_i = log Σ_{[θ′(1),...,θ′(i)]} sup_g P_i(θ′(i)|θ_g,{M_k,θ′(k)}) is not the statistic maximal leakage of the adaptive mechanism M_i. For a fixed history h, the per-step SML would be log Σ_{θ′(i)} sup_g P_i(θ′(i)|θ_g,h); Q_i additionally sums over all previous histories, so Q_i ≥ sup_h Π_{M_i,g}(h), and the inequality can be strict. Concretely, take Θ={θ1,θ2}, g(θ1)=g1, g(θ2)=g2, let M1 output h=1 for θ1 and h=2 for θ2, and let M2 output y=h for every θ. Then Q_2=log 2 while Π_{M2,g}(h)=0 for each history h, so the asserted equality Q_i=Π_{M_i,g} fails. Since the displayed chain in App. D relies on this equality, Theorem 2 is not proved as written. A corrected argument is not a mere typo: the surrounding inequalities bound the composition by Σ_i Q_i, and the fact that Q_i ≥ Π_{M_i,g} goes in the wrong direction for the desired additive bound. The result may be salvageable by proving a product bound with a history-supremum formulation, but that proof is absent.
  2. [Theorem 2 statement] The statement of adaptive composition is not well-defined because Eq. (2) defines SML only for a fixed conditional distribution P_{Θ′|Θ}. In Theorem 2, M_i is a function of θ and all previous outputs, so there is no single channel P_{Θ′|Θ} to which Eq. (2) applies. Appendix D introduces channels P_{Θ′(i)|Θ,{M_k,Θ′(k)}} but does not define what it means for an adaptive mechanism to satisfy a per-step guarantee Π_{M_i,g}. This ambiguity is not cosmetic: it is what permits the invalid equality discussed above. The authors should either define per-step SML for adaptive mechanisms explicitly (e.g., as a worst case over histories) and prove the theorem under that definition, or restate the result in a way that avoids the undefined quantity.
  3. [Prop. 2 / Alg. 1] The minimum-cost-flow computation in Algorithm 1 is underspecified: the text does not state the required flow value or whether the objective is to minimize cost among all feasible flows, among maximum flows, or among flows of a fixed amount. The proof of Proposition 2 later refers to the flow 'going through' a set Θ′(+), which is only meaningful if the optimal flow is a maximum flow in the constructed network. If the intended interpretation is the standard min-cost flow with a prescribed flow amount, the construction is incomplete; if the intended interpretation is min-cost max-flow, that should be stated explicitly and used consistently in the proof. This is a load-bearing specification issue for the paper's central computation result, and it should be resolved before the reader can implement or verify the algorithm.
minor comments (5)
  1. [App. C] In the 3-set cover reduction, the set is written as T_i = {t(i)_1, t(i)_3, t(i)_3}; the second subscript should presumably be 2, not 3.
  2. [App. D] Lemma 2's proof cites 'Eq. (13)', but Eq. (13) appears later in Appendix L for the continuous-parameter extension. The reference should be to the analogous discrete expression from Proposition 1.
  3. [Sec. VII-B] The continuous-parameter extension in Eq. (3) and Proposition 8 are stated without regularity conditions on the densities or on the mechanism kernel; some integrability or absolute-continuity assumptions should be stated explicitly.
  4. [Sec. III and Sec. V-C] The notation τ is used both for the histogram precision level and for the number of samples in Proposition 3 ('a dataset with τ samples'). Since the paper assumes τ ≤ n, please clarify whether the robustness result requires τ = n or only τ ≤ n.
  5. [Sec. V-C] Theorem 4 combines the two mechanism-specific results and the comparison into a single theorem with three statements. Separating the RR and QM claims would make the statement and proof easier to follow.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SML is defined operationally and the mechanism analyses are self-contained computations from Prop. 1; the flagged composition-proof issue is a correctness gap, not circularity.

full rationale

The privacy measure in Eq. (2) is defined operationally as the worst-case multiplicative increase in one-try guessing success for a known secret function g. Proposition 1 is derived from that definition by an explicit supremum-exchange and prior-restriction argument (App. A-C), and Proposition 2 then equates deterministic SML to the negative log cost of a min-cost flow by constructing feasible flows from the Prop. 1 expression rather than by assuming the intended leakage value. Theorem 4 likewise evaluates the SML of randomized response and the quantization mechanism by direct substitution of their transition probabilities into Prop. 1, with no fitted parameters and no imported uniqueness theorem. The self-citations in the paper, such as [1], [17], [26], and [52], motivate the quantization mechanism and contextualize related summary-statistic privacy work, but they are not load-bearing for the SML definitions, bounds, or mechanism comparisons. The empirical section computes privacy values from the proved formulas and measures distortion independently, so it does not rename fitted inputs as predictions. The only substantive concern raised by the skeptical review is in App. D: the proof of Theorem 2 defines Q_i = log Σ_{[θ'(1),...,θ'(i)]} sup_g P_i(θ'(i)|θ_g, past) and then asserts Q_i = Π_{M_i,g}; this equality is not valid for adaptive mechanisms because Q_i averages over all past histories whereas the SML of an adaptive mechanism is a worst case over histories. That is a mathematical gap in the advertised adaptive composition proof, not a circular reduction from a conclusion back to an input, so it does not raise the circularity score. The central derivation chain is self-contained: the definition, the equivalent form, the deterministic computation, and the mechanism-specific leakage values are each computed from stated assumptions rather than from the results they are meant to establish.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central derivations rest on finite categorical data, a deterministic known secret, and worst-case expected TV utility. These are explicitly stated, so they are not hidden, but they limit the scope. No new physical or computational entities are introduced beyond the privacy measure itself.

assumptions (4)
  • domain assumption Finite parameter space Θ and finite secret space G; data modeled as categorical histograms with precision τ
    Prop. 1, Thm. 4 and the deterministic flow construction all require finite Θ; the paper defers continuous spaces to Sec. VII-B and App. L.
  • domain assumption Secret G is a deterministic known function g(Θ), and adversary aims to maximize exact guessing success with unbounded computation
    This is the operational model in Eq. (2) and the Markov chain G-Θ-Θ'-Ghat in Sec. III.
  • domain assumption Utility is the worst-case expected total variation distance between original and released distribution parameters (Eq. 1)
    This utility choice drives the QM-over-RR comparison in Thm. 4 and the experiments; other utility measures could change the conclusion.
  • standard math Standard probability and information-theoretic inequalities, plus the cited NP-completeness of 3-set cover and the approximation algorithm for edge-cost flow [65]
    The NP-hardness reduction in App. C relies on 3-set cover; the approximation claim relies on [65] without a detailed proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Statistic Maximal Leakage." pith.science (2026). https://pith.science/paper/XZILRI6C

@misc{pith2026241118531,
  author       = {Pith},
  title        = {Pith review of: Statistic Maximal Leakage},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XZILRI6C}},
  note         = {Machine review of arXiv:2411.18531}
}
read the original abstract

We introduce a privacy measure called statistic maximal leakage that quantifies how much a privacy mechanism leaks about a specific secret, relative to the adversary's prior information about that secret. Statistic maximal leakage is an extension of the well-known maximal leakage. Unlike maximal leakage, which protects an arbitrary, unknown secret, statistic maximal leakage protects a single, known secret. We show that statistic maximal leakage satisfies composition and post-processing properties. Additionally, we show how to efficiently compute it in the special case of deterministic data release mechanisms. We analyze two important mechanisms under statistic maximal leakage: the quantization mechanism and randomized response. We show theoretically and empirically that the quantization mechanism achieves better privacy-utility tradeoffs in the settings we study.

Figures

Figures reproduced from arXiv: 2411.18531 by the authors.

Figure 1
Figure 1. Given a mechanism M = PΘ′ |Θ, the left subfigure shows a policy matrix. For each column j, the red outlined region indicates rows of parameters with secret g maximizing PΘ′ |Θ [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Relation between Γ, Γ ∗ , Γˆ∗ , Γˆ∗ 0 and Γˆ∗ 1 . Γ ∗ is the set depicted in black, containing all feasible attribute combinations. Γ in red is the set of attribute combinations existing in the dataset D, and Γ ⊆ Γ ∗ . Γˆ∗ in dark yellow is the data holder’s estimate of Γ ∗ ; it may contain both feasible attribute combinations, as shown in the blue sub-region with notation Γˆ∗ 0 , and infeasible attribute combinatio… view at source ↗
Figure 3
Figure 3. For a tabular dataset, we can generate a categorical distribution with each category corresponding to the fraction of [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: Under attribute privacy, the privacy level of RR does not vary with the number of possible secrets, indicating its inability [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]
Figure 5
Figure 5. Figure 5: Privacy-utility trade-offs of RR, QM, and MaxL when [PITH_FULL_IMAGE:figures/full_fig_p011_5.png]
Figure 6
Figure 6. Figure 6: Comparison of ROC curves of random forests under QM with different SML. [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: Comparisons of ROC curves of random forests trained on released data by quantization mechanism with different SML,  [PITH_FULL_IMAGE:figures/full_fig_p013_7.png]
Figure 8
Figure 8. Figure 8: Given a mechanism M = PΘ′ |Θ, the left subfigure shows a policy matrix. For each column j, the red outlined region indicates rows of parameters with secret g maximizing PΘ′ |Θ [PITH_FULL_IMAGE:figures/full_fig_p021_8.png]
Figure 9
Figure 9. Figure 9: The lower and upper bounds of the privacy-distortion performance of quantization mechanism and Randomized Response [PITH_FULL_IMAGE:figures/full_fig_p036_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

87 extracted references · 76 canonical work pages

  1. [1]

    Statistic maximal leakage,

    S. Wang, Z. Lin, and G. Fanti, “Statistic maximal leakage,” in 2024 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2024, pp. 2742–2747

    2024

  2. [2]

    A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers (corresp.),

    H. Yamamoto, “A source coding problem for sources with additional outputs to keep secret from the receiver or wiretappers (corresp.),” IEEE Transactions on Information Theory , vol. 29, no. 6, pp. 918–923, 1983

    1983

  3. [3]

    On the foundations of quantitative information flow,

    G. Smith, “On the foundations of quantitative information flow,” in FoSSaCS. Springer, 2009, pp. 288–302

    2009

  4. [4]

    Measuring information leakage using generalized gain functions,

    S. A. Mario, K. Chatzikokolakis, C. Palamidessi, and G. Smith, “Measuring information leakage using generalized gain functions,” in CSF. IEEE, 2012

    2012

  5. [5]

    Privacy with estimation guarantees,

    H. Wang, L. V o, F. P. Calmon, M. Médard, K. R. Duffy, and M. Varia, “Privacy with estimation guarantees,” IEEE Transactions on Information Theory , vol. 65, no. 12, pp. 8025–8042, 2019

    2019

  6. [6]

    From the information bottleneck to the privacy funnel,

    A. Makhdoumi, S. Salamatian, N. Fawaz, and M. Médard, “From the information bottleneck to the privacy funnel,” in IEEE ITW 2014 . IEEE, 2014, pp. 501–505

    2014

  7. [7]

    Bounds for privacy-utility trade-off with non-zero leakage,

    A. Zamani, T. J. Oechtering, and M. Skoglund, “Bounds for privacy-utility trade-off with non-zero leakage,” in IEEE ISIT 2022 . IEEE, 2022, pp. 620–625

    2022

  8. [8]

    Quantitative notions of leakage for one-try attacks,

    C. Braun, K. Chatzikokolakis, and C. Palamidessi, “Quantitative notions of leakage for one-try attacks,” Electronic Notes in Theoretical Computer Science, vol. 249, pp. 75–91, 2009

    work page 2009

Show all 87 references
  1. [9]

    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

    2019

  2. [10]

    Principal inertia components and applications,

    F. du Pin Calmon, A. Makhdoumi, M. Médard, M. Varia, M. Christiansen, and K. R. Duffy, “Principal inertia components and applications,” IEEE Transactions on Information Theory , vol. 63, no. 8, pp. 5011–5038, 2017

    2017

  3. [11]

    Secrecy by design with applications to privacy and compression,

    Y . Y . Shkel, R. S. Blum, and H. V . Poor, “Secrecy by design with applications to privacy and compression,” IEEE Transactions on Information Theory , vol. 67, no. 2, pp. 824–843, 2020

    2020

  4. [12]

    On the privacy-utility trade-off with and without direct access to the private data,

    A. Zamani, T. J. Oechtering, and M. Skoglund, “On the privacy-utility trade-off with and without direct access to the private data,” IEEE Transactions on Information Theory , 2023

    2023

  5. [13]

    An efficient difference-of-convex solver for privacy funnel,

    T.-H. Huang and H. El Gamal, “An efficient difference-of-convex solver for privacy funnel,” in 2024 IEEE International Symposium on Information Theory Workshops (ISIT-W). IEEE, 2024, pp. 1–6

    2024

  6. [14]

    A compression perspective on secrecy measures,

    Y . Y . Shkel and H. V . Poor, “A compression perspective on secrecy measures,” IEEE Journal on Selected Areas in Information Theory , vol. 2, no. 1, pp. 163–176, 2021

    2021

  7. [15]

    Cache-aided private variable-length coding with zero and non-zero leakage,

    A. Zamani, T. J. Oechtering, D. Gündüz, and M. Skoglund, “Cache-aided private variable-length coding with zero and non-zero leakage,” in 2023 21st International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt) . IEEE, 2023, pp. 247–254

    2023

  8. [16]

    Private variable-length coding with non-zero leakage,

    A. Zamani, T. J. Oechtering, and M. Skoglund, “Private variable-length coding with non-zero leakage,” in 2023 IEEE International Workshop on Information Forensics and Security (WIFS) . IEEE, 2023, pp. 1–6

    2023

  9. [17]

    Summary statistic privacy in data sharing,

    Z. Lin, S. Wang, V . Sekar, and G. Fanti, “Summary statistic privacy in data sharing,” arXiv preprint arXiv:2303.02014 , 2023

    2023 arXiv

  10. [18]

    Consequences of model misspecification for maximum likelihood estimation with missing data,

    R. M. Golden, S. S. Henley, H. White, and T. M. Kashner, “Consequences of model misspecification for maximum likelihood estimation with missing data,” Econometrics, vol. 7, no. 3, p. 37, 2019

    2019

  11. [19]

    Some comments on misspecification of priors in bayesian modelling of measurement error problems,

    S. Richardson and L. Leblond, “Some comments on misspecification of priors in bayesian modelling of measurement error problems,” Statistics in Medicine, vol. 16, no. 2, pp. 203–213, 1997

    1997

  12. [20]

    Misspecification in infinite-dimensional bayesian statistics,

    B. J. Kleijn and A. W. van der Vaart, “Misspecification in infinite-dimensional bayesian statistics,” 2006

    2006

  13. [21]

    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,” in TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3 . Springer, 2006, pp. 265–284

    2006

  14. [22]

    Deep learning with differential privacy,

    M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, “Deep learning with differential privacy,” in ACM CCS 2016 , 2016, pp. 308–318

    2016

  15. [23]

    Attribute privacy: Framework and mechanisms,

    W. Zhang, O. Ohrimenko, and R. Cummings, “Attribute privacy: Framework and mechanisms,” in FACCT. ACM, 2022

    2022

  16. [24]

    Local obfuscation mechanisms for hiding probability distributions,

    Y . Kawamoto and T. Murakami, “Local obfuscation mechanisms for hiding probability distributions,” in Computer Security–ESORICS 2019, Luxembourg, September 23–27, 2019, Proceedings, Part I 24 . Springer, 2019, pp. 128–148

    2019

  17. [25]

    Formalizing and estimating distribution inference risks,

    A. Suri and D. Evans, “Formalizing and estimating distribution inference risks,” arXiv preprint arXiv:2109.06024 , 2021

    2021 arXiv

  18. [26]

    Guarding multiple secrets: Enhanced summary statistic privacy for data sharing,

    S. Wang, R. Wei, M. Ghassemi, E. Kreacic, and V . K. Potluru, “Guarding multiple secrets: Enhanced summary statistic privacy for data sharing,” in Privacy Regulation and Protection in Machine Learning

  19. [27]

    Pointwise maximal leakage,

    S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Pointwise maximal leakage,” in IEEE ISIT 2022 . IEEE, 2022, pp. 626–631

    2022

  20. [28]

    Development and analysis of deterministic privacy-preserving policies using non-stochastic information theory,

    F. Farokhi, “Development and analysis of deterministic privacy-preserving policies using non-stochastic information theory,” IEEE Transactions on Information Forensics and Security , vol. 14, no. 10, pp. 2567–2576, 2019

    2019

  21. [29]

    Chaudhuri and R

    A. Chaudhuri and R. Mukerjee, Randomized response: Theory and techniques . Routledge, 2020

    2020

  22. [30]

    Extremal mechanisms for local differential privacy,

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

    2016

  23. [31]

    Using randomized response for differential privacy preserving data collection

    Y . Wang, X. Wu, and D. Hu, “Using randomized response for differential privacy preserving data collection.” in EDBT/ICDT Workshops, vol. 1558, 2016, pp. 0090–6778

    2016

  24. [32]

    Tunable measures for information leakage and applications to privacy-utility tradeoffs,

    J. Liao, O. Kosut, L. Sankar, and F. du Pin Calmon, “Tunable measures for information leakage and applications to privacy-utility tradeoffs,” IEEE Transactions on Information Theory , vol. 65, no. 12, pp. 8043–8066, 2019

    2019

  25. [33]

    (α, β)-leakage: A unified privacy leakage measure,

    A. Gilani, G. R. Kurri, O. Kosut, and L. Sankar, “ (α, β)-leakage: A unified privacy leakage measure,” 2023

    2023

  26. [34]

    An operational approach to information leakage via generalized gain functions,

    G. R. Kurri, L. Sankar, and O. Kosut, “An operational approach to information leakage via generalized gain functions,” 2022

    2022

  27. [35]

    Binary maximal leakage,

    R. D. Cung, Y . Y . Shkel, and I. Issa, “Binary maximal leakage,” in 2024 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2024, pp. 2748–2753

    2024

  28. [36]

    Fundamental limits of perfect privacy,

    F. P. Calmon, A. Makhdoumi, and M. Médard, “Fundamental limits of perfect privacy,” in ISIT. IEEE, 2015

    2015

  29. [37]

    On perfect privacy,

    B. Rassouli and D. Gündüz, “On perfect privacy,” IEEE JSAIT, vol. 2, no. 1, pp. 177–191, 2021

    2021

  30. [38]

    Privic: A privacy-preserving method for incremental collection of location data,

    S. Biswas and C. Palamidessi, “Privic: A privacy-preserving method for incremental collection of location data,” 2022

    2022

  31. [39]

    Back to the drawing board: Revisiting the design of optimal location privacy-preserving mechanisms,

    S. Oya, C. Troncoso, and F. Pérez-González, “Back to the drawing board: Revisiting the design of optimal location privacy-preserving mechanisms,” in 2017 ACM CCS , 2017, pp. 1959–1972

    2017

  32. [40]

    Quantitative analysis of the leakage of confidential data,

    D. Clark, S. Hunt, and P. Malacaria, “Quantitative analysis of the leakage of confidential data,” Electronic Notes in Theoretical Computer Science , vol. 59, no. 3, pp. 238–251, 2002

    2002

  33. [41]

    A static analysis for quantifying information flow in a simple imperative language,

    ——, “A static analysis for quantifying information flow in a simple imperative language,” Journal of Computer Security , vol. 15, no. 3, pp. 321–371, 2007

    2007

  34. [42]

    Assessing security threats of looping constructs,

    P. Malacaria, “Assessing security threats of looping constructs,” in 2007 ACM POPL , 2007, pp. 225–235

    2007

  35. [43]

    Optimal utility-privacy trade-off with total variation distance as a privacy measure,

    B. Rassouli and D. Gündüz, “Optimal utility-privacy trade-off with total variation distance as a privacy measure,” IEEE Transactions on Information Forensics and Security, vol. 15, pp. 594–603, 2019

    2019

  36. [44]

    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,” in IEEE CSF 2014 . IEEE, 2014, pp. 308–322. 15

    2014

  37. [45]

    Privacy-aware guessing efficiency,

    S. Asoodeh, M. Diaz, F. Alajaji, and T. Linder, “Privacy-aware guessing efficiency,” in ISIT. IEEE, 2017

    2017

  38. [46]

    Estimation efficiency under privacy constraints,

    ——, “Estimation efficiency under privacy constraints,” IEEE Transactions on Information Theory , vol. 65, no. 3, pp. 1512–1534, 2018

    2018

  39. [47]

    Correlated secrets in quantitative information flow,

    N. E. Bordenabe and G. Smith, “Correlated secrets in quantitative information flow,” in CSF. IEEE, 2016

    2016

  40. [48]

    Analyzing the shuffle model through the lens of quantitative information flow,

    M. Jurado, R. G. Gonze, M. S. Alvim, and C. Palamidessi, “Analyzing the shuffle model through the lens of quantitative information flow,” arXiv preprint arXiv:2305.13075, 2023

    2023 arXiv

  41. [49]

    On the security-privacy tradeoff in collaborative security: A quantitative information flow game perspective,

    R. Jin, X. He, and H. Dai, “On the security-privacy tradeoff in collaborative security: A quantitative information flow game perspective,”IEEE Transactions on Information Forensics and Security , vol. 14, no. 12, pp. 3273–3286, 2019

    2019

  42. [50]

    A novel analysis of utility in privacy pipelines, using kronecker products and quantitative information flow,

    M. S. Alvim, N. Fernandes, A. McIver, C. Morgan, and G. H. Nunes, “A novel analysis of utility in privacy pipelines, using kronecker products and quantitative information flow,” in 2023 ACM CCS , 2023, pp. 1718–1731

    2023

  43. [51]

    Coding theorems for a discrete source with a fidelity criterion,

    C. E. Shannon, “Coding theorems for a discrete source with a fidelity criterion,” IRE International Convention Record , vol. 4, no. 142-163, p. 1, 1959

    1959

  44. [52]

    Guarding multiple secrets: Enhanced summary statistic privacy for data sharing,

    S. Wang, R. Wei, M. Ghassemi, E. Kreacic, and V . K. Potluru, “Guarding multiple secrets: Enhanced summary statistic privacy for data sharing,” arXiv preprint arXiv:2405.13804, 2024

    2024 arXiv

  45. [53]

    D. E. R. Denning, Cryptography and data security . Addison-Wesley Reading, 1982, vol. 112

    1982

  46. [54]

    Toward a mathematical foundation for information flow security,

    J. W. Gray III, “Toward a mathematical foundation for information flow security,” Journal of Computer Security , vol. 1, no. 3-4, pp. 255–294, 1992

    1992

  47. [55]

    Noiseless database privacy,

    R. Bhaskar, A. Bhowmick, V . Goyal, S. Laxman, and A. Thakurta, “Noiseless database privacy,” in ASIACRYPT 2011, Seoul, South Korea, December 4-8, 2011. Proceedings 17 . Springer, 2011, pp. 215–232

    2011

  48. [56]

    Noiseless privacy: Definition, guarantees, and applications,

    F. Farokhi, “Noiseless privacy: Definition, guarantees, and applications,” IEEE Transactions on Big Data , 2021

    2021

  49. [57]

    Non-stochastic private function evaluation,

    F. Farokhi and G. Nair, “Non-stochastic private function evaluation,” in 2020 IEEE ITW . IEEE, 2021, pp. 1–5

    2020

  50. [58]

    A nonstochastic information theory for communication and state estimation,

    G. N. Nair, “A nonstochastic information theory for communication and state estimation,” IEEE Transactions on automatic control , vol. 58, no. 6, pp. 1497–1510, 2013

    2013

  51. [59]

    Dissecting distribution inference,

    A. Suri, Y . Lu, Y . Chen, and D. Evans, “Dissecting distribution inference,” in First IEEE Conference on Secure and Trustworthy Machine Learning , 2023

    2023

  52. [60]

    Local differential privacy: a tutorial,

    B. Bebensee, “Local differential privacy: a tutorial,” arXiv preprint arXiv:1907.11908 , 2019

    1907 arXiv

  53. [61]

    Differential privacy: on the trade-off between utility and information leakage,

    M. S. Alvim, M. E. Andrés, K. Chatzikokolakis, P. Degano, and C. Palamidessi, “Differential privacy: on the trade-off between utility and information leakage,” in Formal Aspects of Security and Trust: 8th International Workshop, FAST 2011, Leuven, Belgium, September 12-14, 201...

    2011

  54. [62]

    {Utility-Optimized} local differential privacy mechanisms for distribution estimation,

    T. Murakami and Y . Kawamoto, “ {Utility-Optimized} local differential privacy mechanisms for distribution estimation,” in 28th USENIX Security Symposium (USENIX Security 19) , 2019, pp. 1877–1894

    2019

  55. [63]

    Flows in networks,

    L. R. Ford, “Flows in networks,” 2015

    2015

  56. [64]

    R. M. Karp, Reducibility among combinatorial problems . Springer, 2010

    2010

  57. [65]

    Flow improvement and network flows with fixed costs,

    S. O. Krumke, H. Noltemeier, S. Schwarz, H.-C. Wirth, and R. Ravi, “Flow improvement and network flows with fixed costs,” in Operations Research Proceedings 1998: Selected Papers of the International Conference on Operations Research Zurich, August 31–September 3, 1998 . Sprin...

    1998

  58. [66]

    Boosting and differential privacy,

    C. Dwork, G. N. Rothblum, and S. Vadhan, “Boosting and differential privacy,” in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science. IEEE, 2010, pp. 51–60

    2010

  59. [67]

    Becker and R

    B. Becker and R. Kohavi, “Adult,” UCI Machine Learning Repository, 1996, DOI: https://doi.org/10.24432/C5XW20

    1996 doi

  60. [68]

    Optimal mechanisms under maximal leakage,

    B. Wu, A. B. Wagner, and G. E. Suh, “Optimal mechanisms under maximal leakage,” in 2020 IEEE Conference on Communications and Network Security (CNS). IEEE, 2020, pp. 1–6

    2020

  61. [69]

    Michael r. πgarey and david s. johnson. computers and intractability. a guide to the theory of np-completeness. wh freeman and company, san francisco1979, x+ 338 pp

    H. R. Lewis, “Michael r. πgarey and david s. johnson. computers and intractability. a guide to the theory of np-completeness. wh freeman and company, san francisco1979, x+ 338 pp.” The Journal of Symbolic Logic , vol. 48, no. 2, pp. 498–500, 1983

    1983

  62. [70]

    Minimum cost flow problem with conflicts,

    Z. ¸ Suvak, ˙I. K. Altınel, and N. Aras, “Minimum cost flow problem with conflicts,” Networks, vol. 78, no. 4, pp. 421–442, 2021. 16 APPENDIX A PROOFS OF LEMMA 1, P ROPERTY 1, AND PROP. 1 A. Proof of Lemma 1 Lemma 1. The distortion measure ∆M can be rewritten as ∆M = supθ EΘ′=...

    2021

  63. [71]

    𝜃! 𝜃" 𝜃# 𝜃!$ 𝜃

    For any i ∈ [k], there exists ji ∈ [m] such that θgi = θ(gi) ji , and we construct a sub-collection of T as ˜T = {Tj1 , . . . , Tjk }. Since Θ′ = U and PΘ′|Θ (θ′|θgi ) = 1 3 if and only if θ′ ∈ Tji (i ∈ [k]), we can get that ∀u ∈ U, ∃i ∈ [k] : u ∈ Tji. Therefore, S i∈[k] Tji =...

  64. [72]

    Therefore, there exists an approximation algorithm for SML calculation with approximation ratio 1 +ρ (ρ >0) and running time polynomial in |Θ| · |Θ′| and 1/ρ

    provides an approximation algorithm for the edge cost flow problem, with approximation ratio 1 + ρ (ρ > 0) and running time polynomial in m and 1/ρ, where m represents the number of edges in the network. Therefore, there exists an approximation algorithm for SML calculation wi...

  65. [73]

    4, we know that Π∗ MRR,g = log τ +d∗−1 d∗−1 + s (eϵ − 1) τ +d∗−1 d∗−1 + eϵ − 1 ≥ log τ +d∗+ ˆd∗ 1 −1 d∗+ ˆd∗ 1 −1 + s (eϵ − 1) τ +d∗+ ˆd∗ 1 −1 d∗+ ˆd∗ 1 −1 + eϵ − 1

    Randomized Response For Randomized Response with hyperparameter ϵ, from Thm. 4, we know that Π∗ MRR,g = log τ +d∗−1 d∗−1 + s (eϵ − 1) τ +d∗−1 d∗−1 + eϵ − 1 ≥ log τ +d∗+ ˆd∗ 1 −1 d∗+ ˆd∗ 1 −1 + s (eϵ − 1) τ +d∗+ ˆd∗ 1 −1 d∗+ ˆd∗ 1 −1 + eϵ − 1 . 27 For ΠMRR,g, we can get that ΠM...

  66. [74]

    4, we know that Π∗ MQM,g = log l s I m

    Quantization Mechanism For quantization mechanism with interval length I, from Thm. 4, we know that Π∗ MQM,g = log l s I m . 28 For convenience, let gk,I represent g(k+ 1 2 )I, the output secret value of the k-th interval. For ΠMQM,g, we have ΠMQM,g = sup PΘ|G∈{0,1} log X θ′∈Θ...

  67. [75]

    s I 1 + τ I−2s(d∗− ˆd∗ 0) τ I+2s(d∗+ ˆd∗ 1 −2) d∗− ˆd∗ 0 # , d ∗ − ˆd∗ 0 ≤ log I, log

    Quantization Mechanism ΠMQM,g can be upper bounded by ΠMQM,g = sup PΘ|G∈{0,1} log X θ′∈Θ′(∗) sup g∈G PΘ′|Θ (θ′|θg) ≤ sup PΘ|G∈{0,1} log X k∈{0,1,··· ,⌈ s I ⌉−1}  sup g∈G X θ′∈Θ′(0) R(k) PΘ′|Θ (θ′|θg) + X g∈G X θ′∈Θ′(∗) R(k)\Θ′(0) R(k) PΘ′|Θ (θ′|θg)   ≤ sup PΘ|G∈{0,1} log...

  68. [76]

    Therefore, we can get that ΠMRR,g = sup PΘ|G∈{0,1} log X θ′∈Θ′(∗) sup g∈G PΘ′|Θ (θ′|θg) = sup PΘ|G∈{0,1} log X θ′∈{θg}g∈G sup g∈G PΘ′|Θ (θ′|θg) + X θ′∈Θ′(∗)\{θg}g∈G sup g∈G PΘ′|Θ (θ′|θg) ! ≥ log   X θ′∈{θg}g∈G eϵ τ + ˆd∗ 0 + ˆd∗ 1 +β(θ′)−1 ˆd∗ 0 + ˆd∗ 1 +β(θ′)−1 + eϵ − 1 + ...

  69. [77]

    Denote ζ ≜ j d∗− ˆd∗ 0 s k

    We can find a prior distribution PΘ of the distribution parameter such that PΘ|G ∈ {0, 1} and ∀g1, g2 ∈ G, g1 ̸= g2 : ˜Γθg1 ∩ ˜Γθg1 = ∅ and ˜Γθg1 = ˜Γθg2 = j d∗− ˆd∗ 0 s k . Denote ζ ≜ j d∗− ˆd∗ 0 s k . Therefore, we can get that ΠMRR,g = sup PΘ|G∈{0,1} log X θ′∈Θ′(∗) sup g∈G ...

  70. [78]

    Quantization Mechanism Denote Gk as the set of the secret values within the k-th interval, i.e., Gk = {gkI +j}j∈[I]. When d∗ − ˆd∗ 0 ≤ log I, we can find a prior distribution PΘ of the distribution parameter such that PΘ|G ∈ {0, 1} and ∀˜Γ ⊆ Γ∗ \ ˆΓ∗ 0, k∈ 0, 1, · · ·, s I − 1...

  71. [79]

    When log I < d∗ − ˆd∗ 0 < I, we can easily get that ΠMQM,g ≥ log   j s I k  1 + τ I− 2s · log I τ I+ 2s d∗ + ˆd∗ 1 − 2   log I  

    Therefore, we can get that ΠMQM,g = sup PΘ|G∈{0,1} log X θ′∈Θ′(∗) sup g∈G PΘ′|Θ (θ′|θg) ≥ sup PΘ|G∈{0,1} log X k∈{0,1,··· ,⌊ s I ⌋−1} X θ′∈Θ′(∗) R(k) sup g∈G PΘ′|Θ (θ′|θg) ≥ log X k∈{0,1,··· ,⌊ s I ⌋−1} X θ′∈Θ′(∗) R(k) 1 τ (1−gk,I )+ ˆd∗ 0 + ˆd∗ 1 +β(θ′)−2 ˆd∗ 0 + ˆd∗ 1 +β(θ′)...

  72. [80]

    Denote ζ ≜ j d∗− ˆd∗ 0 I k

    We can find a prior distribution PΘ of the distribution parameter such that PΘ|G ∈ {0, 1} and ∀k ∈ 0, 1, · · ·, s I − 1 , g1, g2 ∈ Gk, g1 ̸= g2 : ˜Γθg1 ∩ ˜Γθg1 = ∅ and ˜Γθg1 = ˜Γθg2 = j d∗− ˆd∗ 0 I k . Denote ζ ≜ j d∗− ˆd∗ 0 I k . Therefore, we can get that ΠMQM,g = sup PΘ|G∈{...

  73. [81]

    Quantization Mechanism Let ∆MQM,τ be the gap of lower and upper bounds of the privacy of randomized response under a dataset with τ samples. When d∗ − ˆd∗ 0 ≤ log I, we have lim τ →∞ ∆MQM,τ ≤ lim τ →∞ log   l s I m 1 + τ τ + ˆd∗ 0 + ˆd∗ 1 − 2 !d∗− ˆd∗ 0   − lim τ →∞ log  ...

  74. [82]

    Randomized Response Similar to the proof of Thm. 4, we can bound the distortion of Randomized Response as ˆd∗ 0 + ˆd∗ 1 − 1 ˆd∗ 0 + ˆd∗ 1 (1 + r1) ≤ ∆MRR ≤ d∗ + ˆd∗ 1 − 1 d∗ + ˆd∗ 1 (1 + r2) , where r1 ≜ eϵ−1 ( τ + ˆd∗ 0 + ˆd∗ 1 −1 ˆd∗ 0 + ˆd∗ 1 −1 ) and r2 ≜ eϵ−1 ( τ +d∗ + ˆd...

  75. [83]

    4, we can bound the distortion of Quantization Mechanism as 1 2 + ˆd∗ 0 + ˆd∗ 1 I 2 − τ 2τ ˆd∗ 0 + ˆd∗ 1 − 1 ≤ ∆MQM ≤ 1 2 + d∗ + ˆd∗ 1 I 2 − τ 2τ d∗ + ˆd∗ 1 − 1

    Quantization Mechanism When secret is the fraction of a category, similar to the proof of Thm. 4, we can bound the distortion of Quantization Mechanism as 1 2 + ˆd∗ 0 + ˆd∗ 1 I 2 − τ 2τ ˆd∗ 0 + ˆd∗ 1 − 1 ≤ ∆MQM ≤ 1 2 + d∗ + ˆd∗ 1 I 2 − τ 2τ d∗ + ˆd∗ 1 − 1 . APPENDIX I ANALYSIS...

  76. [84]

    Under this setting, we can get that τ τ + ˆd∗ 0 + ˆd∗ 1 −2 ≈ τ τ + ˆd∗ 0 ≜ r and ˆd∗ 0 + ˆd∗ 1 −1 τ +d∗+ ˆd∗ 1 −2 ≈ ˆd∗ 0 τ + ˆd∗ 0 = 1 − r. Therefore, when log s I 1 + τ τ + ˆd∗ 0 + ˆd∗ 1 −2 d∗− ˆd∗ 0 ≤ log s I + s − s · ˆd∗ 0 + ˆd∗ 1 −1 τ +d∗+ ˆd∗ 1 −2 d∗− ˆd∗ 0 ! , we have ...

  77. [86]

    We analyze the connections between those privacy measures in Prop

    , ∀θ1, θ2 ∈ Θ, g (θ1) ̸= g (θ2) ;∀Θ′ 0 ⊆ Θ′. We analyze the connections between those privacy measures in Prop. 7. Proposition 7. If a data release mechanism M is µ-LDP , then it satisfies ΠM,g ≤ µ and Πinf M,g ≤ µ. If a data release mechanism M satisfies ˜ΠM,g ≤ µ1 and ˜Πinf ...

  78. [87]

    ≤ eµ · P (M (θ2) ∈ Θ′

  79. [88]

    (10) From Prop

    , ∀θ1, θ2 ∈ Θ, g (θ1) ̸= g (θ2) ;∀Θ′ 0 ⊆ Θ′, we have PΘ′|Θ (θ′|θ1) ≤ eµ · PΘ′|Θ (θ′|θ2) , ∀θ1, θ2 ∈ Θ, g (θ1) ̸= g (θ2) ;∀θ′ ∈ Θ′. (10) From Prop. 1, we know that ΠM,g = sup PΘ|G∈{0,1} log X θ′∈Θ′ sup g∈G PΘ′|Θ (θ′|θg) . 38 We can find a θ0 ∈ Θ that satisfies ∃g ∈ G, P∗ Θ|G ∈ ...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.