Published by the Department of Computer Science, The University of Chicago.
André Chailloux
INRIA Paris, SECRET Project Team
Paris, France.
andre.chailloux AT inria DOT fr
Gus Gutoski
Perimeter Institute for Theoretical Physics
Waterloo, Ontario, Canada.
ggutoski AT perimeterinstitute DOT ca
and
Jamie Sikora
Centre for Quantum Technologies
National University of Singapore
Singapore.
cqtjwjs AT nus DOT edu DOT sg
Oblivious transfer is a fundamental cryptographic primitive in which Bob transfers
one of two bits to Alice in such a way that Bob cannot know which of the two bits
Alice has learned.
We present an optimal security bound for quantum oblivious transfer protocols, in
the information theoretic setting, under a natural and {arguably} demanding
definition of what it means for Alice to cheat.
Our lower bound is a smooth tradeoff between the probability $P^*_{Bob}$ with
which Bob can guess Alice's bit choice and the probability $P^*_{Alice}$ with
which Alice can guess both of Bob's bits given that she learns one of the bits
with certainty.
We prove that $2 P^*_{Bob} + P^*_{Alice} \geq 2$ in any quantum protocol for
oblivious transfer, from which it follows that one of the two parties must be able
to cheat with probability at least $2/3$.
We prove that this bound is optimal by exhibiting a family of protocols whose
cheating probabilities can be made arbitrarily close to any point on the tradeoff
curve.
Submitted September 29, 2014, revised August 30, 2016, published September 16, 2016.