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:1205.3736

Towards the Impossibility of Non-Signalling Privacy Amplification from Time-Like Ordering Constraints

Rotem Arnon-Friedman, Esther Hänggi, Amnon Ta‐Shma

Published May 16, 2012• 8 citations
arXivHTMLPDF

Abstract

In the past few years there was a growing interest in proving the security of cryptographic protocols, such as key distribution protocols, from the sole assumption that the systems of Alice and Bob cannot signal to each other. This can be achieved by making sure that Alice and Bob perform their measurements in a space-like separated way (and therefore signalling is impossible according to the non-signalling postulate of relativity theory) or even by shielding their apparatus. Unfortunately, it was proven in [E. Haenggi, R. Renner, and S. Wolf. The impossibility of non-signaling privacy amplification] that, no matter what hash function we use, privacy amplification is impossible if we only impose non-signalling conditions between Alice and Bob and not within their systems. In this letter we reduce the gap between the assumptions of Haenggi et al. and the physical relevant assumptions, from an experimental point of view, which say that the systems can only signal forward in time within the systems of Alice and Bob. We consider a set of assumptions which is very close to the conditions above and prove that the impossibility result of Haenggi et al. still holds.

DOI
10.48550/arxiv.1205.3736

Related papers

Limits of privacy amplification against nonsignaling memory attacks

Rotem Arnon-Friedman, Amnon Ta‐Shma

The task of privacy amplification, in which Alice holds some partially secret information with respect to an adversary Eve and wishes to distill it until it is completely secret, is known to be solvable almost optimally in both the classical and quantum worlds. Unfortunately, when considering an adversary who is limited only by nonsignaling constraints such a statement cannot be made in general. We here consider systems which violate the chained Bell inequality and prove that under the natural assumptions of a time-ordered nonsignaling system, which allow past subsystems to signal future subsystems (using the device's memory for example), superpolynomial privacy amplification by any hashing is impossible. This is of great relevance when considering practical device-independent key-distribution protocols which assume a superquantum adversary.

arXiv:1211.1125•Physical Review A•Dec 27, 2012•52 citations

Universally Composable Privacy Amplification from Causality Constraints

Lluís Masanes

We consider schemes for secret key distribution which use as a resource correlations that violate Bell inequalities. We provide the first security proof for such schemes, according to the strongest notion of security, the so-called universally composable security. Our security proof does not rely on the validity of quantum mechanics, it solely relies on the impossibility of arbitrarily fast signaling between separate physical systems. This allows for secret communication in situations where the participants distrust their quantum devices.

arXiv:0807.2158•Physical Review Letters•Apr 10, 2009•146 citations

Summoning, No-Signalling and Relativistic Bit Commitments

Adrian Kent

Summoning is a task between two parties, Alice and Bob, with distributed networks of agents in space-time. Bob gives Alice a random quantum state, known to him but not her, at some point. She is required to return the state at some later point, belonging to a subset defined by communications received from Bob at other points. Many results about summoning, including the impossibility of unrestricted summoning tasks and the necessary conditions for specific types of summoning tasks to be possible, follow directly from the quantum no-cloning theorem and the relativistic no-superluminal-signalling principle. The impossibility of cloning devices can be derived from the impossibility of superluminal signalling and the projection postulate, together with assumptions about the devices' location-independent functioning. In this qualified sense, known summoning results follow from the causal structure of space-time and the properties of quantum measurements. Bounds on the fidelity of approximate cloning can be similarly derived. Bit commitment protocols and other cryptographic protocols based on the no-summoning theorem can thus be proven secure against some classes of post-quantum but non-signalling adversaries.

arXiv:1804.05246•Entropy•May 25, 2019•1 citation

The Impossibility of Keyless Communication in Quantum Cryptography

Daniel M. Greenberger, Mark Hillary

We define a keyless communication as a message sent from one party (Alice) to another (Bob), such that the message is totally secure. This means that if a third party (Eve) is trying to eavesdrop, she will receive only random bits. She cannot understand the content of the message, even if she is able to intercept it in such away that Alice and Bob do not know it has been intercepted. For such a totally secure message, Alice and Bob do not need to set up any key beforehand, as it can add no further security. Starting with a system that we felt sure met such criteria, we were shocked to find out that it could be broken in at least two ways, by a semi-classical method and by a quantum method, such that Eve could read a message and Alice and Bob would not know it. Alice and Bob can counter such eavesdropping, but only by sending out test messages. This will enable them to ascertain that Eve is on the line, but then she can still occasionally pick up snippets of their conversation. In that case, in order to be totally secure, it is better to establish an unbreakable key beforehand. We postulate and give plausibility arguments that in general it is impossible to establish keyless communication between two parties.

Fortschritte der Physik•May 1, 2000•0 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•121 citations

Quantum Key Distribution with Classical Bob

Michel Boyer, Dan Kenigsberg, Tal Mor

Secure key distribution among two remote parties is impossible when both are classical, unless some unproven computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? We present a protocol with this constraint and prove its robustness against attacks: we prove that any attempt of an adversary to obtain information necessarily induces some errors that the legitimate users could notice.

arXiv:quant-ph/0703107•Physical Review Letters•Oct 5, 2007•386 citations
In the past few years there was a growing interest in proving the security of cryptographic protocols, such as key distribution protocols, from the sole assumption that the systems of Alice and Bob cannot signal to each other. This can be achieved by making sure that Alice and Bob perform their measurements in a space-like separated way (and therefore signalling is impossible according to the non-signalling postulate of relativity theory) or even by shielding their apparatus. Unfortunately, it was proven in [E. Haenggi, R. Renner, and S. Wolf. The impossibility of non-signaling privacy amplification] that, no matter what hash function we use, privacy amplification is impossible if we only impose non-signalling conditions between Alice and Bob and not within their systems. In this letter we reduce the gap between the assumptions of Haenggi et al. and the physical relevant assumptions, from an experimental point of view, which say that the systems can only signal forward in time within the systems of Alice and Bob. We consider a set of assumptions which is very close to the conditions above and prove that the impossibility result of Haenggi et al. still holds.
The task of privacy amplification, in which Alice holds some partially secret information with respect to an adversary Eve and wishes to distill it until it is completely secret, is known to be solvable almost optimally in both the classical and quantum worlds. Unfortunately, when considering an adversary who is limited only by nonsignaling constraints such a statement cannot be made in general. We here consider systems which violate the chained Bell inequality and prove that under the natural assumptions of a time-ordered nonsignaling system, which allow past subsystems to signal future subsystems (using the device's memory for example), superpolynomial privacy amplification by any hashing is impossible. This is of great relevance when considering practical device-independent key-distribution protocols which assume a superquantum adversary.
We consider schemes for secret key distribution which use as a resource correlations that violate Bell inequalities. We provide the first security proof for such schemes, according to the strongest notion of security, the so-called universally composable security. Our security proof does not rely on the validity of quantum mechanics, it solely relies on the impossibility of arbitrarily fast signaling between separate physical systems. This allows for secret communication in situations where the participants distrust their quantum devices.
Summoning is a task between two parties, Alice and Bob, with distributed networks of agents in space-time. Bob gives Alice a random quantum state, known to him but not her, at some point. She is required to return the state at some later point, belonging to a subset defined by communications received from Bob at other points. Many results about summoning, including the impossibility of unrestricted summoning tasks and the necessary conditions for specific types of summoning tasks to be possible, follow directly from the quantum no-cloning theorem and the relativistic no-superluminal-signalling principle. The impossibility of cloning devices can be derived from the impossibility of superluminal signalling and the projection postulate, together with assumptions about the devices' location-independent functioning. In this qualified sense, known summoning results follow from the causal structure of space-time and the properties of quantum measurements. Bounds on the fidelity of approximate cloning can be similarly derived. Bit commitment protocols and other cryptographic protocols based on the no-summoning theorem can thus be proven secure against some classes of post-quantum but non-signalling adversaries.
We define a keyless communication as a message sent from one party (Alice) to another (Bob), such that the message is totally secure. This means that if a third party (Eve) is trying to eavesdrop, she will receive only random bits. She cannot understand the content of the message, even if she is able to intercept it in such away that Alice and Bob do not know it has been intercepted. For such a totally secure message, Alice and Bob do not need to set up any key beforehand, as it can add no further security. Starting with a system that we felt sure met such criteria, we were shocked to find out that it could be broken in at least two ways, by a semi-classical method and by a quantum method, such that Eve could read a message and Alice and Bob would not know it. Alice and Bob can counter such eavesdropping, but only by sending out test messages. This will enable them to ascertain that Eve is on the line, but then she can still occasionally pick up snippets of their conversation. In that case, in order to be totally secure, it is better to establish an unbreakable key beforehand. We postulate and give plausibility arguments that in general it is impossible to establish keyless communication between two parties.
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.
Secure key distribution among two remote parties is impossible when both are classical, unless some unproven computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? We present a protocol with this constraint and prove its robustness against attacks: we prove that any attempt of an adversary to obtain information necessarily induces some errors that the legitimate users could notice.