For an n-party monotone access structure Gamma⊆ 2^[n], let ell_Gamma be the minimum, over all linear secret-sharing schemes for one-bit secrets realizing Gamma, of the maximum number of bits in any party's share. Define L(n)=max_Gamma⊆ 2^[n]ell_Gamma. Determine the exact or asymptotically optimal growth of L(n), including the optimal exponential share-size exponent for realizing arbitrary access structures by linear secret-sharing schemes.

Linear secret-sharing scheme size problem

For an $n$ -party monotone access structure $\Gamma\subseteq 2^{[n]}$ , let $\ell_{\Gamma}$ be the minimum, over all linear secret-sharing schemes for one-bit secrets realizing $\Gamma$ , of the maximum number of bits in any party's share. Define $L(n)=\max_{\Gamma\subseteq 2^{[n]}}\ell_{\Gamma}$ . Determine the exact or asymptotically optimal growth of $L(n)$ , including the optimal exponential share-size exponent for realizing arbitrary access structures by linear secret-sharing schemes.

Progress summary

Partially solved

A 2026 e-print reports a better construction, but no matching lower bound or full solution is established.

The problem asks how small shares can be made in linear secret-sharing schemes, with the central goal of improving the best asymptotic construction. The remaining gap is between known upper and lower bounds.

Known results

Ball, Çakan, and Malkin (2021) prove a total-share lower bound of $2n-1$ for $1<t<n$ .
Over a field $\mathbb{F}$ , they prove a lower bound of $n\lceil\log_{\operatorname{char}(\mathbb{F})} n\rceil$ .
In characteristic $2$ , this matches the known $O(n\log n)$ upper bound attributed to Karchmer and Wigderson, while the general gap remains open.

August 2026 upper-bound update

An IACR e-print reports reducing the asymptotic upper-bound exponent from $0.585$ to $0.496$ , advancing the best known construction. The available evidence does not establish a matching lower bound or a complete resolution.

Current status (as of August 2026): The best reported upper-bound exponent is $0.496$ , while the general lower-bound gap and the full size problem remain open.

Sources

Sources & referencesView supporting material

Primary source

IACR Cryptology ePrint Archive

Additional references

Linear secret-sharing upper bound — IACR Cryptology ePrint Archive

1 day ago