An Oblivious Transfer Protocol with Log-Squared Communication

Helger Lipmaa. An Oblivious Transfer Protocol with Log-Squared Communication. In Jianying Zhou and Javier Lopez, editors, The 8th Information Security Conference (ISC'05), volume 3650 of Lecture Notes in Computer Science, pages 314--328, Singapore, September 20--23, 2005. Springer, Heidelberg. 10.1007/11556992_23.

File: [.ps.bz2 (135 KB), .pdf (228 KB)] pdf recommended.

Abstract:

We propose a one-round 1-out-of-n computationally-private information retrieval protocol for l-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication Θ(k·log² n+l·log n), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1-out-of-n oblivious-transfer protocol for l-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model..

Keywords: Computationally-private information retrieval, length-flexible additively homomorphic public-key cryptosystem, oblivious transfer.

Old versions:

• Eprint version 2, February 2004, contains several results not in the final version
• Eprint version 3, May 2004, contains several results not in the final version. Compared to v2, more readable, with proofs. Almost no new results.
• Eprint version 4, October 2004, contains several results not in the final version. Compared to v3, detailed communication and security analysis, CPIR->OT transformations.

Slides:

• Slides from Estonian Theory Days, 1-3.10.2004
• Slides from an invited talk, Institute for Infocomm Research, Singapore, 25.1.2005 (longer talk)
• Slides from the ISC 2005 conference

Comment: Proceedings version. @eprint can contain a fuller version. Note that for large database elements, this protocol achieves communication rate 1, i.e., it transforms one bit per one bit of database.

More information: Publisher Webpage.

DOI: 10.1007/11556992_23

• Helger Lipmaa

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