2008 | OriginalPaper | Buchkapitel
Almost-Everywhere Secure Computation
verfasst von : Juan A. Garay, Rafail Ostrovsky
Erschienen in: Advances in Cryptology – EUROCRYPT 2008
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Secure multi-party computation (MPC) is a central problem in cryptography. Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large connectivity — in fact,
Ω
(
t
), where
t
is the number of potential corruptions in the network. This impossibility result renders existing MPC results far less applicable in practice, since many deployed networks have in fact a very small degree.
In this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call
almost-everywhere MPC
, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. In essence, our definition allows the adversary to
implicitly
wiretap some of the good nodes by corrupting sufficiently many nodes in the “neighborhood” of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions.
Instrumental in our constructions is a new model and protocol for the
secure message transmission
(SMT) problem, which we call
SMT by public discussion
, and which we use for the establishment of pairwise secure channels in limited connectivity networks.