Threshold Secret Sharing Requires A Linear Size Alphabet
Siyao Guo

Abstract:

We prove that for every n and 1 < t < n, any t-out-of-n threshold secret sharing scheme for 1-bit secrets requires share size log(t + 1). Our bound is tight when t = n - 1 and n is a power of a prime. Combined with a result of Kilian and Nisan, we obtain 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. This gives a complete answer to the share complexity of threshold secret sharing for the first time in over two decades.

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. In contrast, we observe that the entropy-based framework of Csirmaz does not give any non-trivial lower bound for threshold secret sharing of a 1-bit secret.

Joint work with Andrej Bogdanov and Ilan Komargodski.