Secret Sharing, Slice Formulas, and Monotone Real Circuits
ACM Transactions on Computation Theory · 30.06.2026 · 18 (2) · 1-32
DOI: 10.1145/3812798 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, online erschienen am 16.06.2026. Verfasst von Benny Applebaum und 4 weiteren Autor:innen. Die Arbeit nennt 56 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: European Union’s Horizon 2020 Programme, Israel Science Foundation, ERC.
Abstract (Originalsprache)
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^{n^{1-\varepsilon }}\) 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.
Förderung
- European Union’s Horizon 2020 Programme
- Israel Science Foundation
- ERC
- Cyber Security Research Center at Ben-Gurion University
- NSERC, IAS School of Mathematics, and NSF Grant
Zitieren
APA
Applebaum, B., Beimel, A., Nir, O., Peter, N., & Pitassi, T. (2026). Secret Sharing, Slice Formulas, and Monotone Real Circuits. ACM Transactions on Computation Theory, 18(2), 1-32. https://doi.org/10.1145/3812798
Vancouver
Applebaum B, Beimel A, Nir O, Peter N, Pitassi T. Secret Sharing, Slice Formulas, and Monotone Real Circuits. ACM Transactions on Computation Theory. 2026;18(2):1-32. doi:10.1145/3812798
BibTeX
@article{Applebaum2026,
author = {Applebaum, Benny and Beimel, Amos and Nir, Oded and Peter, Naty and Pitassi, Toniann},
title = {Secret Sharing, Slice Formulas, and Monotone Real Circuits},
journal = {ACM Transactions on Computation Theory},
year = {2026},
volume = {18},
number = {2},
pages = {1--32},
doi = {10.1145/3812798}
}
EUVIMED