Speaker: Severin Winkler
Title: "Statistical Impossibility Results for Oblivious Transfer
Reductions"
Time: 5 pm
Place: IFW E44
The talk presents results from a project with Juerg Wullschleger on
lower bounds for information-theoretically secure implementations of
oblivious transfer in the statistical case (title and abstract below).
Some familiarity with concepts from secure two-party computation is
assumed - and there is no relation to quantum information theory :( .
Title: Statistical Impossibility Results for Oblivious Transfer Reductions
Abstract: Due to its universality oblivious transfer (OT) is a primitive
of great importance in secure multi-party computation. OT is impossible
to implement from scratch in an unconditionally secure way, but there
are many reductions of OT to other variants of OT, as well as other
primitives such as noisy channels. It is important to know how efficient
such unconditionally secure reductions can be in principle, i.e., how
many instances of a given primitive are at least needed to implement OT.
For perfect (error-free) implementations good lower bounds are known,
e.g. the bounds by Beaver (STOC '96) or by Dodis and Micali (EUROCRYPT
'99). But since in practice one is usually willing to tolerate a small
probability of error, and since these statistical reductions can be much
more efficient, the known bounds have only limited application. In this
work we provide lower bounds on the efficiency of 1-out-of-n OT and
Rabin-OT reductions to distributed randomness in the statistical case.
From these results we derive bounds on reductions to different variants
of OT that generalize known bounds to the statistical case. Our bounds
hold in particular for transformations between a finite number of
primitives and for any error.