Hi all,
This week's talk will be by Severin and is on Thursday in HIT K51 at 17:15 (title and abstract below).
Also, a reminder that there is an additional talk this Tuesday by Hans Christian Oettinger at 15:00 in HIT J52.
Cheers, Roger
--- The talk presents results from a project with Juerg Wullschleger "On the Efficiency of Classical and Quantum Oblivious Transfer Reductions". Familiarity with concepts from secure two-party computation is assumed - and this time there is a relation to quantum information theory :-) :
In the first part of the talk I will shortly present lower bounds on the efficiency of statistically secure classical protocols implementing 1-out-of-n Oblivous Transfer (OT) from (trusted) distributed randomness, i.e., bounds on the minimal number of instances of a given primitive needed to implement OT. (seminar talk of December 8 or http://eprint.iacr.org/2009/508: Statistical Impossiblity Results for Oblivous Transfer Reductions). Then I will present a statistically secure quantum protocol implementing OT that is more efficient than any /statistical /implementation in the classical case and any /perfect/ implementation in the quantum case (by an arbitrarily large factor). I will then present a weaker lower bound that holds for statistically secure implementations of OT in the quantum setting. In particular this bound can be used to show that even quantum protocols /cannot/ extend OT. See full abstract below.
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 the first part of 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. In the second part we look at the efficiency of quantum reductions. Recently, Salvail, Schaffner and Sotakova (ASIACRYPT ’09) showed that most classical lower bounds for perfectly secure reductions of OT to distributed randomness still hold in a quantum setting. We present a statistically secure protocol that violates these bounds by an arbitrarily large factor. We then present a weaker lower bound for the statistical setting. We use this bound to show that even quantum protocols cannot extend OT. Finally, we present two lower bounds for reductions of OT to commitments and a protocol based on string commitments that is optimal with respect to both of these bounds.