One Way Functions

The minimal cryptographic assumption, and what it does or does not imply in a black-box sense.

Status	Statement	Tags
	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
	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