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)
	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	standardseparationresearch-opennew-idea (ai)
	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	otherassumptionresearch-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)
	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	standardseparationresearch-opennew-idea (ai)
	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	standardseparationresearch-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)
	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.	standardseparationresearch-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)