Key-exchange protocols have been overlooked as a possible means for implementing oblivious transfer (OT). In this article, we present protocols for mutual exchange of secrets, 1-out-of-2 OT and coin-flipping similar to the Diffie-Hellman protocol using the idea of obliviously exchanging encryption keys. Since the Diffie-Hellman scheme is widely used, our protocol may provide a useful alternative to the conventional methods for implementation of oblivious transfer and a useful primitive in building larger cryptographic schemes.
In 1-out-of-
qOblivious Transfer (OT) protocols, a sender Alice is able to send one of
q≥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 take
ninstances of OT protocols as input, and produce an OT protocol that is secure if sufficiently many of the
noriginal OT instances are secure. We present new 1-out-of-
qOT combiners that are perfectly secure against active adversaries. Our combiners arise from secret sharing techniques. We show that given an
Fq-linear secret sharing scheme on a set of
nparticipants and adversary structure
A, we can construct an
n-server, 1-out-of-
qOT combiner that is secure against an adversary corrupting either Alice and a set of servers in
A, or Bob and a set of servers
Bwith
Bˉ∈/A. If the normalized total share size of the scheme is$\ell
,thentheresultingOTcombinerrequires\ell
callstoOTprotocols,andthetotalamountofbitsexchangedduringtheprotocolis(q^{2}+q+1)\ell \log q
.Wealsopresentaconstructionbasedon1−out−of−2OTcombinersthatusestheprotocolofCreˊpeau,BrassardandRobert(FOCS1986).Thisconstructionprovidessmallercommunicationcostsforcertainadversarystructures,suchasthresholdones:Foranyprimepowerq\geq n
,therearen
−server,1−out−of−q
OTcombinersthatareperfectlysecureagainstactiveadversariescorruptingeitherAliceorBob,andaminorityoftheOTcandidates,exchangingO(qn\log q)$bits in total.