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 formats: PDF | BibTeX Citation Version: 20080218:081341 (All versions of this report) Discussion forum: Show discussion | Start new discussion