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.

A new 2^{n-o(n)} lower bound for linear schemes over all fields simultaneously, and a small optimization that improves the non-linear exponent from 0.496 to 0.494.

A secret-sharing scheme allows a dealer to distribute a secret $s$ among $n$ parties such that only predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about $s$. 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 for one-bit secrets with maximal share size of $2^{\lceil n/2\rceil-1}+1$ bits. A counting lower bound for monotone span programs shows that almost all access structures require linear share size $2^{n/2-o(n)}$, 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-DNFs access structures (also known as $k$-upslices). Then, by combining it with a non-linear scheme of Applebaum et al. (STOC 2020), we derive a scheme for all access structures with share size $2^{0.496n+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. Plugging the quadratic construction of Beimel, Othman, and Peter (CRYPTO 2021) into this framework yields quadratic schemes of share size $2^{0.4995n+o(n)}$, separating the quadratic and linear exponents.

The linear scheme for upslices and its proof were discovered in conversations prompted by the author with GPT-5.6 Sol and Claude Fable 5.