International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: A Framework for Efficient and Composable Oblivious Transfer

Authors:
Chris Peikert
Vinod Vaikuntanathan
Brent Waters
Download:
URL: http://eprint.iacr.org/2007/348
Search ePrint
Search Google
Abstract: We propose and simple, general, and unified 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, such as the decisional Diffie-Hellman assumption and the Quadratic Residuosity assumption. Most interestingly, we can also instantiate our framework with \emph{worst-case} complexity assumptions relating to \emph{lattices}. Our OT protocols are round-optimal (one message each way), efficient in the parties' communication and local computation, and use only one reference string for an unbounded number of executions. Furthermore, the protocols can provide \emph{unconditional} security to either the sender or receiver, simply by changing the distribution of the reference string. (For several versions of the protocol, even a common \emph{random} string suffices.) One of our key technical contributions is a simple and novel abstraction that we call a \emph{dual-mode} cryptosystem. We implement dual-mode cryptosystems by taking a unified view of several cryptosystems in the literature that have what we call ``message-lossy'' public keys, whose defining property is that a ciphertext produced under such a key carries \emph{no information} (even 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 particular, the amortized runtime per message bit is only $\tilde{O}(n)$ bit operations, and the ciphertext expansion can be made as small as a constant.
BibTeX
@misc{eprint-2007-13628,
  title={A Framework for Efficient and Composable Oblivious Transfer},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / oblivious transfer, universal composability, lattices},
  url={http://eprint.iacr.org/2007/348},
  note={ cpeikert@alum.mit.edu 13761 received 5 Sep 2007},
  author={Chris Peikert and Vinod Vaikuntanathan and Brent Waters},
  year=2007
}