Hubbry Logo
One-way functionOne-way functionMain
Open search
One-way function
Community hub
One-way function
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
One-way function
One-way function
One-way function
View on Wikipedia
from Wikipedia
Unsolved problem in computer science
Do one-way functions exist?
More unsolved problems in computer science

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. This has nothing to do with whether the function is one-to-one; finding any one input with the desired image is considered a successful inversion. (See § Theoretical definition, below.)

The existence of such one-way functions is still an open conjecture. Their existence would prove that the complexity classes P and NP are not equal, thus resolving the foremost unsolved question of theoretical computer science.[1]: ex. 2.2, page 70  The converse is not known to be true, i.e. the existence of a proof that P ≠ NP would not directly imply the existence of one-way functions.[2]

In applied contexts, the terms "easy" and "hard" are usually interpreted relative to some specific computing entity; typically "cheap enough for the legitimate users" and "prohibitively expensive for any malicious agents".[citation needed] One-way functions, in this sense, are fundamental tools for cryptography, personal identification, authentication, and other data security applications. While the existence of one-way functions in this sense is also an open conjecture, there are several candidates that have withstood decades of intense scrutiny. Some of them are essential ingredients of most telecommunications, e-commerce, and e-banking systems around the world.

Theoretical definition

[edit]

A function f : {0, 1}* → {0, 1}* is one-way if f can be computed by a polynomial-time algorithm, but any polynomial-time randomized algorithm that attempts to compute a pseudo-inverse for f succeeds with negligible probability. (The * superscript means any number of repetitions, see Kleene star.) That is, for all randomized algorithms , all positive integers c and all sufficiently large n = length(x),

where the probability is over the choice of x from the discrete uniform distribution on {0, 1} n, and the randomness of .[3]

Note that, by this definition, the function must be "hard to invert" in the average-case, rather than worst-case sense. This is different from much of complexity theory (e.g., NP-hardness), where the term "hard" is meant in the worst-case. That is why even if some candidates for one-way functions (described below) are known to be NP-complete, it does not imply their one-wayness. The latter property is only based on the lack of known algorithms to solve the problem.

It is not sufficient to make a function "lossy" (not one-to-one) to have a one-way function. In particular, the function that outputs the string of n zeros on any input of length n is not a one-way function because it is easy to come up with an input that will result in the same output. More precisely: For such a function that simply outputs a string of zeroes, an algorithm F that just outputs any string of length n on input f(x) will "find" a proper preimage of the output, even if it is not the input which was originally used to find the output string.

[edit]

A one-way permutation is a one-way function that is also a permutation—that is, a one-way function that is bijective. One-way permutations are an important cryptographic primitive, and it is not known if their existence is implied by the existence of one-way functions.

A trapdoor one-way function or trapdoor permutation is a special kind of one-way function. Such a function is hard to invert unless some secret information, called the trapdoor, is known.

A collision-free hash function f is a one-way function that is also collision-resistant; that is, no randomized polynomial time algorithm can find a collision—distinct values x, y such that f(x) = f(y)—with non-negligible probability.[4]

Theoretical implications of one-way functions

[edit]

If f is a one-way function, then the inversion of f would be a problem whose output is hard to compute (by definition) but easy to check (just by computing f on it). Thus, the existence of a one-way function implies that FP ≠ FNP, which in turn implies that P ≠ NP. However, P ≠ NP does not imply the existence of one-way functions.

The existence of a one-way function implies the existence of many other useful concepts, including:

Candidates for one-way functions

[edit]

The following are several candidates for one-way functions (as of April 2009). Clearly, it is not known whether these functions are indeed one-way; but extensive research has so far failed to produce an efficient inverting algorithm for any of them.[citation needed]

Multiplication and factoring

[edit]

The function f takes as inputs two prime numbers p and q in binary notation and returns their product. This function can be "easily" computed in O(b2) time, where b is the total number of bits of the inputs. Inverting this function requires finding the factors of a given integer N. The best factoring algorithms known run in time, where b is the number of bits needed to represent N.

This function can be generalized by allowing p and q to range over a suitable set of semiprimes. Note that f is not one-way for randomly selected integers p, q > 1, since the product will have 2 as a factor with probability 3/4 (because the probability that an arbitrary p is odd is 1/2, and likewise for q, so if they're chosen independently, the probability that both are odd is therefore 1/4; hence the probability that p or q is even, is 1 − 1/4 = 3/4).

The Rabin function (modular squaring)

[edit]

The Rabin function,[1]: 57  or squaring modulo , where p and q are primes is believed to be a collection of one-way functions. We write

to denote squaring modulo N: a specific member of the Rabin collection. It can be shown that extracting square roots, i.e. inverting the Rabin function, is computationally equivalent to factoring N (in the sense of polynomial-time reduction). Hence it can be proven that the Rabin collection is one-way if and only if factoring is hard. This also holds for the special case in which p and q are of the same bit length. The Rabin signature algorithm is based on the assumption that this Rabin function is one-way.

Discrete exponential and logarithm

[edit]

Modular exponentiation can be done in polynomial time. Inverting this function requires computing the discrete logarithm. Currently there are several popular groups for which no algorithm to calculate the underlying discrete logarithm in polynomial time is known. These groups are all finite abelian groups and the general discrete logarithm problem can be described as thus.

Let G be a finite abelian group of cardinality n. Denote its group operation by multiplication. Consider a primitive element α ∈ G and another element β ∈ G. The discrete logarithm problem is to find the positive integer k, where 1 ≤ k ≤ n, such that:

The integer k that solves the equation αk = β is termed the discrete logarithm of β to the base α. One writes k = logα β.

Popular choices for the group G in discrete logarithm cryptography are the cyclic groups (Zp)× (e.g. ElGamal encryption, Diffie–Hellman key exchange, and the Digital Signature Algorithm) and cyclic subgroups of elliptic curves over finite fields (see elliptic curve cryptography).

An elliptic curve is a set of pairs of elements of a field satisfying y2 = x3 + ax + b. The elements of the curve form a group under an operation called "point addition" (which is not the same as the addition operation of the field). Multiplication kP of a point P by an integer k (i.e., a group action of the additive group of the integers) is defined as repeated addition of the point to itself. If k and P are known, it is easy to compute R = kP, but if only R and P are known, it is assumed to be hard to compute k.

Cryptographically secure hash functions

[edit]

There are a number of cryptographic hash functions that are fast to compute, such as SHA-256. Some of the simpler versions have fallen to sophisticated analysis, but the strongest versions continue to offer fast, practical solutions for one-way computation. Most of the theoretical support for the functions are more techniques for thwarting some of the previously successful attacks.

Other candidates

[edit]

Other candidates for one-way functions include the hardness of the decoding of random linear codes, the hardness of certain lattice problems, and the subset sum problem (Naccache–Stern knapsack cryptosystem).

Universal one-way function

[edit]

There is an explicit function f that has been proved to be one-way, if and only if one-way functions exist.[5] In other words, if any function is one-way, then so is f. Since this function was the first combinatorial complete one-way function to be demonstrated, it is known as the "universal one-way function". The problem of finding a one-way function is thus reduced to proving—perhaps non-constructively—that one such function exists.

There also exists a function that is one-way if polynomial-time bounded Kolmogorov complexity is mildly hard on average. Since the existence of one-way functions implies that polynomial-time bounded Kolmogorov complexity is mildly hard on average, the function is a universal one-way function.[6]

See also

[edit]

References

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

One-way function

View on Grokipedia
from Grokipedia
In , 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. Formally, such a function f:{0,1}∗→{0,1}∗f: \{0,1\}^* \to \{0,1\}^* is polynomial-time computable, yet for every probabilistic polynomial-time adversary AA, the probability that AA outputs a valid preimage for a randomly chosen input is negligible in the input length. 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. 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. 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. 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 ϵ(n)\epsilon(n) even for adversaries running in time in nn, the input size. 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. Candidate constructions include , where multiplying two large primes is easy but factoring the product is hard, and the problem over finite fields. The existence of one-way functions is a foundational assumption in modern , proven necessary and sufficient for constructing pseudorandom generators, pseudorandom functions, and secure schemes. 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. Their unproven existence underscores ongoing research into , 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.

Core Concepts

Definition

A one-way function is a mathematical function that is computationally efficient to evaluate but extremely difficult to invert, forming a of modern . Formally, a function f:{0,1}∗→{0,1}∗f: \{0,1\}^* \to \{0,1\}^* is one-way if it can be computed in time and, for every probabilistic -time adversary AA, the probability that AA successfully inverts ff on a random input is negligible in the input length nn. Specifically, there exists a ϵ(n)\epsilon(n) such that Pr⁡X←{0,1}n[A(f(X),1n)∈f−1(f(X))]≤ϵ(n)\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 nn, where negligible means that for every constant c>0c > 0, ϵ(n)<n−c\epsilon(n) < n^{-c} beyond some n0n_0, and f−1(f(X))f^{-1}(f(X)) denotes the set of preimages of f(X)f(X). 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\{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. One-way permutations represent a special case of one-way functions that are bijective, mapping {0,1}n\{0,1\}^n onto itself for each nn while preserving the one-way property. For such permutations fn:{0,1}n→{0,1}nf_n: \{0,1\}^n \to \{0,1\}^n, the inversion requirement is that no probabilistic polynomial-time AA can find the unique preimage with more than negligible probability: Pr⁡X←{0,1}n[A(fn(X),1n)=X]≤ϵ(n),\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. 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),1n)∈f−1(f(X))]<1−1/q(n)\Pr[A(f(X), 1^n) \in f^{-1}(f(X))] < 1 - 1/q(n) for some polynomial q(n)q(n). This weaker guarantee still implies the existence of strong (full) one-way functions through repeated applications and amplification techniques. Trapdoor one-way functions extend this by allowing easy inversion with auxiliary secret information, known as a trapdoor.

Historical Development

The concept of one-way functions emerged in the mid-1970s as a foundational primitive for public-key cryptography, introduced informally by and 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. 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. 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. 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. 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.

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 nn, there exists some ϵ=1/poly(n)\epsilon = 1/\mathrm{poly}(n) where the probability that any PPT adversary A\mathcal{A} finds a preimage for f(x)f(x) on a random x∈{0,1}nx \in \{0,1\}^n satisfies Pr⁡[f(A(f(x)))=f(x)]≤1−ϵ\Pr[f(\mathcal{A}(f(x))) = f(x)] \leq 1 - \epsilon. In contrast, a strong one-way function requires that this inversion probability is negligible in nn, i.e., Pr⁡[f(A(f(x)))=f(x)]≤negl(n)\Pr[f(\mathcal{A}(f(x))) = f(x)] \leq \mathrm{negl}(n) for all PPT A\mathcal{A}. 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. The security of one-way functions is typically defined against non-adaptive adversaries, who receive a single random image y=f(x)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 ff on adaptively chosen inputs; one-wayness holds if such an adversary cannot invert a random challenge yy (not previously queried) with more than negligible probability, ensuring resilience even when the adversary probes the function's behavior. This formulation prevents exploits where an adversary might select inputs to reveal patterns in ff, as the random challenge remains computationally intractable to invert for PPT algorithms. One-way functions may be length-preserving (where output length m=nm = n) or length-expanding (where m≥nm \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. Length expansion (m>nm > n) enhances certain security properties, such as aiding 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. 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 , yielding a strong one-way function equivalent in existence to weak variants. 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 f:{0,1}n→{0,1}nf: \{0,1\}^n \to \{0,1\}^n, there exists a hardcore predicate b:{0,1}n×{0,1}n→{0,1}b: \{0,1\}^n \times \{0,1\}^n \to \{0,1\} such that b(x,r)b(x,r) is unpredictable given f(x),rf(x), r for uniform random x,r∈{0,1}nx, r \in \{0,1\}^n, where predictability advantage is negligible for PPT predictors. This lemma, proven via a recovery procedure using inner-product queries, facilitates constructions like pseudorandom generators from any one-way function. Measurable security quantifies one-wayness through advantage functions, capturing an adversary's success excess over a baseline. For a one-way function ff, the advantage of PPT A\mathcal{A} is defined as AdvA(f)=Pr⁡[f(A(f(x)))=f(x)]−baseline\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/2n1/2^n for unique preimages or 0 for general cases). Strong one-wayness requires max⁡AAdvA(f)≤negl(n)\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. A trapdoor one-way function extends the notion of a one-way function by incorporating a secret "" that enables efficient inversion. Formally, a function ff is a trapdoor one-way function if it is one-way in the usual sense, but there exists a tt such that a probabilistic polynomial-time (PPT) algorithm can invert ff using tt, while inversion remains hard without it. This concept, introduced by Yao, underpins by allowing selective reversibility. 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 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 , 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≠yx \neq y such that f(x)=f(y)f(x) = f(y) is computationally infeasible for PPT adversaries. This property implies one-wayness because an inverter for ff could be used to find collisions: given xx, compute y=f(x)y = f(x), invert to get x′≠xx' \neq x mapping to yy, yielding a collision; since precludes this, inversion must be hard. However, the converse does not hold, as OWFs do not necessarily resist collisions, establishing as a stricter often needed for applications like digital signatures. 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 Θ(T)\Theta(T) time even with massive parallelism, but verification takes polylog(T)(T) time. Wesolowski's achieves this by iteratively applying 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 hh, no PPT algorithm can efficiently find any input mm such that hash(m)=h\text{hash}(m) = h. 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.

Theoretical Foundations

Existence and Implications

The existence of one-way functions remains one of the most fundamental open problems in , first articulated by Diffie and Hellman in their seminal 1976 paper introducing the concept as a foundation for . Despite extensive study, no unconditional proof of their existence has been established within ZFC , rendering it an unresolved question since its inception. However, their existence follows from widely believed assumptions such as P ≠ NP; specifically, if P = NP, then every function computable in time is invertible in time, precluding one-way functions. 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. 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. 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 = DTIME(2^{O(n)}) that are hard to solve on average by subexponential-size circuits. The Impagliazzo-Wigderson theorem (1997) provides a key connection: if every language in can be decided by circuits of size 2^{o(n)}, then P = BPP, highlighting how the apparent nonexistence of such hardness would probabilistic and deterministic polynomial time. Conversely, one-way functions imply sufficient average-case hardness in to prevent such a against nonuniform computation. 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 on polynomially many bits, imposing significant non-relativizing barriers in relativized worlds. Further advancements include the work by Haitner, Harnik, and Reingold (2010), who presented an improved from any one-way function, achieving better seed length and computational efficiency while simplifying the underlying techniques. More recently, as of 2025, one-way functions have been shown sufficient for constructing threshold signatures, expanding their role in secure multiparty protocols. Recent work (2024) has also clarified separations between one-way functions and TFNP problems, refining our understanding of their place in complexity theory.

Universal One-Way Functions

A universal one-way function is a polynomial-time ff that is one-way with respect to every probabilistic polynomial-time (PPT) samplable distribution DD. That is, for every PPT inverter AA, the probability Pr⁡[x∼D:A(1n,f(x))=x]\Pr[x \sim D : A(1^n, f(x)) = x] is negligible in the security parameter nn, where negligible means smaller than any inverse polynomial. 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 gg be an arbitrary one-way function. The input consists of an index ii to the ii-th PPT sampler and a seed ss; it computes xx as the output of the sampler DiD_i on ss, then the output incorporates g(x)g(x), the index ii, and a hash derived from ss to facilitate the reduction while expanding the input length roughly to twice the original. Inverting ff on a random input thus requires inverting gg on samples from any PPT-samplable DiD_i, with the pairwise independence ensuring that no PPT adversary can distinguish or invert selectively without breaking gg everywhere. 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. 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 . 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 .

Practical Candidates

is a leading candidate for a practical one-way function, particularly in cryptographic contexts. The function is defined as f(p,q)=p×qf(p, q) = p \times q, where pp and qq are distinct large prime numbers of roughly equal . Multiplication to obtain the composite number N=p×qN = p \times q is computationally efficient, performable in time relative to the of NN. However, inverting the function—recovering the primes pp and qq from NN—is believed to be intractable for sufficiently large NN without knowledge of the factors. The hardness of this problem rests on the 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 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 a composite. 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 NN serves as the modulus. The system's security directly depends on the one-wayness of this function, as factoring NN would reveal the private key. The state-of-the-art algorithm for integer factorization is the General Number Field Sieve (GNFS), which achieves a subexponential time complexity of exp⁡(O((log⁡N)1/3(log⁡log⁡N)2/3))\exp\left( O\left( (\log N)^{1/3} (\log \log N)^{2/3} \right) \right). This asymptotic bound highlights the practical infeasibility for large NN; 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.

Discrete Logarithm

The discrete logarithm problem provides a classic example of a one-way function in , particularly within of finite fields or groups. Consider a prime pp and a generator gg of the Zp∗\mathbb{Z}_p^*, where the function is defined as fg(x)=gxmod  pf_g(x) = g^x \mod p for x∈{0,1,…,p−2}x \in \{0, 1, \dots, p-2\}. Computing fg(x)f_g(x) via repeated squaring or is efficient in time, but recovering xx from y=fg(x)y = f_g(x) is believed to be intractable for large pp. This formulation extends to other prime-order cyclic groups, such as those arising from over finite fields. The hardness of the discrete logarithm problem is formalized by the discrete logarithm assumption, which states that no probabilistic polynomial-time exists to compute log⁡g(y)\log_g(y) given gg and y=gxy = g^x for randomly chosen xx. Targeted attacks, such as the , exploit the structure of Zp∗\mathbb{Z}_p^* to achieve subexponential complexity O(exp⁡(log⁡plog⁡log⁡p))O(\exp(\sqrt{\log p \log \log p}))
Add your contribution
Related Hubs
User Avatar
No comments yet.