Threshold Secret Sharing Requires a Linear Size Alphabet

A $t$-out-of-$n$ threshold secret sharing scheme is a protocol for sharing a secret among $n$ parties so that no $t -1$ parties gain any information about the secret but any $t$ parties can recover the secret.

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)$ (in bits). Our bound is tight when $t = n - 1$ and $n$ is a prime power. Together with a result of Kilian and Nisan, this implies a share size lower bound of $\max\{\log(n - t + 2), \log(t + 1)\} ≥ \log ((n + 3)/2)$ for every $n$ and $1 < t < n$.

Our proof introduces a new semidefinite programming framework for proving share size lower bounds for general access structures. We show that our analysis for threshold secret sharing is tight in this framework (the talk is based on joint work with Siyao Guo and Ilan Komargodski).