ECCC-Report TR22-006https://eccc.weizmann.ac.il/report/2022/006Comments and Revisions published for TR22-006en-usWed, 12 Jan 2022 17:39:53 +0200
Paper TR22-006
| Secret Sharing, Slice Formulas, and Monotone Real Circuits |
Benny Applebaum,
Amos Beimel,
Oded Nir,
Naty Peter,
Toniann Pitassi
https://eccc.weizmann.ac.il/report/2022/006A 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 recently no better scheme was known. In a recent breakthrough, 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^{n^{1-\epsilon}}$ for some constant $\epsilon>0$, or even all the way down to polynomial upper-bounds.
In this paper, 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\'{a}k (J. Symb. Log., 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 implicitly 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. Interestingly, it seems that proving similar lower-bounds for general MRCs is beyond the reach of current techniques.
We use this connection to obtain lower-bounds against a natural family of secret-sharing schemes, as well as new non-trivial upper-bounds for MRCs. Specifically, we conclude that recent approaches for secret-sharing schemes cannot achieve sub-exponential share size and that every monotone function can be realized by an MRC (or even MRF) of complexity $1.5^{n+o(n)}$. To the best of our knowledge, this is the first improvement over the trivial $2^{n-o(n)}$ upper-bound. Along the way, we show that the recent constructions of general secret-sharing schemes implicitly give rise to Boolean formulas over slice functions and prove that such formulas can be simulated by separable MRCs of similar size. On a conceptual level, our paper continues the rich line of study that relates the share size of secret-sharing schemes to monotone complexity measures.Wed, 12 Jan 2022 17:39:53 +0200https://eccc.weizmann.ac.il/report/2022/006