The Meta-complexity of Secret Sharing

A secret-sharing scheme allows the distribution of a secret s among n parties, such that only certain predefined “authorized” sets of parties can reconstruct the secret, while all other “unauthorized” sets learn nothing about s. The collection of authorized/unauthorized sets is defined by a monotone function f: 0,1n → 0,1. It is known that any monotone function can be realized by a secret-sharing scheme; thus, the smallest achievable total share size, S(f), serves as a natural complexity measure. In this paper, we initiate the study of the following meta-complexity question: Given a monotone function f, is it possible to efficiently distinguish between cases where the secret-sharing complexity of f 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 f of size L, it is coNP-hard to distinguish between “cheap” functions, where the maximum share size is 1 bit and the total share size is O(L0.01), and “expensive” functions, where the maximum share size is Ω(√L) and the total share size is Ω(L/logL). This latter bound nearly matches known secret-sharing constructions yielding a total share size of L bits. For monotone circuits, we strengthen the bound on the expensive case to a maximum share size of Ω(L/logL) and a total share size of Ω(L2/logL). These results rule out the existence of instance-optimal compilers that map a formula f to a secret-sharing scheme with complexity polynomially related to S(f). (Hardness for truth tables): Under cryptographic assumptions, either (1) every n-bit slice function can be realized by a poly(n)-size secret-sharing scheme, or (2) given a truth-table representation of f of size N = 2n, it is computationally infeasible to distinguish in time poly(N) between cases where S(f) = poly(n) and S(f) = nω(1). Option (1) would be considered a breakthrough result, as the best-known construction for slices has a sub-exponential complexity of 2Õ(√n) (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 f is given as a 2-DNF, represented by a graph G 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 Ω(logn). 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.