Cryptology ePrint Archive: Report 2008/534

Somewhat Non-Committing Encryption and Efficient Adaptively Secure Oblivious Transfer

Juan A. Garay and Daniel Wichs and Hong-Sheng Zhou

Abstract: Designing efficient cryptographic protocols tolerating adaptive adversaries, who are able to corrupt parties on the fly as the computation proceeds, has been an elusive task. Indeed, thus far no \emph{efficient} protocols achieve adaptive security for general multi-party computation, or even for many specific two-party tasks such as oblivious transfer (OT). In fact, it is difficult and expensive to achieve adaptive security even for the task of \emph{secure communication}, which is arguably the most basic task in cryptography.

In this paper we make progress in this area. First, we introduce a new notion called \emph{semi-adaptive} security which is slightly stronger than static security but \emph{significantly weaker than fully adaptive security}. The main difference between adaptive and semi-adaptive security is that, for semi-adaptive security, the simulator is not required to handle the case where \emph{both} parties start out honest and one becomes corrupted later on during the protocol execution. As such, semi-adaptive security is much easier to achieve than fully adaptive security. We then give a simple, generic protocol compiler which transforms any semi-adaptively secure protocol into a fully adaptively secure one. The compilation effectively decomposes the problem of adaptive security into two (simpler) problems which can be tackled separately: the problem of semi-adaptive security and the problem of realizing a weaker variant of secure channels.

We solve the latter problem by means of a new primitive that we call {\em somewhat non-committing encryption} resulting in significant efficiency improvements over the standard method for realizing (fully) secure channels using (fully) non-committing encryption. Somewhat non-committing encryption has two parameters: an equivocality parameter $\ell$ (measuring the number of ways that a ciphertext can be ``opened'') and the message sizes $k$. Our implementation is very efficient for small values $\ell$, \emph{even} when $k$ is large. This translates into a very efficient compilation of many semi-adaptively secure protocols (in particular, for a task with small input/output domains such as bit-OT) into a fully adaptively secure protocol.

Finally, we showcase our methodology by applying it to the recent Oblivious Transfer protocol by Peikert \etal\ [Crypto 2008], which is only secure against static corruptions, to obtain the first efficient, adaptively secure and composable OT protocol. In particular, to transfer an $n$-bit message, we use a constant number of rounds and $O(n)$ public key operations.

Category / Keywords: cryptographic protocols /

Date: received 19 Dec 2008, last revised 15 Apr 2009

Contact author: hszhou at cse uconn edu

Available format(s): PDF | BibTeX Citation

Version: 20090415:173455 (All versions of this report)

Short URL: ia.cr/2008/534

Discussion forum: Show discussion | Start new discussion