Basing One-Way Functions on NP-Hardness

Basing One-Way Functions on NP-Hardness

Definitions and mathematical statement

A worst-case hardness assertion excludes an efficient algorithm correct on every input; average-case inversion hardness bounds success on $f(U_n)$, where $U_n$ is uniform on $\{0,1\}^n$. The desired construction and reduction would establish \[ \mathsf P\ne\mathsf{NP}\quad\Longrightarrow\quad \exists\text{ a one-way function family}. \] More operationally, an efficient inverter with nonnegligible success would be transformed into an efficient solver for an NP-hard decision problem. The class of allowed reductions matters: an obstruction to a restricted black-box reduction does not by itself refute the unrestricted goal. The catalogue leaves this reduction model broad.

Formulation and concept references: [S1].

Short English statement

Can worst-case NP-hardness alone be turned into the average-case inversion hardness needed for one-way functions?

Research attempt

Scope, process, and a correction to the source context.

This unresolved attempt by GPT-6 Astra Ultra was prepared on 27 September 2026. The strategy is to make the missing worst-case-to-average-case step quantitative, then test it on exact distributions. The assumption is $\mathsf P\ne\mathsf{NP}$ alone. Replacing it by a conjecture about randomized algorithms, or by average-case hardness, would change the question.

The author-hosted version of Akavia--Goldreich--Goldwasser--Moshkovitz [E1], corresponding to [S1], studies restricted reductions. Its nonadaptive result gives a consequence $\mathsf{coNP}\subseteq\mathsf{AM}$ from a reduction of the stated kind. Crucially, the authors' 2010 erratum [E2] identifies a gap in the more general adaptive argument; it preserves the nonadaptive analysis and an adaptive special case with polynomially bounded fibers. The unrestricted adaptive assertion from the older abstract is not used. Even the unaffected result is a conditional obstruction to a reduction class, not a disproof of the full implication in the catalogue.

The recent references also retain extra hypotheses. The zero-knowledge result [S2] assumes $\mathsf{NP}\not\subseteq\mathsf{ioP/poly}$ and particular nontrivial zero-knowledge protocols. The boundary-complexity result [S3] states its derandomization assumption for its deterministic-complexity characterization. Hirahara [S4] requires NP-hardness of the specified meta-computational approximation problem as well as worst-case NP hardness. None of those additional inputs follows merely by renaming $\mathsf P\ne\mathsf{NP}$. Their statements were checked for scope; their full proofs are not independently certified here.

Quantifiers and the easy direction.

Write $f_n:\{0,1\}^n\to\{0,1\}^{m(n)}$, with polynomially bounded output length and one uniform polynomial-time evaluation algorithm. For an inverter $I$, set \[ s_I(n)=\Pr_{X\leftarrow\{0,1\}^n,I} [I(1^n,f_n(X))\in f_n^{-1}(f_n(X))]. \] The preimage must have length $n$, but need not be the sampled $X$. One-wayness requires $s_I$ to be negligible for every probabilistic polynomial-time $I$. Its negation for this particular family says that some such $I$ and constant $c>0$ have $s_I(n)>n^{-c}$ on infinitely many lengths. It does not say that one inverter succeeds almost always, or succeeds at every length. A proposed reduction must not strengthen this negation without an argument.

The reverse implication, existence of a one-way function implies $\mathsf P\ne\mathsf{NP}$, has a short proof. If P equals NP, consider the language of triples $(1^n,y,u)$ such that some $n$-bit extension $z$ of prefix $u$ satisfies $f_n(z)=y$. The witness $z$ is polynomial in the input length, and evaluation and prefix checking are polynomial-time, so this language would be in P. Start with the empty prefix and ask whether it can be extended after appending zero. Keep zero if so, and otherwise keep one. On $y$ in the image, induction retains an extendible prefix. After $n$ queries the result is a valid preimage. This is one deterministic polynomial-time inverter on every image value, contradicting one-wayness. The converse direction requested here is precisely what this search argument does not supply.

In fact the same construction rules out one-way functions under the weaker assumption $\mathsf{NP}\subseteq\mathsf{BPP}$. Use the bounded-error decider for the same prefix language, and reduce each query error to $1/(3n)$ by majority repetition. For example an odd number of repetitions at least $27n$ suffices by Chebyshev's inequality, since each trial has bias at least $1/6$ from one half. Even with adaptively selected prefixes, the uniform error bound holds conditional on each history. A union bound on the $n$ queries gives a valid preimage with probability at least $2/3$ on every image value. All repetition costs are polynomial. Thus deriving one-way functions from the catalogue premise would also imply $\mathsf P\ne\mathsf{NP}\Longrightarrow\mathsf{NP}\not\subseteq\mathsf{BPP}$; this additional consequence cannot be silently taken as the premise.

Lemma 33.1: worst-case hardness survives extreme density loss.

Let $L$ be any NP-complete binary language and define \begin{equation}\label{wsref-0-72-33-33-3a-70-61-64-64-69-6e-67} L_{\rm pad}=\{1^{n^2}0x:\ |x|=n,\ x\in L\}. \end{equation} Then $L_{\rm pad}$ is NP-complete, but the deterministic algorithm that always says no has exponentially small error on uniform strings of each sufficiently large length.

Proof. Mapping $x$ to $1^{|x|^2}0x$ is a polynomial-time many-one reduction. Membership in the padded language is verified by checking the format and then using the NP witness for $x\in L$. Thus both hardness and NP membership hold. At length $M=n^2+n+1$, at most $2^n$ strings have this format. The proportion accepted by the language, and hence the error of the constant-no algorithm, is at most \[ 2^{n-M}=2^{-n^2-1}. \] At every other length the language is empty. For $n\ge1$, $n^2+1\ge M/2$, so the error bound is at most $2^{-M/2}$ on the nonempty length classes. $\square$

This is not a sparse NP-complete set in the usual polynomial-cardinality sense: the format permits $2^{\Theta(\sqrt M)}$ strings. The argument therefore does not invoke, or contradict, sparse-hard-set theorems. It shows directly that deterministic worst-case NP-hardness says nothing like constant error on the uniform input distribution. A distribution supported on the padded format would behave differently. Choosing the right distribution is part of a reduction, not an innocuous encoding convention.

Likewise, an efficiently generated instance need not be distributed uniformly among distinct possible instances. If $F$ maps $m$ uniform seed bits to an instance, its output mass at $y$ is $2^{-m}|F^{-1}(y)|$. Large fibers are sampled more often. An algorithm which is good on this distribution may omit a small collection of particular worst-case targets completely. The following lemma states a sufficient condition for transferring its guarantee.

Lemma 33.2: a distribution-transfer certificate.

Fix $n$ and let $\mu_n$ be the law of $f_n(U_n)$. An inverter $I$ has failure probability \[ \epsilon_n=\sum_y\mu_n(y)e_I(y),\qquad e_I(y)=\Pr_I[f_n(I(1^n,y))\ne y], \] where invalid-length outputs count as failures. Consider a reduction on an input $x$ that prepares $q$ nonadaptive queries of this same length. Write $D_{x,j}$ for the marginal law of query $j$. Suppose, for every $x,j,y$, that \begin{equation}\label{wsref-0-72-33-33-3a-64-6f-6d-69-6e-61-74-69-6f-6e} D_{x,j}(y)\le\kappa\mu_n(y). \end{equation} Suppose also that its polynomial-time postprocessing always gives the correct answer whenever all returned preimages are valid, regardless of which valid preimages are returned. Then plugging in fresh independent runs of $I$ makes its error at most $q\kappa\epsilon_n$.

Proof. Because the queries are prepared without using inversion answers, the failure probability at query $j$ is \[ \sum_yD_{x,j}(y)e_I(y) \le\kappa\sum_y\mu_n(y)e_I(y)=\kappa\epsilon_n. \] A union bound over the queries finishes the proof. The queries themselves may be correlated; independence between their values is not required. Only their marginals and the freshly run inverter coins enter this bound. $\square$

If $q,\kappa,n$ are polynomially bounded in $|x|$, the reduction and inverter are efficient, and $\epsilon_n\le1/(3q\kappa)$ at all required lengths, this gives a bounded-error randomized solver. The lemma does not construct the distributions satisfying (r33:domination), the sound postprocessing, or the required inverter. For adaptive queries, the same proof works if the domination hypothesis holds after every possible prior history, with fresh inverter coins at the next step. An unconditional average over histories cannot simply be substituted for that conditional hypothesis. This is an elementary transfer lemma, not a replacement proof for [E1].

A sharp failure of average-to-worst-case transfer.

Take the identity function on $n$ bits and let $I$ return its input except that it fails on $0^n$. Its average failure on $\mu_n=U_n$ is $2^{-n}$. A query distribution concentrated on $0^n$ nevertheless has failure one. The least possible domination factor for that query is $\kappa=2^n$, so the bound from Lemma 33.2 is exactly one. Calling the average error negligible does not turn it into a useful worst-case bound.

This example uses an easy function deliberately: it refutes a purported inference about probability distributions without assuming any unproved hard function. It is not a lower bound against reductions allowed to exploit the function's code. In particular, the identity has a perfect inverter; the example concerns a reduction which must be sound when provided with the specified high-average-success inverter.

The opposite endpoint is equally important. A merely nonnegligible average success $s_I(n)$ does not supply the small failure $\epsilon_n$ used by Lemma 33.2. Let $p(y)$ be the success probability on an individual image value. Repeating $I$ independently $t$ times and verifying its answers yields average success \begin{equation}\label{wsref-0-72-33-33-3a-72-65-70-65-74-69-74-69-6f-6e} \sum_y\mu_n(y)\left(1-(1-p(y))^t\right). \end{equation} If $p(y)$ equals one on a set of mass $\eta$ and zero elsewhere, this quantity is $\eta$ for every $t$. Repetition removes bad coins on a good instance; it cannot create success on instances the inverter never solves. A worst-case-to-average-case reduction needs an additional mechanism to redistribute its target into that good region while preserving a way to recover the original answer.

Two further logical gaps in the proposed reduction.

First, a randomized solver for an NP-complete language yields $\mathsf{NP}\subseteq\mathsf{BPP}$. It does not, by definition alone, yield $\mathsf P=\mathsf{NP}$. The latter requires deterministic deciders. Thus an argument contradicting only $\mathsf{NP}\not\subseteq\mathsf{BPP}$ would establish a theorem under a different hardness assumption. To use exactly the catalogue premise, one must also justify the removal of that randomness, or derive another genuine contradiction to $\mathsf P\ne\mathsf{NP}$. No such step is supplied here.

Second, a reduction which needs a good inverter at a computable length $n=n(|x|)$ cannot infer this from nonnegligible success on an unknown infinite set of lengths. The successful lengths can have arbitrarily large gaps from the proposed embedding lengths. Padding to a larger length helps only if an appropriate good length can be found within the permitted polynomial budget and inversion can be transferred back. Neither property follows from infinitude alone. These are uniformity and quantifier issues, not objections to the possibility of a more sophisticated reduction.

Verification, continuation, and outcome.

The companion exact checks enumerate the padded format at small lengths, verify its density formula, and compute the identity-function failure example and (r33:repetition) with rational arithmetic. They also check the domination inequality on finite distributions. The written proofs establish the general lemmas; finite examples do not decide any complexity-class separation.

UNRESOLVED. The attempt proves an explicit density-loss example and a quantitative sufficient transfer lemma, and identifies exactly where their hypotheses fail for a generic inversion claim. A successful continuation needs a uniform construction and reduction that transports worst-case NP instances to the actual image distribution, tolerates the nonnegligible and infinitely-often success given by failure of one-wayness, and resolves the deterministic-versus-randomized premise. The restricted literature barriers and these examples do not rule out all such reductions. No one-way function has been derived from $\mathsf P\ne\mathsf{NP}$ here.

Sources

• S1 A. Akavia, O. Goldreich, S. Goldwasser and D. Moshkovitz, 'On basing one-way functions on NP-hardness', Proc. 38th Annual ACM Symp. on Theory of Computing (STOC), 2006, pp. 701-710. DOI:10.1145/1132516.1132614. https://api.openalex.org/works/doi:10.1145/1132516.1132614. Formulation source.
• S2 Non-Trivial Zero-Knowledge Implies One-Way Functions. https://arxiv.org/abs/2602.17651. Further reference; not a proof endorsement.
• S3 Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity. https://eccc.weizmann.ac.il/report/2025/125/. Further reference; not a proof endorsement.
• S4 Capturing One-Way Functions via NP-Hardness of Meta-Complexity. https://eccc.weizmann.ac.il/report/2023/037/. Further reference; not a proof endorsement.
• E1 Adi Akavia, Oded Goldreich, Shafi Goldwasser and Dana Moshkovitz, On Basing One-Way Functions on NP-Hardness, STOC 2006, 701--710, author-hosted proceedings paper corresponding to [S1]. https://people.csail.mit.edu/akavia/2006-stocAGGM.pdf. Reduction-model context; read together with the erratum below.
• E2 Adi Akavia, Oded Goldreich, Shafi Goldwasser and Dana Moshkovitz, Errata for: On Basing One-Way Functions on NP-Hardness, 8 February 2010. https://people.csail.mit.edu/akavia/AGGM_errata.pdf. Identifies the gap in the general adaptive argument and specifies unaffected cases. Additional references consulted 27 September 2026.

Basing One-Way Functions on NP-Hardness

Definitions and mathematical statement

A worst-case hardness assertion excludes an efficient algorithm correct on every input; average-case inversion hardness bounds success on $f(U_n)$, where $U_n$ is uniform on $\{0,1\}^n$. The desired construction and reduction would establish \[ \mathsf P\ne\mathsf{NP}\quad\Longrightarrow\quad \exists\text{ a one-way function family}. \] More operationally, an efficient inverter with nonnegligible success would be transformed into an efficient solver for an NP-hard decision problem. The class of allowed reductions matters: an obstruction to a restricted black-box reduction does not by itself refute the unrestricted goal. The catalogue leaves this reduction model broad.

Formulation and concept references: [S1].

Short English statement

Can worst-case NP-hardness alone be turned into the average-case inversion hardness needed for one-way functions?

Research attempt

Current frontier.

Akavia--Goldreich--Goldwasser--Moshkovitz's nonadaptive-reduction obstruction has important model hypotheses; it is not a disproof of the unrestricted implication in this entry. Their adaptive result required a 2010 erratum. Bogdanov--Brzuska subsequently prove, in Theorem 1, that a language admitting their reduction to an approximately size-verifiable function belongs to $\mathsf{AM}\cap\mathsf{coAM}$. The theorem and the unaffected nonadaptive result, rather than an unqualified reading of the original abstract, are the relevant barriers. [S1], [E1], [E2].

Hirahara's meta-complexity characterization assumes the NP-hardness of a specific approximation problem in addition to worst-case NP hardness; Liu--Pass's boundary characterization retains a substantial derandomization assumption for ordinary time-bounded Kolmogorov complexity. [S3], [S4]. The 2026 zero-knowledge implication assumes $\mathsf{NP}\not\subseteq\mathsf{ioP/poly}$ and existence of specified nontrivial zero-knowledge protocols. It does not replace those hypotheses by $\mathsf P\ne\mathsf{NP}$. [S2], [E3]. These are statement-level comparisons, not independent audits of the complete recent proofs.

Attack route.

I try to start from a transparent worst-case NP-hard inversion task and amplify it by independent products. This separates the two jobs often conflated in a proposed proof: encoding NP witnesses into an image fiber, and ensuring that uniformly sampled inputs encounter hard fibers often enough. The attempted construction below has the first property exactly. I then prove that every number of independent repetitions of this particular construction still permits an efficient average-case inverter. A second check isolates the difference between deterministic worst-case hardness and resistance to randomized inversion.

Attempt.

Fix a standard padded Boolean formula encoding: a description $z$ of $n$ bits has at most $n$ variables, and $V(z,w)$, for $w\in\{0,1\}^n$, evaluates that assignment, ignoring unused bits. Invalid descriptions have value zero. This is polynomial time, and every formula can be padded to such a format with polynomial overhead. Define \begin{equation}\label{wsref-0-72-33-33-3a-72-61-72-65} G_{3n}(r,z,w)= \begin{cases} 1\,\|\,r\,\|\,z\,\|\,w,&r\ne0^n,\\ 0\,\|\,0^n\,\|\,z\,\|\,V(z,w)\,\|\,0^{n-1},&r=0^n, \end{cases} \end{equation} where all three input blocks have $n\ge1$ bits. The output always has $3n+1$ bits. At positive input lengths not divisible by three, use $G_N(x)=1\|x$. Thus the evaluation algorithm is one uniform polynomial-time algorithm on every length; inversion is allowed to return any preimage.

Lemma 33.1 (hard worst-case fibers, easy uniform inversion). A polynomial-time algorithm that inverts $G$ correctly on every image point would decide SAT in polynomial time. Nevertheless a deterministic inverter succeeds on $G_{3n}(U_{3n})$ with probability at least $1-2^{-n}$.

Proof. For a formula encoded by $z$, query the hypothetical inverter on $0\|0^n\|z\|1\|0^{n-1}$. If the formula is satisfiable, this is an image point and every valid preimage contains a satisfying $w$. If it is unsatisfiable, no answer passes the direct check $V(z,w)=1$. One runs the fixed polynomial-time inverter and verifies its answer, so no correctness assumption on nonimage points is needed. This is an ordinary worst-case reduction for the inversion task, not an average-case reduction.

For the average-case algorithm, an output starting in one displays its entire original input. Return that input and fail on outputs starting in zero. The probability of the latter branch is exactly $2^{-n}$, because $r$ is uniform. This proves the claimed success bound.$\square$

Consequently "inversion is NP-hard in the worst case" does not imply that the same function is one-way. This example does not refute the existence of another reduction or a different one-way function under $\mathsf P\ne\mathsf{NP}$.

Lemma 33.2 (the independent-product repair also fails). Consider the componentwise product of $k\ge1$ copies of $G_{3n}$, with $n,k$ given as parsing parameters. There is one inverter, polynomial in the total input/output length $\Theta(nk)$, whose success on uniformly sampled product inputs is bounded below by an absolute positive constant for every $n,k$, and tends to one in the small-$k$ regime as $n\to\infty$.

Proof. Compare the integers $k^2$ and $2^n$, a polynomial-time operation on their binary representations. If $k^2\le2^n$, invert each explicit branch as above and fail if any block is on the rare branch. By the union bound, \begin{equation}\label{wsref-0-72-33-33-3a-73-6d-61-6c-6c-70-72-6f-64-75-63-74} \Pr[\text{success}]=(1-2^{-n})^k \ge1-k2^{-n}\ge1-2^{-n/2}\ge1-2^{-1/2}>0. \end{equation} If $k^2>2^n$, enumerate the $2^n$ assignments for each rare block, using $V$ to find a preimage with the indicated output bit. On sampled image points such a preimage exists, including when that bit is zero. The work is at most $k2^n\operatorname{poly}(n)<k^3\operatorname{poly}(n)$, which is polynomial in $nk$. This branch succeeds with probability one. Malformed inputs may be rejected immediately, and the enumeration stops after its explicitly bounded list even on nonimage points. Hence the algorithm has a worst-case polynomial running-time bound.$\square$

The lemma holds even when $k$ is exponentially large as a function of $n$: in that regime brute-force search is affordable in the new total input length. It is not legitimate to call the brute force exponential without specifying which security parameter is being charged. The result is specific to this rare-core encoding and does not disprove general hardness amplification, whose starting point needs an appropriate inverse-polynomial hardness fraction.

Can a reduction ignore distributional exposure? No. If an inverter is perfect outside a set of image points of measure $\varepsilon$ under $G(U)$, its behavior on that set can be arbitrary. A reduction placing its important query inside that set cannot use the average success guarantee alone. Even when every query marginal has the same distribution as $G(U)$, nonnegligible inverter success does not imply that a polynomial collection of queries contains all the answers a reduction needs. An actual worst-case-to-average-case reduction must prove how arbitrary successful fibers can be used, not just show that some hard fiber exists. The nonadaptive barriers in [E2] make this demand substantive; they do not rule out every possible adaptive or non-black-box construction.

Lemma 33.3 (a randomized-hardness dependency). If $\mathsf{NP}\subseteq\mathsf{BPP}$, then no one-way function family in the sense of UnsolvedMath problem 3403 exists.

Proof. Fix any deterministic polynomial-time family $f_n$ with polynomial output length. The language \[ Q_f=\{\langle1^n,y,u\rangle: \exists x\in\{0,1\}^n\text{ extending }u,\ f_n(x)=y\} \] is in NP. Under the hypothesis it has a uniform randomized polynomial-time decider. Amplify its error to at most $1/(3(n+1))$ per query. For an image point $y$, start with the empty prefix, ask whether a preimage extending $u0$ exists, and append zero if yes and one otherwise. With fresh coins on each query, the conditional error bound holds even though the prefixes are adaptive. A union bound implies all $n$ decisions are correct with probability at least $2/3$. Then the resulting $x$ is a valid preimage. Verify it and otherwise output failure. This is a polynomial-time inverter with constant success on every image point, contradicting one-wayness. $\square$

The original target therefore entails the additional implication \begin{equation}\label{wsref-0-72-33-33-3a-64-65-70-65-6e-64-65-6e-63-79} \mathsf{NP}\subseteq\mathsf{BPP}\quad\Longrightarrow\quad \mathsf P=\mathsf{NP}. \end{equation} Indeed, its contrapositive premise would produce an OWF, contradicting Lemma 33.3. The elementary observation does not establish (r33:dependency); it warns that a merely randomized solver for an NP-hard language is not automatically a contradiction to $\mathsf P\ne\mathsf{NP}$. Any claimed deterministic worst-case foundation has to address that quantifier issue.

Stress test.

The hard-fiber reduction is verified only for perfect worst-case inversion. Replacing that oracle by an algorithm with small average success is exactly the unjustified step being tested. The output padding keeps image lengths and malformed outputs explicit; no recovery of the originally sampled witness is required. Product success in (r33:smallproduct) uses independent inputs, but the constructed inverter's validity does not assume an arbitrary adversary treats blocks independently.

The accompanying exact tests use small truth tables for $V$, enumerate preimages of the encoded function, and verify the rare-branch probability and product inequalities. The finite experiments do not establish SAT hardness; that follows from the stated reduction with a universal verifier. The supplied source's broad reduction model is preserved, and its existing bibliography remains unchanged. The 2010 erratum is recorded rather than silently citing the original adaptive theorem as if its proof were intact.

\Needspace{8\baselineskip}

Outcome.

Outcome: Exploratory approach with unresolved gap.

An explicit uniformly computable family has NP-hard worst-case inversion but an easy uniform-input inverter, and the proposed independent-product repair is defeated for every product length by a parameter-sensitive inverter. The attempt also proves a randomized-hardness consequence any positive resolution must respect. These are obstructions to particular routes, not a counterexample to the unrestricted implication $\mathsf P\ne\mathsf{NP}\Rightarrow\mathrm{OWF}$. No construction overcoming the distributional exposure and deterministic-versus-randomized gaps is supplied, and historical novelty of these elementary deductions is not asserted.

Sources

• S1 A. Akavia, O. Goldreich, S. Goldwasser and D. Moshkovitz, 'On basing one-way functions on NP-hardness', Proc. 38th Annual ACM Symp. on Theory of Computing (STOC), 2006, pp. 701-710. DOI:10.1145/1132516.1132614. https://api.openalex.org/works/doi:10.1145/1132516.1132614. Catalogue formulation source.
• S2 Non-Trivial Zero-Knowledge Implies One-Way Functions. https://arxiv.org/abs/2602.17651. Catalogue research/status reference; not a proof endorsement.
• S3 Hardness Along the Boundary: Towards One-Way Functions from the Worst-case Hardness of Time-Bounded Kolmogorov Complexity. https://eccc.weizmann.ac.il/report/2025/125/. Catalogue research/status reference; not a proof endorsement.
• S4 Capturing One-Way Functions via NP-Hardness of Meta-Complexity. https://eccc.weizmann.ac.il/report/2023/037/. Catalogue research/status reference; not a proof endorsement.
• E1 Adi Akavia, Oded Goldreich, Shafi Goldwasser and Dana Moshkovitz, Erratum for: On basing one-way functions on NP-hardness, STOC 2010, p. 795. https://doi.org/10.1145/1806689.1806798. Erratum metadata and its affected adaptive result checked via the institutional record and [E2], 27 September 2026.
• E2 Andrej Bogdanov and Christina Brzuska, On Basing Size-Verifiable One-Way Functions on NP-Hardness, ECCC TR14-108 $2014$, Theorem 1 and the footnote on the unaffected nonadaptive theorem; TCC 2015, pp. 1--6. https://eccc.weizmann.ac.il/report/2014/108/download. https://doi.org/10.1007/978-3-662-46494-6_1. Use is of Theorem 1, not the inconsistent inclusion written in the report abstract/corollary. Checked 27 September 2026.
• E3 Suvradip Chakraborty, James Hulett, Dakshita Khurana and Kabir Tomer, Non-Trivial Zero-Knowledge Implies One-Way Functions, arXiv:2602.17651v1, 19 February 2026, abstract and assumption package. https://arxiv.org/abs/2602.17651v1. Version-specific supplement to [S2], checked 27 September 2026; no full proof audit claimed.