Theoretical computer science · cryptography · average-case complexity · algebraic complexity

Existence of One-Way Functions

Collaboration beta

Can a deterministic function be efficient to evaluate while every efficient randomized algorithm fails to invert a typical output?

\exists (f_{n})_{n} \forall A \in PPT, \Pr_{x \leftarrow {0,1}^{n}} [A (f_{n} (x)) \in f_{n}^{- 1} (f_{n} (x))] = negl (n)

Known results and sources

Forward evaluation may be efficient even when recovering any preimage of a typical output defeats every efficient randomized inverter—the unconditional existence of such a family remains open.

Research problem

Exact mathematical statement

Does there exist a deterministic polynomial-time computable family

f_n: \{0,1\}^n\longrightarrow\{0,1\}^{q(n)}

for some polynomially bounded output length $q(n)$ , such that for every probabilistic polynomial-time algorithm $A$ , the probability—over uniform $x\leftarrow\{0,1\}^n$ and $A$ 's internal randomness—that $A(f_n(x))$ returns any $x'$ satisfying

f_n(x')=f_n(x)

is negligible in $n$ ? The family need not be injective: successful inversion means finding any preimage of the sampled output, not necessarily recovering the original input. Unconditional existence remains open. It would imply $P\ne NP$ , but the converse is not known because worst-case hardness does not by itself provide the required average-case inversion hardness.

Problem infographic

Problem at a glance

Scientific explainer for the open existence-of-one-way-functions problem, showing a growing security parameter, uniform random input, polynomial-time forward evaluation, average-case inversion by any probabilistic polynomial-time algorithm, the unknown converse from P not equal to NP, and stronger cryptographic variants. — A one-way function must be easy to evaluate yet hard to invert on random outputs against every efficient randomized algorithm; P not equal to NP is necessary but is not known to be sufficient.

Current mathematical picture

Where work on Existence of One-Way Functions stands

Open problem

The v4 packet promotes the dense quadratic Veronese construction to the primary candidate, records exact Fourier and bounded-degree opacity results, eliminates the Toeplitz and Toeplitz-plus-Hankel kernels as random-subspace surrogates, and repairs the average-case decision-to-search and all-length reductions. The decisive arbitrary-polynomial-time model-transfer theorem is still missing, and the easy linear control shows that bounded-degree opacity alone cannot establish one-wayness.

Strongest supported footholdRestricted-model footholds isolated

The current work records an exponential transversal independent core and a near-linear adaptive parity-query threshold, while explicitly preserving their restricted scope.

Evidence posture · Reported result

Leading routeNonlinear model-transfer firewall

Exploit identities among dense Veronese coordinates, or a distribution-preserving nonlinear restriction absent from y=Ax, to bridge arbitrary efficient computation to a model controlled by the retained restricted lower bounds.

Route status · Active route

Useful failureLegacy compressed planted/null target

The exact Toeplitz target and its valid special-case theorems remain retained history, but deterministic shift-module structure and the lack of dense affine masking remove this route from the current main line.

Route status · Narrowed route

Main reductionDense all-length wrapper handles success spikes

Trying every polynomially many tail length between consecutive dense base lengths transfers any non-negligible wrapper inversion success back to a base length, so hardness on the base sequence would extend to all sufficiently large lengths without assuming regularity of the inverter's success function.

Evidence posture · Source-reported route statement

Completed special caseFull-random affine-mask proof laboratory

For the full-random block family, the current work develops an affine-mask search-to-decision route. That secondary-laboratory theorem does not transfer to the legacy compressed Toeplitz family; the governing dense full-random candidate has its own affine-mask reduction.

Evidence posture · Source-reported route statement

Priority open bridgeClose the current load-bearing frontier

Find a theorem using the nonlinear Veronese identities that converts an arbitrary polynomial-time distinguisher or inverter into a controlled model while preserving noticeable advantage.

Task status · Ready to work on

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Existence of One-Way Functions in numbers

3kretained lines of mathematical investigation1,706 in the current working snapshot

Argument development: 2,549 · 85%
Explored or eliminated routes: 58 · 2%
Computational analysis: 106 · 4%
Open obligations: 87 · 3%
Definitions and setup: 193 · 6%

18selected mapped statements11routes investigated3reported milestones3open questions3contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byWhitfield Diffie, Martin E. HellmanProposed1976Status checkedAug 6, 2026

Source recordedAug 7, 2026

Recommended next task

Close the current load-bearing frontier

Find a theorem using the nonlinear Veronese identities that converts an arbitrary polynomial-time distinguisher or inverter into a controlled model while preserving noticeable advantage.

Suggested move: Treat the easy linear system as a mandatory control and require every proposed transfer theorem to use genuinely quadratic identities rather than bounded-degree opacity alone.

What would count as progress

State the target computational model and all adaptive/random quantifiers exactly.
Preserve inverse-polynomial advantage through the conversion.
Separate the Veronese candidate from the Gaussian-elimination-solvable linear control.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

22 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routeNonlinear model-transfer firewall

Route status · Active route

Active routeAttack the dense primary candidate

Search directly for a polynomial-time attack on AΨ(x)=y and compare every transformation with the easy linear control under identical preprocessing.

Route status · Active route

Active routeDense nonlinear cube and elimination route

Use the omitted multiplicative cube constraints and explicit average-case algebraic-elimination models to obtain a theorem that separates the Veronese system from the easy linear control.

Route status · Active route

Active routeDense models that read the whole input

Seek lower bounds for branching, memory, communication, time-space, or few-nonlinear-gate models while preserving the exact dense distribution and keeping the remaining gap to arbitrary polynomial time explicit.

Route status · Active route

Explored alternatives

Other routes

7 recorded

Narrowed routeLegacy compressed planted/null target

Route status · Narrowed route

Narrowed routeLegacy structured attack program

Systematic, fixed-point, multiple-choice-XOR, canonical-basis, and Toeplitz experiments remain useful structured diagnostics, but the governing work order now attacks the dense Veronese candidate.

Route status · Narrowed route

Useful but insufficientLegacy block-defect algebraic route

The block-distance and transversal results remain valid at their exact structured scope, but even a completed complex would not overcome the structured-kernel obstruction or supply the missing general-computation bridge.

Route status · Useful but insufficient

Browse 4 more explored routes

Narrowed routeLegacy Toeplitz models beyond parity queries

The Toeplitz annihilator geometry remains a restricted special-case foothold; current stronger-model work must preserve the dense distribution and use nonlinear Veronese structure.

Route status · Narrowed route

Narrowed routeFull-random proof laboratory

Retain the full-random affine-mask, Fourier, and degree-four/five proof patterns as supporting laboratories, without treating their distribution-specific results as compressed-family evidence.

Route status · Narrowed route

Route held in reserveDirect diagonalization

The route is paused because the evaluator/security exponent ratio does not grow and randomized inverter tapes introduce additional uniformity obstacles.

Route status · Route held in reserve

Narrowed routeCompressed Toeplitz route recorded as legacy

The v2 construction and its exact special-case theorems remain available for structured mathematics and attack diagnostics, but shift-chain structure and missing affine-mask symmetry remove it from the current primary program.

Route status · Narrowed route

Route statements and reductions

Statements the next route can inspect and build on

Route statementDense quadratic Veronese candidate

The governing packet replaces the compressed Toeplitz family as its primary target by the full-random dense family F_n(A,x,r)=(A,AΨ(x)), where Ψ contains every nonconstant squarefree monomial of degree at most two. The public matrix is ordinary function input, the base construction is exactly length preserving, and evaluation is polynomial in the actual input length N=Θ(n^3).

Source-reported route statement

Route statementDense planted/null computational indistinguishability

The current unresolved target is computational indistinguishability of (A,AΨ(x)) from (A,y), for uniform A, x, and independent y, against every probabilistic polynomial-time distinguisher.

Source-reported route statement · dependencies incomplete

Route statementBounded algebraic degrees controlled

For the dense Veronese distribution, Reed–Muller product growth and Gowers-cube counting give exponentially small planted-versus-null advantage for every fixed-degree polynomial phase and negligible advantage through degree approximately one-half log_2 n.

Source-reported route statement

Route statementAverage-case decision-to-search reduction

For the dense distribution, exact affine masking and Goldreich–Levin recovery make non-negligible planted-versus-null distinction and non-negligible inversion polynomially equivalent at the average-case level; the reduction preserves non-negligibility with polynomial loss rather than pointwise advantage.

Source-reported route statement

Route statementEasy linear control blocks the bounded-degree inference

Replacing Ψ(x) by x gives y=Ax, which is inverted by Gaussian elimination while retaining the same type of bounded-degree phase and query bounds. Bounded-degree opacity alone therefore cannot establish one-wayness.

Source-reported route statement

Route statementNonlinear model-transfer frontier

The current frontier asks for a theorem that exploits identities among dense Veronese coordinates, or another invariant absent from y=Ax, and converts a successful arbitrary polynomial-time computation into a model controlled by the retained spectral or algebraic bounds while preserving noticeable advantage.

Source-reported route statement · dependencies incomplete

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

3 featured tasks

Close the current load-bearing frontier

Find a theorem using the nonlinear Veronese identities that converts an arbitrary polynomial-time distinguisher or inverter into a controlled model while preserving noticeable advantage.

Suggested move: Treat the easy linear system as a mandatory control and require every proposed transfer theorem to use genuinely quadratic identities rather than bounded-degree opacity alone.

Ready to work on

Attack the dense primary candidate

Search for a polynomial-time attack on AΨ(x)=y using linear elimination, low-rank equation combinations, lifted-matrix recovery, spectral methods, SAT, XL, Gröbner, decoding, and time-memory tradeoffs.

Suggested move: Run identical preprocessing on planted dense, null dense, and easy linear-control instances; retain the exact structure and asymptotic resource bound of any advantage or attack.

Ready to work on

Audit the v4 dense reductions and barriers

Independently check the dense affine-mask reduction, wrapper, bounded-degree arguments, linear control, structured-kernel chains, and the separation between candidate distributions before stronger public evidence wording.

Suggested move: Work through the v4 proof-audit queue with every distribution, fixed/adaptive choice, and average-case quantifier stated explicitly.

Ready to work on

Sourced mathematical context

The known mathematical landscape

Context collected Aug 6, 2026

Current statusOpen problem

The unconditional existence of classical one-way functions remains open. The target requires average-case resistance to every probabilistic polynomial-time inverter on outputs of uniformly random inputs. It would imply P is not equal to NP and stronger average-case hardness, but ordinary worst-case P not equal to NP is not known to imply it. Recent results characterize additional average-case or lossy-reduction conditions under which OWFs would follow; those conditional bridges do not settle the unconditional question.

[2][13][14]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2025
PreprintFallahpour, Grilo, Muguruza, and Riahinia gave conditional routes from ETH plus specified lossy-reduction hypotheses to fine-grained OWFs and explicitly described unconditional OWF existence as a major open…[19]
2020–2022
Peer reviewedLiu and Pass characterized OWF existence through mild average-case hardness of time-bounded Kolmogorov complexity and then identified a natural NP-complete conditional Kolmogorov-complexity problem for which…[10][11]
2003
Peer reviewedLevin presented a combinatorial complete or universal one-way function: an explicit function that is one-way if any one-way function exists, while emphasizing subtleties in the definitions.[12]
1999
Peer reviewedHastad, Impagliazzo, Levin, and Luby completed the equivalence between existence of one-way functions and existence of pseudorandom generators.[6]

Mathematical neighborhood

Related results and reusable starting points

Current focusExistence of One-Way Functions

Logical consequenceP versus NP and NP versus BPP

One-way functions would imply P is not equal to NP and, in the standard probabilistic setting, stronger average-case separation. Ordinary worst-case P not equal to NP is not known to imply one-way functions.

[2][13]

Equivalent formulationExistence of pseudorandom generators

A pseudorandom generator can be built from any one-way function, and a pseudorandom generator directly yields a one-way function; their unconditional existence questions are equivalent.

[6]

Equivalent formulationExistence of secure digital signatures

Secure digital signatures in the standard adaptive chosen-message sense exist if and only if one-way functions exist.

[7]

Logical consequencePrivate-key cryptography, pseudorandom functions, and commitment

OWFs yield pseudorandom generators, which yield pseudorandom functions and bit commitment. These constructions place several central private-key primitives at the OWF level; they do not produce public-key encryption from OWFs alone.

[6][8]

Stronger or generalized formExistence of one-way permutations

A one-way permutation is a bijective one-way function. It is unknown whether arbitrary one-way functions imply one-way permutations.

[13]

Stronger or generalized formPublic-key cryptography and key agreement

Trapdoor functions and key agreement support public-key cryptography and imply one-wayness, but black-box barrier results show why this public-key layer must not be treated as equivalent to ordinary OWF existence.

[1][18]

Equivalent formulationAverage-case time-bounded Kolmogorov complexity

Mild average-case hardness of specified time-bounded Kolmogorov-complexity problems characterizes OWF existence; a suitable worst-case-to-average-case reduction for the NP-complete conditional variant would bridge NP not contained in BPP to OWFs.

[10][11]

Dependency or reductionExponential Time Hypothesis and lossy reductions

ETH combined with sufficiently efficient mildly lossy reductions or related instance-randomization hypotheses yields conditional fine-grained OWFs. ETH alone is not asserted to imply standard OWFs by this result.

[19]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal proof · source linked; not reproduced by ProofAtlasVerypto/Isabelle composition theorem for one-to-one one-way functions
Berg's Isabelle-based Verypto development machine-checks that composition of one-to-one OWFs remains one-way. This is a conditional closure theorem assuming OWFs, not a proof that an OWF exists.
[16]
formal library support · source linked; not reproduced by ProofAtlasEasyCrypt
EasyCrypt provides an interactive framework for formalizing game-based cryptographic definitions, adversaries, and reductions. No exact proof of unconditional OWF existence was located.
[15]
formal library support · source linked; not reproduced by ProofAtlasSSProve
SSProve is a Coq framework with machine-checked semantics and modular cryptographic proof infrastructure. Its available examples formalize conditional protocol security, not the existence of one-way functions.
[17]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA checked asymptotic complexity layer for uniform probabilistic polynomial-time algorithms, security parameters, negligible functions, and distributions over random inputs and adversary coins.
Formalization targetA statement-aligned formal definition of inversion that accepts any preimage of the sampled output, together with weak and strong one-wayness and a checked amplification theorem.
Formalization targetFormal worst-case and average-case reduction infrastructure that keeps distributions, advice, uniformity, and quantifier order explicit.
Formalization targetFor the current work's candidate specifically, checked finite-field, Toeplitz-matrix, canonical-kernel-basis, block-quadratic, and all-length-wrapper definitions before any security claim can be stated faithfully.

Later mathematical changes

What changed after the initial research map

Later recorded revisions that changed the mathematics, without inventing a date or an AI attribution.

Dense Veronese route becomes primaryThe dense candidate gains a repaired reduction stack and strong restricted-model evidence while two compressed structured-kernel routes are ruled out.

Changed the research frontierLater mathematical revision

Research stage 6

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected supporting details in the research record. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

How the route was assembled

Argument structure

These stages follow the mathematical order of the supplied argument.

5 mapped milestonesretained argument map

Browse all 5 mapped stages

stage 1Linear-description candidate isolated
stage 2Distributional footholds developed
stage 3Restricted-model lower bounds isolated
stage 4Attack-first route adopted
stage 5General-computation frontier made explicit

Linear-description candidate isolatedThe current work presents an explicit Toeplitz block-quadratic candidate with actual input length N=7n+o(n).