Secure Multi-Party Computation without Agreement |
| |
Authors: | Shafi Goldwasser Yehuda Lindell |
| |
Institution: | (1) Department of Computer Science, The Weizmann Institute of Science, Rehovot 76100, Israel;(2) Department of Computer Science, Bar-Ilan University, Ramat Gan 52900, Israel |
| |
Abstract: | It has recently been shown that authenticated Byzantine agreement,
in which more than a third of the parties are corrupted, cannot be
securely realized under concurrent or parallel (stateless)
composition. This result puts into question any usage of
authenticated Byzantine agreement in a setting where many
executions take place. In particular, this is true for the whole
body of work of secure multi-party protocols in the case that a
third or more of the parties are corrupted. This is because these
protocols strongly rely on the extensive use of a broadcast
channel, which is in turn realized using authenticated Byzantine
agreement. We remark that it was accepted folklore that the use of
a broadcast channel (or authenticated Byzantine agreement) is
actually essential for achieving meaningful secure multi-party
computation whenever a third or more of the parties are corrupted.
In this paper we show that this folklore is false. We present a
mild relaxation of the definition of secure computation allowing
abort. Our new definition captures all the central security issues
of secure computation, including privacy, correctness and
independence of inputs. However, the novelty of the definition is
in decoupling the issue of agreement from these issues. We
then show that this relaxation suffices for achieving secure
computation in a point-to-point network. That is, we show that
secure multi-party computation for this definition can be achieved
for any number of corrupted parties and without a
broadcast channel (or trusted pre-processing phase as required for
running authenticated Byzantine agreement). Furthermore, this is
achieved by just replacing the broadcast channel in known
protocols with a very simple and efficient echo-broadcast
protocol. An important corollary of our result is the ability to
obtain multi-party protocols that remain secure under composition,
without assuming a broadcast channel. |
| |
Keywords: | Secure multi-party computation Broadcast Protocol composition |
本文献已被 SpringerLink 等数据库收录! |
|