International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Oblivious Transfer and Linear Functions

Ivan Damgård
Serge Fehr
Louis Salvail
Christian Schaffner
Search ePrint
Search Google
Abstract: We study unconditionally secure 1-out-of-2 Oblivious Transfer (1-2 OT). We first point out that a standard security requirement for 1-2 OT of bits, namely that the receiver only learns one of the bits sent, holds if and only if the receiver has no information on the XOR of the two bits. We then generalize this to 1-2 OT of strings and show that the security can be characterized in terms of binary linear functions. More precisely, we show that the receiver learns only one of the two strings sent if and only if he has no information on the result of applying any binary linear function (which non-trivially depends on both inputs) to the two strings. We then argue that this result not only gives new insight into the nature of 1-2 OT, but it in particular provides a very powerful tool for analyzing 1-2 OT protocols. We demonstrate this by showing that with our characterization at hand, the reduceability of 1-2 OT (of strings) to a wide range of weaker primitives follows by a very simple argument. This is in sharp contrast to previous literature, where reductions of 1-2 OT to weaker flavors have rather complicated and sometimes even incorrect proofs.
  title={Oblivious Transfer and Linear Functions},
  booktitle={IACR Eprint archive},
  keywords={foundations / Oblivious transfer, information theory},
  note={Full version of the Crypto 2006 paper. 13388 received 4 Oct 2005, last revised 28 Aug 2006},
  author={Ivan Damgård and Serge Fehr and Louis Salvail and Christian Schaffner},