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
[ Cryptology ePrint archive ]