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

Logical Methods in Computer Science

On the Compositionality of Quantitative Information Flow

Yusuke Kawamoto, Konstantinos Chatzikokolakis A, Catuscia Palamidessi A

Published Jan 1, 2017• 4 citations
Publisher

Abstract

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.

DOI
10.23638/lmcs-13(3:11)2017

Related papers

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.

International Conference on the Quantitative Evaluation of Systems (QEST)•Sep 1, 2011•65 citations

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•259 citations

Scalable Information Flow Analysis of Secure Three-Party Affine Computations

Patrick Ah-Fat, Michael Huth

Elaborate protocols in Secure Multi-party Computation enable several participants to compute a public function of their own private inputs while ensuring that no undesired information leaks about the private inputs, and without resorting to any trusted third party. However, the public output of the computation inevitably leaks some information about the private inputs. Recent works have introduced a framework and proposed some techniques for quantifying such information flow. Yet, owing to their complexity, those methods do not scale to practical situations that may involve large input spaces. The main contribution of the work reported here is to formally investigate the information flow captured by the min-entropy in the particular case of secure three-party computations of affine functions in order to make its quantification scalable to realistic scenarios. To this end, we mathematically derive an explicit formula for this entropy under uniform prior beliefs about the inputs. We show that this closed-form expression can be computed in time constant in the inputs sizes and logarithmic in the coefficients of the affine function. Finally, we formulate some theoretical bounds for this privacy leak in the presence of non-uniform prior beliefs.

arXiv:1901.00798•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•2 citations

Accessible Quantum Correlations Under Complexity Constraints

Álvaro Yángüez, Noam Avidan, Jan Kochanowski +1 more

Quantum systems may contain underlying correlations which are inaccessible to computationally bounded observers. We capture this distinction through a framework that analyses bipartite states only using efficiently implementable quantum channels. This leads to a complexity-constrained max-divergence and a corresponding computational min-entropy. The latter quantity recovers the standard operational meaning of the conditional min-entropy: in the fully quantum case, it quantifies the largest overlap with a maximally entangled state attainable via efficient operations on the conditional subsystem. For classical-quantum states, it further reduces to the optimal guessing probability of a computationally bounded observer with access to side information. Lastly, in the absence of side information, the computational min-entropy simplifies to a computational notion of the operator norm. We then establish strong separations between the information-theoretic and complexity-constrained notions of min-entropy. For pure states, there exist highly entangled families of states with extremal min-entropy whose efficiently accessible entanglement in terms of computational min-entropy is exponentially suppressed. For mixed states, the separation is even sharper: the information-theoretic conditional min-entropy can be highly negative while the complexity-constrained quantity remains nearly maximal. Under the cryptographic Learning with Errors hardness assumption, we construct efficiently preparable states exhibiting both separations, even when their preparation circuits are fully known. Overall, our results demonstrate that computational constraints can fundamentally limit the quantum correlations that are observable in practice.

quant-pharXiv:2604.15540•Apr 20, 2026•1 citation

QQIF: Quantum Quantitative Information Flow (invited paper)

Arthur Américo, Pasquale Malacaria

The field of Quantitative Information Flow (QIF) is concerned with quantifying information leakage in systems. This work generalises the QIF framework to the quantum setting, having as foundations the recently developed g-leakage framework. Next, some recent results of the field of quantum statistical decision are presented and translated in terms of the "quantum" g-leakage framework, including a recently developed quantum generalisation of the Coriasceous Theorem, an important result for QIF.

IEEE European Symposium on Security and Privacy Workshops (EuroS&PW)•Sep 1, 2020•2 citations

Entropic Resilience: Information-Theoretic Limits of Post-Quantum Cryptography

PAULO SÉRGIO DE ANDRADE

The looming threat of large-scale quantum computers necessitates a paradigm shift in cryptographic design, giving rise to the field of Post-Quantum Cryptography (PQC). While the computational hardness assumptions underpinning PQC schemes are well-studied, their fundamental security limits from an information-theoretic perspective remain an area requiring deeper exploration. This paper introduces and systematically investigates the concept of "entropic resilience," defined as the inherent ability of a cryptographic system to maintain its security guarantees even under an adversary possessing unbounded computational power, provided only limited information about the secret components is revealed. We present a comprehensive framework for analyzing the information-theoretic security of prominent PQC families, including lattice-based, code-based, and hash-based schemes. Our methodology leverages various entropy measures, such as min-entropy and conditional entropy, to quantify the information leakage and the irreducible uncertainty preserved in cryptographic secrets. We derive theoretical bounds on the information-theoretic security for representative PQC constructions and discuss the implications of these bounds for parameter selection, key generation, and resistance against information-theoretic attacks and side channels. The findings highlight critical trade-offs between entropy requirements, efficiency, and the achievable level of provable security in a post-quantum world. Ultimately, this work provides a foundational understanding of the ultimate security boundaries for PQC, guiding the design of more robust and provably secure schemes against both classical and quantum adversaries.

•Nov 23, 2025•0 citations
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.
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.
Elaborate protocols in Secure Multi-party Computation enable several participants to compute a public function of their own private inputs while ensuring that no undesired information leaks about the private inputs, and without resorting to any trusted third party. However, the public output of the computation inevitably leaks some information about the private inputs. Recent works have introduced a framework and proposed some techniques for quantifying such information flow. Yet, owing to their complexity, those methods do not scale to practical situations that may involve large input spaces. The main contribution of the work reported here is to formally investigate the information flow captured by the min-entropy in the particular case of secure three-party computations of affine functions in order to make its quantification scalable to realistic scenarios. To this end, we mathematically derive an explicit formula for this entropy under uniform prior beliefs about the inputs. We show that this closed-form expression can be computed in time constant in the inputs sizes and logarithmic in the coefficients of the affine function. Finally, we formulate some theoretical bounds for this privacy leak in the presence of non-uniform prior beliefs.
Quantum systems may contain underlying correlations which are inaccessible to computationally bounded observers. We capture this distinction through a framework that analyses bipartite states only using efficiently implementable quantum channels. This leads to a complexity-constrained max-divergence and a corresponding computational min-entropy. The latter quantity recovers the standard operational meaning of the conditional min-entropy: in the fully quantum case, it quantifies the largest overlap with a maximally entangled state attainable via efficient operations on the conditional subsystem. For classical-quantum states, it further reduces to the optimal guessing probability of a computationally bounded observer with access to side information. Lastly, in the absence of side information, the computational min-entropy simplifies to a computational notion of the operator norm. We then establish strong separations between the information-theoretic and complexity-constrained notions of min-entropy. For pure states, there exist highly entangled families of states with extremal min-entropy whose efficiently accessible entanglement in terms of computational min-entropy is exponentially suppressed. For mixed states, the separation is even sharper: the information-theoretic conditional min-entropy can be highly negative while the complexity-constrained quantity remains nearly maximal. Under the cryptographic Learning with Errors hardness assumption, we construct efficiently preparable states exhibiting both separations, even when their preparation circuits are fully known. Overall, our results demonstrate that computational constraints can fundamentally limit the quantum correlations that are observable in practice.
The field of Quantitative Information Flow (QIF) is concerned with quantifying information leakage in systems. This work generalises the QIF framework to the quantum setting, having as foundations the recently developed g-leakage framework. Next, some recent results of the field of quantum statistical decision are presented and translated in terms of the "quantum" g-leakage framework, including a recently developed quantum generalisation of the Coriasceous Theorem, an important result for QIF.
The looming threat of large-scale quantum computers necessitates a paradigm shift in cryptographic design, giving rise to the field of Post-Quantum Cryptography (PQC). While the computational hardness assumptions underpinning PQC schemes are well-studied, their fundamental security limits from an information-theoretic perspective remain an area requiring deeper exploration. This paper introduces and systematically investigates the concept of "entropic resilience," defined as the inherent ability of a cryptographic system to maintain its security guarantees even under an adversary possessing unbounded computational power, provided only limited information about the secret components is revealed. We present a comprehensive framework for analyzing the information-theoretic security of prominent PQC families, including lattice-based, code-based, and hash-based schemes. Our methodology leverages various entropy measures, such as min-entropy and conditional entropy, to quantify the information leakage and the irreducible uncertainty preserved in cryptographic secrets. We derive theoretical bounds on the information-theoretic security for representative PQC constructions and discuss the implications of these bounds for parameter selection, key generation, and resistance against information-theoretic attacks and side channels. The findings highlight critical trade-offs between entropy requirements, efficiency, and the achievable level of provable security in a post-quantum world. Ultimately, this work provides a foundational understanding of the ultimate security boundaries for PQC, guiding the design of more robust and provably secure schemes against both classical and quantum adversaries.