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

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.

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