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.
Category / Keywords: foundations / secure secure multi-party computation, verifiable secret sharing Publication Info: Full version of paper that appeared in the Proceedings of EUROCRYPT '00, Springer LNCS, May 2000. Date: received 27 Jul 2000 Contact author: cramer at brics dk, ivan@daimi aau dk, maurer@inf ethz ch Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Version: 20000727:155806 (All versions of this report) Discussion forum: Show discussion | Start new discussion