Cryptology ePrint Archive: Report 2009/031

Adaptively Secure Two-Party Computation with Erasures

Yehuda Lindell

Abstract: In the setting of multiparty computation a set of parties with private inputs wish to compute some joint function of their inputs, whilst preserving certain security properties (like privacy and correctness). An adaptively secure protocol is one in which the security properties are preserved even if an adversary can adaptively and dynamically corrupt parties during a computation. This provides a high level of security, that is arguably necessary in today's world of active computer break-ins. Until now, the work on adaptively secure multiparty computation has focused almost exclusively on the setting of an honest majority, and very few works have considered the honest minority and two-party cases. In addition, significant computational and communication costs are incurred by most protocols that achieve adaptive security.

In this work, we consider the two-party setting and assume that honest parties may \emph{erase} data. We show that in this model it is possible to securely compute any two-party functionality in the presence of \emph{adaptive semi-honest adversaries}. Furthermore, our protocol remains secure under concurrent general composition (meaning that it remains secure irrespective of the other protocols running together with it). Our protocol is based on Yao's garbled-circuit construction and, importantly, is as efficient as the analogous protocol for static corruptions. We argue that the model of adaptive corruptions with erasures has been unjustifiably neglected and that it deserves much more attention.

Category / Keywords: cryptographic protocols / adaptive security, secure computation

Publication Info: An extended abstract appeared in CT-RSA 2009; this is the full version.

Date: received 14 Jan 2009

Contact author: lindell at cs biu ac il

Available formats: PDF | BibTeX Citation

Version: 20090117:030645 (All versions of this report)

Discussion forum: Show discussion | Start new discussion