One-way function
From Wikipedia, the free encyclopedia
In cryptography, 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. One-way functions are fundamental objects in the foundations of cryptography.
Contents |
[edit] Definition
A function f: {0, 1}* → {0, 1}* is one-way if f can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm A,
- Pr[f(A(f(x))) = f(x)] < 1/p(n)
for every polynomial p(n) and sufficiently large n, where the probability is taken over x chosen from the uniform distribution on {0, 1}n and the randomness of A.
[edit] Notes
Note that unlike hardness in most of complexity theory (e.g., NP-hardness), "hard" in the context of one-way functions refers to average-case hardness rather than worst-case hardness.
Note that just making a function "lossy" (not one-to-one) does not make it a one-way function; inverting a function in this context merely means identifying some preimage element of a given value, which does not require the existence of an inverse function. For example, f(x) = x2 is not invertible (for example f(2) = f(-2) = 4) but is also not one-way, since given any value, you can compute one of its preimage elements in polynomial time by taking its square root.
[edit] Existence of one-way functions
The existence of one-way functions is an open conjecture. In fact, their existence would imply P≠NP[citation needed], resolving the foremost unsolved question of theoretical computer science. However, it is not known whether P≠NP implies the existence of one-way functions.
The existence of a one-way function implies the existence of many other useful cryptographic primitives, including:
- Pseudorandom generators;
- Pseudorandom function families;
- Bit commitment schemes;
- Private-key encryption schemes secure against adaptive chosen-ciphertext attack;
- Message authentication codes;
- Digital signature schemes (secure against adaptive chosen-message attack).
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. RSA is a well known example of a function believed to belong to this class.
A one-way permutation is a one-way function that is also a permutation — that is, a one-way function that is both injective and surjective. One-way permutations are an important cryptographic primitive, and it is not known that their existence is implied by the existence of one-way functions.
[edit] Candidates for one-way functions
Following are several candidates for one-way functions. Clearly, it is not known whether these functions are indeed one-way. This is only a conjecture supported by extensive research which has so far failed to produce an efficient inverting algorithm.
[edit] Integer factorization
Consider the function f that takes as input two integers and multiplies them. This function is easy to compute, but inverting this function requires solving the factoring problem, which is believed to be hard in general. Although finding a factor is easy for most integers (all multiples of 2 or 3 are easy), these easy cases can be, and in practice are, filtered out by allowing only inputs which result in a suitable subset of semiprimes.
In spite of the extensive research directed towards the construction of the efficient factoring algorithm, the best algorithms known for factoring an integer N run in time 
, which is only pseudo-polynomial in the number of bits needed to represent N. Hence it is reasonable to believe that the function which multiplies a pair of integers (represented as bitstrings) is one-way.
[edit] Rabin function
It can be shown that extracting square roots modulo N is computationally equivalent to factoring N (i.e., the two tasks are reducible to one another via probabilistic polynomial-time reductions). Hence, squaring modulo a composite is a one-way function if and only if factoring is intractable. The Rabin cryptosystem is based on the assumption that Rabin function is one-way.
[edit] Discrete logarithms
Another computational number problem which is widely believed to be intractable is that of extracting discrete logarithms in a finite field (and in particular of prime cardinality). Thus exponentiation in the finite field is a reasonable candidate for one-way function. The ElGamal encryption scheme is based on this.
[edit] Other candidates
Other candidates for one-way functions have been based on the hardness of the decoding of random linear codes, the subset sum problem (Naccache-Stern knapsack cryptosystem), travelling salesman problem[citation needed], or other NP-complete problems.
[edit] Universal one-way function
There is an explicit function which has been demonstrated to be one-way if one-way functions exist.[1] Since this function was the first combinatorial complete one-way function to be demonstrated, it is known as the "universal one-way function".
[edit] References
[edit] Further reading
- Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
- Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography. CRC Press. ISBN 1-584-88551-3.
- Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 10.6.3: One-way functions, pp.374–376.
- Christos Papadimitriou (1993). Computational Complexity (1st edition ed.). Addison Wesley. ISBN 0-201-53082-1. Section 12.1: One-way functions, pp.279–298.
