Berlin: Springer-Verlag. – 2003. – 202 p. (Lecture Notes in Computer Science 2815) In the setting of multi-party computation, sets of two or more parties with private inputs wish to jointly compute some (predetermined) function of their inputs. The computation should be such that the outputs received by the parties are correctly distributed, and furthermore, that the privacy of each party’s input is preserved as much as possible. This encompasses any distributed computing task and includes computations as simple as coin-tossing and broadcast, and as complex as electronic voting, electronic auctions, electronic cash schemes, and anonymous transactions. The feasibility (and infeasibility) of multi-party computation has been extensively studied, resulting in a seemingly comprehensive understanding of what can and cannot be securely computed, and under what assumptions. However, most of this research relates only to the stand-alone setting, where a single set of parties execute a single protocol in isolation. In contrast, in modern network settings, it is usually the case that many different sets of parties run many different protocol executions at the same time. Furthermore, an active adversary can try to utilize these many different executions in order to somehow “break” the security of the individual protocols. A protocol that is secure in such a multi-execution setting is said to remain secure under “protocol composition”. Unfortunately, protocols that are secure in the stand-alone setting do not necessarily remain secure under composition. In fact, as we show here, the situation is actually much worse. That is, in this work, we show that there exist multi-party tasks which have secure protocols for the stand-alone setting, but which cannot be solved by any protocol in the setting of composition. We demonstrate this fact on the important task of secure broadcast. Specifically, in the stand-alone model, it is known that a public-key infrastructure of digital signatures can be used in order to obtain broadcast that is secure for any number of corrupted parties. In contrast, we show that it is impossible to obtain a secure broadcast protocol that composes in parallel or concurrently (even assuming an infrastructure of digital signatures), unless one assumes that less than one third of the parties are corrupted. Thus, solving multiparty tasks when security under composition is required, is strictly harder than in the stand-alone model. An additional result presented in this work is related to the fact that all known protocols for secure multi-party computation rely extensively on a broadcast channel, and implement this channel in a point-to-point network using a protocol for secure broadcast. Table of Contents Foreword Preface Introduction The Composition of Authenticated Byzantine Agreement Secure Computation without Agreement Universally Composable Multi-party Computation References Index
Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.