The Experts below are selected from a list of 324 Experts worldwide ranked by ideXlab platform
Renato Renner - One of the best experts on this subject based on the ideXlab platform.
-
Chain Rule for the quantum relative entropy
Physical Review Letters, 2020Co-Authors: Kun Fang, Omar Fawzi, Renato Renner, David SutterAbstract:The Chain Rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a Chain Rule inequality for the quantum relative entropy. The new Chain Rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to nonadaptive strategies.
-
A Chain Rule for the quantum relative entropy
arXiv: Quantum Physics, 2019Co-Authors: Kun Fang, Omar Fawzi, Renato Renner, David SutterAbstract:The Chain Rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a similar Chain Rule inequality for the quantum relative entropy in terms of channel relative entropies. The new Chain Rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to non-adaptive strategies. In addition, we give examples of quantum channels showing that the channel relative entropy is not additive under the tensor product.
-
Chain Rules for Smooth Min- and Max-Entropies
IEEE Transactions on Information Theory, 2013Co-Authors: Alexander Vitanov, Frédéric Dupuis, Marco Tomamichel, Renato RennerAbstract:The Chain Rule for the Shannon and von Neumann entropy, which relates the total entropy of a system to the entropies of its parts, is of central importance to information theory. Here, we consider the Chain Rule for the more general smooth min- and max-entropies, used in one-shot information theory. For these entropy measures, the Chain Rule no longer holds as an equality. However, the standard Chain Rule for the von Neumann entropy is retrieved asymptotically when evaluating the smooth entropies for many identical and independently distributed states.
David Sutter - One of the best experts on this subject based on the ideXlab platform.
-
Chain Rule for the quantum relative entropy
Physical Review Letters, 2020Co-Authors: Kun Fang, Omar Fawzi, Renato Renner, David SutterAbstract:The Chain Rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a Chain Rule inequality for the quantum relative entropy. The new Chain Rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to nonadaptive strategies.
-
A Chain Rule for the quantum relative entropy
arXiv: Quantum Physics, 2019Co-Authors: Kun Fang, Omar Fawzi, Renato Renner, David SutterAbstract:The Chain Rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a similar Chain Rule inequality for the quantum relative entropy in terms of channel relative entropies. The new Chain Rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to non-adaptive strategies. In addition, we give examples of quantum channels showing that the channel relative entropy is not additive under the tensor product.
Kun Fang - One of the best experts on this subject based on the ideXlab platform.
-
Chain Rule for the quantum relative entropy
Physical Review Letters, 2020Co-Authors: Kun Fang, Omar Fawzi, Renato Renner, David SutterAbstract:The Chain Rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a Chain Rule inequality for the quantum relative entropy. The new Chain Rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to nonadaptive strategies.
-
A Chain Rule for the quantum relative entropy
arXiv: Quantum Physics, 2019Co-Authors: Kun Fang, Omar Fawzi, Renato Renner, David SutterAbstract:The Chain Rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a similar Chain Rule inequality for the quantum relative entropy in terms of channel relative entropies. The new Chain Rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to non-adaptive strategies. In addition, we give examples of quantum channels showing that the channel relative entropy is not additive under the tensor product.
Omar Fawzi - One of the best experts on this subject based on the ideXlab platform.
-
Chain Rule for the quantum relative entropy
Physical Review Letters, 2020Co-Authors: Kun Fang, Omar Fawzi, Renato Renner, David SutterAbstract:The Chain Rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a Chain Rule inequality for the quantum relative entropy. The new Chain Rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to nonadaptive strategies.
-
A Chain Rule for the quantum relative entropy
arXiv: Quantum Physics, 2019Co-Authors: Kun Fang, Omar Fawzi, Renato Renner, David SutterAbstract:The Chain Rule for the classical relative entropy ensures that the relative entropy between probability distributions on multipartite systems can be decomposed into a sum of relative entropies of suitably chosen conditional distributions on the individual systems. Here, we prove a similar Chain Rule inequality for the quantum relative entropy in terms of channel relative entropies. The new Chain Rule allows us to solve an open problem in the context of asymptotic quantum channel discrimination: surprisingly, adaptive protocols cannot improve the error rate for asymmetric channel discrimination compared to non-adaptive strategies. In addition, we give examples of quantum channels showing that the channel relative entropy is not additive under the tensor product.
Krzysztof Pietrzak - One of the best experts on this subject based on the ideXlab platform.
-
A Counterexample to the Chain Rule for Conditional
2020Co-Authors: Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia, Daniel WichsAbstract:Most entropy notions H(:) like Shannon or min-entropy satisfy a Chain Rule stating that for random variables X;Z and A we have H(XjZ;A) H(XjZ) jAj. That is, by conditioning on A the entropy of X can decrease by at most the bitlength jAj of A. Such Chain Rules are known to hold for some computational entropy notions like Yao’s and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the Chain Rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption and memory delegation. These applications rely on restricted special cases of the Chain Rule. Whether the Chain Rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: We construct joint distributions (X;Z;A), where A is a distribution over a single bit, such that the HILL entropy H HILL (XjZ) is large but H HILL (XjZ;A) is basically zero. Our counterexample just makes the minimal assumption that NP * P=poly. Under the stronger assumption that injective one-way function exist, we can make all the distributions eciently samplable. Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the Chain Rule making only a single invocation to the underlying object.
-
a counterexample to the Chain Rule for conditional hill entropy
Computational Complexity, 2016Co-Authors: Stephan Krenn, Krzysztof Pietrzak, Akshay Wadia, Daniel WichsAbstract:Most entropy notions $${H(.)}$$H(.) like Shannon or min-entropy satisfy a Chain Rule stating that for random variables $${X,Z,}$$X,Z, and $${A}$$A we have $${H(X|Z,A)\ge H(X|Z)-|A|}$$H(X|Z,A)źH(X|Z)-|A|. That is, by conditioning on $${A}$$A the entropy of $${X}$$X can decrease by at most the bitlength $${|A|}$$|A| of $${A}$$A. Such Chain Rules are known to hold for some computational entropy notions like Yao's and unpredictability-entropy. For HILL entropy, the computational analogue of min-entropy, the Chain Rule is of special interest and has found many applications, including leakage-resilient cryptography, deterministic encryption, and memory delegation. These applications rely on restricted special cases of the Chain Rule. Whether the Chain Rule for conditional HILL entropy holds in general was an open problem for which we give a strong negative answer: we construct joint distributions $${(X,Z,A)}$$(X,Z,A), where $${A}$$A is a distribution over a single bit, such that the HILL entropy HHILL$${(X|Z)}$$(X|Z) is large but HHILL$${(X|Z,A)}$$(X|Z,A) is basically zero. Our counterexample just makes the minimal assumption that $${{\mathbf{NP}} \nsubseteq{\mathbf{P/poly}}}$$NPźP/poly. Under the stronger assumption that injective one-way function exist, we can make all the distributions efficiently samplable. Finally, we show that some more sophisticated cryptographic objects like lossy functions can be used to sample a distribution constituting a counterexample to the Chain Rule making only a single invocation to the underlying object.
-
the Chain Rule for hill pseudoentropy revisited
International Conference on Progress in Cryptology, 2015Co-Authors: Krzysztof Pietrzak, Maciej SkorskiAbstract:Computational notions of entropy a.k.a. pseudoentropy have found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The most important tools to argue about pseudoentropy are Chain Rules, which quantify by how much in terms of quantity and quality the pseudoentropy of a given random variable X decreases when conditioned on some other variable Z think for example of X as a secret key and Z as information leaked by a side-channel. In this paper we give a very simple and modular proof of the Chain Rule for HILL pseudoentropy, improving best known parameters. Our version allows for increasing the acceptable length of leakage in applications upi¾?to a constant factor compared to the best previous bounds. As a contribution of independent interest, we provide a comprehensive study of all known versions of the Chain Rule, comparing their worst-case strength and limitations.
-
LATINCRYPT - The Chain Rule for HILL Pseudoentropy, Revisited
Progress in Cryptology -- LATINCRYPT 2015, 2015Co-Authors: Krzysztof Pietrzak, Maciej SkorskiAbstract:Computational notions of entropy a.k.a. pseudoentropy have found many applications, including leakage-resilient cryptography, deterministic encryption or memory delegation. The most important tools to argue about pseudoentropy are Chain Rules, which quantify by how much in terms of quantity and quality the pseudoentropy of a given random variable X decreases when conditioned on some other variable Z think for example of X as a secret key and Z as information leaked by a side-channel. In this paper we give a very simple and modular proof of the Chain Rule for HILL pseudoentropy, improving best known parameters. Our version allows for increasing the acceptable length of leakage in applications upi¾?to a constant factor compared to the best previous bounds. As a contribution of independent interest, we provide a comprehensive study of all known versions of the Chain Rule, comparing their worst-case strength and limitations.
-
a counterexample to the Chain Rule for conditional hill entropy and what deniable encryption has to do with it
Theory of Cryptography Conference, 2013Co-Authors: Stephan Krenn, Krzysztof Pietrzak, Akshay WadiaAbstract:A Chain Rule for an entropy notion H(·) states that the entropy H(X) of a variable X decreases by at most l if conditioned on an l-bit string A, i.e., H(X|A)≥H(X)−l. More generally, it satisfies a Chain Rule for conditional entropy if H(X|Y,A)≥H(X|Y)−l. All natural information theoretic entropy notions we are aware of (like Shannon or min-entropy) satisfy some kind of Chain Rule for conditional entropy. Moreover, many computational entropy notions (like Yao entropy, unpredictability entropy and several variants of HILL entropy) satisfy the Chain Rule for conditional entropy, though here not only the quantity decreases by l, but also the quality of the entropy decreases exponentially in l. However, for the standard notion of conditional HILL entropy (the computational equivalent of min-entropy) the existence of such a Rule was unknown so far. In this paper, we prove that for conditional HILL entropy no meaningful Chain Rule exists, assuming the existence of one-way permutations: there exist distributions X,Y,A, where A is a distribution over a single bit, but HHILL(X|Y)≫ HHILL(X|Y,A), even if we simultaneously allow for a massive degradation in the quality of the entropy. The idea underlying our construction is based on a surprising connection between the Chain Rule for HILL entropy and deniable encryption.