Cryptology ePrint Archive: Report 2012/319

Bounds on the Threshold Gap in Secret Sharing over Small Fields

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

Date: received 5 Jun 2012, last revised 27 Sep 2012

Contact author: i cascudo at cwi nl

Available formats: PDF | BibTeX Citation

Note: There is only one change compared to the first version of June 5, 2012. We have added an appendix in which we state a direct proof of a weaker bound implied by our Main Theorem 3.1, which is instructive for the reader. Indeed, it is exactly the same as that of Main Theorem 3.1, except that the weaker setting allows for a shorter exposition. It is copied from our lectures at the Chinese Academy of Sciences and at Institute of Advanced Study, Tsinghua University, May 2012.

Version: 20120927:124144 (All versions of this report)

Discussion forum: Show discussion | Start new discussion