Constructing a length-preserving 1-1 one-way function from the intractability of factoring, and simpler weak-to-strong amplification: the open problems of Goldreich, Levin, and Nisan

In 1995 Goldreich, Levin, and Nisan gave the first method for constructing a single length-preserving 1-1 one-way function — equivalently, a one-way permutation in the single-function sense, a bijection of $\{0,1\}^n$ for every $n$ that is hard to invert on average — from any family of one-way permutations satisfying two extra conditions: augmented one-wayness (inversion stays hard even given the random coins used to select the index of the family member) and canonical domain sampling (efficiently recognizable, dense domains). They instantiated the method from RSA and from discrete-logarithm assumptions, and posed two problems. First, base such a function on the intractability of factoring alone; the standard factoring-based permutation family — squaring on the quadratic residues modulo a Blum integer — fails augmented one-wayness because the coins that select the modulus are its prime factors, with which the function is inverted. Second, replace the expander-based security-preserving amplification of Goldreich–Impagliazzo–Levin–Venkatesan–Zuckerman used in the final step by something simpler that exploits the special structure of the weak one-way function produced (the identity on a large part of its domain, hard on the rest). Both problems remain open as of 2026: black-box separations rule out generic routes even from injective one-way functions (Matsuda–Matsuura), non-black-box techniques deliver injective but not length-preserving functions (Rotem–Segev), and the Brzuska–Couteau–Karanko–Rohrbach direct-product lower bound shows that elementary non-adaptive amplification cannot be security-preserving.

Background

One-way functions, single and in families

A one-way function is a polynomial-time computable $f:\{0,1\}^*\to\{0,1\}^*$ such that every probabilistic polynomial-time algorithm, given $f(x)$ for uniformly random $x$ of length $n$, returns some preimage of $f(x)$ only with negligible probability. If inverting can only be shown to fail on at least a $1/\mathrm{poly}(n)$ fraction of inputs, $f$ is weakly one-way; standard amplification converts weak one-wayness into the strong kind. The function is length-preserving if $|f(x)|=|x|$ and 1-1 (injective) if distinct inputs always produce distinct outputs. A length-preserving 1-1 one-way function is thus a bijection of $\{0,1\}^n$ for every $n$ — a one-way permutation in the single-function sense. This must be distinguished from what cryptography usually calls a one-way permutation: an infinite family (collection) of finite permutations $\{f_i:D_i\to D_i\}$ together with efficient algorithms for evaluating $f_i$, for sampling an index $i$ of the family, and for sampling a domain element $x\in D_i$, such that inverting $f_i(x)$ for random $i$ and $x$ is infeasible. Typical examples are the RSA family ($x\mapsto x^e \bmod N$ on the multiplicative group $\mathbb{Z}_N^*$) and the discrete-logarithm family ($x\mapsto g^x \bmod P$); the standard factoring-based example is squaring $x\mapsto x^2 \bmod N$ restricted to the quadratic residues modulo a Blum integer $N=pq$ with $p\equiv q\equiv 3 \pmod 4$ (a quadratic residue is an element that is a square; on this subset squaring is a bijection, and extracting square roots modulo $N$ is computationally equivalent to factoring $N$).

Why single one-way permutations are wanted

From a single one-way permutation, the classical iterated-permutation pseudorandom generator — output a hard-core bit of the seed, then of the image of the seed, then of the image of the image, and so on, where a hard-core bit is a predicate of the input that remains unpredictable given the function's output — is extremely simple and efficient. From arbitrary one-way functions, pseudorandom generators also exist but are far more complex and inefficient, and a comparable simplicity gap holds elsewhere (for example, in signature schemes). Obtaining a single one-way permutation from the most classical hardness assumptions was therefore posed as a goal by Goldreich, Levin, and Nisan.

The Goldreich–Levin–Nisan construction and its two gaps

Goldreich–Levin–Nisan start from a family of permutations $\{f_i:D_i\to D_i\}$ satisfying: (a) augmented one-wayness — no efficient algorithm can invert $f_i(x)$ even when given the random coins $r$ used by the index-sampling algorithm, a strengthening that rules out families whose index-selection coins leak a trapdoor; and (b) canonical domain sampling — each $D_i$ is efficiently recognizable (membership decidable in polynomial time) and dense in $\{0,1\}^{l(n)}$ (at least a $2^{l(n)}/\mathrm{poly}(n)$ fraction of the strings). Their construction merges index and preimage into a single length-preserving function: on input $(r,s)$, if $s$ lands in the domain $D_i$ of the permutation $i$ selected using coins $r$, output $(r, f_i(s))$, otherwise output $(r,s)$; the result is a 1-1 (or almost 1-1) weakly one-way function, which is then amplified into a strongly one-way function. They instantiate the scheme from RSA (with prime exponents), from the discrete logarithm restricted to safe primes $P=2Q+1$ with $Q$ prime (under a density assumption), and from the general discrete logarithm when the factorization of $P-1$ is available. Two gaps remained, stated as open problems in their conclusions. First, factoring: the standard factoring-based family fails augmented one-wayness, since the coins that generate a Blum modulus are its prime factors, with which squaring is inverted. Second, amplification: the weak-to-strong step applies the security-preserving amplification of Goldreich–Impagliazzo–Levin–Venkatesan–Zuckerman, which interleaves evaluations of the weak function with random walks on expander graphs — constant-degree graphs whose random walks mix rapidly, allowing correlated hard instances to be generated from few random bits; the authors note that their weak function has a special structure (it is the identity off the sampled domain and hard only on a noticeable fraction of inputs — a fraction at least $1/\mathrm{poly}(n)$) and wished for an elementary construction avoiding expander graphs, but could not find one.

Problem Statement

Part A (primary): a single one-way permutation from factoring

Construct an explicit function $f:\{0,1\}^*\to\{0,1\}^*$ and prove:

1. Efficiency. $f$ is computable in deterministic polynomial time.

2. Permutation structure. $f$ is length-preserving and 1-1 — equivalently, for every $n$ it is a bijection of $\{0,1\}^n$.

3. One-wayness from factoring alone. Under the standard factoring assumption — every probabilistic polynomial-time algorithm, given $N$ drawn as the product of two random equal-length primes (or, equivalently for this problem, a random Blum integer), factors $N$ with only negligible probability — $f$ is strongly one-way: there is an explicit probabilistic polynomial-time reduction that converts any algorithm inverting $f$ with success probability at least $1/\mathrm{poly}(n)$ on random inputs of length $n$ into a factoring algorithm for the stated distribution with non-negligible success. Every ingredient of the construction and its analysis (sampling, domain-membership testing, any number-theoretic subroutine) must itself be unconditional or reducible to the same factoring assumption; hidden extra assumptions (for example, density of special primes, hardness of quadratic residuosity, or access to a random oracle) are not permitted.

Part B (companion): elementary, security-preserving amplification for the special structure

The weak one-way function produced by the Goldreich–Levin–Nisan construction is a permutation of $\{0,1\}^{q(n)+l(n)}$ that acts as the identity on the complement of the sampled domain and is hard to invert only on a noticeable fraction of inputs (a fraction at least $1/\mathrm{poly}(n)$). Construct an amplification that maps this weak one-way function to a strongly one-way 1-1 function while (i) avoiding expander graphs and random walks on them, and (ii) preserving security — the degradation of the work factor (running time times inverse success probability) should be at most polynomial with input lengths growing at most linearly, qualitatively better than the $\Omega(p(n))$ input blow-up that is unavoidable for non-adaptive direct-product constructions applied to a weak one-way function that is inverted with probability at most $1-1/p(n)$. As the source notes, the amplification may exploit the special structure of the specific function produced by its construction, whether the transformation is tailored to that function or handles any weak one-way function with this structure.

Relationship

Both parts are the two open problems posed together in the conclusions of the source: Part A completes the first step of the source's three-step method for the factoring assumption, Part B simplifies its third step. They share the common objective of completing and streamlining the construction of single one-way permutations from standard hardness assumptions, but are scientifically independent.

References

1. Oded Goldreich, Leonid A. Levin, and Noam Nisan (2011), 'On Constructing 1-1 One-Way Functions', in Studies in Complexity and Cryptography: Miscellanea on the Interplay between Randomness and Computation (Lecture Notes in Computer Science 6650), Springer, pp. 13–25, DOI 10.1007/978-3-642-22670-0_3, https://doi.org/10.1007/978-3-642-22670-0_3 (original manuscript of June 12, 1995: https://www.wisdom.weizmann.ac.il/~oded/PSX/gln.pdf)
2. O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman (1990), 'Security Preserving Amplification of Hardness', 31st IEEE Symposium on Foundations of Computer Science (FOCS 1990), pp. 318–326, DOI 10.1109/FSCS.1990.89550, https://doi.org/10.1109/FSCS.1990.89550
3. Takahiro Matsuda and Kanta Matsuura (2011), 'On Black-Box Separations among Injective One-Way Functions', Theory of Cryptography (TCC 2011), Lecture Notes in Computer Science 6597, pp. 597–614, DOI 10.1007/978-3-642-19571-6_36, https://doi.org/10.1007/978-3-642-19571-6_36
4. Chris Brzuska, Geoffroy Couteau, Pihla Karanko, and Felix Rohrbach (2021), 'On Derandomizing Yao's Weak-to-Strong OWF Construction', Theory of Cryptography (TCC 2021), Springer, pp. 429–456, DOI 10.1007/978-3-030-90453-1_15, https://doi.org/10.1007/978-3-030-90453-1_15
5. Lior Rotem and Gil Segev (2021), 'Injective Trapdoor Functions via Derandomization: How Strong is Rudich's Black-Box Barrier?', Journal of Cryptology 34(4), article 39, DOI 10.1007/s00145-021-09405-z, https://doi.org/10.1007/s00145-021-09405-z
6. Gilad Asharov and Gil Segev (2018), 'On Constructing One-Way Permutations from Indistinguishability Obfuscation', Journal of Cryptology 31(3), pp. 698–736, DOI 10.1007/s00145-017-9268-6, https://doi.org/10.1007/s00145-017-9268-6
7. Kevin J. Compton (2017), 'Conditional Expectation Bounds with Applications in Cryptography', arXiv:1708.00092, https://arxiv.org/abs/1708.00092
8. Oded Goldreich (2005), 'On one-way permutations (a clarification)', online note, Weizmann Institute of Science, November 2005, https://www.wisdom.weizmann.ac.il/~oded/owp.html
9. Kaoru Kurosawa and Tsuyoshi Takagi (2009), 'One-Wayness Equivalent to General Factoring', IEEE Transactions on Information Theory 55(9), pp. 4249–4262, DOI 10.1109/TIT.2009.2025532, https://doi.org/10.1109/TIT.2009.2025532
10. Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, and Amit Sahai (2023), 'Hard Languages in NP ∩ coNP and NIZK Proofs from Unstructured Hardness', Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023), pp. 1243–1256, DOI 10.1145/3564246.3585119, https://doi.org/10.1145/3564246.3585119