We provide a complete investigation of security in the presence of semi-honest adversaries---static and adaptive, with and without erasures---and initiate the study of security in the presence of malicious adversaries. For semi-honest static adversaries, our bounds essentially match the corresponding bounds when there is no communication restriction---i.e., we can tolerate up to t < (1/2 - \epsilon)n corrupted parties. For the adaptive case, however, the situation is different. We prove that without erasures even a small constant fraction of corruptions is intolerable, and---more surprisingly---when erasures are allowed, we prove that t < (1- \sqrt(0.5) -\epsilon)n corruptions can be tolerated, which we also show to be essentially optimal. The latter optimality proof hinges on a new treatment of probabilistic adversary structures that may be of independent interest. In the case of active corruptions in the sublinear communication setting, we prove that static “security with abort” is feasible when t < (1/2 - \epsilon)n, namely, the bound that is tight for semi-honest security. All of our negative results in fact rule out protocols with sublinear message complexity.
Category / Keywords: cryptographic protocols / Secure multi-party computation; Oblivious Transfer; adversary structures Original Publication (with minor differences): IACR-CRYPTO-2017 Date: received 2 Jun 2017, last revised 5 Jun 2017 Contact author: juan a garay at gmail com Available format(s): PDF | BibTeX Citation Version: 20170606:052816 (All versions of this report) Short URL: ia.cr/2017/520 Discussion forum: Show discussion | Start new discussion