Paper 2000/037

General Secure Multi-Party Computation from any Linear Secret Sharing Scheme

Ronald Cramer, Ivan Damgård, and 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.

Metadata
Available format(s)
PS
Category
Foundations
Publication info
Published elsewhere. Full version of paper that appeared in the Proceedings of EUROCRYPT '00, Springer LNCS, May 2000.
Keywords
secure secure multi-party computationverifiable secret sharing
Contact author(s)
cramer @ brics dk
ivan @ daimi aau dk
maurer @ inf ethz ch
History
2000-07-27: received
Short URL
https://ia.cr/2000/037
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/037,
      author = {Ronald Cramer and Ivan Damgård and Ueli Maurer},
      title = {General Secure Multi-Party Computation from any Linear Secret Sharing Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2000/037},
      year = {2000},
      note = {\url{https://eprint.iacr.org/2000/037}},
      url = {https://eprint.iacr.org/2000/037}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.