BARC talk by Kasper Green Larsen, Feb 2019

On Thursday, 7 February, associate professor, ph.d. Kasper Green Larsen, Department of Computer Science, Aarhus University, will give a talk "Exponential Lower Bounds for Secret Sharing"

Titel

Exponential Lower Bounds for Secret Sharing

Abstract

A secret sharing scheme allows a dealer to distribute shares of a secret among a set of n parties P={p_1,…,p_n} such that any authorized subset of parties can reconstruct the secret, yet any unauthorized subset learns nothing about it. The family A \subseteq 2^P of all authorized subsets is called the access structure. Classic results show that if A contains precisely all subsets of cardinality at least t, then there exists a secret sharing scheme where the length of the shares are proportional to the length of the secret. However, for general access structures, the best known upper bounds have shares of size exponential in n, whereas the strongest lower bound shows that the shares must have length at least n/logn. Beimel conjectured that the exponential upper bound is tight, but proving it has so forth resisted all attempts. In this talk, we almost prove Beimel's conjecture by showing that there exists an access structure A, such that any secret sharing scheme for A must have either exponential share lengths, 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 on reconstructing the secret via a constant fan-in boolean circuit of size polynomial in the share lengths, then the share lengths must be exponential in n.

Joint work with Mark Simkin.

Bio

Kasper Green Larsen is an assistant professor at the Department of Computer Science at Aarhus University.His research span in many areas of theoretical computer science, but in particular, he enjoys working on data structures, range searching, lower bounds, dimensionality reduction, and streaming algorithms.

Kasper received his Ph. D. from Aarhus University in 2013 and since 2017 he has been a member of the Young Academy under the Royal Danish Academy of Sciences and Letters.

Read more about Kasper Green Larsen