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.
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] 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.
, 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.
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] 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.
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.
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).
Currently there are several popular groups for which no algorithm to calculate the underlying discrete logarithm in polynomial time is known.
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).
Most of the theoretical support for the functions are more techniques for thwarting some of the previously successful attacks.
There also exists a function that is one-way if polynomial-time bounded Kolmogorov complexity is mildly hard on average.