Paper 2007/348

A Framework for Efficient and Composable Oblivious Transfer

Chris Peikert, Vinod Vaikuntanathan, and Brent Waters

Abstract

We propose a simple and general framework for constructing oblivious transfer (OT) protocols that are \emph{efficient}, \emph{universally composable}, and \emph{generally realizable} from a variety of standard number-theoretic assumptions, including the decisional Diffie-Hellman assumption, the quadratic residuosity assumption, and \emph{worst-case} lattice assumptions. Our OT protocols are round-optimal (one message each way), quite efficient in computation and communication, and can use a single common string for an unbounded number of executions. Furthermore, the protocols can provide \emph{statistical} security to either the sender or receiver, simply by changing the distribution of the common string. For certain instantiations of the protocol, even a common \emph{random} string suffices. Our key technical contribution is a simple abstraction that we call a \emph{dual-mode} cryptosystem. We implement dual-mode cryptosystems by taking a unified view of several cryptosystems that have what we call ``messy'' public keys, whose defining property is that a ciphertext encrypted under such a key carries \emph{no information} (statistically) about the encrypted message. As a contribution of independent interest, we also provide a multi-bit version of Regev's lattice-based cryptosystem (STOC 2005) whose time and space efficiency are improved by a linear factor in the security parameter $n$. The amortized encryption and decryption time is only $\tilde{O}(n)$ bit operations per message bit, and the ciphertext expansion can be made as small as a constant; the public key size and underlying lattice assumption remain essentially the same.

Note: Fixed a minor error in the DDH-based instantiation, pointed out by Claudio Orlandi and Peter Scholl.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2008
Keywords
oblivious transferuniversal composabilitylattices
Contact author(s)
cpeikert @ alum mit edu
History
2019-01-23: last of 2 revisions
2007-09-06: received
See all versions
Short URL
https://ia.cr/2007/348
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/348,
      author = {Chris Peikert and Vinod Vaikuntanathan and Brent Waters},
      title = {A Framework for Efficient and Composable Oblivious Transfer},
      howpublished = {Cryptology ePrint Archive, Paper 2007/348},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/348}},
      url = {https://eprint.iacr.org/2007/348}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.