Asymptotically Good Ideal Linear Secret Sharing with Strong Multiplication over Any Finite Field

Abstract. This work deals with “MPC-friendly ” linear secret sharing schemes (LSSS), a mathematical primitive upon which secure multi-party computation (MPC) can be based and which was introduced by Cramer, Damgaard and Maurer (EUROCRYPT 2000). Chen and Cramer pro-posed a special class of such schemes that is constructed from algebraic geometry and that enables efficient secure multi-party computation over fixed finite fields (CRYPTO 2006). We extend this in four ways. First, we propose an abstract coding-theoretic framework in which this class of schemes and its (asymptotic) properties can be cast and analyzed. Sec-ond, we show that for every finite field Fq, there exists an infinite family of LSSS over Fq that is asymptotically good in the following sense: the schemes are “ideal, ” i.e., each share consists of a single Fq-element, and the schemes have t-strong multiplication on n players, where the corrup-tion tolerance 3t n−1 tends to a constant ν(q) with 0 < ν(q) < 1 when