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

arXiv:1003.0703 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Duality of privacy amplification against quantum adversaries and data compression with quantum side information

Joseph M. Renes

Published Dec 15, 2010• 36 citations
arXivHTMLPDF

Abstract

Information processing protocols are typically built out of simpler parts, called primitives, and two of the most important such primitives are privacy amplification (PA) and data compression. The former extracts the truly secret part of some classical data, while the latter squeezes it into the smallest possible form. We show these tasks are dual in the setting of quantum information processing. Specifically, the tasks of PA of classical information against quantum adversaries and classical data compression with quantum side information are dual in the sense that the ability to perform one implies the ability to perform the other. The duality arises because the two protocols are connected by complementarity and the uncertainty principle in the quantum setting. Applications include a new uncertainty principle formulated in terms of smooth min- and max-entropies, which are useful in the study of one-shot protocols, as well as new conditions for approximate quantum error correction.

DOI
10.1098/rspa.2010.0445

Related papers

Equivalence of Three Classical Algorithms With Quantum Side Information: Privacy Amplification, Error Correction, and Data Compression

Toyohiro Tsurumaru

Privacy amplification (PA) is an indispensable component in classical and quantum cryptography. Error correction (EC) and data compression (DC) algorithms are also indispensable in classical and quantum information theory. We here study these three algorithms (PA, EC, and DC) in the presence of quantum side information, and show that they all become equivalent in the one-shot scenario. As an application of this equivalence, we take previously known security bounds of PA, and translate them into coding theorems for EC and DC which have not been obtained previously. Further, we apply these results to simplify and improve our previous result that the two prevalent approaches to the security proof of quantum key distribution (QKD) are equivalent. We also propose a new method to simplify the security proof of QKD.

arXiv:2009.08823•IEEE Transactions on Information Theory•Nov 8, 2021•8 citations

Noisy Channel Coding via Privacy Amplification and Information Reconciliation

Joseph M. Renes, Renato Renner

We show that optimal protocols for noisy channel coding of public or private information over either classical or quantum channels can be directly constructed from two more primitive information-theoretic protocols: privacy amplification and information reconciliation, also known as data compression with side information. We do this in the one-shot scenario of structureless resources, and formulate our results in terms of the smooth min- and max-entropy. In the context of classical information theory, this shows that essentially all two-terminal protocols can be reduced to these two primitives, which are in turn governed by the smooth min- and max-entropies, respectively. In the context of quantum information theory, the recently-established duality of these two protocols means essentially all two-terminal protocols can be constructed using just a single primitive. As an illustration, we show how optimal noisy channel coding protocols can be constructed solely from privacy amplification.

arXiv:1012.4814•IEEE Transactions on Information Theory•Aug 3, 2011•107 citations

On Privacy Amplification, Lossy Compression, and Their Duality to Channel Coding

Joseph M. Renes

We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. The converse significantly improves on previous bounds based on smooth min-entropy by Watanabe and Hayashi [7] and turns out to be equivalent to a recent formulation in terms of the Eγ divergence by Yang et al. [9]. In the latter, we show that the protocols for privacy amplification based on linear codes can be easily repurposed for channel simulation. Combined with the known relations between channel simulation and lossy source coding, this implies that the privacy amplification can be understood as a basic primitive for both channel simulation and lossy compression. Applied to symmetric channels or lossy compression settings, our construction leads to protocols of the optimal rate in the asymptotic i.i.d. limit. Finally, appealing to the notion of channel duality recently detailed by us in [15], we show that the linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [16] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.

arXiv:1708.05685•IEEE Transactions on Information Theory•Aug 13, 2018•11 citations

Privacy Amplification, Lossy Compression, and their Duality to Channel Coding

Joseph M. Renes

We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. This formulation can be easily computed to give finite- blocklength bounds and turns out to be equivalent to smooth min-entropy bounds by Renner and Wolf [Asiacrypt 2005] and Watanabe and Hayashi [ISIT 2013], as well as a bound in terms of the Eγdivergence by Yang, Schaefer, and Poor [arXiv:1706.03866 [cs.IT]]. In the latter, we show that protocols for privacy amplification based on linear codes can be easily repurposed for lossy compression. Our construction leads to protocols of optimal rate in the asymptotic i.i.d. limit for a variety of compression scenarios. Finally, appealing to the notion of channel duality recently detailed by us in [IEEE Trans. Inf. Theory 64,577 (2018)], we show that linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [Allerton 2003; arXiv:cs/0408008] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•0 citations

Equivalence of three quantum algorithms: Privacy amplification, error correction, and data compression.

Toyohiro Tsurumaru

Privacy amplification (PA) is an indispensable component in classical and quantum cryptography. Error correction (EC) and data compression (DC) algorithms are also indispensable in classical and quantum information theory. We here study quantum algorithms of these three types (PA, EC, and DC) in the one-shot scenario, and show that they all become equivalent if modified properly. As an application of this equivalence, we take previously known security bounds of PA, and translate them into coding theorems for EC and DC which have not been obtained previously. Further, we apply these results to simplify and improve our previous result that the two prevalent approaches to the security proof of quantum key distribution (QKD) are equivalent. We also propose a new method to simplify the security proof of QKD.

•Sep 18, 2020•1 citation

Rethinking quantum smooth entropies: Tight one-shot analysis of quantum privacy amplification

Bartosz Regula, Marco Tomamichel

We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.

quant-pharXiv:2603.04493•Mar 6, 2026•0 citations
Information processing protocols are typically built out of simpler parts, called primitives, and two of the most important such primitives are privacy amplification (PA) and data compression. The former extracts the truly secret part of some classical data, while the latter squeezes it into the smallest possible form. We show these tasks are dual in the setting of quantum information processing. Specifically, the tasks of PA of classical information against quantum adversaries and classical data compression with quantum side information are dual in the sense that the ability to perform one implies the ability to perform the other. The duality arises because the two protocols are connected by complementarity and the uncertainty principle in the quantum setting. Applications include a new uncertainty principle formulated in terms of smooth min- and max-entropies, which are useful in the study of one-shot protocols, as well as new conditions for approximate quantum error correction.
Privacy amplification (PA) is an indispensable component in classical and quantum cryptography. Error correction (EC) and data compression (DC) algorithms are also indispensable in classical and quantum information theory. We here study these three algorithms (PA, EC, and DC) in the presence of quantum side information, and show that they all become equivalent in the one-shot scenario. As an application of this equivalence, we take previously known security bounds of PA, and translate them into coding theorems for EC and DC which have not been obtained previously. Further, we apply these results to simplify and improve our previous result that the two prevalent approaches to the security proof of quantum key distribution (QKD) are equivalent. We also propose a new method to simplify the security proof of QKD.
We show that optimal protocols for noisy channel coding of public or private information over either classical or quantum channels can be directly constructed from two more primitive information-theoretic protocols: privacy amplification and information reconciliation, also known as data compression with side information. We do this in the one-shot scenario of structureless resources, and formulate our results in terms of the smooth min- and max-entropy. In the context of classical information theory, this shows that essentially all two-terminal protocols can be reduced to these two primitives, which are in turn governed by the smooth min- and max-entropies, respectively. In the context of quantum information theory, the recently-established duality of these two protocols means essentially all two-terminal protocols can be constructed using just a single primitive. As an illustration, we show how optimal noisy channel coding protocols can be constructed solely from privacy amplification.
We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. The converse significantly improves on previous bounds based on smooth min-entropy by Watanabe and Hayashi [7] and turns out to be equivalent to a recent formulation in terms of the Eγ divergence by Yang et al. [9]. In the latter, we show that the protocols for privacy amplification based on linear codes can be easily repurposed for channel simulation. Combined with the known relations between channel simulation and lossy source coding, this implies that the privacy amplification can be understood as a basic primitive for both channel simulation and lossy compression. Applied to symmetric channels or lossy compression settings, our construction leads to protocols of the optimal rate in the asymptotic i.i.d. limit. Finally, appealing to the notion of channel duality recently detailed by us in [15], we show that the linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [16] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.
We examine the task of privacy amplification from information-theoretic and coding-theoretic points of view. In the former, we give a one-shot characterization of the optimal rate of privacy amplification against classical adversaries in terms of the optimal type-II error in asymmetric hypothesis testing. This formulation can be easily computed to give finite- blocklength bounds and turns out to be equivalent to smooth min-entropy bounds by Renner and Wolf [Asiacrypt 2005] and Watanabe and Hayashi [ISIT 2013], as well as a bound in terms of the Eγdivergence by Yang, Schaefer, and Poor [arXiv:1706.03866 [cs.IT]]. In the latter, we show that protocols for privacy amplification based on linear codes can be easily repurposed for lossy compression. Our construction leads to protocols of optimal rate in the asymptotic i.i.d. limit for a variety of compression scenarios. Finally, appealing to the notion of channel duality recently detailed by us in [IEEE Trans. Inf. Theory 64,577 (2018)], we show that linear error-correcting codes for symmetric channels with quantum output can be transformed into linear lossy source coding schemes for classical variables arising from the dual channel. This explains a “curious duality” in these problems for the (self-dual) erasure channel observed by Martinian and Yedidia [Allerton 2003; arXiv:cs/0408008] and partly anticipates recent results on optimal lossy compression by polar and low-density generator matrix codes.
Privacy amplification (PA) is an indispensable component in classical and quantum cryptography. Error correction (EC) and data compression (DC) algorithms are also indispensable in classical and quantum information theory. We here study quantum algorithms of these three types (PA, EC, and DC) in the one-shot scenario, and show that they all become equivalent if modified properly. As an application of this equivalence, we take previously known security bounds of PA, and translate them into coding theorems for EC and DC which have not been obtained previously. Further, we apply these results to simplify and improve our previous result that the two prevalent approaches to the security proof of quantum key distribution (QKD) are equivalent. We also propose a new method to simplify the security proof of QKD.
We introduce an improved one-shot characterisation of randomness extraction against quantum side information (privacy amplification), strengthening known one-shot bounds and providing a unified derivation of the tightest known asymptotic constraints. Our main tool is a new class of smooth conditional entropies defined by lifting classical smooth divergences through measurements. A key role is played by the measured smooth Rényi relative entropy of order 2, which we show to admit an equivalent variational form: it can be understood as allowing for smoothing over not only states, but also non-positive Hermitian operators. Building on this, we establish a tightened leftover hash lemma, significantly improving over all known smooth min-entropy bounds on extractable randomness and recovering the sharpest classical achievability results. We extend these methods to decoupling, the coherent analogue of privacy amplification, obtaining a corresponding improved one-shot bound. Relaxing our smooth entropy bounds leads to one-shot achievability results in terms of measured Rényi divergences, tightening the bounds of [Dupuis, arXiv:2105.05342] and recovering state-of-the-art asymptotic i.i.d. error exponents. We show an approximate optimality of our results by giving a matching one-shot converse bound up to additive logarithmic terms. This yields an optimal second-order asymptotic expansion of privacy amplification under trace distance, establishing a significantly tighter one-shot achievability result than previously shown in [Shen et al., arXiv:2202.11590] and proving its optimality for all hash functions.