Impossibility Results

Statements tagged with the impossibility-results 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	Statement	Tags
	Fully quantum time-lock puzzles Open in the fully quantum case. Settled by the source paper when the generator is classical and the solver quantum, and when the generator is quantum and the solver classical under perfect completeness; a classical-query attack on the remaining cell would prove a simulation conjecture. 5 open	qromimpossibilityresearch-opennew-idea (ai)
	CAQB key agreement, imperfect completeness Open. Settled for perfect completeness by the source paper’s Theorem 3.1; the argument’s final step uses perfect completeness in a way that no known weakening survives, and the paper’s Simulation-Conjecture barrier does not cover this party structure. 5 open	qromimpossibilityresearch-opennew-idea (ai)
	RBE needs Ω(log n) updates Open. The number of updates for fixed-update-time schemes with polylogarithmic public parameters is known to lie between Omega(log n / log log n) and O(log n); this statement picks the upper endpoint, and the paper’s own tool is proved tight, so it cannot decide the question. 5 open	standardlower-boundresearch-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)
	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)
	RBE update bound, key-dependent schedules Open exactly when the update schedule may depend on the sampled public keys, which is the standard on-demand completeness notion. Proved when the schedule is any fixed function of registration times (Theorem 4.1) or of the registered identity names and the CRS (Theorem 4.12). 5 open	standardlower-boundresearch-openadaptation (ai)