Cryptology ePrint Archive: Report 2007/348

A Framework for Efficient and Composable Oblivious Transfer

Chris Peikert and 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.

Category / Keywords: cryptographic protocols / oblivious transfer, universal composability, lattices

Date: received 5 Sep 2007, last revised 18 Feb 2008

Contact author: cpeikert at alum mit edu

Available format(s): PDF | BibTeX Citation

Version: 20080218:081341 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]