Threshold Secret Sharing

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

Status	Statement	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 <= (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 >= n-d+1-epsilon 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 <= t <= 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)