Theory of Computing
-------------------
Title : Threshold Secret Sharing Requires a Linear-Size Alphabet
Authors : Andrej Bogdanov, Siyao Guo, and Ilan Komargodski
Volume : 16
Number : 2
Pages : 1-18
URL : http://www.theoryofcomputing.org/articles/v016a002
Abstract
--------
We prove that for every $n$ and $1 < t < n$ any $t$-out-of-$n$
threshold secret sharing scheme for one-bit secrets requires share
size $\log(t + 1)$. Our bound is tight when $t = n - 1$ and $n$ is a
prime power. In 1990 Kilian and Nisan proved the incomparable bound
$\log(n - t + 2)$. Taken together, the two bounds imply that the share
size of Shamir's secret sharing scheme (Comm. ACM 1979) is optimal up to
an additive constant even for one-bit secrets for the whole range of
parameters $1 < t < n$. More generally, we show that for all
$1 < s < r < n$, any ramp secret sharing scheme with secrecy
threshold $s$ and reconstruction threshold $r$ requires share size
$\log((r + 1)/(r - s))$. As part of our analysis we formulate a
simple game-theoretic relaxation of secret sharing for arbitrary
access structures. We prove the optimality of our analysis for
threshold secret sharing with respect to this method and point out
a general limitation.