Black Box Separations

Impossibility or separation results ruling out a fully black-box construction or reduction between two primitives.

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
	SK-DEPIR from One-Way Functions Stated by the source as its own conjecture and proved for two-round passive-server schemes. Its main theorem – that any crypto oracle can be stripped out of a SK-DEPIR and replaced by a one-way function – is stated conditionally on this, so the conjecture is the single remaining hypothesis between that compiler and a clean statement that no idealized generic primitive helps. 4 open	Black Box Separations One Way Functions Private Information Retrievalimpossibility
	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)
	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
	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
	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	Black Box Separations Blind Signatures Generic Group Model Signature Schemesggmimpossibilityadaptation (ai)
	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
	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)