CryptoDB
Multi-Party Computation from any Linear Secret Sharing Scheme Secure against Adaptive Adversary: The Zero-Error Case
| Authors: | |
|---|---|
| Download: | |
| Abstract: | 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. |
BibTeX
@misc{eprint-2003-11724,
title={Multi-Party Computation from any Linear Secret Sharing Scheme Secure against Adaptive Adversary: The Zero-Error Case},
booktitle={IACR Eprint archive},
keywords={foundations / Multi-Party Computation, Linear Secret Sharing Schemes},
url={http://eprint.iacr.org/2003/006},
note={the paper was submitted to Eurocrypt 2003 svetla.nikova@esat.kuleuven.ac.be 12122 received 17 Jan 2003, last revised 11 Mar 2003},
author={Ventzislav Nikov and Svetla Nikova and Bart Preneel},
year=2003
}