Helger Lipmaa's publications

Practical Fully Simulatable Oblivious Transfer with Sublinear Communication

Bingsheng Zhang, Helger Lipmaa, Cong Wang and Kui Ren. Practical Fully Simulatable Oblivious Transfer with Sublinear Communication. In Ahmad-Reza Sadeghi, editor, FC 2013, volume 7859 of Lecture Notes in Computer Science, pages ?--?, Okinawa, Japan, April 1--5, 2013. Springer, Heidelberg.

File: [.pdf (462 KB)] pdf recommended.


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 those chosen documents. Many fully simulatable and universally composable adaptive OT schemes have been proposed, but those schemes typically require $O(N)$ communication in the initialization phase, which yields $O(N)$ overall communication. On the other hand, in some applications, the receiver just needs to fetch a small number of documents, so the initialization cost dominates in the entire protocol, especially for $1$-out-of-$N$ OT. We propose the first fully simulatable adaptive OT with sublinear communication under the DDH assumption in the plain model. Our scheme has $O(N^{1/2})$ communication in both the initialization phase and each transfer phase. It achieves better (amortized) overall communication complexity compared to existing schemes when $k=O(N^{1/2})$.

Keywords: Adaptive oblivious transfer, fully simulatable security, sublinear communication, zero knowledge batch argument.


Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa><at>gmail.com.