Welcome to the resource topic for 2000/037
Title:
General Secure Multi-Party Computation from any Linear Secret Sharing Scheme
Authors: Ronald Cramer, Ivan Damgård, Ueli Maurer
Abstract:We show that verifiable secret sharing (VSS) and secure multi-party
computation (MPC) among a set of n players can efficiently be based
on {\em any} linear secret sharing scheme (LSSS) for the players,
provided that the access structure of the LSSS allows MPC or VSS at
all. Because an LSSS neither guarantees reconstructability when some
shares are false, nor verifiability of a shared value, nor allows for
the multiplication of shared values, an LSSS is an apparently much weaker
primitive than VSS or MPC.
Our approach to secure MPC is generic and applies to both the
in-for-ma-tion-theoretic and the cryptographic setting. The
construction is based on 1) a formalization of the special
multiplicative property of an LSSS that is needed to perform a
multiplication on shared values, 2) an efficient generic construction
to obtain from any LSSS a multiplicative LSSS for the same access
structure, and 3) an efficient generic construction to build
verifiability into every LSSS (always assuming that the adversary
structure allows for MPC or VSS at all).
The protocols are efficient. In contrast to all previous
information-theo-re-ti-cal-ly secure protocols, the field size is not
restricted (e.g, to be greater than n). Moreover, we exhibit
adversary structures for which our protocols are polynomial in n
while all previous approaches to MPC for non-threshold adversaries
provably have super-polynomial complexity.
ePrint: https://eprint.iacr.org/2000/037
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 .