Multi-party computation from any linear secret sharing scheme unconditionally secure against adaptive adversary : the zero-error case

We consider a generalized adaptive and active adversary model for unconditionally secure Multi-Party Computation (MPC) in the zero error case. Cramer et al. proposed a generic approach to build a multiplicative Monotone Span Programs (MSP) – the special property of a Linear Secret Sharing Schemes (LSSS) that is needed to perform a multiplication of shared values. They give an efficient generic construction to build verifiability into every LSSS and to obtain from any LSSS a multiplicative LSSS for the same access structure. But the multiplicative property guarantees security against passive adversary only. For an active adversary a strong multiplicative property is required. Unfortunately there is no known efficient construction to obtain a strongly multiplicative LSSS yet. Recently Nikov et al. have expanded the construction of Cramer et al. using a different approach. Multiplying two different MSP M 1 and M 2 computing the access structures G1 and G2 a new MSP M called "resulting" is obtained. M computes a new access structure G¿¿¿G1 (or G2). The goal of this construction is to enable the investigation of how the properties that G should fulfil are linked to the initial access structures G1 and G2. It is proved that G2 should be a dual access structure of G1 in order to have a multiplicative resulting MSP. But there are still not known requirements for initial access structures in order to obtain strongly multiplicative resulting MSP. Nikov et al. proved that to have unconditionally secure MPC the following minimal conditions for the resulting access structure should be satisfied (G A ¿G A ) ¿ ¿G . In this paper we assume that the resulting MSP could be constructed such that the corresponding access structure G satisfies the required properties. Our goal is to study the requirements that G should fulfil in order to have an MPC unconditionally secure against adaptive and active adversary in the zero error case. First, we prove that G could satisfy weaker conditions than those in Nikov et al., namely G ¿ A ¿G . Second, we propose a commitment "degree reduction" protocol which allows the players to "reduce" one access structure, e.g. G, to another access structure G3. This reduction protocol appears to be a generalization of the reduction protocol of Cramer et al. in the sense that we can choose to reduce G to the initial access structures G1 or G2, or to a new one G3. This protocol is also more efficient, since it requires less Verifiable Secret Sharing Schemes to be used.