Abstract
This lecture is the first in a series of two lectures devoted to secure multi-party computation (in ENglish: Multi-Party Computation, MPC), a secure mode of computation in which several participants cooperate to compute a function of their private data, without ever revealing it to the other participants. Unlike the homomorphic encryption approach studied in the two previous lectures, the secure multi-party approach relies on distributed algorithms implementing interactive protocols.
We have studied several schemes for sharing secret data between multiple participants: the GMW (Goldreich-Micali-Wigderson) scheme for sharing bits between two participants; full additive sharing, which generalizes GMW to any number of participants; replicated sharing "two among three", which resists the failure of one of the participants at the cost of doubling the size of the data; and finally, Shamir sharing, which withstands the failure of several participants and also enables errors made by some participants to be detected and corrected. These different schemes are instances of a general class of Linear Secret Sharing Schemes (LSSS), elegantly expressed in terms of linear algebra.
For these different schemes, we have seen how to share a secret into several parts (one per participant), how to reveal a shared secret, and how to perform arithmetic or logical operations on distributed shared secrets. While linear operations (addition, multiplication by a constant) are simple and can be performed locally by each participant, multiplying two shared secrets is more complex and requires an exchange of information between participants.
Finally, we have studied the passive or active security of these secret-sharing schemes, i.e. their ability to withstand attacks carried out by a malicious participant or a collusion of several malicious participants. In particular, the error detection and correction capabilities of the Reed-Solomon codes on which Shamir sharing is based make it possible, under certain assumptions, to guard against active attacks where malicious participants do not follow the protocol and inject incorrect values into the calculation.
