Threshold Secret Sharing Requires a Linear Size Alphabet

Speaker: 

Andrej Bogdanov

Affiliation: 

The Chinese University of Hong Kong
Shatin, NT
Hong Kong SAR
The Peoples Republic of China

Time: 

Wednesday, 2 March 2016, 16:00 to 17:00

Venue: 

  • A-201 (STCS Seminar Room)

Organisers: 

Abstract: 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).