Chailloux, André ;
Kerenidis, Iordanis ;
Sikora, Jamie
Lower bounds for Quantum Oblivious Transfer
Abstract
Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest players' cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1outof2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than $1/2$. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a coin flipping protocol and conclude by using Kitaev's coin flipping lower bound. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most $3/4$. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower
and upper bounds for them.
BibTeX  Entry
@InProceedings{chailloux_et_al:LIPIcs:2010:2861,
author = {Andr{\'e} Chailloux and Iordanis Kerenidis and Jamie Sikora},
title = {{Lower bounds for Quantum Oblivious Transfer}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
pages = {157168},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897231},
ISSN = {18688969},
year = {2010},
volume = {8},
editor = {Kamal Lodaya and Meena Mahajan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2010/2861},
URN = {urn:nbn:de:0030drops28613},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.157},
annote = {Keywords: quantum oblivious transfer, coin flipping protocol, semidefinite programming}
}
2010
Keywords: 

quantum oblivious transfer, coin flipping protocol, semidefinite programming 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Issue date: 

2010 
Date of publication: 

2010 