Foundations of Cryptography

Status	Statement	Tags
	Planted-Subgraph Character Sum The source derives the formula governing low-degree detection of a planted subgraph, observes the character sum in it should be small for most graphs, and says it leaves the rigorous study of the question to future work. No bound is proved and none is stated as a target. 5 open	Average Case Hardness Planted Subgraph Problemslower-boundadaptation (ai)
	Best-first search trees Open, with no bound of any kind proved for the best-first algorithm on any class of query distributions. Exact optimality is already refuted by the paper’s own exhaustive search, so only the approximation ratio remains, and a workload on which greedy is off by an unbounded factor would settle it. 5 open	Search Treestight-bound
	Dream DPT for a moderately hard function Open: whether there exists a function family, and a standard fine-grained hardness hypothesis (the paper suggests NSETH as an example), for which solving t independent instances requires resources within a subexponentially small factor of solving them one at a time, with no loss in the exponent. The source reduces its permissionless consensus protocol to exactly this statement and leaves it unconstructed. 5 open	Direct Product Theorems Fine Grained CryptographyassumptionIOG
	Four-party NIKE, quadratic, Maurer’s model Open. Achieved in Shoup’s generic group model by the source paper (Construction 9, Theorem 10); in Maurer’s model the paper’s own O(n^2) attack sets a ceiling that a construction would meet exactly, and nothing is known about reaching it. 5 open	Generic Group Model Non Interactive Key Exchangeggmseparation
	Subexponential-query PCF from sparse LPN Open in both directions, and the source paper poses it as a question rather than conjecturing an answer; the affirmative direction is this page’s reading. The one follow-up construction from sparse LPN inherits the same superpolynomial ceiling and says so. 6 open	Learning Parity With Noise Pseudorandom Correlation Functions Random Oracle Modelromassumption
	Quadratic attack on 3-NIKE, Shoup’s model Open in Shoup’s model. Settled by the source paper in Maurer’s model for every K at least 3, including imperfect correctness; its own three-party Shoup construction achieves only an n^1.5 gap, so the truth for three parties lies somewhere between n^1.5 and n^2. 5 open	Generic Group Model Non Interactive Key Exchangeggmlower-bound
	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
	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)
	Optimal 2D LPHS Open, and asserted rather than asked: the source prints the algorithm, conjectures the error rate, reports experiments consistent with it, states it could not analyse it, and leaves settling it to future work. The matching lower bound is the source’s own theorem, so a proof would close the two-dimensional case exactly. 7 open	Distributed Discrete Logarithm Generic Group Model Locality Preserving Hashingtight-boundadaptation (ai)
	Optimal martingale gap finders Open for small mu. Settled when mu is bounded away from zero, where the Cleve-Impagliazzo gap finder already gives the conjectured product; for general mu the known bound is a factor mu short and the paper states it does not know the answer. 5 open	Coin Tossinglower-bound
	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
	CSAT with Small Space and Preprocessing Conjecture 1.2 of the source, a parameterized family rather than a single claim. Corollary 1.3 turns each parameter setting into a limitation on succinct IOPs. The source attaches decreasing confidence as the class T grows, calling the largest setting only (arguably) unlikely to be false rather than confidently believed. 4 open	Interactive Oracle Proofs Proof Size Lower Bounds Space Bounded Computation Time Space Tradeoffslower-boundbarrier (ai)
	Classical presampling, quantum queries Open, and provably hard to prove: the source’s Theorem 4 shows it implies a central open problem in quantum computing. No refutation has been attempted either, and the source takes no position on which way it goes – it states the conjecture in order to show that the classical technique cannot simply be transplanted. 6 open	Presampling Quantum Query Complexity Quantum Random Oracle Model Random Oracle Modelqromlower-boundbarrier (ai)
	Almost k-Wise Locality Gap Settled up to a log n factor at word size 1 and at word size Omega(log^2 n) and above; the source gives no matching construction at all for intermediate word sizes, so the gap is recorded only where both a bound and a construction exist to compare. 4 open	Limited Independence Locally Computable Hashingtight-boundadaptation (ai)
	SBP Collision Resistance Posed as a displayed Open Question and called a central open challenge. The source gives an efficient online collision finder for small kappa and an overlap-gap-based online lower bound for a different, randomized activation – introduced precisely because the SBP’s own collision space resists a first-moment analysis. For very large kappa collisions become trivial. The middle window is reached by neither technique. 4 open	Average Case Hardness Collision Resistant Hashing Overlap Gap Property Planted Constraint Satisfactionseparation
	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
	Partial-PKI consensus up to one-half resilience Open: whether consensus is achievable at every resilience gamma < 1/2 in the paper’s permissionless common-random-string setting, by some protocol using any means of bootstrapping party identities. The source proves resilience up to 1/4(1-3*epsilon) via a specific protocol and proves 1/4 is tight only for the restricted class of protocols that sign everything they send and verify everything they receive; the gap to the classical 1/2 ceiling is open for arbitrary protocols. 5 open	Byzantine Agreementtight-boundIOG
	Split-source decomposition Open for a query budget of two or more: whether a random oracle decomposes into bit-fixing mixtures when the advice is produced by two sources that never communicate. Proved and tight at q = 0, and proved at q = 1 under an extra hypothesis. 4 open	Multi Source Extractors Random Oracle Model Randomness Extractionromtight-bound
	r-round DLOG tradeoff Open for every intermediate r: the r = 1 endpoint is the source’s own theorem and r = T is Corrigan-Gibbs–Kogan, with nothing proved in between. The source conjectures the interpolating formula and says a matching attack exists at every r, so the missing half is the lower bound. 6 open	Adaptivity Discrete Logarithm Generic Group Model Time Space Tradeoffsggmtight-bound
	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
	Composability implies circular security Open with no partial result in either direction. The converse – circular security plus limited homomorphism gives full composability – is the source paper’s Theorem 6; this direction, which would make the two properties essentially equivalent, is conjectured there and nothing has been published towards it. 7 open	Circular Security Fully Homomorphic Encryptionequivalence
	Seeded Extractors Are Multi-Instance Posed by the source with both answers live. It proves the property for two code-based extractors via a hinting property it isolates; concurrent independent work of Dinur, Stemmer, Woodruff and Zhou proves it for universal hash functions by a different argument. No extractor is known to fail it and no general proof is known. 4 open	Incompressible Encryption Randomness Extractioncharacterization
	Double-sided zero search Resolved, unconditionally. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, STOC 2026) proves this exact statement – his Problem 3, p. 72, naming it ‘the double-sided zero search problem, due to Unruh’ – as a corollary (Corollary 7.6) of a general predicate-search lower bound (Theorem 7.5) proved directly from his own compressed permutation oracle’s soundness (Theorem 5.19). Unlike Unruh’s own derivation, this proof does not route through Unruh’s CPO-soundness conjecture (c/0036) at all, so it holds regardless of that conjecture’s status.	Compressed Oracle Quantum Query Complexityotherlower-boundresearch-solved
	Level-optimal beyond disjunctions Open beyond disjunctive queries, and the authors state it as a conjecture without naming the broader class – identifying one is part of the problem. Proved for every distribution supported on disjunctions, where the log n factor is also shown necessary. Wide open for conjunctive queries, where the paper’s proof technique demonstrably fails. 5 open	Search Treestight-bound
	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
	RBE needs Ω(log n) updates Refuted. Mahmoody and Qi, Online Mergers and Applications to Registration-Based Encryption and Accumulators (ITC 2023), construct an RBE scheme with O(log n / log log n) decryption updates and poly(kappa, log n) public parameters – strictly below the Omega(log n) this statement conjectured – via a fully online merger structure, matching the known lower bound exactly. The paper states this explicitly resolves the open question. 4 open	Registration Based Encryptionlower-boundresearch-solvedadaptation (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
	No key agreement from GC-OWF Open for round complexity growing with the security parameter. Proved in full for two messages, which is public-key encryption; the constant-round extension is sketched in the paper’s appendix without a theorem, its security half deferred to the PKE proof. 5 open	Black Box Separations Garbled Circuits Key Agreementotherseparationadaptation (ai)
	No Self-Reduction for LSN Conjecture 5.20 of the source. It proves no random self-reduction exists from an arbitrary worst-case QNCP instance into LSN, naming exchange symmetry between code and error as the obstruction, and proves the tableau-randomizing barrier conditionally on the scrambling gap being polynomially related to eps. It is explicit that this is not an impossibility for random self-reductions in general. 4 open	Average Case Hardness Learning Parity With Noise Quantum Information Stabilizer Codesimpossibilityadaptation (ai)
	iO Overhead, Single-Output The first of the source’s named main open problems. Its main theorem gives an Omega(s/log s) additive overhead lower bound for iO on multi-output circuits under NP not in BPP – an assumption that is minimal, since a zero-overhead scheme exists if NP is in BPP. The single-output case is not covered, and the source says why: its route runs through NP-hardness of Multi-MCSP. 4 open	Black Box Separations Minimum Circuit Size Problem One Way Functionslower-boundbarrier (ai)
	OWFs are black-box useless for key agreement Open in the general case, which the paper names as the central open problem left by its work. Settled for three restricted protocol classes: constant-query perfect, constant-round constant-query imperfect, and Merkle-type. 5 open	Black Box Separations Key Agreement One Way Functionsotherimpossibility
	OWFs are black-box helpful for CRHFs Open in both directions. Two relaxations — distributional and class-reduction helpfulness — are proved conditional on the Simon-oracle amplification conjecture; neither yields the universal auxiliary primitive the full statement needs. 4 open	Black Box Separations Collision Resistant Hashing One Way Functionsotherseparation
	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
	OWF minimality, non-black-box reductions Open when the classical security implication is not witnessed by a black-box reduction between the two games. Settled affirmatively whenever it is, for uniform and non-uniform quantum adversaries alike, with the implementation reduction left arbitrary. 5 open	Black Box Separations One Way Functions Quantum Cryptographyequivalence
	Simon-oracle amplification, strong version Open. The version without the collision finder is known only when the one-way function is itself a random oracle; with an arbitrary one-way function, with or without the collision finder, nothing is established. 5 open	Black Box Separations Collision Resistant Hashing One Way Functionsotherlower-bound
	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)
	Ring-LWE error parity Open: whether recovering the Ring-LWE error modulo two is as hard as recovering the error itself. The easy direction is trivial; the source states it has no formal reduction for this one and relies on two heuristics instead, one of which changes the error distribution. 6 open	Learning With Errorsequivalence
	RM Gap to Capacity for BEC Conjecture 14 of the source. That Reed-Muller codes achieve capacity for the BEC is a theorem of Kudekar et al.; the gap to capacity – a polynomial rate of convergence – is open. The source needs it to strengthen its refutation of the expansion-implies-hardness conjecture for noisy k-XOR from quasi-polynomially many constraints to polynomially many, and notes the question was raised explicitly in three prior works. 4 open	Average Case Hardness Code Based Cryptography Expander Graphs Reed Solomon Codestight-bound
	Computationally unique VDFs in the ROM Resolved. Guan, Riazanov and Yuan, Breaking Verifiable Delay Functions in the Random Oracle Model (ePrint 2024/766, CRYPTO 2025), prove that no VDF in the parallel ROM can have completeness and computational uniqueness and be sigma-sequential for sigma a fixed polynomial in the security parameter and the Setup/Verify query counts – their Theorem 5.1, which in fact covers general (not just perfect) completeness error, strictly more than this conjecture asked for. The proof is human-authored and published; it has not yet been independently re-derived by this site or formalized in Lean. 3 open	Black Box Separations Random Oracle Model Verifiable Delay Functionsromimpossibilityresearch-solved
	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
	Compressed permutation oracle soundness Still open as formalized, but the underlying research question – can the compressed-oracle technique be extended to permutations at all – is now resolved in the affirmative by a different construction. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, STOC 2026) proves his own compressed permutation oracle unconditionally sound. That oracle is, in his own words, ‘similar to that of Unruh [Unr23], though we explicitly and unitarily maintain injectivity of the database’ – a change that goes beyond resolving Unruh’s own left-open choice of how the flipping operator acts on non-injective inputs. Whether Unruh’s original construction (for an arbitrary such choice) is itself sound remains, on the reading defended here, unestablished.	Compressed Oracle Pseudorandom Permutations Quantum Query Complexityotherequivalence
	Hold-Out Soundness, Dirty Coordinates The source’s distinguishing attack is unconditional and proved. Its decryption attack is heuristic, and this is the unproved step: completeness on clean coordinates is its Claim 6.2, while soundness on dirty ones is supported only by a heuristic dimension count and small-parameter experiments. 5 open	Code Based Cryptography Private Information Retrievalcharacterization
	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
	Censoring can only hurt Open. The censored side is proved at essentially optimal round count with matching lower bounds; what is missing is the transfer of any such bound to uncensored AES at the same round count. 5 open	Block Ciphers Pseudorandom Permutationslower-bound
	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)
	CHV Online Threshold Conjecture 1 of the source, its online threshold conjecture. The source gives an online algorithm achieving kappa = O(sqrt(alpha)/B) and an overlap-gap argument against stable algorithms; the conjecture pins the constant sqrt(pi/8) as the exact place where online algorithms stop. Separately it proves, under worst-case lattice hardness, that no polynomial-time algorithm solves CHV for kappa = O(1/(B n^(1/2+eps))). 4 open	Average Case Hardness Collision Resistant Hashing Locality Preserving Hashing Overlap Gap Propertytight-bound
	Non-adaptive DDH bound Open, and asserted rather than asked: the source proves 1/2 + O~(T^2/N + sqrt(ST/N)), states twice that it conjectures this is not tight for DDH, and names 1/2 + O~(T^2/N + ST/N) as the right answer. The same theorem’s square-DDH bound is sharp, with a matching attack, which is what makes the DDH case a question rather than a suspicion. 6 open	Adaptivity Discrete Logarithm Generic Group Model Time Space Tradeoffsggmtight-boundadaptation (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
	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
	RBE update bound, key-dependent schedules Resolved. Wei Qi, Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators (IACR Communications in Cryptology, 2026), generalizes the Mahmoody-Qi-Rahimi lower-bound framework to schedules that may depend on the sampled public keys themselves, via a new combinatorial structure (the falling-step sequence), and proves the same asymptotic bound holds. The paper states this explicitly resolves the open problem left in the source paper. 5 open	Registration Based Encryptionlower-boundresearch-solvedadaptation (ai)
	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)