Paper 2026/1667

Resolving the Worst-Case Complexity of Linear Secret Sharing

Abstract

A secret-sharing scheme allows a dealer to distribute a secret among $n$ parties such that only predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about it. Families of authorized sets are called access structures, and a scheme is called linear if its sharing map is linear in the secret and the dealer’s randomness. We show that every $n$-party access structure can be realized by a linear secret-sharing scheme over every finite field with at most $2^{\lceil n/2\rceil-1}+1$ field elements per share. Taking the field to be $\mathbb{F}_2$ yields the same bound in bits for one-bit secrets. A known counting lower bound for monotone span programs shows that for every fixed finite field, almost all access structures require share size $2^{n/2-o(n)}$ in every linear scheme, which makes our upper bound tight. Our scheme is considerably simpler than previous schemes that obtained share size $2^{cn+o(n)}$ with $1/2\leq c<1$. We also present a variant of this linear construction that is tailored for monotone k-DNF access structures (also known as $k$-upslices). Then, by combining it with existing non-linear schemes, we derive a scheme for all access structures with share size $2^{0.494n+o(n)}$. This improves the previous upper bound of $2^{0.585n+o(n)}$ by Applebaum and Nir (CRYPTO 2021), and establishes a separation between the worst-case non-linear and linear exponents. Additionally, we prove that almost all monotone functions require monotone span programs of size $2^{n/2-o(n)}$ simultaneously over all fields, finite or infinite, improving the previous bound of $2^{n/3-o(n)}$ for this setting. In particular, almost all access structures require information ratio $2^{n/2-o(n)}$ in linear schemes over every finite field, including fields whose size depend on $n$. Some of the constructions and proofs were discovered in conversations prompted by the author with GPT-5.6 Sol and Claude Fable 5.