PaperlayerView exact revision on arXiv

Source-linked AI summary

An Operational Approach to Information Leakage

Ibrahim Issa, Aaron B. Wagner, Sudeep Kamath

arXiv:1807.07878v1cs.IT

TL;DR

The paper studies how observations leak sensitive quantities and develops an operational leakage measure for analyzing privacy and secrecy systems. It applies this framework to encryption, estimation from data, and comparisons with established leakage measures.

  • Problem

    Quantifying how much an observation leaks about a sensitive quantity is central to secrecy and privacy problems, including side-channel settings.

  • Method

    The paper analyzes maximal leakage through adversarial guessing and studies its use in the Shannon cipher system and estimation from data.

  • Results

    The paper characterizes an optimal normalized maximal-leakage limit for the Shannon cipher system and defines the sample-complexity problem for estimating maximal leakage from data.

  • Takeaways & Limitations

    The framework supports leakage analysis for encryption and data-trace estimation while distinguishing maximal leakage from Shannon capacity in side-channel settings.

  • Takeaways & Limitations

    For binary X revealed exactly, maximal leakage is one bit regardless of the sensitivity of the binary quantity, so it may not capture the gravity of highly confidential disclosures.

Abstract

from arXiv · show

Given two random variables $X$ and $Y$, an operational approach is undertaken to quantify the ``leakage'' of information from $X$ to $Y$. The resulting measure $\mathcal{L}(X \!\! \to \!\! Y)$ is called \emph{maximal leakage}, and is defined as the multiplicative increase, upon observing $Y$, of the probability of correctly guessing a randomized function of $X$, maximized over all such randomized functions. A closed-form expression for $\mathcal{L}(X \!\! \to \!\! Y)$ is given for discrete $X$ and $Y$, and it is subsequently generalized to handle a large class of random variables. The resulting properties are shown to be consistent with an axiomatic view of a leakage measure, and the definition is shown to be robust to variations in the setup. Moreover, a variant of the Shannon cipher system is studied, in which performance of an encryption scheme is measured using maximal leakage. A single-letter characterization of the optimal limit of (normalized) maximal leakage is derived and asymptotically-optimal encryption schemes are demonstrated. Furthermore, the sample complexity of estimating maximal leakage from data is characterized up to subpolynomial factors. Finally, the \emph{guessing} framework used to define maximal leakage is used to give operational interpretations of commonly used leakage measures, such as Shannon capacity, maximal correlation, and local differential privacy.

I. INTRODUCTION

The paper introduces maximal leakage as an operational measure of how much an observation increases an adversary’s ability to guess randomized functions of sensitive information. It develops computable, robust, and extended forms, then applies the measure to encryption, estimation, and comparisons with other leakage metrics.

  • Motivation and definition: The measure addresses leakage from side channels such as SSH packet timing, shared-resource timing, encrypted messages, and wiretapped transmissions.These observations can reveal information correlated with passwords, keys, messages, or identities.
  • Motivation and definition: Maximal leakage measures the logarithm of the greatest multiplicative increase in correctly guessing a randomized function of X after observing Y.A leak of ℓ bits bounds the guessing-probability increase by 2^ℓ.
  • Properties and extensions: For discrete variables, maximal leakage equals Sibson mutual information of order infinity and satisfies data processing, independence, and additivity properties.It is also lower-bounded by mutual information, indicating that mutual information can underestimate leakage.
  • Properties and extensions: The definition remains unchanged when adversaries choose functions after observing Y, approximate their guesses, make several guesses, or optimize arbitrary gain functions.Conditional and generalized forms retain the axiomatic properties and are lower-bounded by conditional mutual information where appropriate.
  • Applications: In the Shannon cipher system, memoryless encryption schemes are strictly suboptimal, while optimal schemes correspond to good rate-distortion codes.The paper derives a single-letter characterization of the optimal normalized maximal-leakage limit.
  • Applications: Estimating maximal leakage requires knowing a lower bound θ on the smallest positive symbol probability, with a lower bound of Ω(|Y|/(θ log |Y|)) samples.The lower bound diverges as θ approaches zero, while the paper also gives a sufficient upper bound.
  • Applications: The guessing framework gives operational interpretations of Shannon capacity, local differential privacy, and maximal correlation.For example, Shannon capacity restricts the guessed functions and can therefore underestimate leakage.

A. Comparison with Related Metrics

The paper contrasts maximal leakage with mutual information, Shannon capacity, gain-based measures, and difference-based security criteria. It argues that maximal leakage better matches guessing-based secrecy goals while retaining computable bounds and axiomatic properties.

  • Mutual information: Maximal leakage upper-bounds mutual information, and no positive scalar multiple of mutual information universally upper-bounds maximal leakage.Equality requires additional structural conditions on the joint distribution.
  • Shannon capacity: For full-support X, maximal leakage is at least the Shannon capacity of the channel, and the inequality can be strict.This follows because maximal leakage depends on PX only through its support.
  • Gain-based measures: Existing gain-based definitions do not explicitly account for randomized functions of X and lack an operational interpretation for the maximizing gain function.The paper nevertheless notes that these metrics are related to maximal leakage.
  • Guessing criteria: Difference-based guessing criteria can behave differently from maximal leakage’s ratio because the ratio is designed for functions that are hard to guess a priori.The paper notes that its bound also controls the relevant difference quantity under suitable min-entropy conditions.

B. Proof of Theorem 1

The paper proves computable characterizations of maximal leakage by constructing a randomized function of X whose conditional supports are disjoint shards. It then shows that several threat-model variations produce the same quantity.

  • Proof of Theorem 1: The proof first bounds leakage for every U satisfying U−X−Y by the relevant information quantity.This establishes one direction of the characterization.
  • Proof of Theorem 1: A “shattering” conditional distribution is constructed using p⋆ = min_x PX(x), splitting each x into shards with disjoint conditional supports.The construction uses k(x) = PX(x)/p⋆ and assigns shard probabilities so the supports for distinct x do not overlap.
  • Proof of Theorem 1: The shattering construction attains the supremum for every finite output alphabet and conditional distribution.Thus one distribution PU|X works universally for a fixed finite PX.
  • Robustness: The same computable characterization persists across several guesses and arbitrary gain functions, demonstrating robustness to the adversary’s objective.The paper also extends the framework to conditional leakage and broad classes of random variables.
  • Robustness: Allowing the adversary to choose different secrets after observing Y does not change the computable characterization.The resulting opportunistic maximal leakage equals ordinary maximal leakage.
  • Robustness: For approximate guesses in a metric space, maximal locational leakage is bounded by ordinary maximal leakage and equals it when the space contains sufficiently separated countably many points.The equality condition holds, for example, when the space is unbounded.

C. Multiple Guesses

The paper shows that several adversarial variations, including multiple guesses and arbitrary gain functions, yield the same maximal leakage, while conditional and generalized forms retain core leakage properties. Examples further show that independent noise may be insecure and that accumulate-and-dump mechanisms can reduce leakage more effectively.

  • Multiple guesses: k-maximal leakage equals maximal leakage for every positive integer k, so allowing multiple guesses does not change the measure.The result holds for finite-alphabet X and Y.
  • Gain variations: Maximal gain leakage is equivalent to maximal leakage even when the adversary assigns different gains to different outcomes.The gain function may be arbitrary and nonnegative, with U ranging over finite but arbitrary alphabets.
  • Conditional leakage: Conditional maximal leakage equals the maximum unconditional leakage over supported values of the side information Z.It also satisfies data processing, cardinality bounds, zero-leakage characterization, additivity, and a lower bound by conditional mutual information.
  • General alphabets: The generalized formula preserves data processing, covers discrete, countable, and continuous variables, and gives zero leakage exactly under independence.Under the stated probability-space assumptions, maximal leakage is also additive and lower-bounds mutual information.
  • Side-channel mechanisms: Adding independent noise is not necessarily secure under maximal leakage, whereas accumulate-and-dump can make leakage arbitrarily small.For a matched average-waiting-time comparison, the memoryless scheme has leakage 2λ and accumulate-and-dump has leakage 3λ/2.
  • Side-channel mechanisms: The accumulate-and-dump guarantee assumes a process-dependent upper bound on packets released in an interval, which does not hold for a Poisson process.For processes satisfying that boundedness property, the leakage with injected dummy packets is upper-bounded by the stated expression.

IV. SHANNON CIPHER SYSTEM

The paper evaluates lossy Shannon cipher systems by normalized maximal leakage while requiring reliable reconstruction under a distortion constraint. For discrete memoryless sources, it derives the optimal asymptotic limit and an asymptotically optimal type-based scheme, and shows memoryless schemes are generally suboptimal in information blurring systems.

  • IV. SHANNON CIPHER SYSTEM: The Shannon cipher system uses a public message and shared random key, while the legitimate receiver reconstructs the source under a distortion constraint.The eavesdropper observes the public message only.
  • IV. SHANNON CIPHER SYSTEM: The analysis measures dependence between the source sequence and public message using maximal leakage, allowing lossy communication with exponentially decaying distortion-violation probability.The asymptotic quantity studied is normalized maximal leakage.
  • IV. SHANNON CIPHER SYSTEM: For discrete memoryless sources, the paper derives the minimal possible limit of normalized maximal leakage.The proposed primary-user scheme operates on a type-by-type basis with rate-distortion codes, binning, and key-based codeword randomization.
  • IV. SHANNON CIPHER SYSTEM: Under an expected-distortion constraint without a common key and with high channel rate, memoryless schemes are strictly suboptimal in the information blurring system.The result models side-channels such as perturbed SSH packet timings subject to quality constraints.

A. Problem Setup and Statement of Result

The paper studies encryption schemes that minimize maximal leakage from a source sequence to an eavesdropper while satisfying rate and distortion constraints. It characterizes the optimal normalized leakage and shows that memoryless schemes are generally suboptimal under expected distortion.

  • Problem setup: The eavesdropper observes the transmitted message and knows source statistics and coding functions but not the shared key.The transmitter sends X^n using a noiseless rate-R channel and common randomness of rate r.
  • Problem setup: The primary objective is to minimize maximal leakage L(X^n→M^n) asymptotically under the stated source, alphabet, distortion, and rate assumptions.The main assumptions include finite alphabets, a full-support memoryless source, bounded distortion, and a rate exceeding the relevant rate-distortion values.
  • Main result: The optimal normalized leakage is max Q:D(Q||P)≤α [R(Q,D)−r]+ bits.Here [a]+ = max{0,a}; the result applies under assumptions (A1)–(A4).
  • Main result: Under an almost-sure distortion constraint, the characterization also holds for non-memoryless sources with the same support.Both leakage and the constraint then depend on the source distribution only through the support of X^n.
  • Expected distortion: With expected distortion, memoryless schemes are generally strictly suboptimal for maximal leakage, unlike the corresponding mutual-information objective.The paper introduces a separate assumption R > R(P,D) and gives a binary Hamming-distortion example establishing strict suboptimality.

C. Notation

This section introduces type-based notation and the coding objects used in the Shannon cipher analysis. The proof framework partitions rate-distortion codebooks into key-sized bins and analyzes leakage through guessing.

  • Notation: Q_x^n denotes the empirical PMF, or type, of a sequence x^n, and T_Q is its associated type class.The notation also uses expectations, entropies, and mutual informations evaluated under a distribution Q.
  • Coding construction: The codebook is constructed separately for each type and contains at most 2^{n(R(Q,D)+ε)} codewords for type Q.The type covering lemma guarantees coverage of every sequence in the corresponding type class.
  • Coding construction: Each type-specific codebook is divided into bins of size 2^{nr}, with message components identifying the type, bin, and within-bin codeword.The shared key hides the within-bin index from the eavesdropper while enabling legitimate decoding.
  • Leakage analysis: The scheme effectively leaks the type and bin index while completely hiding the within-bin index.Because the number of types is polynomial, the type description does not affect normalized leakage; the bin index contributes roughly [R(Q,D)−r]+ bits.
  • Leakage analysis: The converse lower bound matches the achievability expression: L ≥ max Q:D(Q||P)≤α [R(Q,D)−r]+.The lower bound uses a specific shattering guessing function and the positivity of maximal leakage.

V. LEARNING MAXIMAL LEAKAGE FROM DATA

This section studies how many samples are needed to estimate maximal leakage from data. It finds that unrestricted estimation can be impossible, while a known lower bound on source probabilities yields finite bounds that are tight up to subpolynomial factors.

  • Problem formulation: The sample-complexity problem estimates maximal leakage from independent samples of the joint distribution P_XY with prescribed accuracy and confidence.The estimator is a randomized function mapping a finite sample sequence to a real-valued leakage estimate.
  • Impossibility and bounds: Without a lower bound on the minimum positive probability in X, the sample complexity is infinite for relevant parameter ranges.The impossibility is attributed mainly to maximal leakage’s discontinuity in the support of X.
  • Impossibility and bounds: A known lower bound θ on positive probabilities in X restores a finite upper bound for finite alphabets and arbitrary accuracy and confidence parameters.Theorem 11 provides the corresponding upper bound under θ ∈ (0,1).
  • Impossibility and bounds: The upper and lower bounds have matching dependence on alphabet size and θ up to subpolynomial factors.This comparison is stated explicitly in Remark 8.
  • Sampling models: Fixed-length and Poisson sampling are equivalent up to constant factors for maximal-leakage estimation.The proof uses Poisson tail bounds to relate estimators under the two sampling models.

B. Proof of Theorem 11

The proof of the finite-sample upper bound constructs a Poissonized estimator by truncating observations for each source symbol. It controls multiplicative overestimation and connects the lower bound to support-size estimation.

  • Estimator construction: When truncation is infeasible for some source symbol, the estimator outputs 1; otherwise it computes the leakage estimate from the retained counts.The retained pair counts e_Nx,y determine the estimator’s input frequencies.
  • Upper-bound analysis: In the infinite-sequence analysis, each retained conditional count is Poisson with mean nθ′P_Y|X(y|x).For each output y, the analysis selects a source symbol maximizing the conditional probability of y.
  • Upper-bound analysis: Chernoff bounds and Poisson coupling control the probability that the estimator exceeds the true leakage by a prescribed multiplicative factor.The finite-sample result follows after transferring the infinite-sequence analysis through the Poisson-to-fixed-length equivalence.
  • Lower-bound analysis: The lower-bound construction reduces leakage estimation to estimating a property of a distribution over the output alphabet.The reduction uses a source symbol with probability θ and a conditional distribution whose positive masses are at least 1/k.
  • Lower-bound analysis: Estimating that property is related to support-size estimation, yielding the lower bound through an established support-estimation result.The construction receives Poisson(nθ) conditional samples from the selected source symbol.

VI. GUESSING FRAMEWORK TO INTERPRET LEAKAGE METRICS

The guessing framework gives operational interpretations for established leakage metrics by matching each metric to the adversary’s objective and risk model. Shannon capacity fits reliable message reconstruction, while maximal correlation fits estimation through variance reduction.

  • VI. GUESSING FRAMEWORK TO INTERPRET LEAKAGE METRICS: The framework supplies operational definitions clarifying when Shannon capacity, maximal correlation, and related leakage metrics should be used.The interpretations distinguish covert-channel, estimation, and guessing-oriented settings.
  • D. Maximal Correlation: Maximal correlation captures multiplicative variance reduction and is therefore more suitable for estimation than guessing problems.The guessing framework also motivates a cost-based leakage notion based on reductions in adversarial costs.
  • A. Shannon Capacity: Maximal leakage and recoverable leakage are connected to channel coding through the asymptotic characterization involving C(P_Y|X).The coding setup uses a uniform message, stochastic encoding, a memoryless channel, and an allowed average decoding-error probability.
  • A. Shannon Capacity: Shannon capacity is suitable for covert-channel analysis, where communicating parties must reliably reconstruct messages.It is generally lower than maximal leakage because capacity imposes a reliability constraint that leakage does not.
  • A. Shannon Capacity: For a BEC(ε) with X ∼ Ber(p), maximal leakage equals log(2 − ε), exceeding capacity (1 − ε) log 2.The stated regime is p ∈ (0, 1/2) and ε ∈ (0, 1).

B. Maximal Realizable Leakage

Maximal realizable leakage replaces average guessing performance with a worst-case analysis over realizations of the observation. It equals Rényi divergence of order infinity, connects to local differential privacy, and supports cost- and variance-based interpretations of leakage.

  • B. Maximal Realizable Leakage: Maximal realizable leakage addresses settings where low-probability observation outcomes remain unacceptable and leakage must be evaluated by maximum guessing performance.The paper gives medical data and public databases as examples where leakage should not be concentrated around particular observations.
  • B. Maximal Realizable Leakage: Maximal realizable leakage equals D∞(P_XY || P_X × P_Y) for finite alphabets.Unlike maximal leakage, it depends on the marginal P_X and is symmetric in X and Y.
  • B. Maximal Realizable Leakage: Maximal realizable leakage satisfies data processing, vanishes exactly under independence, and is additive over independent pairs.These properties follow from corresponding properties of Rényi divergence of order infinity.
  • C. Local Differential Privacy: Local differential privacy is suited to database security when low risk is not tolerated and no assumptions are made about the data-generating distribution.It uses worst-case analysis over observation realizations and is robust to the marginal distribution P_X.
  • C. Local Differential Privacy: The leakage ordering is L_dp(X→Y) ≥ L_r(X→Y) ≥ L(X→Y), with equality between local differential privacy and maximal realizable leakage only under independence.The result also permits incorporating information about P_X by restricting the optimization set.
  • D. Maximal Correlation: For discrete functions such as passwords or social-security numbers, correct-guessing probability can be more relevant than variance reduction.The paper also cites discrete location-privacy targets such as home or work addresses and political affiliations.
  • D. Maximal Correlation: Variance leakage measures the adversary’s reduction in mean-squared-error cost and is linked to maximal correlation.This extends the framework toward cost functions rather than assuming the adversary’s objective is known in advance.

E. Maximal Cost Leakage

Maximal cost leakage measures the greatest reduction in an adversary’s guessing cost, complementing the gain-based maximal leakage framework. It has closed forms and axiomatic properties, but can be infinite and is less operationally meaningful for side-channel analysis.

  • Maximal cost leakage measures the maximum reduction in an adversary’s cost when observing Y instead of making no observation.
  • The gain-based approach is more operationally meaningful for side-channel analysis because it focuses on adversarial compromise rather than failure costs.
  • For finite alphabets, maximal cost leakage has a simple characterization and depends on PY|X and the support of PX.
  • Maximal cost leakage satisfies data processing, independence, additivity, asymmetry, differential-privacy upper bounds, and convexity properties.
  • For a non-trivial deterministic channel, maximal cost leakage is infinite, and even Lc(X→X) is infinite for a non-degenerate binary X.
  • Maximal realizable cost equals the Rényi divergence D∞(PX × PY || PXY), while local differential privacy captures worst-case cost reductions and gain increases.

APPENDIX A PROOFS FOR SECTION II

The appendix proves foundational properties of maximal leakage from its operational definition. These include data processing, support-based upper bounds, independence characterization, and additivity.

  • Maximal leakage obeys data processing: post-processing Y into Z cannot increase leakage from X.
  • For discrete Y, maximal leakage is bounded by log |supp(Y)|, and for discrete X it is at most log |supp(X)|.
  • Maximal leakage is zero exactly when X and Y are independent.
  • The proof establishes additivity and characterizes equality conditions through the channel’s support structure.
  • The appendix also proves robustness to allowing k guesses by constructing auxiliary variables that preserve the relevant guessing ratio.
  • The conditional form is analyzed by optimizing conditional leakage over side-information realizations and constructing a matching lower bound.

D. Proof of Theorem 7

Theorem 7 is proved first for finite X using a shattering auxiliary variable, then extended to general variables through refining finite partitions and measure-theoretic convergence.

  • For finite X, the proof uses a shattering conditional distribution whose largest marginal probability equals the smallest positive input probability.
  • General X is handled by discretizing it through an increasing sequence of finite partitions that generate its sigma-algebra.
  • The discretized likelihood-ratio processes form a martingale, enabling convergence to the relevant Radon–Nikodym derivative.
  • Monotone convergence and Egoroff’s theorem establish the required essential-supremum limit on sets of positive probability.
  • When absolute continuity fails, mutual information becomes infinite and discretizations yield diverging lower bounds on maximal leakage.
  • The proof also verifies that changing equivalent input measures preserves the induced output-measure equivalence needed for the characterization.

APPENDIX C PROOF OF EQUATION (38)

The appendix derives the relation underlying maximal cost leakage by optimizing likelihood ratios over output reference measures. The argument handles zero channel probabilities and identifies an attaining choice.

  • The proof rewrites the maximal-cost expression as an optimization involving an arbitrary output distribution QY and channel likelihood terms.
  • If every output has zero probability under some supported input, the relevant divergence and maximal cost leakage are both infinite.
  • A suitable choice of QY achieves the lower bound, completing the finite-alphabet characterization.
  • The appendix records equality cases for the resulting inequalities, including independence and deterministic relationships.
  • Convexity in the channel follows because the pointwise minimum channel probability is concave and negative logarithm is decreasing and convex.
  • The corresponding maximal realizable-cost relation is bounded by D∞(PX × PY || PXY), with the reverse direction obtained using the same distortion choice.
Loading 1807.07878v1…