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

An $(n,t,d,n-t)$-arithmetic secret sharing scheme (with uniformity) for $\Fq^k$ over $\Fq$ is an $\Fq$-linear secret sharing scheme where the secret is selected from $\Fq^k$ and each of the $n$ shares is an element of $\Fq$. Moreover, there is $t$-privacy (in addition, any $t$ shares are uniformly random in $\Fq^t$) and, if one considers the $d$-fold ``component-wise'' product of any $d$ sharings, then the $d$-fold component-wise product of the $d$ respective 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 {\em multi-party} computation is a very powerful primitive for {\em communication-efficient two-party} cryptography, as shown recently in a series of surprising results from 2007 on. Moreover, the existence of {\em asymptotically good} arithmetic secret sharing schemes plays a crucial role in their communication-efficiency: for each $d\geq 2$, if $A(q)>2d$, where $A(q)$ is Ihara's constant, then there exists an infinite family of such schemes over $\Fq$ such that $n$ is unbounded, $k=\Omega(n)$ and $t=\Omega(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 function fields. It is based on a new limit that, for a tower with a given Ihara limit and given positive integer $\ell$, gives information on the cardinality of the $\ell$-torsion sub-groups of the associated degree-zero divisor class groups and that we believe is of independent interest. As an application 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 {\em nearly all finite fields} $\Fq$. For example, if $d=2$, it is sufficient that $q=8,9$ or $q\geq 16$.