Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on the Quantitative Evaluation of Systems (QEST)

Quantifying Information Flow Using Min-Entropy

Geoffrey Smith

Published Sep 1, 2011• 65 citations
Publisher

Abstract

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.

DOI
10.1109/qest.2011.31

Related papers

Measuring Information Leakage Using Generalized Gain Functions

Mário S. Alvim, Kostas Chatzikokolakis, Catuscia Palamidessi A +1 more

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, 2012•251 citations

On the Compositionality of Quantitative Information Flow

Yusuke Kawamoto, Konstantinos Chatzikokolakis A, Catuscia Palamidessi A

Information flow is the branch of security that studies the leakage of information due to correlation between secrets and observables. Since in general such correlation cannot be avoided completely, it is important to quantify the leakage. The most followed approaches to defining appropriate measures are those based on information theory. In particular, one of the most successful approaches is the recently proposed $g$-leakage framework, which encompasses most of the information-theoretic ones. A problem with $g$-leakage, however, is that it is defined in terms of a minimization problem, which, in the case of large systems, can be computationally rather heavy. In this paper we study the case in which the channel associated to the system can be decomposed into simpler channels, which typically happens when the observables consist of multiple components. Our main contribution is the derivation of bounds on the (multiplicative version of) $g$-leakage of the whole system in terms of the $g$-leakages of its components. We also consider the particular cases of min-entropy leakage and of parallel channels, generalizing and systematizing results from the literature. We demonstrate the effectiveness of our method and evaluate the precision of our bounds using examples.

Logical Methods in Computer Science•Jan 1, 2017•1 citation

Quantum Computational Unpredictability Entropy and Quantum Leakage Resilience

Noam Avidan, Rotem Arnon-Friedman

Computational entropies provide a framework for quantifying uncertainty and randomness under computational constraints. They play a central role in classical cryptography, underpinning the analysis and construction of primitives such as pseudo-random generators, leakage-resilient cryptography, and randomness extractors. However, in the quantum setting, computational analogs of entropy remain largely unexplored. In this work, we initiate the study of quantum computational entropy by definingquantum computational unpredictability entropy, a natural generalization of classical unpredictability entropy to the quantum setting. Our definition builds on the operational interpretation of quantum min-entropy as the optimal guessing probability, while restricting the adversary to efficient guessing strategies. We prove that this entropy satisfies several fundamental properties, including a leakage chain rule that holds even in the presence of unbounded prior quantum side-information. We also show that unpredictability entropy enables pseudo-randomness extraction against quantum adversaries with bounded computational power. Together, these results lay a foundation for developing cryptographic tools that rely on min-entropy in the quantum computational setting.

arXiv:2505.13710•IEEE Transactions on Information Theory•Jan 28, 2026•1 citation

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.

arXiv:1205.0842•Physical Review A•Oct 15, 2012•58 citations

One-Shot Min-Entropy Calculation of Classical-Quantum States and Its Application to Quantum Cryptography

Rong Wang, H. F. Chau

In quantum Shannon theory, various kinds of quantum entropies are used to characterize the capacities of noisy physical systems. Among them, min-entropy and its smooth version attract wide interest especially in the field of quantum cryptography as they can be used to bound the information obtained by an adversary. However, calculating the exact value or nontrivial bounds of min-entropy are extremely difficult because the composite system dimension may scale exponentially with the dimension of its subsystem. Here, we develop a one-shot lower bound calculation technique for the min-entropy of a classical-quantum state that is applicable to both finite and infinite dimensional reduced quantum states. Moreover, we show our technique is of practical interest in at least three situations. First, it offers an alternative tight finite-data analysis for the BB84 quantum key distribution scheme. Second, it gives the best finite-key bound known to date for a variant of device independent quantum key distribution protocol. Third, it provides a security proof for a novel source-independent continuous-variable quantum random number generation protocol. These results show the effectiveness and wide applicability of our approach.

arXiv:2406.15226•Physical Review Letters•Jun 9, 2025•3 citations

Sampling of Min-Entropy Relative to Quantum Knowledge

Robert König, Renato Renner

Let$X_1, \ldots, X_n$be a sequence of$n$classical random variables and consider a sample$X_{s_1}, \ldots, X_{s_r}$of$r \leq n$positions selected at random. Then, except with (exponentially in$r$) small probability, the min-entropy$H_{\min}(X_{s_1} \cdots X_{s_r})$of the sample is not smaller than, roughly, a fraction${r\over n}$of the overall entropy$H_{\min}(X_1 \cdots X_n)$, which is optimal. Here, we show that this statement, originally proved in [S. Vadhan, LNCS 2729, Springer, 2003] for the purely classical case, is still true if the min-entropy$H_{\min}$is measured relative to a quantum system. Because min-entropy quantifies the amount of randomness that can be extracted from a given random variable, our result can be used to prove the soundness of locally computable extractors in a context where side information might be quantum-mechanical. In particular, it implies that key agreement in the bounded-storage model—using a standard sample-and-hash protocol—is fully secure against quantum adversaries, thus solving a long-standing open problem.

arXiv:0712.4291•IEEE Transactions on Information Theory•Jun 21, 2011•65 citations
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.
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.
Information flow is the branch of security that studies the leakage of information due to correlation between secrets and observables. Since in general such correlation cannot be avoided completely, it is important to quantify the leakage. The most followed approaches to defining appropriate measures are those based on information theory. In particular, one of the most successful approaches is the recently proposed ggg-leakage framework, which encompasses most of the information-theoretic ones. A problem with ggg-leakage, however, is that it is defined in terms of a minimization problem, which, in the case of large systems, can be computationally rather heavy. In this paper we study the case in which the channel associated to the system can be decomposed into simpler channels, which typically happens when the observables consist of multiple components. Our main contribution is the derivation of bounds on the (multiplicative version of) ggg-leakage of the whole system in terms of the ggg-leakages of its components. We also consider the particular cases of min-entropy leakage and of parallel channels, generalizing and systematizing results from the literature. We demonstrate the effectiveness of our method and evaluate the precision of our bounds using examples.
Computational entropies provide a framework for quantifying uncertainty and randomness under computational constraints. They play a central role in classical cryptography, underpinning the analysis and construction of primitives such as pseudo-random generators, leakage-resilient cryptography, and randomness extractors. However, in the quantum setting, computational analogs of entropy remain largely unexplored. In this work, we initiate the study of quantum computational entropy by definingquantum computational unpredictability entropy, a natural generalization of classical unpredictability entropy to the quantum setting. Our definition builds on the operational interpretation of quantum min-entropy as the optimal guessing probability, while restricting the adversary to efficient guessing strategies. We prove that this entropy satisfies several fundamental properties, including a leakage chain rule that holds even in the presence of unbounded prior quantum side-information. We also show that unpredictability entropy enables pseudo-randomness extraction against quantum adversaries with bounded computational power. Together, these results lay a foundation for developing cryptographic tools that rely on min-entropy in the quantum computational setting.
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 BBB to guess XXX, 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.
In quantum Shannon theory, various kinds of quantum entropies are used to characterize the capacities of noisy physical systems. Among them, min-entropy and its smooth version attract wide interest especially in the field of quantum cryptography as they can be used to bound the information obtained by an adversary. However, calculating the exact value or nontrivial bounds of min-entropy are extremely difficult because the composite system dimension may scale exponentially with the dimension of its subsystem. Here, we develop a one-shot lower bound calculation technique for the min-entropy of a classical-quantum state that is applicable to both finite and infinite dimensional reduced quantum states. Moreover, we show our technique is of practical interest in at least three situations. First, it offers an alternative tight finite-data analysis for the BB84 quantum key distribution scheme. Second, it gives the best finite-key bound known to date for a variant of device independent quantum key distribution protocol. Third, it provides a security proof for a novel source-independent continuous-variable quantum random number generation protocol. These results show the effectiveness and wide applicability of our approach.
LetX1,…,XnX_1, \ldots, X_nX1​,…,Xn​be a sequence ofnnnclassical random variables and consider a sampleXs1,…,XsrX_{s_1}, \ldots, X_{s_r}Xs1​​,…,Xsr​​ofr≤nr \leq nr≤npositions selected at random. Then, except with (exponentially inrrr) small probability, the min-entropyHmin⁡(Xs1⋯Xsr)H_{\min}(X_{s_1} \cdots X_{s_r})Hmin​(Xs1​​⋯Xsr​​)of the sample is not smaller than, roughly, a fractionrn{r\over n}nr​of the overall entropyHmin⁡(X1⋯Xn)H_{\min}(X_1 \cdots X_n)Hmin​(X1​⋯Xn​), which is optimal. Here, we show that this statement, originally proved in [S. Vadhan, LNCS 2729, Springer, 2003] for the purely classical case, is still true if the min-entropyHmin⁡H_{\min}Hmin​is measured relative to a quantum system. Because min-entropy quantifies the amount of randomness that can be extracted from a given random variable, our result can be used to prove the soundness of locally computable extractors in a context where side information might be quantum-mechanical. In particular, it implies that key agreement in the bounded-storage model—using a standard sample-and-hash protocol—is fully secure against quantum adversaries, thus solving a long-standing open problem.