Paper 2003/006

Multi-Party Computation from any Linear Secret Sharing Scheme Secure against Adaptive Adversary: The Zero-Error Case

Ventzislav Nikov, Svetla Nikova, and Bart Preneel


We use a general treatment of both information-theoretic and cryptographic settings for Multi-Party Computation (MPC), based on the underlying linear secret sharing scheme. Our goal is to study the Monotone Span Program (MSP), which is the result of local multiplication of shares distributed by two given MSPs as well as the access structure that this resulting MSP computes. First, we expand the construction proposed by Cramer et~al. multiplying two different general access structures and we prove some properties of the resulting MSP ${\cal M}$. Next we expand the definition of multiplicative MSPs and we prove that when one uses dual MSPs only all players together can compute the product, i.e., the construction proposed by Cramer et~al. gives only multiplicative MPC. Third, we propose a solution for the strongly multiplicative MPC (in presence of adversary). The knowledge of the resulting MSP and the access structure it computes allows us to build an analog of the algebraic simplification protocol of Gennaro et~al. We show how to achieve in the computational model MPC secure against adaptive adversary in the zero-error case, through the application of homomorphic commitments. There is an open problem how efficiently we can determine $\Gamma$ the access structure of the resulting MSP ${\cal M}$. This open problem reflects negatively on the efficiency of the proposed solution.

Note: 1. The title of the paper was changed. 2. A revised version.

Available format(s)
Publication info
Published elsewhere. the paper was submitted to Eurocrypt 2003
Multi-Party ComputationLinear Secret Sharing Schemes
Contact author(s)
svetla nikova @ esat kuleuven ac be
2003-03-11: last of 2 revisions
2003-01-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ventzislav Nikov and Svetla Nikova and Bart Preneel},
      title = {Multi-Party Computation from any Linear Secret Sharing Scheme Secure against Adaptive Adversary: The Zero-Error Case},
      howpublished = {Cryptology ePrint Archive, Paper 2003/006},
      year = {2003},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.