Yehuda Lindell
Abstract of PhD Thesis (Weizmann Inst., 2002)
Title: On the Composition of Secure Multi-Party Computation
Available:
the
thesis (in PSfile)
and
a
preface (by O.G.).
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. This computation should
be such that the outputs received by the parties are correctly
distributed, and none of the parties learn anything beyond their
prescribed output. 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, in which a single set of
parties execute a single protocol in isolation. In contrast, in
modern network settings, it is usually the case that many parties
run many protocol executions. In this thesis, we study the
feasibility of secure multi-party computation under this more
realistic setting of general composition of protocols and
executions. The main results presented are as follows:
- We show that the basic task of achieving secure broadcast is
strictly harder under composition. Specifically, in the
stand-alone model, it is known that 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 digital signatures),
unless one assumes that strictly less than one third of the
parties are corrupted.
- The above impossibility result has a serious impact on the
composition of secure multi-party protocols (when a third or more
of the parties may be corrupted). This is because all known
protocols for secure multi-party computation assume a broadcast
channel, and implement this channel in a point-to-point network
using a protocol for secure broadcast. Therefore, these
multi-party protocols do not compose. We bypass this problem as
follows. First, we provide a new definition of secure multi-party
computation that is a mild relaxation of previous definitions.
Next, we show that under this definition, secure computation of
any function can be achieved without broadcast by adapting
known protocols. As a corollary we obtain secure multi-party
protocols that compose (concurrently, when an honest majority is
assumed, and in parallel when any number of parties may be
corrupted).
- Finally, we study the feasibility of obtaining ``universally
composable'' secure multi-party computation. The composition
operation considered in the framework of universal composability
is very general. In particular, it guarantees that a secure
protocol remains secure even when run concurrently with other
arbitrary protocols. This captures the security requirements of
protocols in real settings (like that of the Internet).
Previously, it has been shown that when a majority of the parties
are assumed to be honest, universally composable protocols can be
constructed for any functionality (in the standard model). It has
also been shown that when only a minority of the parties are
honest, there are important functionalities that cannot be
securely realized in a universally composable way in the standard
model. Thus, an important open question is whether or not there
exists a reasonable model in which universally composable
multi-party computation of general functionalities can be
achieved, for an honest minority. We show that in the common
reference string model, universally composable protocols exist for
any two-party and multi-party functionality and for any number of
corrupted parties. This result establishes the feasibility of
obtaining secure two-party and multi-party computation (without an
honest majority) under the most stringent security definition
currently known.
Submitted to the Feinberg Graduate School
of the Weizmann Institute of Science, July 2002.
Available:
the
thesis (in PSfile)
and
a
preface (by O.G.).
Back to Oded Goldreich's homepage.