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:1512.05649 · Physical Review A

Spacetime-constrained oblivious transfer

Damián Pitalúa-García

Published Jun 29, 2016• 30 citations
arXivHTMLPDF

Abstract

In 1-out-of-2 oblivious transfer (OT), Alice inputs numbers ${x}_{0},{x}_{1}$, Bob inputs a bit $b$ and outputs ${x}_{b}$. Secure OT requires that Alice and Bob learn nothing about $b$ and ${x}_{\overline{b}}$, respectively. We define spacetime-constrained oblivious transfer (SCOT) as OT in Minkowski spacetime in which Bob must output ${x}_{b}$ within ${R}_{b}$, where ${R}_{0}$ and ${R}_{1}$ are fixed spacelike separated spacetime regions. We show that unconditionally secure SCOT is impossible with classical protocols in Minkowski (or Galilean) spacetime, or with quantum protocols in Galilean spacetime. We describe a quantum SCOT protocol in Minkowski spacetime, and we show it unconditionally secure.

DOI
10.1103/physreva.93.062346

Related papers

One-out-of- m spacetime-constrained oblivious transfer

Damián Pitalúa-García

In one-out-of-$m$ spacetime-constrained oblivious transfer (SCOT), Alice and Bob agree on $m$ pairwise spacelike separated output spacetime regions ${R}_{0},{R}_{1},...,{R}_{m\ensuremath{-}1}$ in an agreed reference frame in a spacetime that is Minkowski, or close to Minkowski; Alice inputs a message ${\mathbf{x}}_{i}$ in the causal past of a spacetime point ${Q}_{i}$ of ${R}_{i}$, for $i\ensuremath{\in}{0,1,...,m\ensuremath{-}1}$; Bob inputs $b\ensuremath{\in}{0,1,...,m\ensuremath{-}1}$ in the intersection of the causal pasts of ${Q}_{0},{Q}_{1},...,{Q}_{m\ensuremath{-}1}$ and outputs ${\mathbf{x}}_{b}$ in ${R}_{b}$; Alice remains oblivious to $b$ anywhere in spacetime; and Bob is unable to obtain ${\mathbf{x}}_{i}$ in ${R}_{i}$ and ${\mathbf{x}}_{j}$ in ${R}_{j}$ for any pair of different numbers $i,j\ensuremath{\in}{0,1,...,m\ensuremath{-}1}$. We introduce unconditionally secure one-out-of-$m$ SCOT protocols extending the one-out-of-two SCOT protocols of Pital\'ua-Garc\'{\i}a [Phys. Rev. A 93, 062346 (2016)] and Pital\'ua-Garc\'{\i}a and Kerenidis [Phys. Rev. A 98, 032327 (2018)], for arbitrary integers $m\ensuremath{\ge}2$. We define the task of one-out-of-$m$ distributed quantum access with classical memory (DQACM), which works as a subroutine to implement a class ${\mathcal{P}}_{\text{CC}}$ of one-out-of-$m$ SCOT protocols where distant agents only need to communicate classically. We present unconditionally secure one-out-of-$m$ DQACM protocols and one-out-of-$m$ SCOT protocols of the class ${\mathcal{P}}_{\text{CC}}$, for arbitrary integers $m\ensuremath{\ge}2$. We discuss various generalizations of SCOT. In particular, we introduce a straightforward extension of SCOT to a $k$-out-of-$m$ setting, and suggest protocols where distant agents only need to communicate classically, while we leave the investigation of their security as an open problem.

arXiv:1907.02475•Physical Review A•Jul 3, 2019•17 citations

Practical and unconditionally secure spacetime-constrained oblivious transfer

Damián Pitalúa-García, Iordanis Kerenidis

Spacetime-constrained oblivious transfer (SCOT) extends the fundamental primitive of oblivious transfer to Minkowski space. SCOT and location-oblivious data transfer (LODT) are the only known cryptographic tasks with classical inputs and outputs for which unconditional security needs both quantum theory and relativity. We give an unconditionally secure SCOT protocol that, contrasting previous SCOT and LODT protocols, is practical to implement with current technology, where distant agents need only communicate classical information, while quantum communication occurs at a single location. We also show that our SCOT protocol can be used to implement unconditionally secure quantum relativistic bit commitment.

arXiv:1811.07410•Physical Review A•Sep 24, 2018•23 citations

1-out-of-2 oblivious transfer using a flawed bit-string quantum protocol

Martin Plesch, Marcin Pawłowski, Matej Pivoluska

Oblivious transfer (OT) is an important tool in cryptography. It serves as a subroutine to other complex procedures of both theoretical and practical significance. A common attribute of OT protocols is that one party (Alice) has to send a message to another party (Bob) and has to stay oblivious to whether Bob did receive the message. Specific (OT) protocols vary by exact definition of the task---in the all-or-nothing protocol, Alice sends a single bit-string message, which Bob is able to read with only $50%$ probability, whereas in a 1-out-of-2 OT protocol Bob reads one out of two messages sent by Alice. These two flavors of protocol are known to be equivalent. Recently, a computationally secure all-or-nothing OT protocol based on quantum states was developed by A. Souto et al. [Phys. Rev. A 91, 042306 (2015)], which, however, cannot be reduced to a 1-out-of-2 OT protocol by standard means. Here we present an elaborate reduction of this protocol that retains the security of the original.

arXiv:1611.10087•Physical Review A•Apr 18, 2017•7 citations

Noninteractive xor Quantum Oblivious Transfer: Optimal Protocols and Their Experimental Implementations

Lara Stroh, Nikola Horová, Robert Stárek +4 more

Oblivious transfer (OT) is an important cryptographic primitive.Any multiparty computation can be realized with OT as building block.XOR oblivious transfer (XOT) is a variant where the sender Alice has two bits and a receiver Bob obtains either the first bit, the second bit, or their XOR.Bob should not learn anything more than this and Alice should not learn what Bob has learnt.Perfect quantum OT with information-theoretic security is known to be impossible.We determine the smallest possible cheating probabilities for unrestricted dishonest parties in noninteractive quantum XOT protocols using symmetric pure states and present an optimal protocol, which outperforms classical protocols.We also "reverse" this protocol, so that Bob becomes sender of a quantum state and Alice the receiver who measures it, while still implementing oblivious transfer from Alice to Bob.Cheating probabilities for both parties stay the same as for the unreversed protocol.We optically implement both the unreversed and the reversed protocols, and cheating strategies, noting that the reversed protocol is easier to implement.

arXiv:2209.11300•PRX Quantum•May 4, 2023•16 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•55 citations

Quantum Oblivious Transfer Based on POVM Measurements.

Wei Yang, Liusheng Huang, Yonglong Luo +1 more

Abstract- Oblivious transfer (OT) is an important primitive in cryptography. In chosen one-out-of-two OT, Alice offers two bits, one of which Bob can choose to read, not learning any information about the other bit. Alice on the other hand does not obtain any information about Bob’s choice. We present a new technique for the same task in quantum environment, based on POVM measurements. It is shown that our method has two important advantages over the previous approaches. First, it is unconditionally secure without invoking a commitment scheme, and second, it is more efficient in terms of communication complexity. Key words: Oblivious transfer, POVM measurements, Unconditional security

FCS•Jan 1, 2006•0 citations
In 1-out-of-2 oblivious transfer (OT), Alice inputs numbers x0,x1{x}_{0},{x}_{1}x0​,x1​, Bob inputs a bit bbb and outputs xb{x}_{b}xb​. Secure OT requires that Alice and Bob learn nothing about bbb and xb‾{x}_{\overline{b}}xb​, respectively. We define spacetime-constrained oblivious transfer (SCOT) as OT in Minkowski spacetime in which Bob must output xb{x}_{b}xb​ within Rb{R}_{b}Rb​, where R0{R}_{0}R0​ and R1{R}_{1}R1​ are fixed spacelike separated spacetime regions. We show that unconditionally secure SCOT is impossible with classical protocols in Minkowski (or Galilean) spacetime, or with quantum protocols in Galilean spacetime. We describe a quantum SCOT protocol in Minkowski spacetime, and we show it unconditionally secure.
In one-out-of-mmm spacetime-constrained oblivious transfer (SCOT), Alice and Bob agree on mmm pairwise spacelike separated output spacetime regions ${R}_{0},{R}_{1},...,{R}_{m\ensuremath{-}1}$ in an agreed reference frame in a spacetime that is Minkowski, or close to Minkowski; Alice inputs a message xi{\mathbf{x}}_{i}xi​ in the causal past of a spacetime point Qi{Q}_{i}Qi​ of Ri{R}_{i}Ri​, for $i\ensuremath{\in}{0,1,...,m\ensuremath{-}1}$; Bob inputs $b\ensuremath{\in}{0,1,...,m\ensuremath{-}1}$ in the intersection of the causal pasts of ${Q}_{0},{Q}_{1},...,{Q}_{m\ensuremath{-}1}$ and outputs xb{\mathbf{x}}_{b}xb​ in Rb{R}_{b}Rb​; Alice remains oblivious to bbb anywhere in spacetime; and Bob is unable to obtain xi{\mathbf{x}}_{i}xi​ in Ri{R}_{i}Ri​ and xj{\mathbf{x}}_{j}xj​ in Rj{R}_{j}Rj​ for any pair of different numbers $i,j\ensuremath{\in}{0,1,...,m\ensuremath{-}1}$. We introduce unconditionally secure one-out-of-mmm SCOT protocols extending the one-out-of-two SCOT protocols of Pital\'ua-Garc\'{\i}a [Phys. Rev. A 93, 062346 (2016)] and Pital\'ua-Garc\'{\i}a and Kerenidis [Phys. Rev. A 98, 032327 (2018)], for arbitrary integers $m\ensuremath{\ge}2$. We define the task of one-out-of-mmm distributed quantum access with classical memory (DQACM), which works as a subroutine to implement a class PCC{\mathcal{P}}_{\text{CC}}PCC​ of one-out-of-mmm SCOT protocols where distant agents only need to communicate classically. We present unconditionally secure one-out-of-mmm DQACM protocols and one-out-of-mmm SCOT protocols of the class PCC{\mathcal{P}}_{\text{CC}}PCC​, for arbitrary integers $m\ensuremath{\ge}2$. We discuss various generalizations of SCOT. In particular, we introduce a straightforward extension of SCOT to a kkk-out-of-mmm setting, and suggest protocols where distant agents only need to communicate classically, while we leave the investigation of their security as an open problem.
Spacetime-constrained oblivious transfer (SCOT) extends the fundamental primitive of oblivious transfer to Minkowski space. SCOT and location-oblivious data transfer (LODT) are the only known cryptographic tasks with classical inputs and outputs for which unconditional security needs both quantum theory and relativity. We give an unconditionally secure SCOT protocol that, contrasting previous SCOT and LODT protocols, is practical to implement with current technology, where distant agents need only communicate classical information, while quantum communication occurs at a single location. We also show that our SCOT protocol can be used to implement unconditionally secure quantum relativistic bit commitment.
Oblivious transfer (OT) is an important tool in cryptography. It serves as a subroutine to other complex procedures of both theoretical and practical significance. A common attribute of OT protocols is that one party (Alice) has to send a message to another party (Bob) and has to stay oblivious to whether Bob did receive the message. Specific (OT) protocols vary by exact definition of the task---in the all-or-nothing protocol, Alice sends a single bit-string message, which Bob is able to read with only 5050%50 probability, whereas in a 1-out-of-2 OT protocol Bob reads one out of two messages sent by Alice. These two flavors of protocol are known to be equivalent. Recently, a computationally secure all-or-nothing OT protocol based on quantum states was developed by A. Souto et al. [Phys. Rev. A 91, 042306 (2015)], which, however, cannot be reduced to a 1-out-of-2 OT protocol by standard means. Here we present an elaborate reduction of this protocol that retains the security of the original.
Oblivious transfer (OT) is an important cryptographic primitive.Any multiparty computation can be realized with OT as building block.XOR oblivious transfer (XOT) is a variant where the sender Alice has two bits and a receiver Bob obtains either the first bit, the second bit, or their XOR.Bob should not learn anything more than this and Alice should not learn what Bob has learnt.Perfect quantum OT with information-theoretic security is known to be impossible.We determine the smallest possible cheating probabilities for unrestricted dishonest parties in noninteractive quantum XOT protocols using symmetric pure states and present an optimal protocol, which outperforms classical protocols.We also "reverse" this protocol, so that Bob becomes sender of a quantum state and Alice the receiver who measures it, while still implementing oblivious transfer from Alice to Bob.Cheating probabilities for both parties stay the same as for the unreversed protocol.We optically implement both the unreversed and the reversed protocols, and cheating strategies, noting that the reversed protocol is easier to implement.
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
Abstract- Oblivious transfer (OT) is an important primitive in cryptography. In chosen one-out-of-two OT, Alice offers two bits, one of which Bob can choose to read, not learning any information about the other bit. Alice on the other hand does not obtain any information about Bob’s choice. We present a new technique for the same task in quantum environment, based on POVM measurements. It is shown that our method has two important advantages over the previous approaches. First, it is unconditionally secure without invoking a commitment scheme, and second, it is more efficient in terms of communication complexity. Key words: Oblivious transfer, POVM measurements, Unconditional security