Secret Sharing, Slice Formulas, and Monotone Real Circuits

on YouTube ↗33m

" summary

Proves that recent secret sharing techniques cannot achieve subexponential complexity by exhibiting a monotone P function whose schemes (and corresponding constructions) need size at least 2^{Ω(n / log^2 n)}. Key tools are a reduction from secret sharing to formulas over slices, Rosenblum’s transform to separable monotone real circuits, and lower bounds via real Karchmer–Wigderson protocols; also provides matching upper bounds showing all three models admit constructions of size at most (3/2)^n.

AI-written summary · about

" chapters (12)

1. 0:00Secret Sharing, Slice Formulas, and Monotone Real Circuits
2. 0:18Talk Overview
3. 0:57Our Goal: Lower Bounds
4. 7:25Secret Sharing for General Access Structures The share size for n-party general access structure
5. 8:41Slice functions
6. 10:07Formulas over Slices and Secret Sharing
7. 15:19Back to the Big Picture
8. 17:15Lower bounds for a family of MR-Circuits
9. 19:19Real Communication Complexity for kW Protocols
10. 21:23From MR-circuits to Protocols
11. 26:09Separable circuits = balanceable protocols
12. 31:14Conclusion: Open Questions New connection between Secret Sharing and Monotone Complexity Theory . Continues long line of works

" related talks

• 01h 00mSecure Computation 3Peter Scholl · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 44mObfuscation IIIAayush Jain · Lattices: New Cryptographic Capabilities 2020
• 01h 08mSecure Computation 1Peter Scholl · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023
• 29mTowards Scalable Constant-Round MPC from Minimal Assumptions via Round CollapsingVipul Goyal · Secure Computation 2025
• 01h 04mHow to Encrypt a FunctionalityAmit Sahai · Quantum Games and Protocols
• 41mReducibility and Statistical-Computational Gaps from Secret LeakageGuy Bresler · Computational Phase Transitions (Simons Institute, 2020)
• 01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional ExpandersMax Hopkins · Beyond the Boolean Cube 2023