Chicago Journal of Theoretical Computer Science

Volume 2016

Article 13

Published by the Department of Computer Science, The University of Chicago.

Optimal bounds for semi-honest quantum oblivious transfer

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


Jamie Sikora
Centre for Quantum Technologies
National University of Singapore
cqtjwjs AT nus DOT edu DOT sg

September 16, 2016


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.