Length-Preserving 1-1 One-Way Functions from Factoring, and Simpler Amplification Without Expanders

Goldreich, Levin, and Nisan, in their work on constructing 1-1 one-way functions (ECCC TR95-029, 1995; revised text republished as a Springer chapter, DOI 10.1007/978-3-642-22670-0_3), leave open two questions, listed as two separate items in its concluding section: (a) construct a single length-preserving injective (1-1) one-way function based solely on the conjectured intractability of factoring, noting that the standard family of one-way permutations based on factoring (e.g., the Rabin function) does not satisfy the augmented one-wayness condition their method requires; and (b) perform the last step of their construction — transforming the special weak one-way function it produces into a strongly one-way function — without random walks on expander graphs and while matching the security preservation achieved by the general weak-to-strong transformation of Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (1990), efficiency being measured on the source's own scale of security preservation. No construction of a length-preserving 1-1 one-way function from factoring alone is known, and constructing an injective one-way function from general — or even almost-injective — one-way functions remains a long-standing open problem. Question (b) is narrowed by related work — an expander-free amplification exists for regular weak one-way functions (Haitner, Harnik, and Reingold, 2006), and any fully black-box direct-product amplification of a $(1-1/p(n))$ -weak one-way function requires $\Omega(p(n))$ input growth (Brzuska, Couteau, Karanko, and Rohrbach, 2021) — but it is not resolved, since no known amplification for the source's special weak function is both expander-free and security-preserving on the source's scale. Both questions remain open.

Background

A one-way function (OWF) is an efficiently computable function $f$ that is hard to invert on average: for a random input $x$ , no efficient algorithm can find any preimage of $f(x)$ with non-negligible probability. A function is length-preserving if $|f(x)|=|x|$ for every input $x$ , and injective (1-1) if distinct inputs map to distinct outputs. Injectivity matters because several cryptographic primitives and reductions (for example, universal one-way hash functions, and certain commitment and signature constructions) require, or become much simpler given, an injective — or at least almost-injective — one-way function rather than an arbitrary one. Goldreich, Levin, and Nisan emphasized that a single infinite injective OWF should not be confused with an infinite family of finite one-way permutations (OWPs): a family consists of separate finite permutations indexed by a key, whereas the goal is one fixed function, computable on all input lengths, that is injective across its whole (infinite) domain and one-way in the standard asymptotic sense. They showed how to build such a single length-preserving 1-1 OWF from popular intractability assumptions: the RSA assumption (that modular exponentiation modulo a composite of two secret primes is hard to invert) and the discrete logarithm problem (DLP, recovering the exponent $x$ from $g^x$ in a suitable cyclic group). Their method first produces a special weak one-way function — where weak means hard to invert only on some fixed inverse-polynomial fraction of inputs, rather than on a random input as a strong OWF must be — which is the identity on a set $B_n$ of inputs and, on a noticeable set $G_n$ , acts as a permutation that is hard to invert on almost all its points. It then strengthens this weak OWF to a strong one via the general security-preserving amplification construction of Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (1990), which iterates the function on inputs obtained from a random walk on an expander graph (a sparse, highly connected graph whose random walks mix rapidly), so that the hard instances encountered in different iterations behave nearly independently. The source measures such transformations on an explicit security scale (its Section 4, "Security"): writing $s(\cdot)$ for the security of the input object and $s'(\cdot)$ for that of the object produced, the weak relation $s'(\mathrm{poly}(n)) > s(n)/\mathrm{poly}(n)$ , although it translates any super-polynomial security into super-polynomial security, "is of limited practical value", whereas $s'(O(n)) > s(n)/\mathrm{poly}(n)$ is what it means for a transformation to "preserve the security"; the GILVZ transformation preserves security in this sense.

For the factoring-based case, their approach fails: the natural candidate, the family of one-way permutations based on factoring (such as the Rabin function $x\mapsto x^2\bmod N$ , where $N$ is a product of two large secret primes), does not satisfy the augmented one-wayness condition that their transformation requires. In the source's Definition 3.1, a family $\{f_i\}$ with index-selection algorithm $S$ using $q(n)$ coins is augmented one-way if for every probabilistic polynomial-time algorithm $A$ , every positive polynomial $p$ and all sufficiently large $n$ it holds that $\Pr[A(r, f_{S(n,r)}(x))=x] < 1/p(n)$ , where $r\in\{0,1\}^{q(n)}$ and $x\in D_{S(n,r)}$ : the inverting algorithm is given the random coins used to generate the index of the permutation — coins that, for factoring-based families, determine the factorization. The source's footnote 3 contrasts this with enhanced one-wayness, where the inverting algorithm instead gets the coins used by the domain-sampling algorithm. The source also records (footnote 8) that a 1-1 factoring-based OWF is easy to obtain once deterministic polynomial-time primality testing is available — map a pair $(x,y)$ to $x\cdot y$ when $x<y$ and both numbers are prime, and to $(x,y)$ otherwise — "alas this function is not length preserving"; length preservation is therefore the crux of question (a). Whether a different route from factoring yields the desired object has remained unresolved. Separately, the reliance of the amplification step on expander graphs was noted by the authors as an apparently unavoidable complexity of their proof technique: they observe that applying the general weak-to-strong transformation to their special weak function "seems an over-kill", that expander graphs are the only non-elementary component of that transformation, and that in their attempts to avoid it they "were not able to avoid using random walks on expander graphs" — motivating the question of whether the final step can be carried out without expanders and more efficiently.

Problem Statement

The source (Goldreich, Levin, and Nisan; ECCC TR95-029, 1995, in its revised text) establishes that a single length-preserving injective one-way function can be constructed from the RSA assumption and from the discrete logarithm assumption, and its concluding section lists two separate open problems, with no bundling or priority between them; each is an open problem in its own right.

(a) Construct a length-preserving 1-1 one-way function based solely on the conjectured intractability of factoring. The construction should yield one fixed infinite function (not merely a family of finite one-way permutations) that is injective and computable in polynomial time, with a proof that any efficient adversary inverting it on a non-negligible fraction of inputs implies an efficient algorithm for factoring. The obstacle identified in the source is that the standard factoring-based one-way permutations, such as the Rabin function, fail the augmented one-wayness condition required by the known transformation.

(b) Find a weak-to-strong hardness amplification that applies to the special weak one-way function $f$ produced by the source's construction — the identity on $B_n$ and, on the noticeable set $G_n$ , a permutation that is hard to invert — that avoids random walks on expander graphs, and that performs the source's final step, transforming this weak $f$ into a strongly one-way function, while matching the security preservation achieved by the general transformation of Goldreich, Impagliazzo, Levin, Venkatesan, and Zuckerman (1990) and improving on that transformation's use of expander graphs. Efficiency is measured on the source's own scale (Section 4): an amplification resolves this item exactly when it is expander-free and preserves security, that is $s'(O(n)) > s(n)/\mathrm{poly}(n)$ , whereas the weak relation $s'(\mathrm{poly}(n)) > s(n)/\mathrm{poly}(n)$ is described there as "of limited practical value". In particular, an amplification with polynomial input blow-up — Yao's (1982) direct product, and by Brzuska, Couteau, Karanko, and Rohrbach (2021) any fully black-box direct-product construction, which requires $\Omega(p(n))$ input growth when $f$ is invertible with probability $1-1/p(n)$ — does not meet this criterion. The required output is a strongly one-way function; the amplified function need not itself be injective or length-preserving, since neither the source's baseline transformation nor the known expander-free alternative provides this.

References

Oded Goldreich, Leonid A. Levin, Noam Nisan, "On Constructing 1-1 One-Way Functions", Electronic Colloquium on Computational Complexity (ECCC) Technical Report TR95-029 (June 1995); republished in "Studies in Complexity and Cryptography — Miscellanea on the Interplay between Randomness and Computation" (Lecture Notes in Computer Science), Springer, pp. 13–25 (2011). DOI: 10.1007/978-3-642-22670-0_3, https://doi.org/10.1007/978-3-642-22670-0_3 (ECCC report page: https://eccc.weizmann.ac.il/report/1995/029/; author-hosted revised text: https://www.wisdom.weizmann.ac.il/~oded/COL/owp.pdf)
Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman, "Security Preserving Amplification of Hardness", in: Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS 1990), IEEE, pp. 318–326 (1990). DOI: 10.1109/FSCS.1990.89550, https://doi.org/10.1109/FSCS.1990.89550
Takahiro Matsuda, Kanta Matsuura, "On Black-Box Separations among Injective One-Way Functions", in: Theory of Cryptography (TCC 2011), Lecture Notes in Computer Science vol. 6597, Springer, pp. 597–614 (2011). DOI: 10.1007/978-3-642-19571-6_36, https://doi.org/10.1007/978-3-642-19571-6_36
Lior Rotem, Gil Segev, "Injective Trapdoor Functions via Derandomization: How Strong is Rudich's Black-Box Barrier?", Journal of Cryptology 34(4), article 39 (2021). DOI: 10.1007/s00145-021-09405-z, https://doi.org/10.1007/s00145-021-09405-z (also IACR ePrint 2018/812, https://eprint.iacr.org/2018/812)
Iftach Haitner, Danny Harnik, Omer Reingold, "On the Power of the Randomized Iterate", in: Advances in Cryptology — CRYPTO 2006, Lecture Notes in Computer Science, Springer, pp. 22–40 (2006). DOI: 10.1007/11818175_2, https://doi.org/10.1007/11818175_2 (ECCC TR05-135, https://eccc.weizmann.ac.il/report/2005/135/; SIAM Journal on Computing version, DOI: 10.1137/080721820)
Maciej Brzuska, Geoffroy Couteau, Pihla Karanko, Felix Rohrbach, "On Derandomizing Yao's Weak-to-Strong OWF Construction", in: Theory of Cryptography (TCC 2021), Lecture Notes in Computer Science, Springer (2021). DOI: 10.1007/978-3-030-90453-1_15, https://doi.org/10.1007/978-3-030-90453-1_15 (IACR ePrint 2023/1091, https://eprint.iacr.org/2023/1091)