Paper 2009/031

Adaptively Secure Two-Party Computation with Erasures

Yehuda Lindell


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.

Note: Previous versions of this work contained an error regarding the \emph{adaptive security of garbled circuits} \cite{BHR}. This error is fixed here.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. An extended abstract appeared in CT-RSA 2009; this is the full version.
adaptive securitysecure computation
Contact author(s)
lindell @ cs biu ac il
2013-12-25: revised
2009-01-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yehuda Lindell},
      title = {Adaptively Secure Two-Party Computation with Erasures},
      howpublished = {Cryptology ePrint Archive, Paper 2009/031},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.