TY - GEN
T1 - Secret sharing lower bound
T2 - 12th International Conference on Security and Cryptography for Networks, SCN 2020
AU - Larsen, Kasper Green
AU - Simkin, Mark
PY - 2020
Y1 - 2020
N2 - 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/\lg n$$. Beimel conjectured that the exponential upper bound is tight, but proving it has so far resisted all attempts. In this paper we make progress towards proving the 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.
AB - 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/\lg n$$. Beimel conjectured that the exponential upper bound is tight, but proving it has so far resisted all attempts. In this paper we make progress towards proving the 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.
UR - https://www.scopus.com/pages/publications/85091182805
U2 - 10.1007/978-3-030-57990-6_28
DO - 10.1007/978-3-030-57990-6_28
M3 - Article in proceedings
AN - SCOPUS:85091182805
SN - 9783030579890
T3 - Lecture Notes in Computer Science
SP - 566
EP - 578
BT - Security and Cryptography for Networks
A2 - Galdi, Clemente
A2 - Kolesnikov, Vladimir
PB - Springer
CY - Cham
Y2 - 14 September 2020 through 16 September 2020
ER -