Existence of One-Way Permutations

Existence of One-Way Permutations

Definitions and mathematical statement

For every $n\ge1$, require a bijection $f_n:\{0,1\}^n\to\{0,1\}^n$, with one polynomial-time algorithm evaluating $f_n(x)$ from $(1^n,x)$. For each probabilistic polynomial-time $A$, require \[ \Pr_{x\leftarrow\{0,1\}^n,A}[A(1^n,f_n(x))=x]\le\eta_A(n), \] where $\eta_A$ is negligible. Since $f_n$ is bijective, each output has exactly one preimage. This is an unconditional existence problem on all binary strings of each length, without sampled keys or variable domains.

Formulation and concept references: [S1].

Short English statement

Can a length-preserving bijection be easy to compute but negligibly likely to be inverted by any efficient randomized algorithm?

Research attempt

Current frontier.

Research date: 27 September 2026. The distinction between a single length-preserving permutation and a collection indexed by sampled public keys is essential here. Goldreich's clarification distinguishes full-cube index sets from merely samplable index sets, and explicitly warns that the inverter need not receive the coins used to generate an index. The present target is the single, uniformly computable, full-cube version, not a keyed version with a hidden setup tape. [E1]

The inherited formulation reference [S1] is a separation result: Asharov--Segev rule out the specified fully black-box, domain-invariant construction from one-way functions and indistinguishability obfuscation for oracle-aided circuits. This is an established restriction on a construction model, not a disproof of the present existence statement. The publisher's abstract and the authors' presentation were consulted; this notebook does not claim to have independently audited their full separation proof. [E2]

A relevant positive development is the conditional full-input-domain trapdoor-permutation construction in Shmueli--Zhandry's 2025 manuscript: Theorem 6 assumes sub-exponentially secure indistinguishability obfuscation and one-way functions. Their Section 1.4 distinguishes input-domain invariance from key-domain invariance, explaining why its conclusion does not contradict the preceding barrier. Construction 41 still generates a public key and a secret key. Neither this hypothesis package nor its sampled-key conclusion supplies the unconditional family required here. The cited theorem is treated as a manuscript result, not independently certified by this notebook. [S2], [E3]

Two further facts delimit the attack. Direct-product amplification of weak one-wayness is classical; the proof below supplies the quantitative step needed here rather than presuming independence of an inverter's outputs. [E4] The 2025 in-place-query result gives a quantum permutation inverter using $O(\sqrt{M})$ queries on an $M$-element domain. With $M=2^n$, this is not a polynomial-in-$n$ algorithm, and a query theorem does not establish classical, code-aware computational hardness. [S3], [E5] None of these inspected results supplies an unconditional solution of the exact entry.

Attack route.

Four routes were considered. First, compile a sampled-key construction into one full-cube map; the missing ingredient is a way to obtain useful public descriptions without also revealing their generation trapdoors. Second, allow hardness only on a recognizable, inverse-polynomial-density part of the cube, then combine a bijective extension with hardness amplification; the missing ingredient becomes an explicit hard partial action rather than a perfect full-domain construction. Third, obtain hardness from cycle geometry or from elementary reversible gates; the issue is whether the proposed structure already gives an inverse. Fourth, prove a direct lower bound for the unique inverse's bits; this would require an average-case lower bound inside unambiguous complexity classes. The second route yields a fully specified conditional normalization theorem. The other routes are pursued as construction attempts and adversarial tests, not as additional catalogue problems.

Attempt.

Throughout, $U_m$ is uniform on $\{0,1\}^m$. Algorithms are uniform and have a polynomial worst-case running-time bound, including over their random coins. A wrong-length output or a distinguished failure symbol $\bot$ counts as failure. Quantities called negligible satisfy the all-sufficiently-large-lengths convention of the original statement. All lemmas below are proved in this notebook; historical novelty is not asserted, and the amplification mechanism is explicitly classical.

A. Attempting to remove the generated key. Write a deterministic execution of a randomized key generator as \[ (\operatorname{pk}_m(r),\operatorname{sk}_m(r)) =\operatorname{Gen}(1^m;r),\qquad r\in\{0,1\}^{\ell_m}. \] Assume, even favorably, that every seed produces a valid permutation $P_{m,r}$ of $\{0,1\}^m$, that $\ell_m$ is polynomially bounded, and that both $P_{m,r}$ and its inverse can be evaluated in polynomial time given $r$ (the inverse uses the regenerated secret key). These assumptions only strengthen this candidate construction's correctness. The input/output interface of Construction 41 motivates this test. [E3]

The obvious seed-preserving packing is \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-73-65-65-64} B_m(r,x)=(r,P_{m,r}(x)). \end{equation} It is a bijection, but its inverse is explicitly \[ B_m^{-1}(r,y)=(r,P_{m,r}^{-1}(y)). \] The inverter regenerates the secret key from $r$. Thus keeping the seed, although it solves the encoding and bijectivity problems, destroys the intended hardness. Conversely, discarding the seed is not a generally valid injectivity argument; different seeds can generate the same public description. Sampling a public key cannot simply be replaced by fixing a convenient seed: the fixed seed is then reproducible by the inverter. Existence of good keys also does not exhibit a polynomial-time procedure selecting a good key at every length. These are separate issues from the security of a correctly generated public key.

Could one hide the seed instead? The following exact calculation shows the circularity of a broad such proposal.

Lemma A (masked-seed equivalence). Let $h_m:\{0,1\}^{\ell_m}\to\{0,1\}^{\ell_m}$ be efficiently evaluable and put \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-6d-61-73-6b-65-64} F_m(r,x)=\left(h_m(r),P_{m,r}(x)\right). \end{equation} Then $F_m$ is a bijection if and only if $h_m$ is a bijection. In that case an inverter for $F_m$ gives an inverter for $h_m$ with at least the same average success, while an inverter for $h_m$ gives an inverter for $F_m$ with the same average success. The reductions have polynomial running time in $m+\ell_m$ and use the same parameter $1^m$.

Proof. For any $(z,y)$ the number of its preimages under $F_m$ is exactly $\#h_m^{-1}(z)$: each seed in that fiber has exactly one accompanying $x=P_{m,r}^{-1}(y)$. This proves the bijectivity assertion. Given a challenge $z=h_m(r)$, sample $Y\leftarrow U_m$ and run the $F_m$-inverter on $(z,Y)$. Return its seed component after checking $h_m(r')=z$. Conditional on $r$, $P_{m,r}(U_m)$ is uniform, so this is exactly the joint distribution in an $F_m$ inversion experiment. Whenever the full inversion succeeds, the recovered seed is correct. In the reverse direction, recover $r$ from $z$ and then compute $P_{m,r}^{-1}(y)$. Verify the seed before using it. Bijectivity of $h_m$ makes this successful exactly when the seed inverter is successful. $\square$

This proves more than the failure of the unmasked example. In this seed-indexed design, any hardness of the entire construction must already reside in $h_m$. If $h_m$ has an efficient inverse, so does $F_m$; if it does not, the missing hardness has merely moved to a length-preserving bijection on the seed space. No average-case hardness has been created by the trapdoor permutation in the second coordinate. Polynomial comparability of the relevant length parameters would still be required to translate this parameterized equivalence into the precise all-length definition of the target.

B. A conditional dense-domain construction with all lengths handled. Instead of exposing a generation tape, consider a deterministic, recognizable domain of usable descriptions and data. The following hypothesis makes the remaining work explicit.

Hypothesis H (not established). There are fixed positive integers $r,s$, nonempty sets $D_m\subseteq\{0,1\}^m$ for every $m\ge1$, and maps $q_m:D_m\to D_m$ such that:

1. Membership in $D_m$ and evaluation of $q_m$ on $D_m$ are performed by fixed deterministic polynomial-time algorithms, and every $q_m$ is bijective.
2. For all sufficiently large $m$, the density $\rho_m=|D_m|/2^m$ satisfies $\rho_m\ge m^{-r}$.
3. For every probabilistic polynomial-time $C$, for all sufficiently large $m$ (with the threshold allowed to depend on $C$), \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-48} \Pr_{x\leftarrow\mathrm{Unif}(D_m),\,C} [C(1^m,q_m(x))=x]\le 1-m^{-s}. \end{equation}

The same $r,s$ work for every $C$. This hypothesis only asks for a weak average-case failure rate on $D_m$, not negligible inversion success. It does not contain a hidden seed or grant an oracle to the evaluator. Sampling from $D_m$ is not an additional algorithmic assumption below; its uniform distribution specifies the hardness experiment.

Proposition B (conditional normalization theorem). Hypothesis H implies a family meeting every quantifier and domain requirement in UnsolvedMath problem 30006696. The construction is explicit relative to the membership and evaluation algorithms in H.

Step 1: totalize without losing bijectivity. Define \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-67-75-61-72-64} g_m(x)=\begin{cases}q_m(x),&x\in D_m,\\x,&x\notin D_m.\end{cases} \end{equation} Both pieces preserve their respective disjoint sets, so $g_m$ is a uniform polynomial-time permutation of the whole cube. For any inverter $C$, its success on a uniform input decomposes exactly into the conditional successes on $D_m$ and its complement. Applying (eq:30006696:H) to the restriction of $C$ gives, eventually, \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-77-65-61-6b} \Pr[C(1^m,g_m(U_m))\ne U_m] \ge \rho_m m^{-s}\ge m^{-(r+s)}. \end{equation} The first inequality uses only failure on $D_m$; behavior outside it is irrelevant. Nevertheless, simply returning the input inverts $g_m$ with probability at least $1-\rho_m$. Thus totalization alone is not the strong one-wayness demanded by the problem.

Step 2: a verified quantitative amplification lemma. The next argument is a self-contained direct-product proof, in the classical weak-to-strong framework. [E4] It is important that it allows a joint inverter on all blocks.

Lemma C (random-position extraction). Let $g$ be an efficiently evaluable permutation of a finite binary cube $\Omega$, let $k,R$ be positive integers, and let $A$ invert the $k$-fold direct product on a uniform challenge with probability $\epsilon$. If $0<\epsilon_0\le\epsilon$, there is a repeated random-position inverter $C$ for $g$ whose failure probability is at most \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-65-78-74-72-61-63-74} \frac{\log(2/\epsilon_0)}{k} +\exp\left(-\frac{R\epsilon_0}{2k}\right), \end{equation} using at most $R$ runs of $A$ and $O(Rk)$ evaluations of $g$. For a power-of-two $k$, all random choices in this construction can be sampled exactly using a bounded number of unbiased bits.

Proof. For a challenge tuple $\mathbf y\in\Omega^k$, let \[ a(\mathbf y)=\Pr[A(\mathbf y)=(g^{\times k})^{-1}(\mathbf y)]\in[0,1], \qquad {\mathbb{E}} a(\mathbf Y)=\epsilon. \] Here $(g^{\times k})^{-1}$ denotes the inverse of the direct-product map; it is used to define success, not to compute it. For each $j$, put \[ b_j(y)={\mathbb{E}}_{\mathbf Y_{-j}}a(Y_1,\ldots,Y_{j-1},y,Y_{j+1},\ldots,Y_k), \qquad b(y)=\frac1k\sum_{j=1}^k b_j(y). \] An extraction trial on $y$ chooses $j$ uniformly, samples independent uniform inputs for the other $k-1$ positions, evaluates $g$ there, and inserts $y$ in position $j$. It runs $A$, checks every returned block using $g$, and returns block $j$ only when all checks pass. Because $g$ is a permutation, the auxiliary challenges are exactly uniform. This trial succeeds with probability exactly $b(y)$.

Set $\tau=\epsilon_0/(2k)$, let $\mathcal B=\{y:b(y)<\tau\}$, and write $\beta=\Pr[Y\in\mathcal B]$. No algorithm needs to recognize $\mathcal B$. Splitting according to whether the tuple meets this bad set and applying the union bound with the nonnegative weight $a$ gives \begin{align} \epsilon &\le \Pr[\forall j,\ Y_j\notin\mathcal B] +\sum_{j=1}^k {\mathbb{E}}[a(\mathbf Y)1_{\{Y_j\in\mathcal B\}}] \label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-62-61-64-31}\\ &= (1-\beta)^k+k{\mathbb{E}}[b(Y)1_{\{Y\in\mathcal B\}}] \le (1-\beta)^k+k\tau\beta \le (1-\beta)^k+\epsilon_0/2. \label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-62-61-64-32} \end{align} Independence is used only to evaluate the probability that none of the independently sampled challenges is bad. There is no independence assertion about $A$'s answers. Consequently \[ \epsilon_0/2\le(1-\beta)^k\le e^{-k\beta}, \qquad \beta\le\log(2/\epsilon_0)/k. \] For any $y\notin\mathcal B$, $R$ trials with fresh independent coins fail with probability at most $(1-\tau)^R\le e^{-R\tau}$. Averaging over $y$ proves (eq:30006696:extract). Each trial is verifiable without knowing the missing inverse, so the repeated algorithm stops only on a correct answer. $\square$

Step 3: instantiate the parameters and the quantifiers. Set $t=r+s$ and define integer-valued functions \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-6c-65-6e-67-74-68-73} k_m=2^{\lceil\log_2(m^{t+2})\rceil},\qquad M_m=m k_m,\qquad T_m(x_1,\ldots,x_{k_m})=(g_m(x_1),\ldots,g_m(x_{k_m})). \end{equation} The next power of two can be computed with integer arithmetic; no floating-point logarithm is needed. We have \[ m^{t+2}\le k_m<2m^{t+2},\qquad m^{t+3}\le M_m<2m^{t+3}. \] The numbers $M_m$ are strictly increasing. The power-of-two choice for $k_m$ makes position sampling use exactly $\log_2 k_m$ random bits, avoiding an unbounded rejection-sampling subroutine.

Suppose a fixed uniform polynomial-time inverter $A$ for $T_m$ has success at least $m^{-c}$ for infinitely many $m$, where $c$ is a fixed positive integer. Apply Lemma C with \[ \epsilon_0=m^{-c},\qquad R=2k_m m^{c+t+2}. \] At every such length its derived inverter has failure at most \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-63-6f-6e-74-72-61-64-69-63-74-69-6f-6e} \frac{\log 2+c\log m}{k_m}+e^{-m^{t+2}} < m^{-t} \end{equation} for all sufficiently large $m$. The algorithm does not estimate $\epsilon$ or know which lengths are favorable. It uses the displayed parameters at every length; its exponent $c$ is a fixed constant, not advice depending on $m$. Its running time is polynomial in $m$, since $M_m,k_m,R$ are. Infinitely many violations of (eq:30006696:weak) contradict that bound's eventual validity for this one inverter. Thus the success of every uniform polynomial-time inverter for $T_m$ is negligible in $m$.

Step 4: cover every binary length, without an easy subsequence. For every $N\ge1$, compute \[ m(N)=\max\{m\ge1:M_m\le N\}. \] This exists because $M_1=1$; it can be computed by integer search in polynomial time. Split an $N$-bit string uniquely as $u\Vert z$ with $|u|=M_{m(N)}$ and define \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-61-6c-6c-6c-65-6e-67-74-68-73} f_N(u\Vert z)=T_{m(N)}(u)\Vert z. \end{equation} This is a bijection on the entire $N$-cube for every $N$, computed by one polynomial-time algorithm. The unchanged padding is independent uniform data, not a key-generation tape.

The security transfer needs a little care: one may not secretly give an inverter a favorable length as advice. Suppose a fixed inverter $A$ for (eq:30006696:alllengths) succeeds at least $N^{-c}$ for infinitely many $N$. On a challenge for $T_m$, a single uniform inverter runs $A$ for every integer \[ N\in I_m:=\{M_m,M_m+1,\ldots,M_{m+1}-1\}, \] using a fresh uniform padding string of length $N-M_m$ in each run. It verifies the proposed prefix inverse under $T_m$ and returns the first verified one. This loop is polynomial in $m$: $|I_m|\le M_{m+1}<2(m+1)^{t+3}$, and each run has polynomial input length. For each fixed $N\in I_m$, the augmented challenge has exactly the uniform $N$-bit distribution. The loop therefore succeeds with at least $A$'s success at that $N$. Infinitely many favorable $N$ give infinitely many different $m$, with success at least \[ \left(2(m+1)^{t+3}\right)^{-c}, \] a nonnegligible function of $m$. This contradicts Step 3. No favorable length has been selected nonuniformly, and both the target's all-length requirement and its universal adversary quantifier are satisfied. This completes the proof of Proposition B, conditional on H. $\square$

C. Trying to instantiate H, and finding its exact failure points. A tempting choice is to let $D_m$ consist of valid public descriptions and payloads and let $q_m$ preserve the public description while permuting the payload. For this to instantiate H one must prove, in a single fixed encoding, polynomial-time membership in $D_m$, inverse- polynomial density among all $m$-bit strings, invariance of $D_m$ under the proposed map, and the bound (eq:30006696:H) for the uniform conditional distribution. Security under a key generator's distribution does not by itself imply security under uniform valid encodings. Repeated encodings and highly unequal sampling weights can change that distribution. Adding a generation witness makes membership easier, but when that witness is the complete seed, Lemma A gives an inverse instead of hardness. Thus the construction does not currently supply an instance of H from the cited keyed result.

Inverse-polynomial density is not a cosmetic assumption. If $\rho_m$ is negligible, any polynomially bounded number $k(m)$ of copies of the guarded map (eq:30006696:guard) has an identity-inverter success of at least \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-73-70-61-72-73-65} (1-\rho_m)^{k(m)}\ge1-k(m)\rho_m. \end{equation} The proof is that all blocks outside $D_m$ are fixed, independently, and the final inequality is the union bound. For example, $\rho_m=2^{-m/2}$ cannot be amplified by polynomially many copies in this construction, no matter how difficult inversion on $D_m$ might be. An infinite search for a single difficult input, or a sparse collection of difficult encodings, would not repair the missing density condition.

There is also a concrete fatal error in a common simplified product proof. Even for the identity permutation, an algorithm may flip one coin and either output the entire correct tuple or deliberately fail every block. The joint success is $1/2$, not $2^{-k}$, although each individual block is correct with probability $1/2$. Lemma C was derived to remove exactly this unjustified independence step.

D. Structural construction attempts: gates, order, and cycles. A natural way to turn an arbitrary difficult function into a permutation is a Feistel round. For any efficiently computable $h:\{0,1\}^d\to\{0,1\}^d$, define \[ \mathcal F_h(L,R)=(R,L\mathbin\oplus h(R)). \] But \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-66-65-69-73-74-65-6c} \mathcal F_h^{-1}(U,V)=(V\mathbin\oplus h(U),U). \end{equation} Only a forward evaluation of $h$ is used by the inverse. A publicly specified polynomial sequence of such rounds is inverted by reversing the sequence, even if the round functions themselves were one-way. This attempt guarantees bijectivity too transparently.

The same defect appears in a putative universal clean reversible implementation. If a uniformly constructible polynomial-size circuit $R_n$ over a fixed set of explicitly invertible gates satisfies \[ R_n(x,0^{a(n)})=(f_n(x),0^{a(n)}), \] then reversing its gates on $(y,0^{a(n)})$ computes $f_n^{-1}(y)$ in polynomial time. Ordinary forward computation of $f_n$ does not justify this clean implementation: retaining $(x,f_n(x))$ leaves the very preimage that the inverse problem asks to recover. No claim about all polynomial-time bijections follows from the conditional circuit argument.

An order-preserving construction is also too rigid. Give the Boolean cube its coordinatewise partial order. Every order-preserving bijection of this finite poset has an order-preserving inverse: some finite power of the bijection is the identity, so the inverse is a positive power. Hence it is an order automorphism, permutes the atoms $e_1,\ldots,e_n$, and preserves joins. Since every $x$ is the join of its supported atoms, \[ f(x)=\bigvee_{i:x_i=1}f(e_i) \] is merely a coordinate permutation. The inverse can be learned with $n$ forward evaluations and then applied efficiently. The finite order used in the proof need not be found by the inversion algorithm.

Finally, let $\ell_f(y)$ be the length of the cycle containing $y$. Starting with $y$, apply $f$ until the first return to $y$. If the cycle length is at most a given cutoff $T$, the state immediately before that return is $f^{-1}(y)$. Consequently the target requires, for every polynomial $T(n)$, \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-63-79-63-6c-65-73} \Pr_{y\leftarrow U_n}[\ell_{f_n}(y)\le T(n)] \quad\text{to be negligible.} \end{equation} This condition is necessary, not sufficient: binary addition $x\mapsto x+1\pmod{2^n}$ is one cycle of length $2^n$, yet subtraction inverts it in linear time. Efficiently invertible conjugation cannot help. If $\widetilde f=h^{-1}\circ f\circ h$ with uniformly efficient $h,h^{-1}$, then the two inversion experiments reduce to each other with equal success, because $h(U_n)$ is uniform; their cycle lengths also agree. Long cycles and relabeling have not supplied a hard domain.

E. A dependency check using unique inverse bits. For any full-cube family $f$ as in the target's evaluation requirement, define the total binary language, using any fixed unambiguous tuple encoding, \[ L_f=\{\langle1^n,y,i\rangle: |y|=n,\ 1\le i\le n, \ (f_n^{-1}(y))_i=1\}. \] Malformed encodings are outside $L_f$. Recall that $\mathsf{UP}$ consists of languages having a polynomial-time nondeterministic decider with at most one accepting computation on each input; $\mathsf{coUP}$ consists of their complements. On a well-formed tuple, guess exactly $n$ bits $x$, verify $f_n(x)=y$, and check $x_i=1$. There is at most one accepting witness. For the complement, use $x_i=0$ on well-formed tuples and one deterministic accepting branch on malformed ones. Thus \begin{equation}\label{wsref-0-65-71-3a-33-30-30-30-36-36-39-36-3a-75-70} L_f\in\mathsf{UP}\cap\mathsf{coUP}. \end{equation} If $L_f$ were in $\mathsf P$, $n$ bit queries would invert $f_n$ on every output. If $L_f$ were in $\mathsf{BPP}$, amplify each bit query's error to at most $1/(10n)$ and take a union bound; this yields a uniform randomized inverter with success at least $9/10$ on every output. Therefore a family meeting UnsolvedMath problem 30006696 implies \[ \mathsf{UP}\cap\mathsf{coUP}\not\subseteq\mathsf{BPP}, \qquad \mathsf P\ne\mathsf{NP}\cap\mathsf{coNP}, \qquad \mathsf P\ne\mathsf{NP}. \] The latter two consequences follow from $\mathsf{UP}\cap\mathsf{coUP}\subseteq\mathsf{NP}\cap\mathsf{coNP}$ and $\mathsf P\subseteq\mathsf{BPP}$. Existence also implies existence of ordinary one-way functions simply by forgetting bijectivity. Thus an unconditional instantiation of H would settle more than a domain encoding problem: it would also settle catalogue Problems 1, 8, and 34. These implications are proved here; no reverse implication from a worst-case separation is being used.

A finer error audit illustrates the missing average-case estimate. Suppose a fixed randomized predictor $B(1^n,y,i)$ has average bit error \[ e_n=\frac1n\sum_{i=1}^n \Pr_{y\leftarrow U_n,B}[B(1^n,y,i)\ne(f_n^{-1}(y))_i]. \] Running it once for each bit gives a complete candidate whose failure probability is at most $n e_n$, regardless of correlations among bit errors. Hence the target forces $e_n\ge(1-\eta(n))/n$ for a negligible $\eta$ depending on this predictor. This is only a necessary estimate; small advantage over random bit guessing does not automatically recover the full inverse. Neither (eq:30006696:up) nor this estimate proves an average-case lower bound for any explicit $f$.

Stress test.

Exact target and source fit. A sampled-key theorem has not been relabeled as a key-free one. Keeping a generation tape and masking it were separately tested; their inverses and reductions were supplied. The indexed versus single-function issue is independently documented in Goldreich's clarification. [E1] The present conditional construction assumes H outright; it does not claim a fully black-box derivation of H from arbitrary one-way functions or from obfuscation, and therefore does not bypass Asharov--Segev's model-specific separation. [E2]

All lengths, randomness, and adversaries. Every finite-length map in (eq:30006696:alllengths) is exactly bijective, including at small lengths where the hardness assumption says nothing. The padding proof enumerates polynomially many lengths instead of hardwiring favorable ones. The failure bounds hold eventually for each fixed derived inverter, which is why an infinite set of good attack lengths is enough for a contradiction. Position sampling is exact with bounded randomness, and every trial's output is checked. All expectations and sums in Lemma C are finite; no limit exchange is used. The only independence assumptions are explicitly generated independent challenge blocks or fresh repeated trials, never independent answers from a joint adversary.

Finite falsification tests. The companion script 50_checks.py performs exact-arithmetic checks, not security experiments. It checks every function on a four-element set in the Feistel identity, every subset and permutation of that subset for the guarded extension on a four-element universe, and every three-block $\{0,1\}$ success profile with values in $\{0,\tfrac12,1\}$ for the weighted bad-set inequality in Lemma C. It also exhausts all permutations of the three-dimensional Boolean cube for the order-preserving classification, tests the masked-seed fiber-count identity including noninjective masks, and checks the all-length block partition on a finite range. Counts and outcomes are recorded in 50_checks.json. These tests can expose small counterexamples or implementation errors; they are not evidence that any explicit family is hard against every polynomial-time adversary. The displayed proofs, not the tested cutoffs, justify the general lemmas.

What remains missing. No explicit pair $(D_m,q_m)$ has been shown to satisfy H's hardness condition. In particular, H must not be presented as an independently easy conjecture: allowing $D_m$ to be the whole cube shows that the existence of such a primitive is also implied by the target itself. Proposition B is a normalization equivalence at the level of existence, with useful explicit domain and security bookkeeping, not a new unconditional lower bound. The order, Feistel, cycle, and seed constructions fail for the specific reasons proved above; they do not exhaust all polynomial-time bijections. No counterexample to the existence statement has been constructed.

Outcome.

Outcome: Conditional reduction.

An explicit guarded-extension, direct-product, and all-length-padding construction was proved conditional on a uniformly recognizable dense partial permutation with a fixed inverse-polynomial inversion failure rate. The quantitative extraction argument handles joint attacks and the padding argument preserves uniformity. The attempt also proves an exact masked-seed security equivalence and records several constructive inversion obstructions. These are auxiliary deductions and a self-contained use of classical amplification, not asserted historical novelties.

A complete positive resolution would still require an unconditional construction satisfying H, or a substantially different explicit full-cube permutation with a proof of negligible inversion success. A negative resolution would require ruling out all families in the original statement, not just the tested construction classes. Neither has been obtained here.

Sources

• S1 On Constructing One-Way Permutations from Indistinguishability Obfuscation, ePrint2015/752, TCC2016 version. https://eprint.iacr.org/2015/752.pdf. Catalogue formulation source.
• S2 On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations. https://arxiv.org/abs/2507.12456. Catalogue research/status reference; not a proof endorsement.
• S3 Quantum Search with In-Place Queries. https://drops.dagstuhl.de/storage/00lipics/lipics-vol350-tqc2025/LIPIcs.TQC.2025.1/LIPIcs.TQC.2025.1.pdf. Catalogue research/status reference; not a proof endorsement.
• E1 Oded Goldreich, On one-way permutations (a clarification), November 2005, Cases 1--3, especially Case 2 and the distinction between indices and index-generation coins. https://www.wisdom.weizmann.ac.il/~oded/owp.html. Author's primary clarification; consulted 27 September 2026.

• E2 Gilad Asharov and Gil Segev, On Constructing One-Way Permutations from Indistinguishability Obfuscation, Journal of Cryptology 31 $2018$, 698--736, DOI: 10.1007/s00145-017-9268-6; earlier ePrint 2015/752 and TCC 2016-A. https://link.springer.com/article/10.1007/s00145-017-9268-6. Author presentation, slides 28 and 44 (one-based page numbers): https://www.cs.cornell.edu/~asharov/slides/AS16.pdf. Publisher abstract and author slides consulted 27 September 2026 for the fully black-box/domain-invariance restrictions. Direct retrieval of the ePrint PDF failed; a full-paper proof audit is not claimed. This entry supplements, rather than replaces, [S1].

• E3 Omri Shmueli and Mark Zhandry, On One-Shot Signatures, Quantum vs Classical Binding, and Obfuscating Permutations, arXiv:2507.12456v1, 16 July 2025. Theorem 6; Section 1.4; Section 5.1, Construction 41 and Theorem 42. https://arxiv.org/html/2507.12456v1. Specified manuscript version and relevant construction/proof passages consulted 27 September 2026. Conditional result; neither its assumptions nor an independent verification of the whole paper is asserted here.

• E4 Oded Goldreich, Foundations of Cryptography, Volume 1: Basic Tools, Cambridge University Press, 2001, Section 2.3, "Weak One-Way Functions Imply Strong Ones," especially Section 2.3.1, "The Construction and its Analysis." Author's detailed section guide: https://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html. Author's section guide consulted 27 September 2026 to attribute the classical amplification principle. The finite-instance bound used in this notebook is proved in full above, not imported as an unchecked quotation or theorem-number claim.

• E5 Blake Holman, Ronak Ramachandran, and Justin Yirka, Quantum Search with In-Place Queries, in 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025), LIPIcs 350 $2025$, 1:1--1:18, Theorem 2 and Section 3. DOI: 10.4230/LIPIcs.TQC.2025.1. https://drops.dagstuhl.de/storage/00lipics/lipics-vol350-tqc2025/html/LIPIcs.TQC.2025.1/LIPIcs.TQC.2025.1.html. Published HTML text consulted 27 September 2026. A quantum query-model result, not an unconditional classical one-way-permutation construction. This entry supplies authors and the exact result for [S3].