Unconditionally secure computation with reduced interaction

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

We study the question of how much interaction is needed for unconditionally secure multiparty computation. We first consider the number of messages that need to be sent to compute a Boolean function with semi-honest security, where all n parties learn the result. We consider two classes of functions called t-difficult and t-very difficult functions, where t refers to the number of corrupted players. For instance, the AND of an input bit from each player is t-very difficult while the XOR is t-difficult but not t-very difficult. We show lower bounds on the message complexity of both types of functions, considering two notions of message complexity called conservative and liberal, where conservative is the more standard one. In all cases the bounds are Ω(nt). We also show (almost) matching upper bounds for t = 1 and functions in a rich class PSMeff including non-deterministic log-space, as well as a stronger upper bound for the XOR function. In particular, we find that the conservative message complexity of 1-very difficult functions in PSMeff is 2n, while the conservative message complexity for XOR (and t = 1) is 2n − 1. Next, we consider round complexity. It is a long-standing open problem to determine whether all efficiently computable functions can also be efficiently computed in constant-round with unconditional security. Motivated by this, we consider the question of whether we can compute any function securely, while minimizing the interaction of some of the players? And if so, how many players can this apply to? Note that we still want the standard security guarantees (correctness, privacy, termination) and we consider the standard communication model with secure point-to-point channels. We answer the questions as follows: for passive security, with n = 2t + 1 players and t corruptions, up to t players can have minimal interaction, i.e., they send 1 message in the first round to each of the t + 1 remaining players and receive one message from each of them in the last round. Using our result on message complexity, we show that this is (unconditionally) optimal. For malicious security with n = 3t + 1 players and t corruptions, up to t players can have minimal interaction, and we show that this is also optimal.

Original languageEnglish
Title of host publicationAdvances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsMarc Fischlin, Jean-Sébastien Coron
Number of pages28
Volume9666
PublisherSpringer VS
Publication year2016
Pages420-447
ISBN (print)9783662498958
ISBN (Electronic)978-3-662-49896-5
DOIs
Publication statusPublished - 2016
Event35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016 - Vienna, Austria
Duration: 8 May 201612 May 2016

Conference

Conference35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016
LandAustria
ByVienna
Periode08/05/201612/05/2016
SponsorInternational Association for Cryptologic Research (IACR)
SeriesLecture Notes in Computer Science
Volume9666
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 108278818