**Exponential Lower Bounds for Secret Sharing**

*Kasper Green Larsen and Mark Simkin*

**Abstract: **A secret sharing scheme allows a dealer to distribute shares of a
secret among a set of $n$ parties $P=\{p_1,\dots,p_n\}$ such that any
authorized subset of parties can reconstruct the secret, yet any
unauthorized subset learns nothing about it. The family $\mathcal{A}
\subseteq 2^P$ of all authorized subsets is called the access
structure. Classic results show that if $\mathcal{A}$ contains
precisely all subsets of cardinality at least $t$, then there exists a
secret sharing scheme where the length of the shares is proportional
to $\lg n$ bits plus the length of the secret. However, for general
access structures, the best known upper bounds have shares of length
exponential in $n$, whereas the strongest lower bound shows that the
shares must have length at least $n/\log n$. Beimel conjectured that
the exponential upper bound is tight, but proving it has so far
resisted all attempts. In this paper, we almost prove Beimel's
conjecture by showing that there exists an access structure
$\mathcal{A}$, such that any secret sharing scheme for $\mathcal{A}$
must have either exponential share length, or the function used for
reconstructing the secret by authorized parties must have an
exponentially long description. As an example corollary, we conclude
that if one insists that authorized parties can reconstruct the secret
via a constant fan-in boolean circuit of size polynomial in the share
length, then there exists an access structure that requires a share
length that is exponential in $n$.

**Category / Keywords: **foundations / Secret Sharing, Lower Bound

**Date: **received 18 Feb 2019

**Contact author: **larsen at cs au dk,simkin@cs au dk

**Available format(s): **PDF | BibTeX Citation

**Version: **20190226:025851 (All versions of this report)

**Short URL: **ia.cr/2019/174

[ Cryptology ePrint archive ]