Paper 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.

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.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. ISC 2005
Keywords
homomorphic public-key cryptosystemoblivious transfer
Contact author(s)
lipmaa @ cyber ee
History
2005-07-05: last of 8 revisions
2004-02-26: received
See all versions
Short URL
https://ia.cr/2004/063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/063,
      author = {Helger Lipmaa},
      title = {An Oblivious Transfer Protocol with Log-Squared Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2004/063},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/063}},
      url = {https://eprint.iacr.org/2004/063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.