Do one-way functions exist?

The minimal assumption of modern cryptography, and it has never been proved from anything weaker than itself.

Inferred from the community field; finer classification has not been reviewed.

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

Does there exist a polynomial-time computable $f:\{0,1\}^* \to \{0,1\}^*$ such that for every probabilistic polynomial-time adversary $A$ and every polynomial $p$ , for all sufficiently large $n$ ,

\Pr_{x \sim \{0,1\}^n}\!\left[A(f(x)) \in f^{-1}(f(x))\right] < \frac{1}{p(n)}?

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

One-way functions are equivalent to the existence of pseudorandom generators, pseudorandom functions, digital signatures and commitment schemes — the whole of "minicrypt". Their existence implies $\mathrm{P} \ne \mathrm{NP}$ , but the converse is not known and is believed to be false in general.

Known partial results

Liu and Pass (2020) characterised the existence of one-way functions by the average-case hardness of time-bounded Kolmogorov complexity, giving the first natural complete problem for the assumption.
Candidate constructions exist from factoring, discrete logarithm and lattice problems, none of which is proved hard.
Impagliazzo's "five worlds" framing organises which cryptography survives under which assumptions.

References

[1]Y. Liu, R. Pass, On one-way functions and Kolmogorov complexity, FOCS 2020. link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.