Cryptology ePrint Archive: Report 2005/349

Oblivious Transfer and Linear Functions

Ivan B. Damgaard and Serge Fehr and Louis Salvail and Christian Schaffner

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.

Category / Keywords: foundations / Oblivious transfer, information theory

Publication Info: Full version of the Crypto 2006 paper.

Date: received 4 Oct 2005, last revised 28 Aug 2006

Contact author: Serge Fehr at cwi nl

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20060828:082349 (All versions of this report)

Discussion forum: Show discussion | Start new discussion