Paper 2012/319
Bounds on the Threshold Gap in Secret Sharing and its Applications
Ignacio Cascudo, 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$ sharespaces 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 $rt$, 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{nt+1}{q}$ independently of the cardinality of the secretspace. Our second bound pertains to $\FF_q$linear schemes with secretspace $\Fq^k$ ($k\geq 2$). It improves the first bound when $k$ is large enough. Concretely, it implies that $g\geq\frac{nt+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.
Note: Several changes made to incorporate review suggestions, including the change of the title.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. MINOR revision.IEEE Transactions on Information Theory, vol.59, no.9, pp.56005612, Sept. 2013
 DOI
 10.1109/TIT.2013.2264504
 Keywords
 Secret sharingthreshold gaperror correcting codesNorse boundsGriesmer boundarithmetic secret sharing
 Contact author(s)
 i cascudo @ cwi nl
 History
 20130910: last of 3 revisions
 20120605: received
 See all versions
 Short URL
 https://ia.cr/2012/319
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/319, author = {Ignacio Cascudo and Ronald Cramer and Chaoping Xing}, title = {Bounds on the Threshold Gap in Secret Sharing and its Applications}, howpublished = {Cryptology ePrint Archive, Paper 2012/319}, year = {2012}, doi = {10.1109/TIT.2013.2264504}, note = {\url{https://eprint.iacr.org/2012/319}}, url = {https://eprint.iacr.org/2012/319} }