Secret Sharing & Threshold Cryptography

Status	Problem	Tags
	AVPs Are Lengthy Posed as Hypothesis 1.2 and offered both as a working hypothesis and as an ambitious target. Theorem 1.3 proves it implies super-polynomial lower bounds on sd-PIR, general secret sharing and fully-decomposable randomized encodings – for none of which a super-linear lower bound is currently known. The source adapts counting-based arguments to the model but does not reach the best-known bound for any primitive. 4 open	Garbled Circuits Private Information Retrieval Proof Size Lower Bounds Randomized Encodingslower-boundbarrier (ai)
	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)
	Threshold one-shot decryption without extractability Open: whether threshold one-shot decryption (for every corruption threshold \(f<1/2\)) follows from one-shot signatures and an ordinary, non-extractable witness encryption scheme. The one known construction needs the witness-encryption extractor to run its security reduction, and the source paper leaves open whether extractability can be weakened or dropped altogether. 4 open	One Shot Signatures Witness EncryptionassumptionIOG
	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)