**Bounds on the Threshold Gap in Secret Sharing and its Applications**

*Ignacio Cascudo and Ronald Cramer and Chaoping Xing*

**Abstract: **We consider the class of secret sharing schemes where there is no a priori bound on the number of players $n$ but where each of the $n$ share-spaces has fixed cardinality~$q$. We show two fundamental lower bounds on the {\em threshold gap} of such schemes.
The threshold gap $g$ is defined as $r-t$, where $r$ is minimal and $t$ is maximal such that
the following holds: for a secret with arbitrary a priori distribution, each $r$-subset of players can
reconstruct this secret from their joint shares without error ($r$-reconstruction) and the information
gain about the secret is nil for each $t$-subset of players jointly ($t$-privacy).
Our first bound, which is completely general, implies that if $1\leq t<r\leq n$,
then $g \geq \frac{n-t+1}{q}$ independently of the cardinality of the secret-space. Our second bound pertains to
$\FF_q$-linear schemes with secret-space $\Fq^k$ ($k\geq 2$). It improves the first bound when $k$ is large enough. Concretely, it implies that
$g\geq\frac{n-t+1}{q}+f(q,k,t,n)$, for some function $f$ that is strictly positive when $k$ is large enough.
Moreover, also in the $\FF_q$-linear case, bounds on the threshold gap {\em independent} of $t$ or $r$ are obtained by additionally employing a dualization argument.
As an application of our results, we answer
an open question about the asymptotics of {\em arithmetic secret sharing schemes} and prove that the asymptotic optimal corruption tolerance rate is strictly smaller than~1.

**Category / Keywords: **Secret sharing, threshold gap, error correcting codes, Norse bounds, Griesmer bound, arithmetic secret sharing

**Original Publication**** (with minor differences): **IEEE Transactions on Information Theory, vol.59, no.9, pp.5600-5612, Sept. 2013
**DOI: **10.1109/TIT.2013.2264504

**Date: **received 5 Jun 2012, last revised 10 Sep 2013

**Contact author: **i cascudo at cwi nl

**Available format(s): **PDF | BibTeX Citation

**Note: **Several changes made to incorporate review suggestions, including the change of the title.

**Version: **20130910:092422 (All versions of this report)

**Short URL: **ia.cr/2012/319

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]