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 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 (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. 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 ν(q) with 0 < ν(q) < 1 when n tends to infinity. Moreover, when \(|{\mathbb F}_q|\) tends to infinity, ν(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 ≥ 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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bassa, A., Garcia, A., Stichtenoth, H.: A new tower over cubic finite fields. Moscow Mathematical Journal 8(3), 401–418 (2008)
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of STOC 1988, pp. 1–10. ACM Press, New York (1988)
Chaum, D., Crépeau, C., Damgaard, I.: Multi-party unconditionally secure protocols. In: Proceedings of STOC 1988, pp. 11–19. ACM Press, New York (1988)
Chudnovsky, D.V., Chudnovsky, G.V.: Algebraic complexities and algebraic curves over finite fields. Proceedings of the National Academy of Sciences of the United States of America 84(7), 1739–1743 (1987)
Cascudo, I., Cramer, R., Xing, C.: Ongoing work (2009)
Chen, H., Cramer, R., de Haan, R., Cascudo Pueyo, I.: Strongly multiplicative ramp schemes from high degree rational points on curves. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 451–470. Springer, Heidelberg (2008)
Chen, H., Cramer, R., Goldwasser, S., de Haan, R., Vaikuntanathan, V.: Secure Computation from Random Error Correcting Codes. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 291–310. Springer, Heidelberg (2007)
Chen, H., Cramer, R.: Algebraic Geometric Secret Sharing Schemes and Secure Multi-Party Computation over Small Fields. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 521–536. Springer, Heidelberg (2006)
Cramer, R., Daza, V., Gracia, I., Jimenez Urroz, J., Leander, G., Martí-Farré, J., Padró, C.: On codes, matroids and secure multi-party computation from linear secret sharing schemes. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 327–343. Springer, Heidelberg (2005)
Cramer, R., Fehr, S., Stam, M.: Black-Box Secret Sharing from Primitive Sets in Algebraic Number Fields. In: Shoup, V. (ed.) CRYPTO 2005, vol. 3621, pp. 344–360. Springer, Heidelberg (2005)
Cramer, R., Fehr, S.: Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 272–287. Springer, Heidelberg (2002)
Cramer, R., Damgaard, I., Dziembowski, S.: On the complexity of verifiable secret sharing and multi-party computation. In: Proceedings of STOC 2000, pp. 325–334. ACM Press, New York (2000)
Cramer, R., Damgaard, I., Maurer, U.: General secure multi-party computation from any linear secret sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000)
Damgaard, I., Buus Nielsen, J., Wichs, D.: Isolated Proofs of Knowledge and Isolated Zero Knowledge. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 509–526. Springer, Heidelberg (2008)
García, A., Stichtenoth, H.: On the asymptotic behavior of some towers of function fields over finite fields. J. Number Theory 61, 248–273 (1996)
Goppa, V.D.: Codes on algebraic curves. Soviet Math. Dokl. 24, 170–172 (1981)
Huffman, W.G., Pless, V.: Fundamentals of Error Correcting Codes. Cambridge University Press, Cambridge (2003)
Ihara, Y.: Some remarks on the number of rational points of algebraic curves over finite fields. J. Fac. Sci. Tokyo 28(3), 721–724 (1981)
Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer–Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008)
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Proceedings of 39th STOC, San Diego, Ca, USA, pp. 21–30 (2007)
Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pp. 102–111. IEEE, Los Alamitos (1993)
van Lint, J.H.: Introduction to Coding Theory. Graduate Texts in Mathematics. Springer, Heidelberg (1999)
Massey, J.L.: Minimal codewords and secret sharing. In: Proceedings of the 6-th Joint Swedish-Russian Workshop on Information Theory, Molle, Sweden, August 1993, pp. 269–279 (1993)
Massey, J.L.: Some applications of coding theory in cryptography. In: Codes and Ciphers: Cryptography and Coding IV, pp. 33–47 (1995)
Serre, J.-P.: Rational points on curves over finite fields notes of lectures at Harvard University (1985)
Shamir, A.: How to share a secret. Comm. of the ACM 22(11), 612–613 (1979)
Stichtenoth, H.: Algebraic function fields and codes. Springer, Heidelberg (1993)
Shparlinski, I., Tsfasman, M., Vladuts, S.: Curves with many points and multiplication in finite fields. In: Coding Theory and Algebraic Geometry, pp. 145–169. Springer, Heidelberg (1992)
Tsfasman, M., Vladuts, S., Nogin, D.: Algebraic-geometric codes: Basic Notions. AMS, Mathematical Surveys and Monographs, vol. 139 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cascudo, I., Chen, H., Cramer, R., Xing, C. (2009). Asymptotically Good Ideal Linear Secret Sharing with Strong Multiplication over Any Fixed Finite Field. In: Halevi, S. (eds) Advances in Cryptology - CRYPTO 2009. CRYPTO 2009. Lecture Notes in Computer Science, vol 5677. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-03356-8_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-03356-8_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-03355-1
Online ISBN: 978-3-642-03356-8
eBook Packages: Computer ScienceComputer Science (R0)