Falsifiable

Status	Statement	Tags
	CPA PKE, Quantumly Broken The first item in the source’s Open Problems section. It builds counterexamples for PRFs, CPA-secure symmetric-key encryption, MACs, signatures and CCA-2-secure public-key encryption, all classically secure under LWE via black-box reductions and all quantumly broken with two or three classical queries. CPA-secure public-key encryption is the case its technique cannot reach, and it says why. 4 open	Black Box Separations Learning With Errors Quantum Cryptographyseparation
	Two-scheme key cycle Open in both directions, and the source paper says why the existing separations miss it: the counterexamples fix both schemes, whereas here the second is chosen after the first. Two hypotheses left implicit in the printed statement have to be added before it is even non-vacuous. 7 open	Circular Security Fully Homomorphic Encryptionassumption
	1+1 adaptively secure lattice threshold signature Resolved. Oriole (Jiang, Wee, Zhu, ePrint 2026/793, posted April 2026, a month after Tweed) gives a lattice-based threshold signature with exactly this shape – two rounds, only the second message-dependent, adaptive security against T-1 corruptions with no erasures, from MSIS and MLWE in the ROM – verified here directly against the paper’s PDF (Definition of adp-TS-sUF-4 in its Figure 4, and the Theorem 2 + Theorem 3 reduction chain to MSIS), not just its abstract. The proof is human-written and published, but not yet independently re-verified line-by-line by this site, nor formalized in Lean.	Learning With Errors Threshold Signatures Tight Reductionsromseparationresearch-solved
	Planted k-OV Hardness Conjecture 10 of the source, and a newly proposed average-case assumption rather than a question the literature already asked. Its worst-case counterpart – that k-OV requires n^(k-o(1)) time – is a central conjecture of fine-grained complexity. The planting preserves the marginal distribution of any subset of fewer than k vectors, and the source gives a search-to-decision reduction. 5 open	Average Case Hardness Fine Grained Cryptography Orthogonal Vectors Planted Constraint Satisfactionassumption
	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
	Sublinear-Time CGKA Refresh The source achieves worst-case sublinear communication with forward secrecy, but its refresh algorithms still run in time polynomial in the group size, and it leaves open, without committing to a specific target rate, whether sublinear-time refresh is achievable at all. 4 open	Broadcast Encryption Continuous Group Key Agreementcharacterization
	Erasing real-or-random vs Boneh–Zhandry Open: whether erasing real-or-random security implies Boneh-Zhandry security. The reverse non-implication is proved only in the quantum random oracle model, and this direction is one of six non-implications the source paper conjectures and does not prove. 5 open	Quantum Cryptography Quantum Encryption Notionsseparation
	CRS-free everlasting commitment from malicious PUFs Open: whether everlasting UC commitment is achievable in the fully malicious token model with no trusted setup. The source achieves it with a common reference string (its Theorem 31) and explicitly leaves removing the CRS as a question, noting that the usual equivocation techniques do not transfer to the everlasting setting. 6 open	Commitment Schemes Physically Uncloneable Functionsotherassumption
	Logarithmic independence implies PRP Open at independence order log n. The same implication is refuted at order 4 and at every constant order by an explicit construction; the logarithmic-order form is untouched, and no unconditional proof of it can be expected. 5 open	Limited Independence Pseudorandom Permutationscharacterization
	NISC Overhead from a PRG The source poses this question and then answers the variant in which the pseudorandom generator is replaced by a random oracle, which leaves the question as posed unresolved. Each of the four relaxations – polylogarithmic overhead, correlated-abort security, extra rounds, or programmable OLE correlations – is already known. 4 open	Garbled Circuits Non Interactive Secure Computationcharacterizationadaptation (ai)
	No expanding weak quadratic PRGs Open: whether every family of quadratic Λ(n)-bounded polynomials at stretch m ≥ n^{1+ε} admits an efficient distinguisher from the same evaluations plus bounded independent noise; the paper proves only the i.i.d.-nice special case (Theorem 2) and reports, without proof, that no degree-two candidate survives its attacks experimentally. 3 open	Average Case Hardness Pseudorandom Generatorsimpossibility
	One erasing challenge vs many embedding learns Open: whether a single erasing two-ciphertext challenge query, with classical learning queries, implies security against polynomially many embedding-model superposition learning queries. One of six non-implications the source paper conjectures, and on its own account the one that would close the most remaining cells. 5 open	Quantum Cryptography Quantum Encryption Notionsseparation
	Standard real-or-random vs embedding two-ciphertext Open: whether one standard-oracle real-or-random challenge query implies one embedding-model two-ciphertext challenge query, with classical learning queries on both sides. Both notions are singleton classes in the source’s classification, and this is one of six non-implications it conjectures. 5 open	Quantum Cryptography Quantum Encryption Notionsseparation
	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
	Blockwise-random quadratic recovery Open: whether there is a polynomial-time algorithm that provably recovers the planted input from m = n^{1+eps} published quadratics of the blockwise-random (Lin-Matt) form, sum of a random sparse (perfect-matching) part and an independent random dense part. The paper proves this for i.i.d.-nice polynomial distributions (Theorem 2) but the blockwise-random distribution is not nice, and reports only experimental recovery via a modified semidefinite program. 5 open	Average Case Hardness Pseudorandom Generatorsassumption
	PKE from constant-noise planted k-XOR Open: whether public-key encryption can be based on the hardness of planted k-XOR with a linear number of equations and a constant noise rate, as a single assumption. The survey poses it as one of two closing open questions and does not return to it; every combinatorial scheme it surveys needs sub-constant noise.	Average Case Hardness Planted Constraint Satisfactionseparationbarrier (ai)
	Certifying no small non-expanding set Open: whether the non-existence of a small non-expanding set in a random unbalanced bipartite graph admits a nondeterministic certificate that is sound and complete on average, at the parameters the ABW cryptosystem uses. The survey poses it as one of two closing open questions, takes no position, and does not return to it.	Average Case Hardness Expander Graphsseparation
	Signed rank-one reweighting below the square root Resolved, affirmatively and more strongly than asked: every Borel probability measure on the sphere admits a signed reweighting reaching an exact (not merely epsilon-close) nonzero rank-one second moment at entropy cost only O(log n) – below every n^delta, for every delta > 0, with the constant C(epsilon,delta) = 2/(e*delta) independent of epsilon. Proved by an AI-driven proof harness (conjecture-harness campaign c/0048) across six revision rounds, twenty independent blind adversarial referee passes over four audited rounds, and four independent triage rulings; the load-bearing chain (Lemmas 1-4, Theorem, Corollary, Corollary B) has never had an upheld finding against it. No human has reviewed the mathematics, and nothing here is formalized in Lean. A separate concurrent session forked the same campaign at round 3 and closed the same scope-commentary gap by a different (but mathematically equivalent) edit; both branches are recorded in the campaign ledger and the fork is not yet reconciled. 6 open	Log Rank Conjecture Sum Of Squaresassumptionresearch-solved
	SSS Implies Fiat-Shamir Friendly Conjecture 1.3 of the source. It is explicit that it does not prove it – ‘only conjecture it’ – and asks for the proof or refutation as an important open problem. It does prove that SSS implies straight-line soundness, hence post-quantum soundness, and that its own instantiation of Kilian’s protocol is SSS. 4 open	Commitment Schemes Fiat Shamir Snarkscharacterization
	Best Separable State, constant completeness error Open: whether the paper’s 2^{Otilde(sqrt n)}-time algorithm for Best Separable State extends from perfect (and near-perfect, 1-1/n) completeness to any constant completeness error c < 1. The paper conjectures the affirmative and lists this first among its open questions; no partial result at any intermediate error is reported. 5 open	Quantum Information Sum Of Squaresassumption
	Binary dual-distance bound is the worst case Open, and asserted rather than asked – the source writes that it expects the inequality, gives an intuition covering one of the two competing effects, records that all prior work assumes it, and proves nothing. A probe at small parameters is consistent with it; the parameters the source’s own construction uses are out of computational reach, which is why the source does not check it either. 7 open	Average Case Hardness Dual Distance Learning Parity With Noiselower-boundadaptation (ai)
	Permuted Codes Conjecture A new hardness assumption, printed as Conjecture 3.1 of the source and stated in its most general form deliberately, as a target for cryptanalysis rather than as the minimum its applications need. Implied by the older permuted puzzles conjecture; statistically true for O(log n) samples over constant-size alphabets; false if any one of its three randomizations is dropped. 4 open	Code Based Cryptography Dual Distance Pseudorandom Codes Watermarkingassumptionbarrier (ai)
	Polynomial Compatibility Conjecture Open in the inverse-polynomial regime. Proved for exponentially small influences by the paper that introduced it, and false for influences at or above 1/(2d); everything between is what the quantum separations depend on. 5 open	Compressed Oracle Quantum Query Complexity Quantum Random Oracle Modelqromassumption
	Three moves from DL, ROM only Open: three moves, black-box in the group, ROM only, from DL alone. Three moves is achieved from DDH in the ROM and from DL in AGM+ROM; four moves is achieved from DL in the ROM. 5 open	Blind Signatures Random Oracle Model Signature Schemes Tight Reductionsromassumption
	Single-session lattice Chevallier-Mames tightness Open: whether the one-session lattice translation of the Chevallier-Mames signature has a tight SUF-CMA reduction to search Module-LWE, or whether the paper’s two-fold parallel repetition (which doubles signature size and signing time) is inherent to a tight proof of this shape. 4 open	Learning With Errors Signature Schemes Tight Reductionsromtight-bound
	XOR as a Weak 2-Immunizer The single unresolved cell in the source’s own table: XOR fails as a strong 2-immunizer under Alekhnovich, a bilinear pairing fails as a weak one under SXDH, a random oracle succeeds even with auxiliary input. The weak case for XOR is left open with a conjectured answer and a concrete route to it. 4 open	Backdoored Primitives Black Box Separations Pseudorandom Generatorsseparationadaptation (ai)