One-way function
From Wikipedia, the free encyclopedia
A one-way function is a function that is easy to compute but "hard to invert" (in the sense defined below). "Easy to compute" means that some algorithm can compute the function in polynomial time (in the input size). "Hard to invert" means that no probabilistic polynomial-time algorithm can compute a preimage of f(x) with better than negligible probability, when x is chosen at random. 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 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 preimages in polynomial time by taking its square root.
Contents |
[edit] Existence of one-way functions
The existence of one-way functions is an open conjecture. In fact, their existence would imply P≠NP, resolving the foremost unsolved question of computer science. This is easy to show by showing the contrapositive: if P=NP, then FP = FNP, and so any function that can be computed in polynomial time can be inverted in polynomial time, since there is a simple FNP algorithm that inverts it by nondeterministically enumerating all possible inputs. However, it is not known whether P≠NP implies the existence of one-way functions, mainly because of the worst-case hardness vs. average-case hardness distinction.
The existence of a one-way function implies the existence of many other useful cryptographic primitives, including:
- Pseudorandom number 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.
[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). (Technically, f must be modified to prevent the trivial inverting algorithm that on input y outputs the "preimage" (2, y/2) when y is even. This technicality can be addressed but is ignored here.)
In spite of the extensive research directed towards the construction of the efficient (integer) 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 iff 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". The problem of determining the existence of one-way functions can be reduced to the problem of proving that this specific function is one-way.
[edit] References
- ^ Leonid Levin. "The Tale of One-Way Functions". . ACM
[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, Addison Wesley. ISBN 0-201-53082-1. Section 12.1: One-way functions, pp.279–298.
