Asymptotically good ideal linear secret sharing with strong multiplication over any fixed finite field.

*(English)*Zbl 1252.94106
Halevi, Shai (ed.), Advances in cryptology – CRYPTO 2009. 29th annual international cryptology conference, Santa Barbara, CA, USA, August 16–20, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03355-1/pbk). Lecture Notes in Computer Science 5677, 466-486 (2009).

Summary: 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 R. Cramer, I. Damgård and U. Maurer [Lect. Notes Comput. Sci. 1807, 316–334 (2000; Zbl 1082.94515)]. H. Chen and R. Cramer [Lect. Notes Comput. Sci. 4117, 521–536 (2006; Zbl 1129.94016)] proposed a special class of such schemes that is constructed from algebraic geometry and that enables efficient secure multi-party computation over fixed finite fields. 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. Second, we show that for every finite field \({\mathbb F}_q\), there exists an infinite family of LSSS over \({\mathbb F}_q\) that is asymptotically good in the following sense: the schemes are “ideal”, i.e., each share consists of a single \({\mathbb F}_q\)-element, and the schemes have t-strong multiplication on \(n\) players, where the corruption tolerance \(\frac{3t}{n-1}\) tends to a constant \(\nu (q)\) with \(0 < \nu (q) < 1\) when \(n\) tends to infinity. Moreover, when \(|{\mathbb F}_q|\) tends to infinity, \(\nu (q)\) tends to 1, which is optimal. This leads to explicit lower bounds on \(\widehat{\tau}(q)\), our measure of asymptotic optimal corruption tolerance. We achieve this by combining the results of Chen and Cramer with a dedicated field-descent method. In particular, in the \({\mathbb F}_2\)-case there exists a family of binary \(t\)-strongly multiplicative ideal LSSS with \(\frac{3t}{n-1}\approx 2.86\%\) when \(n\) tends to infinity, a one-bit secret and just a one-bit share for every player. Previously, such results were shown for \({\mathbb F}_q\) with \(q \geq 49\) a square. Third, we present an infinite family of ideal schemes with \(t\)-strong multiplication that does not rely on algebraic geometry and that works over every finite field \({\mathbb F}_q\). Its corruption tolerance vanishes, yet still \(\frac{3t}{n-1}= \Omega(1/(\log\log n)\log n)\). Fourth and finally, we give an improved non-asymptotic upper bound on corruption tolerance.

For the entire collection see [Zbl 1173.94004].

For the entire collection see [Zbl 1173.94004].