From Secret Sharing to Multiparty. Computation In this section we give a very high level overview of how an arithmetic secret sharing scheme can be used to build a secure multiparty computation protocol. The purpose of secure multiparty computation is to implement the following functionality: n players want to jointly evaluate a function f : Fn → F of their inputs x1, . . . , xn in a way that ensures the correctness of the outcome and protects the privacy of the parties. We assume the existence of an external adversary who can corrupt a fixed number of players in order to obtain addition information about the other inputs. Here privacy is meant against such an adversary. We now sketch how this is performed in practice and how the properties of the scheme are exploited. At the beginning of the protocol, each player uses the secret sharing scheme to share his own input with all other players. The privacy property of the scheme hides each input from other players. × × × Throughout the protocol, the function f is modeled as a sequence of + and binary gates, and the arithmetic properties of the scheme are used to guarantee the following: if a player enters the gate y + z (y z respectively) with valid shares of y and z, then he exits the gate with a valid share of y + z (y z respectively). At the end of the protocol, each player possesses a valid share of the output f (x1, . . . , xn), which can therefore be reconstructed thanks to the reconstruc- tion property of the scheme. We give more details on how the protocol proceeds through the gates. For all i = 1, . . . , n, let yi and zi denote the i-th share of y and z respectively. As seen in the previous section, yi + zi is a valid share of y + z, hence at every × + gate each player is simply required to sum the shares in his possession. On the other hand, gates require more work and actual interaction among the players. → ∈ Recall that, as the scheme is multiplicative, there exists a linear product re- construction function ρ∗ : Fn F such that, for any pair of secrets s, s′ ∈ ∈ F with corresponding shares x1, . . . , xn F and x1′ , . . . , x′n F, we have ρ∗(x1x1′ , . . . , xnxn′ ) = ss′. As ρ∗ is linear, we can identify it with a list of coefficients ρ1∗, . . . , ρ∗n ∈ F such that Σ n ss′ = ρ∗i xix′i i=1 for any pair of secrets and list of shares as above. Let us highlight that the reconstruction function, being a property of the scheme, is assumed to be publicly known by all players, and so are the coefficients ρ∗i ’s. × For all i = 1, . . . , n...
