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:1011.1612 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

The locking-decoding frontier for generic dynamics

Frédéric Dupuis, Jan Florjanczyk, Patrick M. Hayden, Debbie Leung

Published Sep 18, 2013• 44 citations
arXivHTMLPDF

Abstract

It is known that the maximum classical mutual information, which can be achieved between measurements on pairs of quantum systems, can drastically underestimate the quantum mutual information between them. In this article, we quantify this distinction between classical and quantum information by demonstrating that after removing a logarithmic-sized quantum system from one half of a pair of perfectly correlated bitstrings, even the most sensitive pair of measurements might yield only outcomes essentially independent of each other. This effect is a form of information locking but the definition we use is strictly stronger than those used previously. Moreover, we find that this property is generic, in the sense that it occurs when removing a random subsystem. As such, the effect might be relevant to statistical mechanics or black hole physics. While previous works had always assumed a uniform message, we assume only a min-entropy bound and also explore the effect of entanglement. We find that classical information is strongly locked almost until it can be completely decoded. Finally, we exhibit a quantum key distribution protocol that is 'secure' in the sense of accessible information but in which leakage of even a logarithmic number of bits compromises the secrecy of all others.

DOI
10.1098/rspa.2013.0289

Related papers

The decoupling approach to quantum information theory

Frédéric Dupuis

Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.

arXiv:1004.1641•Apr 9, 2010•133 citations

Secrecy extraction from no-signaling correlations

Valerio Scarani, Nicolas Gisin, Nicolas Brunner +3 more

Quantum cryptography shows that one can guarantee the secrecy of correlation on the sole basis of the laws of physics, that is, without limiting the computational power of the eavesdropper. The usual security proofs suppose that the authorized partners, Alice and Bob, have a perfect knowledge and control of their quantum systems and devices; for instance, they must be sure that the logical bits have been encoded in true qubits and not in higher dimensional systems. In this paper, we present an approach that circumvents this strong assumption. We define protocols, both for the case of bits and for generic $d$-dimensional outcomes, in which the security is guaranteed by the very structure of the Alice-Bob correlations, under the no-signaling condition. The idea is that if the correlations cannot be produced by shared randomness, then Eve has poor knowledge of Alice's and Bob's symbols. The present study assumes on the one hand that the eavesdropper Eve performs only individual attacks (this is a limitation to be removed in further work), and on the other hand that Eve can distribute any correlation compatible with the no-signaling condition (in this sense her power is greater than what quantum physics allows). Under these assumptions, we prove that the protocols defined here allow extracting secrecy from noisy correlations, when these correlations violate a Bell-type inequality by a sufficiently large amount. The region in which secrecy extraction is possible extends within the region of correlations achievable by measurements on entangled quantum states.

arXiv:quant-ph/0606197•Physical Review A•Oct 30, 2006•123 citations

Informationally restricted quantum correlations

Armin Tavakoli, Emmanuel Zambrini Cruzeiro, Jonatan Bohr Brask +2 more

Quantum communication leads to strong correlations, that can outperform classical ones. Complementary to previous works in this area, we investigate correlations in prepare-and-measure scenarios assuming a bound on the information content of the quantum communication, rather than on its Hilbert-space dimension. Specifically, we explore the extent of classical and quantum correlations given an upper bound on the one-shot accessible information. We provide a characterisation of the set of classical correlations and show that quantum correlations are stronger than classical ones. We also show that limiting information rather than dimension leads to stronger quantum correlations. Moreover, we present device-independent tests for placing lower bounds on the information given observed correlations. Finally, we show that quantum communication carrying log⁡d bits of information is at least as strong a resource as d -dimensional classical communication assisted by pre-shared entanglement.

arXiv:1909.05656•Quantum•Sep 24, 2020•35 citations

From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking

Omar Fawzi, Patrick M. Hayden, Pranab Sen

Quantum uncertainty relations are at the heart of many quantum cryptographic protocols performing classically impossible tasks. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message (the message is "locked"). Furthermore, knowing the key, it is possible to recover (or "unlock") the message.

ACM Symposium on Theory of Computing (STOC)•Jun 6, 2011•14 citations

From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking

Omar Fawzi, Patrick M. Hayden, Pranab Sen

The existence of quantum uncertainty relations is the essential reason that some classically unrealizable cryptographic primitives become realizable when quantum communication is allowed. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking [DiVincenzo et al. 2004]. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n -bit message is encoded in a quantum system using a classical key of size much smaller than n . Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be “locked”. Furthermore, knowing the key, it is possible to recover, that is “unlock”, the message. In this article, we make the following contributions by exploiting a connection between uncertainty relations and low-distortion embeddings of Euclidean spaces into slightly larger spaces endowed with the ℓ 1 norm. We introduce the notion of a metric uncertainty relation and connect it to low-distortion embeddings of ℓ 2 into ℓ 1 . A metric uncertainty relation also implies an entropic uncertainty relation. We prove that random bases satisfy uncertainty relations with a stronger definition and better parameters than previously known. Our proof is also considerably simpler than earlier proofs. We then apply this result to show the existence of locking schemes with key size independent of the message length. Moreover, we give efficient constructions of bases satisfying metric uncertainty relations. The bases defining these metric uncertainty relations are computable by quantum circuits of almost linear size. This leads to the first explicit construction of a strong information locking scheme. These constructions are obtained by adapting an explicit norm embedding due to Indyk [2007] and an extractor construction of Guruswami et al. [2009]. We apply our metric uncertainty relations to exhibit communication protocols that perform equality testing of n -qubit states. We prove that this task can be performed by a single message protocol using O (log 2 n ) qubits and n bits of communication, where the computation of the sender is efficient.

arXiv:1010.3007•Journal of the ACM•Nov 1, 2013•52 citations

Small Accessible Quantum Information Does Not Imply Security

Robert König, Renato Renner, Andor Bariska +1 more

The security of quantum key distribution is typically defined in terms of the mutual information between the distributed key S and the outcome of an optimal measurement applied to the adversary's system. We show that even if this so-called accessible information is small, the key S might not be secure enough to be used in applications such as one-time pad encryption. This flaw is due to a locking property of the accessible information: one additional (physical) bit of information can increase the accessible information by more than one bit.

arXiv:quant-ph/0512021•Physical Review Letters•Apr 3, 2007•144 citations
It is known that the maximum classical mutual information, which can be achieved between measurements on pairs of quantum systems, can drastically underestimate the quantum mutual information between them. In this article, we quantify this distinction between classical and quantum information by demonstrating that after removing a logarithmic-sized quantum system from one half of a pair of perfectly correlated bitstrings, even the most sensitive pair of measurements might yield only outcomes essentially independent of each other. This effect is a form of information locking but the definition we use is strictly stronger than those used previously. Moreover, we find that this property is generic, in the sense that it occurs when removing a random subsystem. As such, the effect might be relevant to statistical mechanics or black hole physics. While previous works had always assumed a uniform message, we assume only a min-entropy bound and also explore the effect of entanglement. We find that classical information is strongly locked almost until it can be completely decoded. Finally, we exhibit a quantum key distribution protocol that is 'secure' in the sense of accessible information but in which leakage of even a logarithmic number of bits compromises the secrecy of all others.
Quantum information theory studies the fundamental limits that physical laws impose on information processing tasks such as data compression and data transmission on noisy channels. This thesis presents general techniques that allow one to solve many fundamental problems of quantum information theory in a unified framework. The central theorem of this thesis proves the existence of a protocol that transmits quantum data that is partially known to the receiver through a single use of an arbitrary noisy quantum channel. In addition to the intrinsic interest of this problem, this theorem has as immediate corollaries several central theorems of quantum information theory. The following chapters use this theorem to prove the existence of new protocols for two other types of quantum channels, namely quantum broadcast channels and quantum channels with side information at the transmitter. These protocols also involve sending quantum information partially known by the receiver with a single use of the channel, and have as corollaries entanglement-assisted and unassisted asymptotic coding theorems. The entanglement-assisted asymptotic versions can, in both cases, be considered as quantum versions of the best coding theorems known for the classical versions of these problems. The last chapter deals with a purely quantum phenomenon called locking. We demonstrate that it is possible to encode a classical message into a quantum state such that, by removing a subsystem of logarithmic size with respect to its total size, no measurement can have significant correlations with the message. The message is therefore "locked" by a logarithmic-size key. This thesis presents the first locking protocol for which the success criterion is that the trace distance between the joint distribution of the message and the measurement result and the product of their marginals be sufficiently small.
Quantum cryptography shows that one can guarantee the secrecy of correlation on the sole basis of the laws of physics, that is, without limiting the computational power of the eavesdropper. The usual security proofs suppose that the authorized partners, Alice and Bob, have a perfect knowledge and control of their quantum systems and devices; for instance, they must be sure that the logical bits have been encoded in true qubits and not in higher dimensional systems. In this paper, we present an approach that circumvents this strong assumption. We define protocols, both for the case of bits and for generic ddd-dimensional outcomes, in which the security is guaranteed by the very structure of the Alice-Bob correlations, under the no-signaling condition. The idea is that if the correlations cannot be produced by shared randomness, then Eve has poor knowledge of Alice's and Bob's symbols. The present study assumes on the one hand that the eavesdropper Eve performs only individual attacks (this is a limitation to be removed in further work), and on the other hand that Eve can distribute any correlation compatible with the no-signaling condition (in this sense her power is greater than what quantum physics allows). Under these assumptions, we prove that the protocols defined here allow extracting secrecy from noisy correlations, when these correlations violate a Bell-type inequality by a sufficiently large amount. The region in which secrecy extraction is possible extends within the region of correlations achievable by measurements on entangled quantum states.
Quantum communication leads to strong correlations, that can outperform classical ones. Complementary to previous works in this area, we investigate correlations in prepare-and-measure scenarios assuming a bound on the information content of the quantum communication, rather than on its Hilbert-space dimension. Specifically, we explore the extent of classical and quantum correlations given an upper bound on the one-shot accessible information. We provide a characterisation of the set of classical correlations and show that quantum correlations are stronger than classical ones. We also show that limiting information rather than dimension leads to stronger quantum correlations. Moreover, we present device-independent tests for placing lower bounds on the information given observed correlations. Finally, we show that quantum communication carrying log⁡d bits of information is at least as strong a resource as d -dimensional classical communication assisted by pre-shared entanglement.
Quantum uncertainty relations are at the heart of many quantum cryptographic protocols performing classically impossible tasks. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n-bit message is encoded in a quantum system using a classical key of size much smaller than n. Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message (the message is "locked"). Furthermore, knowing the key, it is possible to recover (or "unlock") the message.
The existence of quantum uncertainty relations is the essential reason that some classically unrealizable cryptographic primitives become realizable when quantum communication is allowed. One operational manifestation of these uncertainty relations is a purely quantum effect referred to as information locking [DiVincenzo et al. 2004]. A locking scheme can be viewed as a cryptographic protocol in which a uniformly random n -bit message is encoded in a quantum system using a classical key of size much smaller than n . Without the key, no measurement of this quantum state can extract more than a negligible amount of information about the message, in which case the message is said to be “locked”. Furthermore, knowing the key, it is possible to recover, that is “unlock”, the message. In this article, we make the following contributions by exploiting a connection between uncertainty relations and low-distortion embeddings of Euclidean spaces into slightly larger spaces endowed with the ℓ 1 norm. We introduce the notion of a metric uncertainty relation and connect it to low-distortion embeddings of ℓ 2 into ℓ 1 . A metric uncertainty relation also implies an entropic uncertainty relation. We prove that random bases satisfy uncertainty relations with a stronger definition and better parameters than previously known. Our proof is also considerably simpler than earlier proofs. We then apply this result to show the existence of locking schemes with key size independent of the message length. Moreover, we give efficient constructions of bases satisfying metric uncertainty relations. The bases defining these metric uncertainty relations are computable by quantum circuits of almost linear size. This leads to the first explicit construction of a strong information locking scheme. These constructions are obtained by adapting an explicit norm embedding due to Indyk [2007] and an extractor construction of Guruswami et al. [2009]. We apply our metric uncertainty relations to exhibit communication protocols that perform equality testing of n -qubit states. We prove that this task can be performed by a single message protocol using O (log 2 n ) qubits and n bits of communication, where the computation of the sender is efficient.
The security of quantum key distribution is typically defined in terms of the mutual information between the distributed key S and the outcome of an optimal measurement applied to the adversary's system. We show that even if this so-called accessible information is small, the key S might not be secure enough to be used in applications such as one-time pad encryption. This flaw is due to a locking property of the accessible information: one additional (physical) bit of information can increase the accessible information by more than one bit.