All statements

Status	Statement	Tags
	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	standardtight-boundresearch-opennew-idea (ai)
	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	romtight-boundresearch-opennew-idea (ai)
	6-round Feistel indifferentiability Whether 6-round Feistel is fully indifferentiable from a random permutation is open, bridging the proven r=5 attack and the proven r>=8 construction. 2 open	othertight-boundresearch-opennew-idea (ai)
	Generalized mirror theory The fully generalized Mirror Theory bound for arbitrary cycle-consistent multi-graphs up to the information-theoretic limit is open; current techniques only reach component size O(N^{1/4}). 2 open	standardlower-boundresearch-opennew-idea (ai)
	Groth16 optimality (pure GGM) Open: whether every sound, non-interactive, publicly verifiable pairing-based argument in the pure generic group model needs at least three group elements, matching Groth16. 2 open	ggmtight-boundresearch-opennew-idea (ai)
	LHL extraction, public seed Proven, and the statement is now formalized in Lean with an AI match check: the public-seed bound holds with a concrete constant, but the proof itself is still only informal (PDF), unreviewed, and unformalized. 4 open	romtight-boundresearch-solvedadaptation (ai)
	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	standardtight-boundresearch-opennew-idea (ai)
	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	standardcharacterizationresearch-opennew-idea (ai)
	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	otherseparationresearch-openadaptation (ai)
	No 2-element split NILPs Open: whether a 2-element split NILP can be statistically sound against affine provers for any hard relation generator, the information-theoretic core of whether Groth16’s 3-element proof size is optimal. 2 open	standardimpossibilityresearch-opennew-idea (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. 6 open	otherimpossibilityresearch-opennew-idea (ai)
	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. 5 open	otherseparationresearch-opennew-idea (ai)
	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	otherlower-boundresearch-opennew-idea (ai)
	No round-optimal pairing-free blind signature Open for a polynomial query budget. The impossibility is proved when User_2 and Verify together make O(log lambda) random-oracle queries, including when oracle outputs contain group elements; the superpolynomial message space hypothesis is retained. 5 open	ggmimpossibilityresearch-openadaptation (ai)
	Computationally unique VDFs in the ROM Open under computational uniqueness, which is the notion the definition of a VDF actually requires. Settled for perfect uniqueness with perfect completeness, and settled in the tight regime even with no uniqueness assumption at all. 5 open	romimpossibilityresearch-opennew-idea (ai)
	3-way collision, oblivious sequential curve Open: closing the factor-root-S gap between the proved oblivious lower bound and a matching table-and-hunt algorithm for finding a 3-way collision with an oblivious sequential branching program. 2 open	romtight-boundresearch-openadaptation (ai)
	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	standardlower-boundresearch-opennew-idea (ai)
	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	romassumptionresearch-opennew-idea (ai)
	Tight \(k\)-collision time-space tradeoff The exact tight time-space tradeoff for k>=3 collisions under preprocessing is open; only the k=2 case has a matching upper and lower bound. 2 open	romtight-boundresearch-opennew-idea (ai)