One-way function
From Free net encyclopedia
Template:Unsolved A one-way function is a function that is easy to calculate but hard to invert — it is difficult to calculate the input to the function given its output. The precise meanings of "easy" and "hard" can be specified mathematically. With rare exceptions, almost the entire field of public key cryptography rests on the existence of one-way functions.
Contents |
Formal definitions
Formally, two variants of one-way functions are defined: strong and weak one-way functions.
Strong one-way functions
A function <math>f : \{0,1\}^* \rightarrow \{0,1\}^*</math> is called (strongly) one-way if the following two conditions hold:
- easy to compute: There exists a (deterministic) polynomial-time algorithm, <math>A</math>, so that on input <math>x</math> algorithm <math>A</math> outputs <math>f(x)</math> (i.e., <math>A(x)=f(x)</math>)
- hard to invert: For every probabilistic polynomial-time algorithm, <math>A^'</math>, every polynomial <math>p(\cdot)</math>, and all sufficiently large <math>n</math>'s
<math>U_n</math> denotes a random variable uniformly distributed over <math>\{0,1\}^n</math>. Hence,the probability in the second condition is taken over all the possible values assigned to <math>U_n</math> and all possible internal coin tosses of <math>A^'</math> with uniform probability distribution. In addition to an input in the range of <math>f</math> the inverting algorithm is also given the desired length of the output in unary notation. The main reason for this convention is to rule out the possibility that a function is considered one-way merely because the inverting algorithm does not have enough time to print the output.
The left hand part of the comparison is quite easy to understand: it is the probability, that <math>A^'</math> finds any value <math>U</math>, with property <math>f(U) = f(U_n)</math>. So, basically, the hard-to-invert condition requires this probability to negligibly small.
Weak one-way functions
One-way functions as defined above, are one-way in a very strong sense. Namely, any efficient inverting algorithm has negligible success in inverting them. A much weaker definition, presented below, only requires that all efficient inverting algorithms fail with some non-negligible probability.
A function <math>f : \{0,1\}^* \rightarrow \{0,1\}^*</math> is called weakly one-way if the following two conditions hold:
- easy to compute: as in the definition of strong one-way function.
- slightly-hard to invert: There exists a polynomial <math>p(\cdot)</math> such that for every probabilistic polynomial-time algorithm, <math>A^'</math>, and all sufficiently large <math>n</math>'s
Existence
It is not known whether one-way functions exist. In fact, their existence would imply P≠NP, resolving the foremost unsolved question of computer science. However, it is not clear if P≠NP implies the existence of one-way functions. It can be proved that weak one-way functions exist if and only if strong one-way functions do. Thus, as far as the mere existence of one-way function goes, the notions of weak and strong one-way functions are equivalent.
It is known that the existence of one-way functions implies the existence of many other useful cryptographic primitives, including (but not limited to):
- Pseudorandom bit generators;
- Pseudorandom function families;
- 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 distinct but related concept in cryptography is that of the cryptographic hash function.
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 having non-negligible success probability.
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 <math>N</math>, run in time <math>2^{O(\sqrt{\log P \log \log P})}</math>, where <math>P</math> is the second biggest prime factor of <math>N</math>. Hence it is reasonable to believe that the function, which partitions its input string into two parts and returns the (binary representation of the) integer by multiplying (the integers represented by) these parts, is one-way.
Rabin (Quadratic Residue) Function
It can be shown that extracting square roots modulo <math>N</math> is computationally equivalent to factoring <math>N</math> (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.
Discrete Logarithms
Another computational number problem which is widely believed to be intractable is that of extracting discrete logarithm in a finite field (and in particular of prime cardinality). Thus exponentiation in the finite field is a reasonable candidate for one-way function.
Other Candidates
Other possible candidates for one-way functions might based on the hardness of: decoding of random linear codes, subset sum problem or any other NP-complete one.
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.
- Template:Cite book Section 10.6.3: One-way functions, pp.374–376.
- Template:Cite book Section 12.1: One-way functions, pp.279–298.de:Einwegfunktion
es:Funciones de un solo sentido fr:Fonction à sens unique ko:일방향함수 ja:一方向性関数