This paper introduces g-leakage, a rich generalization of the min-entropy model of quantitative information flow. In g-leakage, the benefit that an adversary derives from a certain guess about a secret is specified using a gain function g. Gain functions allow a wide variety of operational scenarios to be modeled, including those where the adversary benefits from guessing a value close to the secret, guessing a part of the secret, guessing a property of the secret, or guessing the secret within some number of tries. We prove important properties of g-leakage, including bounds between min-capacity, g-capacity, and Shannon capacity. We also show a deep connection between a strong leakage ordering on two channels, C1and C2, and the possibility of factoring C1into C2C3, for some C3. Based on this connection, we propose a generalization of the Lattice of Information from deterministic to probabilistic channels.This paper introduces g-leakage, a rich generalization of the min-entropy model of quantitative information flow. In g-leakage, the benefit that an adversary derives from a certain guess about a secret is specified using a gain function g. Gain functions allow a wide variety of operational scenarios to be modeled, including those where the adversary benefits from guessing a value close to the secret, guessing a part of the secret, guessing a property of the secret, or guessing the secret within some number of tries. We prove important properties of g-leakage, including bounds between min-capacity, g-capacity, and Shannon capacity. We also show a deep connection between a strong leakage ordering on two channels, C1and C2, and the possibility of factoring C1into C2C3, for some C3. Based on this connection, we propose a generalization of the Lattice of Information from deterministic to probabilistic channels.

IEEE Computer Security Foundations Workshop (CSFW)Jun 1, 2012251 citations

Entropy analysis of systems exhibiting negative probabilities

J. A. Tenreiro Machado

Communications in Nonlinear Science and Numerical SimulationDec 1, 20159 citations

Quantifying Information Flow Using Min-Entropy

Geoffrey Smith

Quantitative theories of information flow are of growing interest, due to the fundamental importance of protecting confidential information from improper disclosure, together with the unavoidability of "small" leaks in practical systems. But while it is tempting to measure leakage using classic information-theoretic concepts like Shannon entropy and mutual information, these turn out not to provide very satisfactory security guarantees. As a result, several researchers have developed an alternative theory based on Renyi's min-entropy. In this theory, uncertainty is measured in terms of a random variable's vulnerability to being guessed in one try by an adversary, note that this is the complement of the Bayes Risk. In this paper, we survey the main theory of min-entropy leakage in deterministic and probabilistic systems, including comparisons with mutual information leakage, results on min-capacity, results on channels in cascade, and techniques for calculating min-entropy leakage in systems.Quantitative theories of information flow are of growing interest, due to the fundamental importance of protecting confidential information from improper disclosure, together with the unavoidability of "small" leaks in practical systems. But while it is tempting to measure leakage using classic information-theoretic concepts like Shannon entropy and mutual information, these turn out not to provide very satisfactory security guarantees. As a result, several researchers have developed an alternative theory based on Renyi's min-entropy. In this theory, uncertainty is measured in terms of a random variable's vulnerability to being guessed in one try by an adversary, note that this is the complement of the Bayes Risk. In this paper, we survey the main theory of min-entropy leakage in deterministic and probabilistic systems, including comparisons with mutual information leakage, results on min-capacity, results on channels in cascade, and techniques for calculating min-entropy leakage in systems.

International Conference on the Quantitative Evaluation of Systems (QEST)Sep 1, 201165 citations

Information Theory and Statistical Entropy

Roger Balian

Springer eBooksJan 1, 19912 citations

Min-entropy uncertainty relation for finite-size cryptography

Nelly H. Y. Ng, Mario Berta, Stephanie Wehner

Apart from their foundational significance, entropic uncertainty relations play a central role in proving the security of quantum cryptographic protocols. Of particular interest are therefore relations in terms of the smooth min-entropy for Bennett-Brassard 1984 (BB84) and six-state encodings. The smooth min-entropy ${H}_{\mathrm{min}}^{\ensuremath{\epsilon}}(X/B)$ quantifies the negative logarithm of the probability for an attacker $B$ to guess $X$ , except with a small failure probability $\ensuremath{\epsilon}$. Previously, strong uncertainty relations were obtained which are valid in the limit of large block lengths. Here, we prove an alternative uncertainty relation in terms of the smooth min-entropy that is only marginally less strong but has the crucial property that it can be applied to rather small block lengths. This paves the way for a practical implementation of many cryptographic protocols. As part of our proof we show tight uncertainty relations for a family of R\'enyi entropies that may be of independent interest.Apart from their foundational significance, entropic uncertainty relations play a central role in proving the security of quantum cryptographic protocols. Of particular interest are therefore relations in terms of the smooth min-entropy for Bennett-Brassard 1984 (BB84) and six-state encodings. The smooth min-entropy ${H}_{\mathrm{min}}^{\ensuremath{\epsilon}}(X/B)$ quantifies the negative logarithm of the probability for an attacker $B$ to guess $X$, except with a small failure probability $\ensuremath{\epsilon}$. Previously, strong uncertainty relations were obtained which are valid in the limit of large block lengths. Here, we prove an alternative uncertainty relation in terms of the smooth min-entropy that is only marginally less strong but has the crucial property that it can be applied to rather small block lengths. This paves the way for a practical implementation of many cryptographic protocols. As part of our proof we show tight uncertainty relations for a family of R\'enyi entropies that may be of independent interest.

arXiv:1205.0842Physical Review AOct 15, 201258 citations

Optimal min-entropy uncertainty relation

Alexandra Musat, Andrei Tănăsescu, Pantelimon George Popescu

Physical Review AJan 26, 20260 citations

B

to guess

X

, except with a small failure probability $\ensuremath{\epsilon}$. Previously, strong uncertainty relations were obtained which are valid in the limit of large block lengths. Here, we prove an alternative uncertainty relation in terms of the smooth min-entropy that is only marginally less strong but has the crucial property that it can be applied to rather small block lengths. This paves the way for a practical implementation of many cryptographic protocols. As part of our proof we show tight uncertainty relations for a family of R\'enyi entropies that may be of independent interest.