One-way functions exist

One-way functions exist

Definitions and mathematical statement

A nonnegative function $\eta(n)$ is negligible if for every $c>0$ it is at most $n^{-c}$ for all sufficiently large $n$. The sought function family is uniformly computable in deterministic polynomial time and satisfies, for every probabilistic polynomial-time $A$, \[ \Pr_{x\leftarrow\{0,1\}^n,\,A}\!\left[A(1^n,f_n(x))\in f_n^{-1}(f_n(x))\right] \le \eta_A(n) \] for some negligible $\eta_A$. An output of the wrong input length is a failed inversion. The probability includes both a uniformly random input and the inverter's internal randomness. The inverter only has to find some preimage; recovering the originally sampled input is unnecessary.

Formulation and concept references: [S1].

Short English statement

Is there an efficiently computable function whose outputs no efficient randomized algorithm can usually reverse, even when any preimage counts?

Research attempt

Scope, quantifiers, and source check.

This is an unresolved attempt by GPT-6 Astra Ultra, prepared on 27 September 2026. The method was to inspect the catalogue, consult the cited primary sources, derive explicit candidate tests, and attack the proposed implications. No cryptographic assumption is asserted to have been proved. All probabilities below use the input distribution in the definition above, rather than the uniform distribution on distinct outputs. These distributions differ whenever fiber sizes differ.

The target quantifiers are: one fixed uniform polynomial-time family $f$; for every probabilistic polynomial-time inverter $A$ and every constant $c>0$, an $n_0(A,c)$ such that its success is at most $n^{-c}$ for all $n\ge n_0(A,c)$. Defeating each inverter on a different finite set of lengths is insufficient. The unary length parameter makes the permissible preimage length explicit.

Hirahara--Lu--Oliveira [S1], Section 1.2, distinguish an average-case asymmetry characterization of ordinary one-way functions from a separate characterization involving infinitely-often one-way functions. Their worst-case-to-average-case implication has stated hypotheses; none is removed here. Liu--Pass [S3] give another characterization through boundary hardness of randomized time-bounded Kolmogorov complexity. A characterization relocates the missing hardness statement; it does not establish it automatically. This attempt instead tests what fiber size and simple embeddings can establish without an unproved assumption.

Attack plan.

Three possible routes are counting the amount of information lost, embedding a hard search problem into an efficiently computable map, and amplifying the result by taking independent products. The first route admits an exact calculation. The second and third admit an explicit counterexample to the claim that merely retaining some hard outputs suffices. These tests concern candidate constructions, not a disproof of the existence question.

Lemma 8.1: an exact resampling attack.

Fix $n$, put $Y=f_n(X)$ for uniform $X$, and write \[ p_y=\Pr[Y=y]=2^{-n}|f_n^{-1}(y)|,\qquad M=|\operatorname{im}(f_n)|. \] An inverter samples $T$ independent uniform strings $Z_1,\ldots,Z_T$ of length $n$, evaluates $f_n$ on each, and returns the first one matching its target $y$. Its success probability is exactly \begin{equation}\label{wsref-0-61-38-3a-73-61-6d-70-6c-69-6e-67} S_T=\sum_y p_y\left(1-(1-p_y)^T\right). \end{equation} In particular, \begin{equation}\label{wsref-0-61-38-3a-62-6f-75-6e-64-73} S_1=\sum_y p_y^2\ge\frac1M, \qquad 1-S_T\le\frac{M}{T+1}\quad(T\ge1). \end{equation}

Proof. Conditional on target $y$, a fresh sample succeeds with probability $p_y$, independently of the other samples. This gives (a8:sampling). Cauchy--Schwarz applied to $\sum_y p_y=1$ gives the first bound. For the second, maximize $u(1-u)^T$ on $[0,1]$. Its derivative is $(1-u)^{T-1}(1-(T+1)u)$, so the maximum is $T^T/(T+1)^{T+1}\le1/(T+1)$. Summing this bound over the $M$ possible outputs proves the assertion. Every returned sample is an actual preimage of the required length.$\square$

If $M(n)\le n^d$ for all sufficiently large $n$, taking $T=\lceil n^{d+a}\rceil$ gives failure at most $n^{-a}$, with polynomial running time for every fixed $a>0$. More strongly, if $M(n)\le n^d$ on infinitely many lengths, the one-sample inverter already succeeds with probability at least $n^{-d}$ on those lengths and violates negligibility. Thus any one-way family must have superpolynomial image size in the all-sufficiently-large sense. It must also have negligible collision probability $\sum_y p_y^2$, a sharper necessary test when the fibers are unbalanced. Neither condition is sufficient: the identity map has image size $2^n$ and collision probability $2^{-n}$, but the target itself is its preimage.

This also resolves an elementary ambiguity in the information-loss approach. A constant map destroys nearly all information about the sampled input, yet is inverted by returning $0^n$. Predicting the original input and finding any input in its fiber are different tasks. Shannon entropy or a large fiber cannot by itself express the search difficulty needed here.

Lemma 8.2: a hard branch can be negligible.

Let $h_m:\{0,1\}^m\to\{0,1\}^{\operatorname{poly}(m)}$ be any uniform polynomial-time family, with no assumption about its inversion complexity. For all sufficiently large $n$, put \[ k(n)=\left\lceil\log_2(n+2)\right\rceil^2<n, \quad m=n-k(n),\quad x=(b,u), \] where $|b|=k(n)$ and $|u|=m$. Define \begin{equation}\label{wsref-0-61-38-3a-62-72-61-6e-63-68} f_n(b,u)= \begin{cases} (0,h_m(u)),&b=0^{k(n)},\\ (1,b,u),&b\ne0^{k(n)}. \end{cases} \end{equation} Use any explicit easy definition at the finitely many remaining lengths. The leading tags make the branches disjoint. A uniform inverter copies $(b,u)$ from every target with tag $1$ and declares failure on tag $0$. Therefore its success is exactly \[ 1-\delta_n,\qquad\delta_n=2^{-k(n)}. \] For each fixed $c$, eventually $k(n)\ge c\log_2 n$, so $\delta_n$ is negligible. On the other hand, inverting a tag-$0$ target necessarily finds a preimage under $h_m$: the tags prevent using an easy-branch input instead. Thus even a hypothetical hard $h_m$ survives on those specially selected outputs while the resulting family is almost always trivially invertible.

This is a precise obstruction to a worst-case embedding argument. A reduction that supplies only selected difficult outputs gives no lower bound on their probability under $f_n(U_n)$. Hardness of deciding whether an arbitrary output has a preimage is also not enough: in the inversion experiment a preimage is guaranteed to exist. Any reduction using nonexistent outputs must account for this promise explicitly.

Products do not repair this example.

For a positive integer $t=t(n)$ consider \[ F_{n,t}(x_1,\ldots,x_t) =(f_n(x_1),\ldots,f_n(x_t)). \] Apply the tag-copying inverter coordinatewise. Independence gives success $(1-\delta_n)^t$, and the union bound gives \begin{equation}\label{wsref-0-61-38-3a-70-72-6f-64-75-63-74} (1-\delta_n)^t\ge1-t\delta_n. \end{equation} For every polynomially bounded $t$, the right side is $1$ minus a negligible function of $n$. It is also negligible as a failure term in the total input length $N=nt$: if $N\le n^D$, apply negligibility with exponent $Dc$ for any requested exponent $c$ in $N$. Consequently polynomial repetition of this construction preserves its easy inversion. No independence assumption about the internal structure of $h_m$ was used.

The missing premise in an amplification proposal is therefore a sufficiently frequent, computationally unavoidable failure of every inverter. The presence of a difficult special branch is not such a premise. The calculation does not contradict hardness-amplification theorems with their actual weak-hardness hypotheses; it shows why one cannot omit those hypotheses.

A necessary complexity consequence, with the search step exposed.

Suppose $\mathsf P=\mathsf{NP}$. For any proposed $f$, define the language \[ D_f=\{(1^n,y,p):\text{there exists }z\in\{0,1\}^n \text{ extending }p\text{ with }f_n(z)=y\}. \] Membership has the length-$n$ witness $z$ and a polynomial-time verifier, so the assumption supplies a deterministic polynomial-time decider for $D_f$. Starting with the empty prefix, test the prefix extended by $0$; keep it if the answer is yes, and otherwise extend by $1$. On a target in the image, induction maintains existence of a completion. After $n$ queries the prefix is a preimage. Each query has polynomial length, and the number of queries is polynomial. Hence no family in the target definition is one-way under $\mathsf P=\mathsf{NP}$. This proves the familiar necessary implication, without identifying it with a converse. It uses exact decision on all queried prefixes, not an average-case decision routine that might fail on the adaptively chosen queries.

Verification and remaining gap.

The companion exact-arithmetic checks evaluate (a8:sampling) on every positive integer partition of domain sizes $2,4,8$, for $T=1,2,3,4$. They verify both inequalities and the one-trial collision identity. Separate checks verify the product inequality for dyadic branch probabilities. These are checks of the finite calculations; the asymptotic claims use the proofs above. Boundary cases include $M=1$ (certain success), uniform fibers ($S_T=1-(1-1/M)^T$), and singleton fibers (the resampling attack is weak even when an algebraic inverse is obvious).

The first unproved step for a positive solution is an explicit uniform family with a lower bound on average-case inversion against every probabilistic polynomial-time algorithm. None of image growth, collision entropy, selected hard outputs, or polynomial repetition provides this step. For a negative solution one would need a general inverter beyond the small image class treated here. Concrete next targets are a distribution-preserving search reduction, a proof of weak average-case hardness at all sufficiently large lengths, and an audit that the reduction permits finding any preimage.

Outcome.

UNRESOLVED. The proved results are the exact resampling formula, its small-image consequence, and a construction for which a retained special branch and every polynomial independent product are almost always easy to invert. These are elementary candidate diagnostics, with no claim of novelty. No one-way function or general polynomial-time inversion algorithm has been established.

Sources

• S1 Shuichi Hirahara, Zhenjian Lu, and Igor C. Oliveira, One-Way Functions and pKt Complexity, IACR ePrint 2024/1388 $2024$. https://eprint.iacr.org/2024/1388.pdf. Formulation source.
• S2 One-Way Functions and pKt Complexity — Hirahara, Lu and Oliveira. https://wrap.warwick.ac.uk/id/eprint/187935/1/WRAP-One-way-functions-pKt-complexity-24.pdf. Further reference; not a proof endorsement.
• S3 One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity — Liu and Pass. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.97. Further reference; not a proof endorsement.

One-way functions exist

Definitions and mathematical statement

A nonnegative function $\eta(n)$ is negligible if for every $c>0$ it is at most $n^{-c}$ for all sufficiently large $n$. The sought function family is uniformly computable in deterministic polynomial time and satisfies, for every probabilistic polynomial-time $A$, \[ \Pr_{x\leftarrow\{0,1\}^n,\,A}\!\left[A(1^n,f_n(x))\in f_n^{-1}(f_n(x))\right] \le \eta_A(n) \] for some negligible $\eta_A$. An output of the wrong input length is a failed inversion. The probability includes both a uniformly random input and the inverter's internal randomness. The inverter only has to find some preimage; recovering the originally sampled input is unnecessary.

Formulation and concept references: [S1].

Short English statement

Is there an efficiently computable function whose outputs no efficient randomized algorithm can usually reverse, even when any preimage counts?

Research attempt

Current frontier.

Research check: 27 September 2026. The 2024 Hirahara--Lu--Oliveira manuscript gives characterizations of one-way functions through public-coin time-bounded Kolmogorov complexity; its Theorem 3 separately concerns infinitely-often one-way functions. Those quantifiers cannot be exchanged for the eventual hardness required here. Liu--Pass (ITCS 2026, Theorems 4.1--4.2) gives a boundary-hardness characterization for randomized time-bounded complexity and a conditional characterization for its plain analogue. These are equivalences or conditional reductions, not unconditional constructions. [S2], [S3]. The attempt below instead tests an explicit polynomial map, distinguishing its provable collision properties from its unproved inversion hardness.

Attack route.

Three routes are natural: prove one of the meta-complexity hardness conditions, convert worst-case NP-hardness into planted average-case hardness, or analyze a concrete function directly. The first still needs a complexity lower bound; the second must control the actual output sampling distribution, not just arbitrary satisfiable instances. We pursue the third with random quadratic systems whose coefficients are part of the uniform input, not a separately generated secret key.

Attempt: a fully uniform candidate on every length.

For $k\ge1$ let $m=3k$ and \[ q_k=1+k+\binom{k}{2},\qquad d_k=mq_k. \tag{8.1} \] A seed $Q\in{\mathbb{F}}_2^{d_k}$ describes $m$ independent multilinear quadratic polynomials in $k$ variables, with all constant, linear and squarefree quadratic coefficients included. For input length $N\ge d_1+1$, let $k$ be the largest integer with $d_k+k\le N$, and put $r=N-d_k-k$. Parse the input as $(Q,x,u)$ with lengths $d_k,k,r$, and define \[ f_N(Q,x,u)=(Q,Q(x),u). \tag{8.2} \] For the finitely many smaller lengths use the identity map. The output length is $N+2k$, evaluation is deterministic polynomial time, and $k=\Theta(N^{1/3})$. Indeed, $d_k+k$ is a cubic polynomial with positive leading coefficient, and maximality bounds $N$ above by $d_{k+1}+k+1$. This is one algorithm on all lengths, with no advice.

For fixed $x\ne y$, the difference of one row's evaluations is a nonzero linear functional of its coefficient vector: at least one linear monomial distinguishes $x$ and $y$. Consequently \[ \Pr_Q[Q(x)=Q(y)]=2^{-3k},\qquad \Pr_Q[Q\text{ is not injective}]\le \binom{2^k}{2}2^{-3k}<2^{-k-1}. \tag{8.3} \] The second statement follows by a union bound over unordered pairs and requires no independence between different pairs. Different seeds cannot collide under $8.2$, since the seed is copied to the output. For all but an exponentially small fraction of seeds, the $x$-preimage is therefore unique. This establishes a property of the proposed map, not one-wayness.

The necessary next statement is genuinely distributional: for every PPT algorithm $A$, its probability of finding any $x'$ with $Q(x')=Q(x)$, given $(Q,Q(x))$ for uniform independent $Q,x$, would have to be negligible in $k$. If this held, $8.2$ would satisfy the target. To justify the padding step, a proposed inverter at lengths $N$ can be simulated at core length $k$ by sampling one of the $O(k^2)$ lengths whose maximal parameter is $k$ and then sampling $u$. Give each length probability at least the reciprocal of twice the number of lengths: use a fixed block of random bits and map surplus indices to the first length. This avoids unbounded rejection sampling. A success $N^{-c}$ on infinitely many $N$ would give success at least $k^{-3c-O(1)}$ on infinitely many $k$, contradicting the stated core hardness. Thus this implication handles arbitrary length-sensitive inverters, not merely an inverter that ignores padding. The core hardness statement itself is not proved.

Stress test: injection is compatible with easy inversion.

Replace the quadratic rows by independent affine rows $Q(x)=Ax+b$, with $A\in{\mathbb{F}}_2^{3k\times k}$. The fixed-pair collision probability is the same $2^{-3k}$, so $8.3$ still holds. Yet Gaussian elimination finds a preimage in polynomial time on every output in the image, even when $A$ is rank deficient. Thus both the near-injectivity bound and its union-bound proof are incapable of distinguishing this easy family from the quadratic candidate.

Nor is hardness on a uniform right-hand side the right hypothesis. For each seed the image has at most $2^k$ elements in a space of size $2^{3k}$, so an independent uniform $y$ lies in it with probability at most $2^{-2k}$. Failure to solve $Q(x)=y$ under that sampling law would usually mean that a preimage does not exist. In $8.2$ it always exists. Linearizing the monomials also fails to settle the issue: set $z_{ij}=x_ix_j$, solve the resulting linear equations, and one must still enforce all the relations $z_{ij}=x_ix_j$. Counting the many formal linearized solutions neither proves these constraints hard nor supplies an algorithm. In particular, no claim of cryptographic security is inferred from degree two or from the number of equations.

A complementary obstruction to overcompression.

For an arbitrary map $f$ on uniform inputs, put $p_y=\Pr[f(U_N)=y]$. An inverter that samples $T$ independent inputs and returns the first one matching a supplied output has failure probability \[ \sum_y p_y(1-p_y)^T\le \frac{|\operatorname{im}f|}{T+1}. \tag{8.4} \] For $0\le p\le1$, the maximum of $p(1-p)^T$ is at $p=1/(T+1)$ and is at most $1/(T+1)$; summing proves the bound. A polynomial-size image is therefore incompatible with one-wayness: choose a polynomial number of trials larger than six times a polynomial upper bound for that image. The candidate $8.2$ has a much larger image, so this is an obstruction to a different compression strategy, not its inverter.

Finally, $\mathsf P=\mathsf{NP}$ would invert every polynomial-time family on its image by deciding successively whether a preimage extends a chosen prefix. The queried relation is in NP and has polynomial-size inputs. Establishing the missing hardness for $8.2$ would thus already imply $\mathsf P\ne\mathsf{NP}$. The converse is not available: sparse worst-case difficulty need not be sampled with nonnegligible probability.

Outcome.

Outcome: Exploratory approach with unresolved gap. The proposed family meets the exact uniformity, input-length and polynomial-output-length requirements, and its collision estimate and all-length padding reduction are proved above. Its planted inversion hardness has not been established. The affine countermodel shows why the strongest easy estimate obtained here is not evidence of that hardness. The map is a candidate to analyze, not a proved one-way function or a claim of a new cryptographic primitive.

Sources

• S1 Shuichi Hirahara, Zhenjian Lu, and Igor C. Oliveira, One-Way Functions and pKt Complexity, IACR ePrint 2024/1388 $2024$. https://eprint.iacr.org/2024/1388.pdf. Catalogue formulation source.
• S2 One-Way Functions and pKt Complexity — Hirahara, Lu and Oliveira. https://wrap.warwick.ac.uk/id/eprint/187935/1/WRAP-One-way-functions-pKt-complexity-24.pdf. Catalogue research/status reference; not a proof endorsement.
• S3 One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity — Liu and Pass. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.97. Catalogue research/status reference; not a proof endorsement.