Welcome to the resource topic for 2012/319
Title:
Bounds on the Threshold Gap in Secret Sharing and its Applications
Authors: Ignacio Cascudo, Ronald Cramer, 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.
ePrint: https://eprint.iacr.org/2012/319
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .