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:quant-ph/0606197 · Physical Review A

Secrecy extraction from no-signaling correlations

Valerio Scarani, Nicolas Gisin, Nicolas Brunner, Lluís Masanes, Sergi Pino, Antonio Acín

Published Oct 30, 2006• 121 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.74.042339

Related papers

Extracting Correlations

Yuval Ishai, Eyal Kushilevitz Z, Rafail Ostrovsky +1 more

Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.

Annual Symposium on Foundations of Computer Science•Oct 1, 2009•47 citations

Full Security of Quantum Key Distribution From No-Signaling Constraints

Lluís Masanes, Renato Renner, Matthias Christandl +2 more

We analyze a cryptographic protocol for generating a distributed secret key from correlations that violate a Bell inequality by a sufficient amount, and prove its security against eavesdroppers, constrained only by the assumption that any information accessible to them must be compatible with the non-signaling principle. The claim holds with respect to the state-of-the-art security definition used in cryptography, known as universally-composable security. The non-signaling assumption only refers to the statistics of measurement outcomes depending on the choices of measurements; hence security is independent of the internal workings of the devices - they do not even need to follow the laws of quantum theory. This is relevant for practice as a correct and complete modeling of realistic devices is generally impossible. The techniques developed are general and can be applied to other Bell inequality-based protocols. In particular, we provide a scheme for estimating Bell-inequality violations when the samples are not independent and identically distributed.

arXiv:quant-ph/0606049•IEEE Transactions on Information Theory•Jun 30, 2014•60 citations

Quantum cryptography

Jonathan A. Jones, Dieter Jaksch

Cryptographic protocols can be classified by the type of security against eavesdropping which they provide. There exist mathematically secure schemes whose security relies on mathematical proofs (like the Vernam cipher discussed below) or conjectures (like public key RSA encryption) about the complexity of deciphering the message without possessing the correct key. The majority of current secure public Internet connections rely on such schemes. Alternatively, a cryptographic setup may provide a physically secure method for communicating. In these setups the security is provided by the physical laws governing the communication protocol. Here we first discuss a provably secure classical communication protocol and then quantum methods for distributing the necessary keys. The BB84 protocol relies on the impossibility of perfectly distinguishing non-orthogonal quantum states from one copy of the quantum system. The scheme was invented in 1984 and is the first of its kind. In contrast, the Ekert91 protocol makes use of Bell correlations between entangled pairs of photons. These correlations are destroyed when Eve attempts to make a measurement on one of the particles but also when imperfections, such as decoherence processes, affect the scheme. As long as no such “elements of reality” are introduced, and Bell correlations violating local realism can be generated by Alice and Bob, no eavesdropper can be present. One-time pads and the Vernam cipher The Vernam cipher is a cryptographic protocol which allows the encryption and decryption protocol to be publicly known. The security of the protocol relies entirely on the key which is private and not publicly known. Alice and Bob share identical n -bit secret key strings (one-time pad).

Cambridge University Press eBooks•Jul 19, 2012•0 citations

Quantum steganography over noisy channels: Achievability and bounds

Chris Sutherland, Todd A. Brun

Characterizing secret communication over noisy quantum channels is an interesting problem from both a practical and theoretical perspective. Suppose Alice and Bob wish to communicate secret information so that an eavesdropper Eve will not suspect any type of encoded communication between the two. Classical or quantum cryptography will not suffice since it is always clear secret communication is taking place. Therefore Alice and Bob must execute what is known as a quantum steganographic protocol. Assuming Eve only has partial knowledge of the channel connecting Alice and Bob, we show that for the bit-flip and depolarizing channels Alice can use Eve's lack of knowledge of the channel parameter to encode quantum information steganographically. We give an explicit encoding procedure and calculate the rate at which Alice and Bob can communicate secretly. We also show that our encoding is optimal for nondegenerate quantum codes. We calculate the rate at which a secret key must be consumed. Finally, we discuss the possibility of steganographic communication over more general quantum channels and conjecture a general formula for the steganographic rate.

arXiv:1808.03183•Physical Review A•Nov 11, 2019•13 citations

From Bell’s Theorem to Secure Quantum Key Distribution

Antonio Acín, Nicolas Gisin, Lluís Masanes

The first step in any quantum key distribution (QKD) protocol consists of sequences of measurements that produce correlated classical data. We show that these correlation data must violate some Bell inequality in order to contain distillable secrecy, if not they could be produced by quantum measurements performed on a separable state of larger dimension. We introduce a new QKD protocol and prove its security against any individual attack by an adversary only limited by the no-signaling condition.

arXiv:quant-ph/0510094•Physical Review Letters•Sep 20, 2006•709 citations

A method of enciphering quantum states

Hiroo Azuma, Masashi Ban

In this paper, we propose a method of enciphering quantum states of two-state systems (qubits) for sending them in secrecy without entangled qubits shared by two legitimate users (Alice and Bob). This method has the following two properties. First, even if an eavesdropper (Eve) steals qubits, she can extract information from them with only a certain probability at most. Second, Alice and Bob can confirm that the qubits are transmitted between them correctly by measuring a signature. If Eve measures m qubits one by one from n enciphered qubits and sends alternative ones (the intercept/resend attack), the probability that Alice and Bob do not notice Eve's action is equal to (3/4) m or less. Passwords for decryption and the signature are given by classical binary strings and they are disclosed through a public channel. Enciphering classical information by this method is equivalent to the one-time pad method with distributing a classical key (random binary string) by the BB84 protocol. If Eve takes away qubits, Alice and Bob lose the original quantum information. If we apply our method to a state in iteration, Eve's success probability decreases exponentially. We cannot examine security against the case that Eve makes an attack using entanglement. This remains to be solved in the future.

arXiv:quant-ph/0006124•Journal of Physics A Mathematical and General•Mar 26, 2001•5 citations
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.
Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.
We analyze a cryptographic protocol for generating a distributed secret key from correlations that violate a Bell inequality by a sufficient amount, and prove its security against eavesdroppers, constrained only by the assumption that any information accessible to them must be compatible with the non-signaling principle. The claim holds with respect to the state-of-the-art security definition used in cryptography, known as universally-composable security. The non-signaling assumption only refers to the statistics of measurement outcomes depending on the choices of measurements; hence security is independent of the internal workings of the devices - they do not even need to follow the laws of quantum theory. This is relevant for practice as a correct and complete modeling of realistic devices is generally impossible. The techniques developed are general and can be applied to other Bell inequality-based protocols. In particular, we provide a scheme for estimating Bell-inequality violations when the samples are not independent and identically distributed.
Cryptographic protocols can be classified by the type of security against eavesdropping which they provide. There exist mathematically secure schemes whose security relies on mathematical proofs (like the Vernam cipher discussed below) or conjectures (like public key RSA encryption) about the complexity of deciphering the message without possessing the correct key. The majority of current secure public Internet connections rely on such schemes. Alternatively, a cryptographic setup may provide a physically secure method for communicating. In these setups the security is provided by the physical laws governing the communication protocol. Here we first discuss a provably secure classical communication protocol and then quantum methods for distributing the necessary keys. The BB84 protocol relies on the impossibility of perfectly distinguishing non-orthogonal quantum states from one copy of the quantum system. The scheme was invented in 1984 and is the first of its kind. In contrast, the Ekert91 protocol makes use of Bell correlations between entangled pairs of photons. These correlations are destroyed when Eve attempts to make a measurement on one of the particles but also when imperfections, such as decoherence processes, affect the scheme. As long as no such “elements of reality” are introduced, and Bell correlations violating local realism can be generated by Alice and Bob, no eavesdropper can be present. One-time pads and the Vernam cipher The Vernam cipher is a cryptographic protocol which allows the encryption and decryption protocol to be publicly known. The security of the protocol relies entirely on the key which is private and not publicly known. Alice and Bob share identical n -bit secret key strings (one-time pad).
Characterizing secret communication over noisy quantum channels is an interesting problem from both a practical and theoretical perspective. Suppose Alice and Bob wish to communicate secret information so that an eavesdropper Eve will not suspect any type of encoded communication between the two. Classical or quantum cryptography will not suffice since it is always clear secret communication is taking place. Therefore Alice and Bob must execute what is known as a quantum steganographic protocol. Assuming Eve only has partial knowledge of the channel connecting Alice and Bob, we show that for the bit-flip and depolarizing channels Alice can use Eve's lack of knowledge of the channel parameter to encode quantum information steganographically. We give an explicit encoding procedure and calculate the rate at which Alice and Bob can communicate secretly. We also show that our encoding is optimal for nondegenerate quantum codes. We calculate the rate at which a secret key must be consumed. Finally, we discuss the possibility of steganographic communication over more general quantum channels and conjecture a general formula for the steganographic rate.
The first step in any quantum key distribution (QKD) protocol consists of sequences of measurements that produce correlated classical data. We show that these correlation data must violate some Bell inequality in order to contain distillable secrecy, if not they could be produced by quantum measurements performed on a separable state of larger dimension. We introduce a new QKD protocol and prove its security against any individual attack by an adversary only limited by the no-signaling condition.
In this paper, we propose a method of enciphering quantum states of two-state systems (qubits) for sending them in secrecy without entangled qubits shared by two legitimate users (Alice and Bob). This method has the following two properties. First, even if an eavesdropper (Eve) steals qubits, she can extract information from them with only a certain probability at most. Second, Alice and Bob can confirm that the qubits are transmitted between them correctly by measuring a signature. If Eve measures m qubits one by one from n enciphered qubits and sends alternative ones (the intercept/resend attack), the probability that Alice and Bob do not notice Eve's action is equal to (3/4) m or less. Passwords for decryption and the signature are given by classical binary strings and they are disclosed through a public channel. Enciphering classical information by this method is equivalent to the one-time pad method with distributing a classical key (random binary string) by the BB84 protocol. If Eve takes away qubits, Alice and Bob lose the original quantum information. If we apply our method to a state in iteration, Eve's success probability decreases exponentially. We cannot examine security against the case that Eve makes an attack using entanglement. This remains to be solved in the future.