zbMATH — the first resource for mathematics

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].

MSC:
 94A62 Authentication, digital signatures and secret sharing 11T71 Algebraic coding theory; cryptography (number-theoretic aspects) 14G50 Applications to coding theory and cryptography of arithmetic geometry
Full Text: