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 pa