Threshold Secret Sharing

Threshold access structures specifically, and the share sizes they need under various privacy notions.

Status	Problem	Tags
	Sub-log Share Size for 2-out-of-\(n\) The information-theoretic share size is exactly \(\log n\) and Shamir’s scheme matches it. The source proves a \((1/5)\log\log n\) lower bound for the computational setting with public information, leaving a \(\log n\) versus \(\log\log n\) gap, and proves that beating \(\log n\) by any constant factor is equivalent to a concrete planted clique-and-independent-set problem. 4 open	Average Case Hardness Planted Subgraph Problems Threshold Secret Sharingtight-bound
	Conflict Checkable Codes Beyond Half-Singleton Theorem 1.8 proves \(k\le(n-d+2)/2\) for codes that are both comparison-based and local-to-global consistent. Theorem 1.3 gives an almost-MDS conflict checkable code at \(k\ge n-d+1-\varepsilon\) which bypasses that bound, but it is neither comparison-based nor known to be local-to-global consistent. The conjecture names comparison-basedness as the culprit. It already holds at \(d=n-1\). 4 open	Code Based Cryptography Locally Testable Codes Threshold Secret Sharingseparationadaptation (ai)
	Perfect FASS at 3-out-of-5 Statistical and computational FASS are settled by the source and prior work. The perfect version is stated by the source to be open for every reconstruction threshold \(3\le t\le n-2\), and open even for the weaker multi-dealer notion, with 3-out-of-5 the smallest open case. Con has settled the perfect case for gap threshold structures. 5 open	Anonymity Threshold Secret Sharingcharacterizationadaptation (ai)
	WP Threshold Share Size The \(2\)-out-of-\(n\) case is settled: Beimel and Franklin give \(1/n\)-weakly-private schemes with share size 2, against \(\Theta(\log n)\) for perfect privacy. The source states large thresholds are open and asks specifically about \((n-1)\)-out-of-\(n\) at share size \(o(\log n)\). 5 open	Threshold Secret Sharingcharacterizationadaptation (ai)