[Resource Topic] 2002/040: Secure Computation Without Agreement

Welcome to the resource topic for 2002/040

Secure Computation Without Agreement

Authors: Shafi Goldwasser, Yehuda Lindell


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 {\em 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 {\em any} number of corrupted parties and {\em without} a
broadcast channel (or trusted preprocessing 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.

ePrint: https://eprint.iacr.org/2002/040

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .