Secret Sharing & Threshold Cryptography

Statements tagged with the secret-sharing area. This is a generated view, not a home directory – a statement can belong to several areas at once. See all statements for the full index, or the schema for what each column means.

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)