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

Implications of superstrong non-locality for cryptography

Harry Buhrman, Matthias Christandl, Falk Unger, Stephanie Wehner, Andreas Winter

Published Feb 14, 2006• 54 citations
arXivHTMLPDF

Abstract

Non-local boxes are hypothetical ‘machines’ that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/Clauser, Horne, Shimony & Holt inequalities than is possible within the framework of quantum mechanics. We show how non-local boxes can be used to perform any two-party secure computation. We first construct a protocol for bit commitment and then show how to achieve oblivious transfer using non-local boxes. Both have been shown to be impossible using quantum mechanics alone.

DOI
10.1098/rspa.2006.1663

Related papers

The physics of no-bit-commitment : Generalized quantum non-locality versus oblivious transfer

Tony Short, Nicolas Gisin, Sandu Popescu

We show here that the recent work of Wolf and Wullschleger (quant-ph/0502030) on oblivious transfer apparently opens the possibility that non-local correlations which are stronger than those in quantum mechanics could be used for bit-commitment. This is surprising, because it is the very existence of non-local correlations which in quantum mechanics prevents bit-commitment. We resolve this apparent paradox by stressing the difference between non-local correlations and oblivious transfer, based on the time-ordering of their inputs and outputs, which prevents bit-commitment.

arXiv:quant-ph/0504134•Apr 18, 2005•5 citations

Quantum non-locality, causality and mistrustful cryptography

Muhammad Nadeem

Here we propose a general relativistic quantum framework for cryptography that exploits the fascinating connection of quantum non-locality and special theory of relativity with cryptography. The underlying principle of unconditional security is causality and two-fold quantum non-local correlations: first entanglement swapping and then teleportation over causally independent entangled systems. We show that the proposed framework has following remarkable and novel features in mistrustful cryptography: (i) It helps in defining a new notion of oblivious transfer where both the data transferred and the transfer position remains oblivious. (ii) The authenticity and integrity of the data transferred is guaranteed by the fundamental principles of quantum theory instead of computational complexity. (iii) It directly leads to unconditionally secure and deterministic two-sided two-party computation which is currently considered to be impossible. (iv) the proposed framework turns out to be asynchronous ideal coin tossing with zero bias which has not been achieved previously. (v) The same framework also implies unconditionally secure bit commitment. Finally, the combination of quantum non-locality and theory of relativity as discussed here can easily be generalized to multiparty setting that could be used to solve other mistrustful cryptographic tasks such as secret sharing and key agreement securely.

arXiv:1407.7025•Jul 25, 2014•9 citations

Quantum cryptography -- an information theoretic security

Nadeem, Muhammad

Methods of quantum mechanics promise information-theoretic security for various protocols in cryptography. However, impossibility of some cryptographic applications such as standard bit commitment, oblivious transfer, multiparty secure computations and ideal coin tossing in quantum regime leaves an obvious question on the completeness of quantum cryptography. Instead of using wide range of rules and techniques for a variety of cryptographic applications, we demonstrate here a unified structure for quantum cryptography based on quantum non-local correlations. The unified framework achieves same goals in information-theoretic way as classical cryptography does with computational hardness. To cover the broad range of cryptographic applications, we show that the framework (i) assures secrecy by providing encryption completely unintelligible to eavesdroppers, (ii) guarantees that input from distant parties is concealed unless they are willing to reveal, (iii) assures binding, (iv) allows splitting information between several parties securely and more generally, (v) evades both quantum and classical attacks from internal as well as external eavesdropping.

arXiv:1507.07918•Jul 28, 2015•3 citations

Oblivious transfer and quantum non-locality

Stefan Wolf, Jürg Wullschleger

Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receiver's choice. Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a "non-locality machine": Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. We show a close connection, in a cryptographic sense, between OT and the "PR primitive." More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT

arXiv:quant-ph/0502030•IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•32 citations

Impossibility of composable Oblivious Transfer in relativistic quantum cryptography

Lorenzo Laneve, Lídia del Rio

We study the cryptographic primitive Oblivious Transfer; a composable construction of this resource would allow arbitrary multi-party computation to be carried out in a secure way, i.e. to compute functions in a distributed way while keeping inputs from different parties private. First we review a framework that allows us to analyze composability of classical and quantum cryptographic protocols in special relativity: Abstract Cryptography implemented with Causal Boxes. We then (1) explore and formalize different versions of oblivious transfer found in the literature, (2) prove that their equivalence holds also in relativistic quantum settings, (3) show that it is impossible to composably construct any of these versions of oblivious transfer from only classical or quantum communication among distrusting agents in relativistic settings, (4) prove that the impossibility also extends to multi-party computation, and (5) provide a mutual construction between oblivious transfer and bit commitment.

arXiv:2106.11200•Jun 21, 2021•3 citations

Bit Commitment from Weak Non-Locality

Stefan Wolf, Juerg Wullschleger

So-called non-local boxes, which have been introduced as an idealization-in different respects-of the behavior of entangled quantum states, have been known to allow for unconditional bit commitment between the two involved parties. We show that, actually, any possible non-local correlation which produces random bits on both sides can be used to implement bit commitment, and that this holds even when the parties are allowed to delay their inputs to the box. Since a particular example is the behavior of an EPR pair, this resource allows for implementing unconditionally secure bit commitment as long as the parties cannot entangle their Qbits with any other system.

arXiv:quant-ph/0508233•Aug 31, 2005•1 citation
Non-local boxes are hypothetical ‘machines’ that give rise to superstrong non-local correlations, leading to a stronger violation of Bell/Clauser, Horne, Shimony & Holt inequalities than is possible within the framework of quantum mechanics. We show how non-local boxes can be used to perform any two-party secure computation. We first construct a protocol for bit commitment and then show how to achieve oblivious transfer using non-local boxes. Both have been shown to be impossible using quantum mechanics alone.
We show here that the recent work of Wolf and Wullschleger (quant-ph/0502030) on oblivious transfer apparently opens the possibility that non-local correlations which are stronger than those in quantum mechanics could be used for bit-commitment. This is surprising, because it is the very existence of non-local correlations which in quantum mechanics prevents bit-commitment. We resolve this apparent paradox by stressing the difference between non-local correlations and oblivious transfer, based on the time-ordering of their inputs and outputs, which prevents bit-commitment.
Here we propose a general relativistic quantum framework for cryptography that exploits the fascinating connection of quantum non-locality and special theory of relativity with cryptography. The underlying principle of unconditional security is causality and two-fold quantum non-local correlations: first entanglement swapping and then teleportation over causally independent entangled systems. We show that the proposed framework has following remarkable and novel features in mistrustful cryptography: (i) It helps in defining a new notion of oblivious transfer where both the data transferred and the transfer position remains oblivious. (ii) The authenticity and integrity of the data transferred is guaranteed by the fundamental principles of quantum theory instead of computational complexity. (iii) It directly leads to unconditionally secure and deterministic two-sided two-party computation which is currently considered to be impossible. (iv) the proposed framework turns out to be asynchronous ideal coin tossing with zero bias which has not been achieved previously. (v) The same framework also implies unconditionally secure bit commitment. Finally, the combination of quantum non-locality and theory of relativity as discussed here can easily be generalized to multiparty setting that could be used to solve other mistrustful cryptographic tasks such as secret sharing and key agreement securely.
Methods of quantum mechanics promise information-theoretic security for various protocols in cryptography. However, impossibility of some cryptographic applications such as standard bit commitment, oblivious transfer, multiparty secure computations and ideal coin tossing in quantum regime leaves an obvious question on the completeness of quantum cryptography. Instead of using wide range of rules and techniques for a variety of cryptographic applications, we demonstrate here a unified structure for quantum cryptography based on quantum non-local correlations. The unified framework achieves same goals in information-theoretic way as classical cryptography does with computational hardness. To cover the broad range of cryptographic applications, we show that the framework (i) assures secrecy by providing encryption completely unintelligible to eavesdroppers, (ii) guarantees that input from distant parties is concealed unless they are willing to reveal, (iii) assures binding, (iv) allows splitting information between several parties securely and more generally, (v) evades both quantum and classical attacks from internal as well as external eavesdropping.
Oblivious transfer, a central functionality in modern cryptography, allows a party to send two one-bit messages to another who can choose one of them to read, remaining ignorant about the other, whereas the sender does not learn the receiver's choice. Oblivious transfer the security of which is information-theoretic for both parties is known impossible to achieve from scratch. The joint behavior of certain bi-partite quantum states is non-local, i.e., cannot be explained by shared classical information. In order to better understand such behavior, which is classically explainable only by communication, but does not allow for it, Popescu and Rohrlich have described a "non-locality machine": Two parties both input a bit, and both get a random output bit the XOR of which is the AND of the input bits. We show a close connection, in a cryptographic sense, between OT and the "PR primitive." More specifically, unconditional OT can be achieved from a single realization of PR, and vice versa. Our reductions, which are single-copy, information-theoretic, and perfect, also lead to a simple and optimal protocol allowing for inverting the direction of OT
We study the cryptographic primitive Oblivious Transfer; a composable construction of this resource would allow arbitrary multi-party computation to be carried out in a secure way, i.e. to compute functions in a distributed way while keeping inputs from different parties private. First we review a framework that allows us to analyze composability of classical and quantum cryptographic protocols in special relativity: Abstract Cryptography implemented with Causal Boxes. We then (1) explore and formalize different versions of oblivious transfer found in the literature, (2) prove that their equivalence holds also in relativistic quantum settings, (3) show that it is impossible to composably construct any of these versions of oblivious transfer from only classical or quantum communication among distrusting agents in relativistic settings, (4) prove that the impossibility also extends to multi-party computation, and (5) provide a mutual construction between oblivious transfer and bit commitment.
So-called non-local boxes, which have been introduced as an idealization-in different respects-of the behavior of entangled quantum states, have been known to allow for unconditional bit commitment between the two involved parties. We show that, actually, any possible non-local correlation which produces random bits on both sides can be used to implement bit commitment, and that this holds even when the parties are allowed to delay their inputs to the box. Since a particular example is the behavior of an EPR pair, this resource allows for implementing unconditionally secure bit commitment as long as the parties cannot entangle their Qbits with any other system.