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

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

Damián Pitalúa-García

Published Jul 3, 2019• 16 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.100.012302

Related papers

Spacetime-constrained oblivious transfer

Damián Pitalúa-García

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.

arXiv:1512.05649•Physical Review A•Jun 29, 2016•28 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•22 citations

One-Out-of-q OT Combiners

Oriol Farràs, Jordi Ribes-González

In 1-out-of-$q$Oblivious Transfer (OT) protocols, a sender Alice is able to send one of$q\ge 2$messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners take$n$instances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of the$n$original OT instances are secure. We present new 1-out-of-$q$OT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given an$\mathbb {F}_{q}$-linear secret sharing scheme on a set of$n$participants and adversary structure$\mathcal {A}$, we can construct an$n$-server, 1-out-of-$q$OT combiner that is secure against an adversary corrupting either Alice and a set of servers in$\mathcal {A}$, or Bob and a set of servers$B$with$\bar {B}\notin \mathcal {A}$. If the normalized total share size of the scheme is$\ell $, then the resulting OT combiner requires$\ell $calls to OT protocols, and the total amount of bits exchanged during the protocol is$(q^{2}+q+1)\ell \log q$. We also present a construction based on 1-out-of-2 OT combiners that uses the protocol of Crépeau, Brassard and Robert (FOCS 1986). This construction provides smaller communication costs for certain adversary structures, such as threshold ones: For any prime power$q\geq n$, there are$n$-server, 1-out-of-$q$OT combiners that are perfectly secure against active adversaries corrupting either Alice or Bob, and a minority of the OT candidates, exchanging$O(qn\log q)$bits in total.

IEEE Transactions on Information Theory•Dec 7, 2023•2 citations

Can relativistic bit commitment lead to secure quantum oblivious transfer?

Guang Ping He

arXiv:1210.5681•The European Physical Journal D•Mar 31, 2015•7 citations

Causal communication constraint for two qubits in Hardy's ladder proof of non-locality

Jose Luis Cereceda

Advanced Studies in Theoretical Physics•Jan 1, 2015•2 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•5 citations
In one-out-of-mmm spacetime-constrained oblivious transfer (SCOT), Alice and Bob agree on mmm pairwise spacelike separated output spacetime regions R0,R1,...,Rm\ensuremath−1{R}_{0},{R}_{1},...,{R}_{m\ensuremath{-}1}R0​,R1​,...,Rm\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∈0,1,...,m\ensuremath−1i\ensuremath{\in}{0,1,...,m\ensuremath{-}1}i\ensuremath∈0,1,...,m\ensuremath−1; Bob inputs b\ensuremath∈0,1,...,m\ensuremath−1b\ensuremath{\in}{0,1,...,m\ensuremath{-}1}b\ensuremath∈0,1,...,m\ensuremath−1 in the intersection of the causal pasts of Q0,Q1,...,Qm\ensuremath−1{Q}_{0},{Q}_{1},...,{Q}_{m\ensuremath{-}1}Q0​,Q1​,...,Qm\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∈0,1,...,m\ensuremath−1i,j\ensuremath{\in}{0,1,...,m\ensuremath{-}1}i,j\ensuremath∈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≥2m\ensuremath{\ge}2m\ensuremath≥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≥2m\ensuremath{\ge}2m\ensuremath≥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.
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.
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.
In 1-out-of-qqqOblivious Transfer (OT) protocols, a sender Alice is able to send one ofq≥2q\ge 2q≥2messages to a receiver Bob, all while being oblivious to which message was transferred. Moreover, the receiver learns only one of these messages. Oblivious Transfer combiners takennninstances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of thennnoriginal OT instances are secure. We present new 1-out-of-qqqOT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given anFq\mathbb {F}_{q}Fq​-linear secret sharing scheme on a set ofnnnparticipants and adversary structureA\mathcal {A}A, we can construct annnn-server, 1-out-of-qqqOT combiner that is secure against an adversary corrupting either Alice and a set of servers inA\mathcal {A}A, or Bob and a set of serversBBBwithBˉ∉A\bar {B}\notin \mathcal {A}Bˉ∈/A. If the normalized total share size of the scheme is$\ell ,thentheresultingOTcombinerrequires, then the resulting OT combiner requires,thentheresultingOTcombinerrequires\ell callstoOTprotocols,andthetotalamountofbitsexchangedduringtheprotocoliscalls to OT protocols, and the total amount of bits exchanged during the protocol iscallstoOTprotocols,andthetotalamountofbitsexchangedduringtheprotocolis(q^{2}+q+1)\ell \log q.Wealsopresentaconstructionbasedon1−out−of−2OTcombinersthatusestheprotocolofCreˊpeau,BrassardandRobert(FOCS1986).Thisconstructionprovidessmallercommunicationcostsforcertainadversarystructures,suchasthresholdones:Foranyprimepower. We also present a construction based on 1-out-of-2 OT combiners that uses the protocol of Crépeau, Brassard and Robert (FOCS 1986). This construction provides smaller communication costs for certain adversary structures, such as threshold ones: For any prime power.Wealsopresentaconstructionbasedon1−out−of−2OTcombinersthatusestheprotocolofCreˊpeau,BrassardandRobert(FOCS1986).Thisconstructionprovidessmallercommunicationcostsforcertainadversarystructures,suchasthresholdones:Foranyprimepowerq\geq n,thereare, there are,therearen−server,1−out−of−-server, 1-out-of-−server,1−out−of−qOTcombinersthatareperfectlysecureagainstactiveadversariescorruptingeitherAliceorBob,andaminorityoftheOTcandidates,exchangingOT combiners that are perfectly secure against active adversaries corrupting either Alice or Bob, and a minority of the OT candidates, exchangingOTcombinersthatareperfectlysecureagainstactiveadversariescorruptingeitherAliceorBob,andaminorityoftheOTcandidates,exchangingO(qn\log q)$bits in total.
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.