Fact-checked by Grok 2 weeks ago

One-way function

In cryptography, a one-way function is a function that is computationally easy to evaluate for any input but computationally infeasible to invert—meaning it is difficult to find a preimage for most outputs—under the assumption of limited computational resources.^[1] Formally, such a function f: \{0,1\}^* \to \{0,1\}^* is polynomial-time computable, yet for every probabilistic polynomial-time adversary A, the probability that A outputs a valid preimage for a randomly chosen input is negligible in the input length.^[2] The concept of one-way functions was introduced by Whitfield Diffie and Martin Hellman in their seminal 1976 paper "New Directions in Cryptography," where they described functions easy to compute forward but hard to reverse as essential for secure authentication and key distribution.^[1] Diffie and Hellman noted that these functions had been informally used earlier in login procedures but formalized their role in enabling public-key cryptography without relying on shared secrets.^[1] Unlike trapdoor one-way functions, which include a secret that allows efficient inversion, standard one-way functions lack such a mechanism and rely purely on computational hardness.^[2] One-way functions are defined asymptotically for varying security parameters or concretely for fixed lengths, ensuring that inversion success probability remains below a negligible threshold \epsilon(n) even for adversaries running in time polynomial in n, the input size.^[3] They must be surjective or nearly so to avoid trivial inversions, and their hardness is typically based on average-case difficulty rather than worst-case, distinguishing them from problems like NP-complete tasks.^[2] Candidate constructions include integer factorization, where multiplying two large primes is easy but factoring the product is hard, and the discrete logarithm problem over finite fields.^[2] The existence of one-way functions is a foundational assumption in modern cryptography, proven necessary and sufficient for constructing pseudorandom generators, pseudorandom functions, and secure encryption schemes.^[2] If one-way functions exist, they enable the Blum-Micali construction for pseudorandom number generators and form the basis for signature schemes, though efficient implementations often require stronger assumptions like the existence of one-way permutations.^[3] Their unproven existence underscores ongoing research into computational complexity, with no known one-way functions proven under standard assumptions like P ≠ NP, but practical candidates like AES in certain modes serve as evidence of their plausibility.^[2]

Core Concepts

Definition

A one-way function is a mathematical function that is computationally efficient to evaluate but extremely difficult to invert, forming a cornerstone of modern cryptography. Formally, a function f: \{0,1\}^* \to \{0,1\}^* is one-way if it can be computed in polynomial time and, for every probabilistic polynomial-time adversary A, the probability that A successfully inverts f on a random input is negligible in the input length n. Specifically, there exists a negligible function \epsilon(n) such that

\Pr_{X \leftarrow \{0,1\}^n} \left[ A(f(X), 1^n) \in f^{-1}(f(X)) \right] \leq \epsilon(n)

for all sufficiently large n, where negligible means that for every constant c > 0, \epsilon(n) < n^{-c} beyond some n_0, and f^{-1}(f(X)) denotes the set of preimages of f(X).^[2] This definition captures average-case one-wayness, the standard notion in cryptography, where inversion is infeasible on a randomly chosen input from a distribution such as the uniform distribution over \{0,1\}^n, rather than requiring hardness for every possible input (worst-case one-wayness). Average-case hardness suffices for cryptographic applications because protocols typically operate on random or pseudorandom inputs, ensuring security against adversaries without needing universal invertibility resistance.^[2]^[4] One-way permutations represent a special case of one-way functions that are bijective, mapping \{0,1\}^n onto itself for each n while preserving the one-way property. For such permutations f_n: \{0,1\}^n \to \{0,1\}^n, the inversion requirement is that no probabilistic polynomial-time A can find the unique preimage with more than negligible probability:

\Pr_{X \leftarrow \{0,1\}^n} \left[ A(f_n(X), 1^n) = X \right] \leq \epsilon(n),

where \epsilon is negligible; this ensures the function's surjectivity and injectivity do not compromise its hardness.^[2] Partial one-way functions, often termed weak one-way functions, relax the inversion requirement slightly to allow success with non-negligible but bounded probability less than 1, specifically \Pr[A(f(X), 1^n) \in f^{-1}(f(X))] < 1 - 1/q(n) for some polynomial q(n). This weaker guarantee still implies the existence of strong (full) one-way functions through repeated applications and amplification techniques.^[4] Trapdoor one-way functions extend this by allowing easy inversion with auxiliary secret information, known as a trapdoor.^[2]

Historical Development

The concept of one-way functions emerged in the mid-1970s as a foundational primitive for public-key cryptography, introduced informally by Whitfield Diffie and Martin Hellman in their seminal 1976 paper. They proposed functions that are easy to compute in one direction but computationally infeasible to invert without additional information, serving as building blocks for secure key exchange and encryption systems without relying on shared secrets. This idea was motivated by the need to address key distribution challenges in symmetric cryptography, though it lacked formal complexity-theoretic foundations at the time. Formalization of one-way functions gained rigor in the early 1980s, with researchers shifting focus to average-case hardness under probabilistic Turing machines. Andrew Chi-Chih Yao's 1982 work on trapdoor functions provided a structured framework, exploring their applications in cryptography and pseudorandom generation while emphasizing computational intractability for inversion.^[5] Concurrently, Adi Shamir contributed significantly through his involvement in the 1978 RSA cryptosystem, which exemplified trapdoor one-way functions where inversion is feasible only with a secret key, influencing subsequent theoretical developments. In 1989, Johan Håstad, Russell Impagliazzo, and Leonid Levin demonstrated that pseudorandom generators could be constructed from any one-way function, with the full proof completed by Michael Luby in the 1999 journal version, establishing a bidirectional equivalence that solidified their role in complexity-based cryptography.^[6] By the mid-1980s, refinements integrated one-way functions into broader cryptographic protocols. An early construction of pseudorandom generators from specific one-way functions was given by Manuel Blum and Silvio Micali in 1984. Oded Goldreich, Shafi Goldwasser, and Silvio Micali's 1984 construction of pseudorandom functions from one-way functions (presented at FOCS 1984) extended their utility to simulating random oracles, with implications for interactive proof systems and zero-knowledge protocols.^[7] Leonid Levin introduced universal one-way functions in 1985, which capture the hardness of all one-way functions in a single, succinct construction, enabling more efficient reductions in cryptographic proofs.^[8] These advancements paved the way for provable security paradigms in the 1990s, where one-way functions underpinned formal security definitions for primitives like signatures and encryption. In the 2000s and 2010s, the concept evolved to address emerging threats, particularly from quantum computing. The U.S. National Institute of Standards and Technology (NIST) incorporated one-wayness requirements into hash function standards, such as in FIPS 180-4 (2015), mandating preimage resistance as a core property for approved algorithms like SHA-256 to ensure their reliability in digital signatures and integrity checks. The 2010s saw adaptations for post-quantum cryptography, with NIST's 2016 standardization process evaluating lattice-based and other candidates relying on conjectured quantum-resistant one-way functions, reflecting a shift toward hardness assumptions resilient to quantum attacks. Key milestones include the 1976 conceptual introduction, the 1980s formalizations, Levin's 1985 universal construction, and the post-2000 integration into standards and quantum-resistant frameworks.^[9]

Properties and Variants

Key Properties

One-way functions are distinguished by their resistance to inversion by probabilistic polynomial-time (PPT) adversaries, with key variants including weak and strong notions of one-wayness. A weak one-way function is defined such that, for inputs of length n, there exists some \epsilon = 1/\mathrm{poly}(n) where the probability that any PPT adversary \mathcal{A} finds a preimage for f(x) on a random x \in \{0,1\}^n satisfies \Pr[f(\mathcal{A}(f(x))) = f(x)] \leq 1 - \epsilon.^[10] In contrast, a strong one-way function requires that this inversion probability is negligible in n, i.e., \Pr[f(\mathcal{A}(f(x))) = f(x)] \leq \mathrm{negl}(n) for all PPT \mathcal{A}.^[11] These distinctions capture varying levels of computational hardness, with strong one-wayness providing robust security for cryptographic applications while weak variants suffice as building blocks for amplification to stronger forms.^[12] The security of one-way functions is typically defined against non-adaptive adversaries, who receive a single random image y = f(x) and attempt to find a preimage without further interaction. However, to address chosen-input attacks, stronger models consider adaptive adversaries with oracle access to f on adaptively chosen inputs; one-wayness holds if such an adversary cannot invert a random challenge y (not previously queried) with more than negligible probability, ensuring resilience even when the adversary probes the function's behavior.^[13] This formulation prevents exploits where an adversary might select inputs to reveal patterns in f, as the random challenge remains computationally intractable to invert for PPT algorithms.^[14] One-way functions may be length-preserving (where output length m = n) or length-expanding (where m \geq n), with the latter often manifesting as permutations when injective. Length-preserving one-way functions, particularly one-way permutations, are crucial for constructing invertible primitives while maintaining hardness, as demonstrated by constructions from assumptions like RSA or the discrete logarithm problem that yield injective, polynomial-time computable functions hard to invert.^[15] Length expansion (m > n) enhances certain security properties, such as aiding collision resistance by increasing the output space, which raises the computational barrier for finding distinct inputs mapping to the same output and supports derivations of collision-resistant hash functions from one-way bases.^[16] Hardness amplification techniques enable conversion of weak one-way functions to strong ones, typically via repetition or direct products. For instance, Yao's XOR lemma shows that repeating a weak one-way function multiple times and XORing the outputs amplifies the inversion hardness, yielding a strong one-way function equivalent in existence to weak variants.^[17] A related approach uses hardcore bits to extract pseudorandomness from one-way functions; the Goldreich-Levin theorem states that for any length-preserving one-way permutation f: \{0,1\}^n \to \{0,1\}^n, there exists a hardcore predicate b: \{0,1\}^n \times \{0,1\}^n \to \{0,1\} such that b(x,r) is unpredictable given f(x), r for uniform random x, r \in \{0,1\}^n, where predictability advantage is negligible for PPT predictors.^[18] This lemma, proven via a recovery procedure using inner-product queries, facilitates constructions like pseudorandom generators from any one-way function.^[11] Measurable security quantifies one-wayness through advantage functions, capturing an adversary's success excess over a baseline. For a one-way function f, the advantage of PPT \mathcal{A} is defined as \mathrm{Adv}_{\mathcal{A}}(f) = \Pr[f(\mathcal{A}(f(x))) = f(x)] - \mathrm{baseline}, where the baseline is typically the trivial success probability (e.g., $1/2^n for unique preimages or 0 for general cases).^[2] Strong one-wayness requires \max_{\mathcal{A}} \mathrm{Adv}_{\mathcal{A}}(f) \leq \mathrm{negl}(n), providing a concrete metric for security reductions and allowing precise analysis of amplification efficiency.^[12] A trapdoor one-way function extends the notion of a one-way function by incorporating a secret "trapdoor" that enables efficient inversion. Formally, a function f is a trapdoor one-way function if it is one-way in the usual sense, but there exists a trapdoor t such that a probabilistic polynomial-time (PPT) algorithm can invert f using t, while inversion remains hard without it.^[5] This concept, introduced by Yao, underpins public-key cryptography by allowing selective reversibility.^[5] Pseudorandom functions (PRFs) differ from one-way functions (OWFs) in that PRFs are efficiently computable families indistinguishable from truly random functions by any PPT distinguisher, whereas OWFs focus solely on hardness of inversion. OWFs imply the existence of PRFs through black-box constructions: first, a pseudorandom generator is built from any OWF, and then PRFs are derived via tree-based extensions like the GGM construction. The Luby-Rackoff construction further shows that applying a 3- or 4-round Feistel network to a PRF yields a pseudorandom permutation, enabling secure block ciphers from weaker primitives ultimately rooted in OWFs. Collision-resistant functions represent a stronger variant than OWFs, where finding any two distinct inputs x \neq y such that f(x) = f(y) is computationally infeasible for PPT adversaries. This property implies one-wayness because an inverter for f could be used to find collisions: given x, compute y = f(x), invert to get x' \neq x mapping to y, yielding a collision; since collision resistance precludes this, inversion must be hard.^[19] However, the converse does not hold, as OWFs do not necessarily resist collisions, establishing collision resistance as a stricter requirement often needed for applications like digital signatures.^[19] Verifiable delay functions (VDFs) build on OWFs to create time-lock puzzles that require a specified number of sequential computations to evaluate, yet allow efficient verification of the output. A VDF is hard to compute faster than \Theta(T) time even with massive parallelism, but verification takes polylog(T) time. Wesolowski's construction achieves this by iteratively applying modular exponentiation in an RSA group, where the delay stems from sequential squarings, and verifiability uses a short proof based on the RSA assumption. Preimage resistance in cryptographic hash functions aligns closely with the core one-way property of OWFs, demanding that given an output h, no PPT algorithm can efficiently find any input m such that \text{hash}(m) = h.^[19] Unlike general OWFs, this is tailored to fixed-length outputs in hashes, serving as a foundational security notion without the additional structure of trapdoors or delay.^[19]

Theoretical Foundations

Existence and Implications

The existence of one-way functions remains one of the most fundamental open problems in computational complexity theory, first articulated by Diffie and Hellman in their seminal 1976 paper introducing the concept as a foundation for public-key cryptography.^[1] Despite extensive study, no unconditional proof of their existence has been established within ZFC set theory, rendering it an unresolved question since its inception.^[20] However, their existence follows from widely believed assumptions such as P ≠ NP; specifically, if P = NP, then every function computable in polynomial time is invertible in polynomial time, precluding one-way functions.^[21] The implications of one-way functions extend deeply into complexity theory and cryptography, serving as a minimal hardness assumption sufficient for numerous primitives. For example, their existence enables the construction of pseudorandom generators, initially demonstrated by Blum and Micali for one-way permutations and later extended to arbitrary one-way functions by Håstad, Impagliazzo, Levin, and Luby.^[22] More precisely, one-way functions imply that BPP ⊈ P/poly, establishing a separation between bounded-error probabilistic polynomial time and nonuniform polynomial time, as the resulting pseudorandom generators fool nonuniform adversaries.^[22] One-way functions are intimately tied to average-case hardness assumptions, forming equivalences with derandomization barriers in complexity classes. In particular, they are equivalent to the existence of problems in E = DTIME(2^{O(n)}) that are hard to solve on average by subexponential-size circuits.^[21] The Impagliazzo-Wigderson theorem (1997) provides a key connection: if every language in E can be decided by circuits of size 2^{o(n)}, then P = BPP, highlighting how the apparent nonexistence of such hardness would collapse probabilistic and deterministic polynomial time. Conversely, one-way functions imply sufficient average-case hardness in E to prevent such a collapse against nonuniform computation.^[21] Black-box separation results further illuminate the theoretical challenges in proving properties of one-way functions. For instance, Viola (2008) demonstrated that any black-box proof amplifying the hardness of weak one-way functions to strong ones requires computing the majority function on polynomially many bits, imposing significant non-relativizing barriers in relativized worlds.^[23] Further advancements include the work by Haitner, Harnik, and Reingold (2010), who presented an improved pseudorandom generator from any one-way function, achieving better seed length and computational efficiency while simplifying the underlying techniques.^[24] More recently, as of 2025, one-way functions have been shown sufficient for constructing threshold signatures, expanding their role in secure multiparty protocols.^[25] Recent work (2024) has also clarified separations between one-way functions and TFNP problems, refining our understanding of their place in complexity theory.^[26]

Universal One-Way Functions

A universal one-way function is a polynomial-time computable function f that is one-way with respect to every probabilistic polynomial-time (PPT) samplable distribution D. That is, for every PPT inverter A, the probability \Pr[x \sim D : A(1^n, f(x)) = x] is negligible in the security parameter n, where negligible means smaller than any inverse polynomial.^[21] The seminal construction of a universal one-way function from any one-way function was given by Levin. The construction is length-doubling and relies on enumeration of all possible PPT samplers for distributions and pairwise independent hash functions to ensure security across all distributions. Specifically, let g be an arbitrary one-way function. The input consists of an index i to the i-th PPT sampler and a seed s; it computes x as the output of the sampler D_i on s, then the output incorporates g(x), the index i, and a hash derived from s to facilitate the reduction while expanding the input length roughly to twice the original. Inverting f on a random input thus requires inverting g on samples from any PPT-samplable D_i, with the pairwise independence ensuring that no PPT adversary can distinguish or invert selectively without breaking g everywhere.^[11] Length-preserving one-way functions can be constructed assuming the existence of any one-way function. The existence of universal one-way functions is equivalent to the existence of general one-way functions up to black-box reductions, meaning any proof of security based on a specific one-way function can be reduced to the universal case without non-black-box assumptions.^[21] Universal one-way functions simplify cryptographic proofs by allowing reductions to a single canonical hard problem rather than distribution-specific assumptions; for example, they enable uniform security arguments across varying input distributions in protocol designs. They also find use in deniability arguments, where the universality ensures that inversion hardness holds regardless of the attacker's assumed input generation, supporting protocols like deniable encryption.^[27] Constructions of universal one-way functions are highly inefficient due to the need for exhaustive enumeration of PPT machines and hash families, resulting in exponential overhead in practice. No practical or efficient candidates for universal one-way functions are known, limiting their direct deployment in real-world cryptography.^[28]

Practical Candidates

Integer Factorization

Integer factorization is a leading candidate for a practical one-way function, particularly in cryptographic contexts. The function is defined as f(p, q) = p \times q, where p and q are distinct large prime numbers of roughly equal bit length. Multiplication to obtain the composite number N = p \times q is computationally efficient, performable in polynomial time relative to the bit length of N. However, inverting the function—recovering the primes p and q from N—is believed to be intractable for sufficiently large N without knowledge of the factors.^[29]^[2] The hardness of this problem rests on the integer factorization assumption, which posits that no probabilistic polynomial-time (PPT) algorithm can factor large semiprimes with non-negligible probability in the average case. As of 2025, the best known algorithms for general integer factorization run in subexponential time with superpolynomial complexity. This assumption underpins the security of systems relying on factorization's one-way property, distinguishing it from related problems like quadratic residuosity, which is computationally equivalent to factoring but focuses on determining whether a number is a square modulo a composite.^[30]^[31] Integer factorization gained prominence as a one-way function candidate through its role in the RSA cryptosystem, introduced in 1977 by Rivest, Shamir, and Adleman. In RSA, the ease of multiplication contrasts with the presumed difficulty of factoring, enabling public-key encryption where the product N serves as the modulus. The system's security directly depends on the one-wayness of this function, as factoring N would reveal the private key.^[32]^[33] The state-of-the-art algorithm for integer factorization is the General Number Field Sieve (GNFS), which achieves a subexponential time complexity of \exp\left( O\left( (\log N)^{1/3} (\log \log N)^{2/3} \right) \right). This asymptotic bound highlights the practical infeasibility for large N; for instance, the largest recorded factorization of an RSA modulus, RSA-250 (a 250-decimal-digit or 829-bit number), was completed in 2020 using GNFS implemented in the CADO-NFS software, requiring approximately 2,700 core-years of computation. In contrast, 2048-bit RSA moduli remain secure against classical attacks, as factoring them would demand vastly more resources.^[34]^[35]^[36]

Discrete Logarithm

The discrete logarithm problem provides a classic example of a candidate one-way function in group theory, particularly within multiplicative groups of finite fields or elliptic curve groups. Consider a prime p and a generator g of the multiplicative group \mathbb{Z}_p^*, where the function is defined as f_g(x) = g^x \mod p for x \in \{0, 1, \dots, p-2\}. Computing f_g(x) via repeated squaring or exponentiation is efficient in polynomial time, but recovering x from y = f_g(x) is believed to be intractable for large p. This formulation extends to other prime-order cyclic groups, such as those arising from elliptic curves over finite fields.^[37]^[38] The hardness of the discrete logarithm problem is formalized by the discrete logarithm assumption, which states that no probabilistic polynomial-time algorithm exists to compute \log_g(y) given g and y = g^x for randomly chosen x. Targeted attacks, such as the index calculus algorithm, exploit the structure of \mathbb{Z}_p^* to achieve subexponential complexity O(\exp(\sqrt{\log p \log \log p})), though this remains infeasible for sufficiently large p.^[39]^[38] Key variants include the elliptic curve discrete logarithm problem (ECDLP), where the group consists of points on an elliptic curve E over a finite field \mathbb{F}_q, and one seeks x such that Q = xP for points P, Q \in E(\mathbb{F}_q). The ECDLP resists index calculus attacks effectively, enabling equivalent security with much smaller parameters—typically 256-bit curves for 128-bit security—compared to finite field discrete logarithms. While pairing-based variants exist on groups with bilinear maps, the standard discrete logarithm focuses on these non-pairing settings.^[40] Introduced as a foundational hardness assumption in 1976, the discrete logarithm problem underpins early public-key protocols like the Diffie-Hellman key exchange. As of 2025, standards recommend security parameters around 2048 bits for finite field discrete logarithms to meet 112-bit security levels against classical attacks.^[1]^[41] Generic attacks, such as Pollard's rho algorithm, solve the problem in O(\sqrt{q}) time and space for a group of order q, independent of group structure; no classical polynomial-time algorithm is known. The index calculus method for discrete logarithms bears a conceptual resemblance to number field sieve techniques for integer factorization.^[37]

Modular Squaring

The Rabin function, a prominent candidate for a one-way function, is defined as f(x) = x^2 \mod N, where N = p q is the product of two distinct odd primes p and q forming a Blum integer (i.e., p \equiv q \equiv 3 \pmod{4}).^[42] Computing f(x) is straightforward via modular arithmetic, but inverting it—finding a square root of y = f(x) modulo N—is computationally infeasible without knowledge of p and q, as extracting square roots modulo a composite requires factoring N.^[42] Proposed by Michael O. Rabin in 1979, this function was introduced as a trapdoor one-way permutation for constructing digital signatures and a public-key cryptosystem known as Rabin's cryptosystem. In Rabin's scheme, the public key is N, and encryption involves squaring the message modulo N; decryption uses the factors to compute square roots efficiently via the Chinese Remainder Theorem. A key property of the Rabin function is that, when restricted to the set of quadratic residues modulo N (denoted \mathrm{QR}_N), it forms a permutation: for Blum integers, squaring is a bijection on \mathrm{QR}_N, ensuring each quadratic residue has exactly four square roots modulo N (arising from the signs and the Chinese Remainder Theorem decomposition).^[42] This 4-to-1 mapping on \mathbb{Z}_N^* contributes to its strong one-wayness under the factoring assumption, as even partial inversion leaks information about the factors.^[43] Inverting the Rabin function is provably polynomial-time equivalent to factoring N. To see this, suppose an algorithm A inverts f_n with non-negligible probability \delta(k) on inputs n of bit-length k. Construct a factoring algorithm A' that picks a random x \in \mathbb{Z}_n^*, computes z = f_n(x), obtains a purported root y = A(z), and checks if y^2 \equiv z \pmod{n} and y \not\equiv \pm x \pmod{n}; if so, \gcd(|x - y|, n) yields a nontrivial factor with probability at least $1/2.^[42] Conversely, if N can be factored, square roots can be computed modulo p and q (each having two solutions) and combined via the Chinese Remainder Theorem to obtain all four roots modulo N.^[43] This equivalence establishes the Rabin function's security precisely on the hardness of integer factorization.^[42] The security of the Rabin function thus mirrors that of the integer factorization problem, with no known attacks more efficient than the best general factoring algorithms, such as the General Number Field Sieve (GNFS), which runs in subexponential time L_N[1/3, c] for constant c \approx 1.923.

Hash Functions

Cryptographic hash functions serve as practical candidates for one-way functions, mapping arbitrary-length inputs from the set of binary strings to fixed-length outputs while ensuring computational difficulty in inverting the process. Specifically, a hash function h: \{0,1\}^* \to \{0,1\}^n is considered one-way if, for a randomly chosen output y \in \{0,1\}^n, it is computationally infeasible for a probabilistic polynomial-time (PPT) adversary to find any preimage x such that h(x) = y; this property, known as preimage resistance, underpins their role as one-way functions.^[44]^[45] The concept of one-way hash functions was formalized in the late 1980s, with Ralph Merkle proposing constructions based on block ciphers in 1989, emphasizing their utility in authentication and digital signatures. These early designs gained widespread adoption in the 1990s, particularly through functions like MD5, though subsequent cryptanalytic advances revealed vulnerabilities in collision resistance for MD5, including partial breaks on its compression function by 1996 and full collisions by 2004, prompting a shift toward more robust standards.^[46]^[47]^[48] A common construction for such hash functions is the Merkle-Damgård (MD) structure, which iteratively applies a compression function to message blocks padded with length information, assuming the underlying compression function is one-way to preserve preimage resistance for the full hash. One prominent compression function is the Davies-Meyer construction, which transforms a block cipher E into a one-way function via f(K, M) = E_M(K) \oplus K, where M is the message block serving as the key and K as the plaintext (or chaining value); security relies on the block cipher's pseudorandom permutation properties.^[46]^[49]^[50] Beyond preimage resistance, secure hash functions typically exhibit collision resistance—difficulty in finding distinct inputs x \neq x' with h(x) = h(x')—and second-preimage resistance—given x, finding x' \neq x with h(x') = h(x)—though one-wayness remains the foundational property for their candidacy as one-way functions. The Secure Hash Algorithm SHA-256, standardized by NIST in 2001 as part of the SHA-2 family, exemplifies this with a 256-bit output produced via 64 rounds of MD-structured compression using Davies-Meyer-like operations on a modified block cipher. As of 2025, no preimage attacks on SHA-256 surpass the 2^{256} brute-force bound, affirming its ongoing viability.^[44]^[9]^[51]

Other Candidates

Lattice-based one-way functions, such as those derived from the Learning With Errors (LWE) problem, involve encoding a secret message into a noisy linear equation over a lattice, where recovering the original message from the resulting syndrome is computationally infeasible without knowledge of a secret short basis for the lattice. Introduced by Oded Regev in 2005, LWE reduces the hardness of worst-case lattice problems like the Shortest Vector Problem (SVP) to the average-case LWE problem, providing a foundation for secure cryptographic primitives.^[52] Similarly, the Shortest Vector Problem (SVP) serves as a candidate by mapping a lattice point to its coordinates, with inversion requiring finding the shortest non-zero vector in the lattice, a task proven hard even for quantum computers under certain parameters.^[52] Code-based one-way functions rely on the syndrome decoding problem, as exemplified in the McEliece cryptosystem, where the function computes the syndrome of a coded message perturbed by a small number of errors, making it difficult to recover the original message without the private generator matrix of the underlying linear code.^[53] Proposed by Robert McEliece in 1978, this approach uses Goppa codes to ensure that decoding an arbitrary syndrome is NP-complete, establishing its resistance to classical attacks despite large key sizes.^[53] Multivariate polynomial-based candidates involve systems of quadratic equations over finite fields, where the one-way function evaluates a central map composed with invertible affine transformations, and inversion requires solving the multivariate quadratic (MQ) problem, which is believed to be hard due to the high degree of the univariate polynomial in the hidden field representation.^[54] The Hidden Field Equations (HFE) scheme, developed by Jacques Patarin in 1996, exemplifies this by using a low-degree univariate polynomial over a finite extension field, translated to multivariate quadratics, with security resting on the difficulty of decomposing the trapdoor.^[54] Pairing-based one-way functions leverage bilinear maps on elliptic curves, focusing on the hardness of inverting the decisional Diffie-Hellman assumption in the target group, where the function maps paired elements to a scalar, and recovering the discrete logarithm from the pairing output is infeasible without solving the underlying elliptic curve discrete logarithm problem. This construction, as utilized in identity-based encryption schemes, assumes that while pairings are efficiently computable, extracting secret exponents from bilinear Diffie-Hellman tuples remains secure against classical adversaries. Among these candidates, lattice-based approaches like LWE have emerged as the most promising, forming the basis for several algorithms standardized by NIST in its 2024-2025 post-quantum cryptography process, including ML-KEM (based on module-LWE), with no known efficient classical algorithms to break them at security levels comparable to AES-128.^[55] Code-based and multivariate schemes remain viable alternatives but face challenges from larger key sizes and historical vulnerabilities, respectively, while pairing-based methods are primarily suited for classical settings.^[55]

Applications and Challenges

Role in Cryptography

One-way functions (OWFs) play a foundational role in public-key encryption by enabling trapdoor variants, where encryption applies the OWF to the message—such as raising it to a public exponent in schemes like RSA—and decryption uses a secret trapdoor to invert the function efficiently.^[56] This asymmetry ensures that only the holder of the private key can recover the plaintext, providing confidentiality against adversaries without the trapdoor. In digital signatures, OWFs underpin existential unforgeability through transformations like the Fiat-Shamir heuristic, introduced in 1986, which converts interactive identification protocols into non-interactive signatures by hashing challenges with an OWF to eliminate the need for a trusted verifier.^[57] This approach allows signers to prove knowledge of a secret without revealing it, ensuring authenticity and non-repudiation in protocols such as those based on discrete logarithms or factorizations.^[58] Pseudorandom generators (PRGs), essential for expanding short seeds into long unpredictable strings, can be constructed from any OWF using the Blum-Micali-Yao (BMY) method from 1984, which iteratively extracts hard-core bits—unpredictable bits even given the OWF output—to build the generator's output.^[59] This construction stretches limited entropy sources for applications like nonce generation and key expansion, assuming the OWF's security.^[22] For key derivation and message authentication codes (MACs), hash-based OWFs enable secure constructions like HMAC, proposed by Bellare, Canetti, and Krawczyk in 1996, which nests the hash function with a secret key to produce a tag resistant to forgery under chosen-message attacks.^[60] HMAC leverages the OWF properties of hashes like SHA-256 to derive keys from passwords or authenticate data in protocols such as TLS. Provable security in these systems relies on reductions that tie protocol security to the hardness of an underlying OWF; for instance, the OAEP padding scheme for RSA, developed by Bellare and Rogaway in 1994, provides chosen-ciphertext security via a reduction showing that breaking the padded encryption implies inverting the RSA OWF.^[56] Such proofs ensure that if the OWF resists inversion, the protocol withstands specified attacks.^[61] As of 2025, OWFs underpin the majority of deployed cryptographic systems in standards-compliant implementations, such as those in FIPS 202 for SHA-3, which relies on sponge-based constructions for hashing in secure communications and data integrity.

Quantum and Post-Quantum Considerations

One-way functions underlying classical cryptographic primitives face significant threats from quantum algorithms. Shor's algorithm, introduced in 1994, provides a polynomial-time quantum method for integer factorization and the discrete logarithm problem, solving both in O((\log N)^3) time on a quantum computer, thereby rendering systems like RSA and Diffie-Hellman insecure against sufficiently large-scale quantum adversaries.^[62] Grover's algorithm, proposed in 1996, offers a quadratic speedup for unstructured search problems, including preimage resistance in hash functions, reducing the required operations from $2^n to $2^{n/2}. For SHA-256, this reduces preimage security from $2^{256} to $2^{128}, necessitating larger hash outputs, such as 512 bits, to maintain equivalent post-quantum protection levels.^[63]^[64] These quantum threats render classical one-way function candidates vulnerable on fault-tolerant quantum hardware. Problems such as integer factorization, discrete logarithms, and modular squaring—key to RSA, elliptic curve cryptography, and related schemes—can be efficiently solved using Shor's algorithm, making them unsuitable for post-quantum security.^[62] As of 2025, noisy intermediate-scale quantum (NISQ) devices have demonstrated factorization of small RSA moduli, such as 48-bit keys, but cryptographically relevant attacks on 2048-bit RSA remain infeasible, with projections for scalable, error-corrected quantum computers capable of such breaks emerging in the 2030s.^[65] Grover's impact on hash functions similarly erodes collision and preimage resistance, prompting recommendations to increase hash sizes or adopt quantum-resistant alternatives to preserve one-way properties.^[63] Post-quantum one-way functions address these vulnerabilities by relying on problems believed to be hard even for quantum computers. Lattice-based constructions, such as those derived from the Learning With Errors (LWE) problem and the Shortest Vector Problem (SVP), form a prominent family; their security stems from the worst-case hardness of approximate SVP in high-dimensional lattices, as established in foundational work showing average-case LWE hardness reduces to worst-case lattice problems. Hash-based signatures, exemplified by SPHINCS+, leverage the one-wayness of collision-resistant hash functions like SHA-3, providing quantum-resistant digital signatures without relying on novel number-theoretic assumptions. Isogeny-based approaches, such as SIDH, were initially promising due to their basis in supersingular isogeny graphs but were rendered insecure by a polynomial-time key recovery attack in 2022.^[66] Standardization efforts have accelerated the adoption of these post-quantum one-way functions. The NIST Post-Quantum Cryptography project, initiated in 2016 and culminating in selections by 2022, designated CRYSTALS-Kyber—a lattice-based key encapsulation mechanism grounded in LWE—as a primary standard for encryption, alongside CRYSTALS-Dilithium for signatures, both finalized as FIPS 203, 204, and 205 in August 2024, with initial deployments and migration efforts underway as of 2025.^[67] SPHINCS+ was also standardized (FIPS 205) as a hash-based alternative, ensuring diversity in quantum-resistant primitives. As of mid-2025, adoption of post-quantum standards remains limited, with only about 8.6% of the top one million websites supporting hybrid PQC mechanisms, underscoring the need for accelerated migration to mitigate quantum risks.^[68] Despite their quantum hardness, post-quantum one-way functions introduce new implementation challenges, particularly susceptibility to side-channel attacks. Lattice-based schemes like Kyber and Dilithium are vulnerable to timing, power, and electromagnetic side-channel analyses that exploit polynomial multiplications and noise sampling, potentially leaking secret keys through non-profiled higher-order attacks.^[69] Hash-based constructions face similar risks from message expansion and state updates, necessitating masked or constant-time implementations to mitigate these physical threats without compromising the underlying one-way properties.^[69]

References

[1]
[PDF] New Directions in Cryptography - Stanford Electrical Engineering
We have already seen that public key cryptosystems imply the existence of trap-door one-way functions. ... DIFFIE. AND. HELLMAN: NEW. DIRECTIONS. IN CRYPTOGRAPHY.
[2]
[PDF] One-way functions - Harvard SEAS
The formal definition: Definition 1 f : {0,1}∗ → {0,1}∗ is a one-way function if: 1. f can be evaluated in polynomial time. 2. For every PPT A, there is ...
[3]
Cryptography - One-Way Functions
Using the Blum-Micali Generator, one-way functions can be used to construct Pseudo Random Number Generators, which enable us to construct Pseudo Random ...
[4]
[PDF] Lecture 3: One-Way Functions 1 Adversaries - CS@Cornell
Jan 29, 2008 · One-way functions are one of the most fundamental cryptographic primitives; we will re- turn to them frequently in this course.
[5]
[PDF] Theory and Applications of Trapdoor Functions
In Part 2, we study the concept of trapdoor functions and examine applications of such functions in cryptography, pseudorandom number generation, and abstract ...
[6]
Pseudo-random generation from one-way functions
We show how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa.
[7]
How to construct random functions | Journal of the ACM
GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. How to construct random functions. Tech. Memo 244, Laboratory for Computer Science, MIT, Cambridge, Mass., Nov ...
[8]
[PDF] fips pub 180-4 - federal information processing standards publication
Aug 4, 2015 · All of the algorithms are iterative, one-way hash functions that can process a message to produce a condensed representation called a message.
[9]
[PDF] Lecture 10: Weak One-Way Functions and Hardness Amplification
Oct 17, 2017 · The main difference between strong OWF and weak OWF depends on the advantage of A, in weak OWF, the adversary only needs to fail to invert f ...
[10]
[PDF] One Way Functions and Pseudorandom Generators
[12] A. C. Yao. Theory and Applications of Trapdoor Functions. Proc. 23rd IEEE Symp. on Foundations of. Computer Science pp. 80-91, 1982.
[11]
https://www.cs.bu.edu/fac/lnd/pdf/onew.pdf
[12]
Non-Adaptive Universal One-Way Hash Functions from Arbitrary ...
Apr 6, 2022 · In this work we give the first non-adaptive construction of universal one-way hash functions (UOWHFs) from arbitrary one-way functions.Missing: cryptography | Show results with:cryptography<|separator|>
[13]
[PDF] Adaptively Secure Garbled Circuits from One-Way Functions
The adversary should not be able to distinguish between the real world and the simulated world. Selective vs. Adaptive Security. Selective security is often ...
[14]
[PDF] On Constructing 1-1 One-Way Functions
Combines papers of Impagliazzo, Levin, and Luby (21st STOC, 1989) and. J. Håstad (22nd STOC, 1990). 13. G.L. Miller, “Riemann's Hypothesis and tests for ...
[15]
[PDF] A New Mode of Operation for Block Ciphers and Length-Preserving ...
Additionally, our mode yields a VIL random oracle (and, hence, a collision-resistant hash function) when instantiated with length-preserving random functions, ...
[16]
Theory and application of trapdoor functions - ACM Digital Library
We study the concept of trapdoor functions and examine applications of such functions in cryptography, pseudorandom number generation, and abstract complexity ...Missing: one- | Show results with:one-
[17]
[PDF] The Goldreich-Levin Theorem - Computer Science
Oct 7, 1999 · Given a length-preserving one-way function f: {0,1}∗ → {0,1}∗, define F(x, r)=(f(x),r) where |x| = |r|. This is also a one-way function.
[18]
[PDF] Cryptographic Hash-Function Basics: Definitions, Implications, and ...
Abstract. We consider basic notions of security for cryptographic hash functions: collision resistance, preimage resistance, and second-preimage resistance.
[19]
[cs/0012023] The Tale of One-way Functions - arXiv
Dec 26, 2000 · The existence of one-way functions is arguably the most important problem in computer theory. The article discusses and refines a number of concepts relevant ...Missing: universal | Show results with:universal
[20]
[PDF] On One-way Functions and Kolmogorov Complexity
Sep 24, 2020 · Impagliazzo and Levin demonstrate the equivalence of one-way functions and the infeasibility of universal extrapolation. As suggested by an ...
[21]
[PDF] Pseudorandom Generators from One-Way Functions - cs.Princeton
Abstract. In a seminal paper, Håstad, Impagliazzo, Levin, and Luby showed that pseudorandom generators exist if and only if one-way func- tions exist.Missing: 1980s | Show results with:1980s
[22]
[PDF] Hardness Amplification Proofs Require Majority - CS@Columbia
Mar 3, 2008 · In this paper we study the complexity of black-box proofs of hardness amplification. A class of circuits D proves a hardness amplification ...
[23]
[PDF] Efficiency Improvements in Constructing Pseudorandom Generators ...
In this paper, we present a significantly more direct and efficient construction of pseudorandom generators from one- way functions. The key to our construction ...
[24]
[PDF] No Better Ways to Generate Hard NP Instances than Picking ...
Since it is hard to extrapo- late pseudo-random functions, the converse follows from [Hastad Impagliazzo Levin Luby. 90]. Thus, universal extrapolation is ...
[25]
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing
Oct 13, 2020 · In an additional result we reprove the seminal result of Impagliazzo and Levin (FOCS 1989): a reduction from “uniform distribution” average ...
[26]
[PDF] 1 Introduction 2 Levin's One Way Function
Sep 7, 2006 · Theorem 1 There exists a particular polynomial-time computable function f such that f is one-way if and only if there are any one-way functions.Missing: paper | Show results with:paper
[27]
[PDF] The Mathematical Cryptography of the RSA Cryptosystem
The underlying one-way function of RSA is the integer factorization problem: Multiplying two large primes is computationally easy, but factoring the result-.
[28]
[PDF] Lecture 9: Lattice Cryptography and the SIS Problem 1 Introduction
Apr 30, 2018 · Let's consider the problem of factoring for example. • Average-case factoring assumption: For all PPT algorithm A, we have. Pr. A(N) → (p, q).
[29]
[2507.07055] Integer Factorization: Another perspective - arXiv
Jul 9, 2025 · It is considered as a one way or trapdoor function in the (RSA) cryptosystem. To date, from elementary trial division to sophisticated ...
[30]
[PDF] THE RSA CRYPTOSYSTEM 1. Introduction In 1977 the internet ...
A function Ek that satisfies (1)-(4) is called a trap-door one-way per mutation [6]. The function is one-way because it is easy to compute in one direction but ...
[31]
[PDF] Twenty Years of Attacks on the RSA Cryptosystem 1 Introduction
The cryptosystem is most commonly used for providing privacy and ensuring authenticity of digital data. These days RSA is deployed in many commercial systems.
[32]
[PDF] Number Field Sieve with provable complexity - arXiv
Jul 14, 2020 · In this thesis we give an in-depth introduction to the General Number Field Sieve, as it was used by Buhler, Lenstra, and Pomerance, [17], ...
[33]
RSA-250 Factored - Schneier on Security -
Apr 8, 2020 · RSA-250 has been factored. This computation was performed with the Number Field Sieve algorithm, using the open-source CADO-NFS software.
[34]
Integer Factoring Records
General-purpose Algorithms: the largest integer factored with a general-purpose algorithm is RSA-250 (250 decimal digits), which was factored on February 28, ...
[35]
Factoring and Discrete Logarithms - Applied Cryptography Group
Discrete logarithm: Given p,g,gxmodp p , g , g x mod p , find x x . Classical Algorithms. Brute force, e.g. trial division, which has running time ...
[36]
[PDF] Computing Discrete Logarithms - Cryptology ePrint Archive
The discrete logarithm problem (DLP) for (G,g,h) is the computational problem of determining an integer x such that h = gx. Note that the integer x is uniquely ...
[37]
[PDF] Revisiting Discrete Logarithm Reductions
Jun 2, 2025 · The discrete logarithm (DL) assumption postulates that in certain groups, it is hard to compute x given a group generator g and a random group ...
[38]
[PDF] Recent progress on the elliptic curve discrete logarithm problem
Oct 22, 2015 · The elliptic curve discrete logarithm problem (ECDLP) is the following computational problem: Given points P, Q ∈ E(Fq) to find an integer a, ...
[39]
[PDF] Recommendation for Key Management: Part 1 - General
May 5, 2020 · NIST SP 800-57 PART 1 REV. 5. RECOMMENDATION ... field and elliptic-curve discrete-log key-establishment schemes are provided in SP 800-56A.
[40]
[PDF] Summary 1 Rabin Squaring Function and the Factoring As- sumption
Oct 11, 2005 · Proof: If the Factoring Assumption is false, then n may be efficiently factored into p and q (with non-negligible probability). Given p and q, ...
[41]
[PDF] RSA and Rabin functions
In particular, if factoring large numbers (a classical open problem) is hard, then the simple function of squaring modulo a composite number is one-way [22].Missing: citation | Show results with:citation
[42]
Cryptographic hash function - Glossary | CSRC
(Preimage resistance) Given a randomly chosen target output, it is computationally infeasible to find any input that maps to that output. (This property is ...
[43]
[PDF] Cryptographic Hash-Function Basics: Definitions, Implications, and ...
Feb 12, 2004 · Preneel [13] describes one-way hash functions (those which are both preimage-resistant and second-preimage resistant) and collision ...Missing: expansion | Show results with:expansion
[44]
One Way Hash Functions and DES - SpringerLink
CRYPTO' 89 Proceedings (CRYPTO 1989). One Way Hash Functions and DES. Download book PDF. Ralph C.
[45]
[PDF] One Way Hash Functions and DES - Semantic Scholar
This work shows three one-way hash functions which are secure if DES is a good random block cipher. One way hash functions are a major tool in cryptography.
[46]
[PDF] MD5
On December 24, 2010, Tao Xie and Dengguo Feng announced the first published single-block MD5 collision (two. 64-byte messages with the same MD5 hash). [16].
[47]
Davies-Meyer Hash Function - ResearchGate
The DM construction was introduced by Donald Davies and Walter Meyer [30] . The constructional approach uses a compression function built out of a block cipher.<|separator|>
[48]
[PDF] Merkle Damgard Revisited: how to Construct a hash Function - CSRC
Abstract. The most common way of constructing a hash function (e.g., SHA-1) is to iterate a compression function on the input message.
[49]
FIPS 180-2, Secure Hash Standard (SHS) | CSRC
This standard specifies four secure hash algorithms, SHA-1, SHA-256, SHA-384, and SHA-512. All four of the algorithms are iterative, one-way hash functions.
[50]
[PDF] The Learning with Errors Problem
In this survey we describe the Learning with Errors (LWE) problem, discuss its properties, its hardness, and its cryptographic applications. In recent years, ...
[51]
[PDF] A Public-Key Cryptosystem Based On Algebraic Coding Theory
In this paper we propose a public key cryptosystem which is based on the theory of algebraic codes. II. Description of the System. We base our system on the ...
[52]
Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP)
Jul 13, 2001 · HFE can be used to do sig- natures, encryption or authentication in an asymmetric way, with very short signatures and short encryptions of short ...
[53]
Post-Quantum Cryptography | CSRC
HQC was selected for standardization on March 11, 2025. NIST IR 8545, Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization ...Workshops and Timeline · Presentations · Email List (PQC Forum) · Post-QuantumMissing: LWE | Show results with:LWE
[54]
[PDF] Optimal Asymmetric Encryption How to Encrypt with RSA - UCSD CSE
Nov 19, 1995 · Bellare, J. Kilian and P. Rogaway, “On the security of cipher-block chaining,” Ad- vances in Cryptology – Crypto 94 Proceedings, Lecture ...
[55]
[PDF] How To Prove Yourself: - Practical Solutions to Identification
In this paper we describe simple identification and signature schemes which enable any user to prove his identity and the authenticity of his messages to ...Missing: original | Show results with:original
[56]
Practical Solutions to Identification and Signature Problems
In this paper we describe simple identification and signature schemes which enable any user to prove his identity and the authenticity of his messages to any ...Missing: original | Show results with:original
[57]
[PDF] How to Generate Cryptographically Strong Sequences ... - cs.wisc.edu
Yao [33] also proves that one can obtain instances of the CSPRB generator schemeif one-way functions with a particular property exist. 1.5. Applications ...
[58]
[PDF] Keying Hash Functions for Message Authentication - UCSD CSE
In this paper we present two (related) new schemes, NMAC (the Nested construction) and HMAC. (the Hash based mac). They can utilize any cryptographic hash ...
[59]
[PDF] Another Look at “Provable Security” - Cryptology ePrint Archive
In 1994, Bellare and Rogaway [7] proposed a protocol for encrypting mes- sages that they called Optimal Asymmetric Encryption Padding (OAEP). Their method was ...
[60]
Algorithms for quantum computation: discrete logarithms and factoring
This paper gives Las Vegas algorithms for finding discrete logarithms and factoring integers on a quantum computer that take a number of steps which is ...
[61]
A fast quantum mechanical algorithm for database search
A fast quantum mechanical algorithm for database search. Author: Lov K. Grover.
[62]
State of the post-quantum Internet in 2025 - The Cloudflare Blog
Oct 28, 2025 · Using factoring as a benchmark, quantum computers don't impress at all: the largest number factored by a quantum computer without cheating is 15 ...The Quantum Threat · Quantum Numerology · Adoption Of Pqc In Protocol...
[63]
PQC Standardization Process: Announcing Four Candidates to be ...
Jul 5, 2022 · CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (digital signatures) were both selected for their strong security and excellent ...
[64]
Side-channel Analysis of Lattice-based Post-quantum Cryptography
We propose a non-profiled side-channel attack methodology targeting all the different polynomial multiplication algorithms used in lattice-based cryptography.