Tata Institute of Fundamental Research
Threshold Secret Sharing Requires a Linear Size Alphabet
STCS Colloquium
Speaker:
Andrej Bogdanov (The Chinese University of Hong Kong
Shatin, NT
Hong Kong SAR
The Peoples Republic of China)
Organiser:
Prahladh Harsha
Date:
Wednesday, 2 Mar 2016, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Andrej Bogdanov (The Chinese University of Hong Kong Shatin, NT Hong Kong SAR The Peoples Republic of China) |
| Organiser: | Prahladh Harsha |
| Date: | Wednesday, 2 Mar 2016, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).