One-way function
From Wikipedia, the free encyclopedia
A one-way function is a function that is easy to compute but hard to invert — given the output of the function it is difficult to find any input which yields this output. The precise meanings of "easy" and "hard" can be specified mathematically:
"Easy" means that some algorithm can compute the function in probabilistic polynomial time (in the input size). "Hard" means no such probabilistic polynomial-time algorithm exists. However, unlike hardness such as NP-hardness, "hard" in the context of one-way functions refers to the average case. Hardness on average is typically proven via random self-reducibility.
With rare exceptions, almost the entire field of public key cryptography rests on the existence of one-way functions.
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. 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 some one-way functions implies the existence of many other useful cryptographic primitives, including:
- Pseudorandom number generators;
- Pseudorandom function families;
- Bit commitment schemes;
- 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. For example, it's believed to be difficult to factorize a product of two primes, but it is easy as soon as you know one of them.
A distinct but related concept in cryptography is that of the cryptographic hash function.
[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
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 
. Hence it is reasonable to believe that the function which multiplies a pair of integers (represented as bitstrings) is one-way.
[edit] Rabin (quadratic residue) 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 (see also quadratic residue).
[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, or other NP-complete problems.
[edit] References
- Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the author's web site.
- 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.
