Reducing String Oblivious Transfer to Universal Oblivious Transfer
Stefan Wolf
This paper is concerned with information-theoretic reductions of 1-out-of-2 chosen string oblivious transfer to other primitives that are as weak as possible. At Eurocrypt '97, Brassard and Crepeau presented a reduction to so-called generalized bit oblivious transfer, a primitive in which the sender inputs a pair of bits of which the receiver can choose to obtain at most one bit of deterministic information (e.g., one of the two bits, the XOR or AND function of the bits, and so on). It was stated as an open problem how this can be generalized to probabilistic information (where the receiver for instance obtains noisy versions of the bits). We show that the most optimistic answer to this question is the correct one: Whenever the so-called universal oblivious transfer is such that Bob does not obtain full information about the bits sent, then string oblivious transfer can be reduced to it in linear time, where an exponentially small failure probability must be tolerated. The new technique applied in the analysis uses specific side information provided to the receiver by an oracle and allows to simplify the argumentation
BibTeX Citation
@unpublished{Wolf00d,
author = {Stefan Wolf},
title = {Reducing String Oblivious Transfer to Universal Oblivious Transfer},
year = {2000},
note = {This is the extended version of \cite{Wolf00b}},
}