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)
- 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
-
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}, url = {https://eprint.iacr.org/2007/348} }