Paper 2025/046
The Meta-Complexity of Secret Sharing
Benny Applebaum, Tel Aviv University
Oded Nir, Tel Aviv University
Abstract
A secret-sharing scheme allows the distribution of a secret among parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about . The collection of authorized/unauthorized sets is defined by a monotone function . It is known that any monotone function can be realized by a secret-sharing scheme; thus, the smallest achievable \emph{total share size}, , serves as a natural complexity measure.
In this paper, we initiate the study of the following meta-complexity question: Given a monotone function , is it possible to efficiently distinguish between cases where the secret-sharing complexity of is small versus large? We examine this question across several computational models, yielding the following main results.
(Hardness for formulas and circuits): Given a monotone formula of size , it is coNP-hard to distinguish between ``cheap'' functions, where the maximum share size is 1 bit and the total share size is , and ``expensive'' functions, where the maximum share size is and the total share size is .
This latter bound nearly matches known secret-sharing constructions yielding a total share size of bits. For monotone circuits, we strengthen the bound on the expensive case to a maximum share size of and a total share size of . These results rule out the existence of instance-optimal compilers that map a formula to a secret-sharing scheme with complexity polynomially related to .
(Hardness for truth tables): Under cryptographic assumptions, either (1) every -bit slice function can be realized by a -size secret-sharing scheme, or (2) given a truth-table representation of of size , it is computationally infeasible to distinguish in time between cases where and . Option (1) would be considered a breakthrough result, as the best-known construction for slices has a sub-exponential complexity of (Liu, Vaikuntanathan, and Wee; Eurocrypt 2018). Our proof introduces a new worst-case-to-average-case reduction for slices, which may be of independent interest.
(Hardness for graphs): We examine the simple case where is given as a 2-DNF, represented by a graph whose edges correspond to 2-terms, and ask whether it is possible to distinguish between cases where the share size is constant and those where the share size is large, say . We establish several connections between this question and questions in communication complexity. For instance, we show that graphs admitting constant-cost secret sharing form a subclass of graphs with constant randomized communication complexity and constant-size adjacency sketches (Harms, Wild, and Zamaraev; STOC 2022). We leverage these connections to establish new lower bounds for specific graph families, derive a combinatorial characterization of graphs with constant-size linear secret-sharing schemes, and show that a natural class of myopic algorithms fails to distinguish cheap graphs from expensive ones.