Cryptology ePrint Archive: Report 2004/063

An Oblivious Transfer Protocol with Log-Squared Communication

Helger Lipmaa

Abstract: We propose a one-round $1$-out-of-$n$ computationally-private information retrieval protocol for $\ell$-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication $\Theta(k\cdot\log^2{n}+\ell\cdot\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 $\ell$-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model.

Category / Keywords: cryptographic protocols/computationally-private information retrieval, homomorphic public-key cryptosystem, oblivious transfer

Publication Info: ISC 2005

Date: received 25 Feb 2004, last revised 5 Jul 2005

Contact author: lipmaa at cyber ee

Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Note: First version (Feb 2004)

Second version: several new results, although the basic scheme remains the same.

Third version (May 2004): more readable, with proofs. Almost no new results.

Fourth version (October 2004): detailed communication and security analysis, CPIR->OT transformations.

Fifth version (July 2005): corresponds to the published version. More readable, some improvements.

Version: 20050705:202256 (All versions of this report)

Discussion forum: Show discussion | Start new discussion