The Torsion-Limit for Algebraic Function Fields and Its Application to Arithmetic Secret Sharing

Abstract. An (n, t, d, n−t)-arithmetic secret sharing scheme (with uni-formity) for Fkq over Fq is an Fq-linear secret sharing scheme where the secret is selected from Fkq and each of the n shares is an element of Fq. Moreover, there is t-privacy (in addition, any t shares are uniformly ran-dom in Ftq) and, if one considers the d-fold “component-wise ” product of any d sharings, then the d-fold component-wise product of the d respec-tive secrets is (n − t)-wise uniquely determined by it. Such schemes are a fundamental primitive in information-theoretically secure multi-party computation. Perhaps counter-intuitively, secure multi-party computa-tion is a very powerful primitive for communication-efficient two-party cryptography, as shown recently in a series of surprising results from 2007 on. Moreover, the existence of asymptotically good arithmetic secret sharing schemes plays a crucial role in their communication-efficiency: for each d ≥ 2, if A(q)> 2d, where A(q) is Ihara’s constant, then there ex-ists an infinite family of such schemes over Fq such that n is unbounded, k = Ω(n) and t = Ω(n), as follows from a result at CRYPTO’06. Our main contribution is a novel paradigm for constructing asymptotically good arithmetic secret sharing schemes from towers of algebraic func-tion fields. It is based on a new limit that, for a tower with a given Ihara limit and given positive integer , gives information on the cardi-nality of the -torsion sub-groups of the associated degree-zero divisor class groups and that we believe is of independent interest. As an appli-cation of the bounds we obtain, we relax the condition A(q)> 2d from the CRYPTO’06 result substantially in terms of our torsion-limit. As a consequence, this result now holds over nearly all finite fields Fq. For example, if d = 2, it is sufficient that q = 8, 9 or q ≥ 16.