TCS Seminar

Date: 07/12/2011 Location: J. Liivi 2, room 317 (next to the coffee room)

Speaker: Bingsheng Zhang

Title: Fully Simulatable Oblivious Transfer
with Sublinear Communication under Simple Assumption

Abstract:

During an adaptive $k$-out-of-$n$ oblivious transfer (OT), a sender has $n$ private documents, and a receiver wants to adaptively fetch $k$ documents from them such that the sender learns nothing about the receiver's selection and the receiver learns nothing more than the chosen documents. Recently, many fully simulatable and universally composable (adaptive) OT schemes were proposed in literatures. In their schemes, typically, the initialization phase costs $\Oh(n)$ communication and each transfer phase costs $\Oh(1)$ communication. However, in many applications, the receiver just needs to fetch small number of documents, so the initialization cost is dominated in the entire protocol, especially for $1$-out-of-n case. We propose the first fully simulatable OT with sublinear communication in the standard model. Our scheme costs $\Oh(n^{2/3})$ in the initialization phase and $\Oh(n^{2/3})$ in each transfer phase. It achieves better amortized communication than existing protocols when $k<n^{1/3}$.