עמוס ביימל

A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about s. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size 2^n-o(n) and until recent years no better scheme was known. In a breakthrough result, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 2^0.994n+o(n), and this was further improved by several follow-ups accumulating in an upper bound of 1.5^n+o(n) (Applebaum and Nir, CRYPTO 2021). Following these advances, it is natural to ask whether these new approaches can lead to a truly sub-exponential upper-bound of 2^n1-ε for some constant ∊ > 0, or even down to polynomial upper-bounds. In this article, we relate this question to the complexity of computing monotone Boolean functions by monotone real circuits (MRCs)-a computational model that was introduced by Pudlák (JSL, 1997) in the context of proof complexity. We introduce a new notion of “separable” MRCs that lies between monotone real circuits and monotone real formulas (MRFs). As our main results, we show that recent constructions of general secret-sharing schemes give rise to separable MRCs for general monotone functions of similar complexity, and that some monotone functions (in monotone NP) cannot be computed by sub-exponential size separable MRCs. Consequently, recent approaches for secret-sharing schemes cannot achieve sub-exponential share size. We also use this connection to show that every monotone function can be realized by an MRC (or even MRF) of complexity 1.5^n+o(n), obtaining the first improvement over the trivial 2^n-o(n) upper-bound. Along the way, we initiate the study of formulas over slices and relate this computational model to secret-sharing schemes and separable MRCs.