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

Impossibility of composable Oblivious Transfer in relativistic quantum cryptography

Lorenzo Laneve, Lídia del Rio

Published Jun 21, 2021• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2106.11200

Related papers

Randomized Oblivious Transfer for Secure Multiparty Computation in the Quantum Setting

Bruno Costa, Pedro Costa Branco, Manuel Goulão +2 more

Secure computation is a powerful cryptographic tool that encompasses the evaluation of any multivariate function with arbitrary inputs from mutually distrusting parties. The oblivious transfer primitive serves is a basic building block for the general task of secure multi-party computation. Therefore, analyzing the security in the universal composability framework becomes mandatory when dealing with multi-party computation protocols composed of oblivious transfer subroutines. Furthermore, since the required number of oblivious transfer instances scales with the size of the circuits, oblivious transfer remains as a bottleneck for large-scale multi-party computation implementations. Techniques that allow one to extend a small number of oblivious transfers into a larger one in an efficient way make use of the oblivious transfer variant called randomized oblivious transfer. In this work, we present randomized versions of two known oblivious transfer protocols, one quantum and another post-quantum with ring learning with an error assumption. We then prove their security in the quantum universal composability framework, in a common reference string model.

Entropy•Jul 31, 2021•12 citations

Composable security in relativistic quantum cryptography

V. Vilasini, Christopher Portmann, Lídia del Rio

Abstract Relativistic protocols have been proposed to overcome certain impossibility results in classical and quantum cryptography. In such a setting, one takes the location of honest players into account, and uses the signalling limit given by the speed of light to constraint the abilities of dishonest agents. However, composing such protocols with each other to construct new cryptographic resources is known to be insecure in some cases. To make general statements about such constructions, a composable framework for modelling cryptographic security in Minkowski space is required. Here, we introduce a framework for performing such a modular security analysis of classical and quantum cryptographic schemes in Minkowski space. As an application, we show that (1) fair and unbiased coin flipping can be constructed from a simple resource called channel with delay; (2) biased coin flipping, bit commitment and channel with delay through any classical, quantum or post-quantum relativistic protocols are all impossible without further setup assumptions; (3) it is impossible to securely increase the delay of a channel, given several short-delay channels as ingredients. Results (1) and (3) imply in particular the non-composability of existing relativistic bit commitment and coin flipping protocols.

arXiv:1708.00433•New Journal of Physics•Mar 8, 2019•18 citations

Composable security in relativistic quantum cryptography

V. Vilasini, Christopher Portmann, Lídia del Rio

Relativistic protocols have been proposed to overcome certain impossibility results in classical and \nquantum cryptography. In such a setting, one takes the location of honest players into account, and \nuses the signalling limit given by the speed of light to constraint the abilities of dishonest agents. \nHowever, composing such protocols with each other to construct new cryptographic resources is \nknown to be insecure in some cases. To make general statements about such constructions, a \ncomposable framework for modelling cryptographic security in Minkowski space is required. \nHere, we introduce a framework for performing such a modular security analysis of classical and \nquantum cryptographic schemes in Minkowski space. As an application, we show that (1) fair and \nunbiased coin flipping can be constructed from a simple resource called channel with delay; (2) \nbiased coin flipping, bit commitment and channel with delay through any classical, quantum or \npost-quantum relativistic protocols are all impossible without further setup assumptions; (3) it is \nimpossible to securely increase the delay of a channel, given several short-delay channels as \ningredients. Results(1) and (3) imply in particular the non-composability of existing relativistic bit \ncommitment and coin flipping protocols.

•Apr 1, 2019•16 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

Promising the Impossible: Classical Certification in a Quantum World

Adrian Kent

I give a simple proof that it is impossible to guarantee the classicality of inputs into any mistrustful quantum cryptographic protocol. The argument illuminates the impossibility of unconditionally secure quantum implementations of essentially classical tasks such as bit commitment with a certified classical committed bit, classical oblivious transfer, and secure classical multi-party computations. It applies both to non-relativistic and to relativistic protocols.

•Sep 4, 2004•6 citations

Secure Quantum Two-Party Computation: Impossibility and Constructions.

Michele Ciampi, Alexandru Cojocaru, Elham Kashefi +1 more

Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output of the computation. In this work, we take the first steps towards understanding the setting in which the two parties want to evaluate a joint quantum functionality while using only a classical channel between them. Our first result indicates that it is in general impossible to realize a two-party quantum functionality against malicious adversaries with black-box simulation, relying only on classical channels. The negative result stems from reducing the existence of a black-box simulator to an extractor for classical proof of quantum knowledge, which in turn leads to violation of the quantum no-cloning. Next, we introduce the notion of oblivious quantum function evaluation (OQFE). An OQFE is a two-party quantum cryptographic primitive with one fully classical party (Alice) whose input is (a classical description of a) quantum unitary, $U$, and a quantum party (Bob) whose input is a quantum state, $\psi$. In particular, Alice receives a classical output corresponding to the measurement of $U(\psi)$ while Bob receives no output. In OQFE, Bob remains oblivious to Alice's input, while Alice learns nothing about $\psi$ more than what can be learned from the output. We present two constructions, one secure against semi-honest parties and the other against malicious parties. Due to the no-go result mentioned above, we consider what is arguably the best possible notion obtainable in our model concerning malicious adversaries: one-sided simulation security. Our protocol relies on the assumption of injective homomorphic trapdoor OWFs, which in turn rely on the LWE problem. As a result, we put forward a first, simple and modular, construction of one-sided quantum two-party computation and quantum oblivious transfer over classical networks.

•Jan 1, 2020•1 citation
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.
Secure computation is a powerful cryptographic tool that encompasses the evaluation of any multivariate function with arbitrary inputs from mutually distrusting parties. The oblivious transfer primitive serves is a basic building block for the general task of secure multi-party computation. Therefore, analyzing the security in the universal composability framework becomes mandatory when dealing with multi-party computation protocols composed of oblivious transfer subroutines. Furthermore, since the required number of oblivious transfer instances scales with the size of the circuits, oblivious transfer remains as a bottleneck for large-scale multi-party computation implementations. Techniques that allow one to extend a small number of oblivious transfers into a larger one in an efficient way make use of the oblivious transfer variant called randomized oblivious transfer. In this work, we present randomized versions of two known oblivious transfer protocols, one quantum and another post-quantum with ring learning with an error assumption. We then prove their security in the quantum universal composability framework, in a common reference string model.
Abstract Relativistic protocols have been proposed to overcome certain impossibility results in classical and quantum cryptography. In such a setting, one takes the location of honest players into account, and uses the signalling limit given by the speed of light to constraint the abilities of dishonest agents. However, composing such protocols with each other to construct new cryptographic resources is known to be insecure in some cases. To make general statements about such constructions, a composable framework for modelling cryptographic security in Minkowski space is required. Here, we introduce a framework for performing such a modular security analysis of classical and quantum cryptographic schemes in Minkowski space. As an application, we show that (1) fair and unbiased coin flipping can be constructed from a simple resource called channel with delay; (2) biased coin flipping, bit commitment and channel with delay through any classical, quantum or post-quantum relativistic protocols are all impossible without further setup assumptions; (3) it is impossible to securely increase the delay of a channel, given several short-delay channels as ingredients. Results (1) and (3) imply in particular the non-composability of existing relativistic bit commitment and coin flipping protocols.
Relativistic protocols have been proposed to overcome certain impossibility results in classical and \nquantum cryptography. In such a setting, one takes the location of honest players into account, and \nuses the signalling limit given by the speed of light to constraint the abilities of dishonest agents. \nHowever, composing such protocols with each other to construct new cryptographic resources is \nknown to be insecure in some cases. To make general statements about such constructions, a \ncomposable framework for modelling cryptographic security in Minkowski space is required. \nHere, we introduce a framework for performing such a modular security analysis of classical and \nquantum cryptographic schemes in Minkowski space. As an application, we show that (1) fair and \nunbiased coin flipping can be constructed from a simple resource called channel with delay; (2) \nbiased coin flipping, bit commitment and channel with delay through any classical, quantum or \npost-quantum relativistic protocols are all impossible without further setup assumptions; (3) it is \nimpossible to securely increase the delay of a channel, given several short-delay channels as \ningredients. Results(1) and (3) imply in particular the non-composability of existing relativistic bit \ncommitment and coin flipping protocols.
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.
Secure two-party computation considers the problem of two parties computing a joint function of their private inputs without revealing anything beyond the output of the computation. In this work, we take the first steps towards understanding the setting in which the two parties want to evaluate a joint quantum functionality while using only a classical channel between them. Our first result indicates that it is in general impossible to realize a two-party quantum functionality against malicious adversaries with black-box simulation, relying only on classical channels. The negative result stems from reducing the existence of a black-box simulator to an extractor for classical proof of quantum knowledge, which in turn leads to violation of the quantum no-cloning. Next, we introduce the notion of oblivious quantum function evaluation (OQFE). An OQFE is a two-party quantum cryptographic primitive with one fully classical party (Alice) whose input is (a classical description of a) quantum unitary, UUU, and a quantum party (Bob) whose input is a quantum state, ψ\psiψ. In particular, Alice receives a classical output corresponding to the measurement of U(ψ)U(\psi)U(ψ) while Bob receives no output. In OQFE, Bob remains oblivious to Alice's input, while Alice learns nothing about ψ\psiψ more than what can be learned from the output. We present two constructions, one secure against semi-honest parties and the other against malicious parties. Due to the no-go result mentioned above, we consider what is arguably the best possible notion obtainable in our model concerning malicious adversaries: one-sided simulation security. Our protocol relies on the assumption of injective homomorphic trapdoor OWFs, which in turn rely on the LWE problem. As a result, we put forward a first, simple and modular, construction of one-sided quantum two-party computation and quantum oblivious transfer over classical networks.