Cryptology ePrint Archive: Report 2012/319

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