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 veri-fiability 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 Γ_1 and Γ_2 a new MSP M called "resulting" is obtained. M computes a new access structure Γis contained in Γ_1 (or Γ_2). The goal of this construction is to enable the investigation of how the properties that Γ should fulfil are linked to the initial access structures Γ_1 and Γ_2 It is proved that Γ_2 should be a dual access structure of Γ_I 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 (Γ_A⊕Γ_A)~⊥is contained in Γ. In this paper we assume that the resulting MSP could be constructed such that the corresponding access structure Γ satisfies the required properties. Our goal is to study the requirements that Γ should fulfil in order to have an MPC unconditionally secure against adaptive and active adversary in the zero error case. First, we prove that Γ could satisfy weaker conditions than those in Nikov et al., namely Γ_A~⊥is contained in Γ. Second, we propose a commitment "degree reduction" protocol which allows the players to "reduce" one access structure, e.g. Γ, to another access structure Γ_3 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 Γ to the initial access structures Γ_1 or Γ_2, or to a new one Γ_3. This protocol is also more efficient, since it requires less Verifiable Secret Sharing Schemes to be used.