One-way function 363890 221023139 2008-06-22T18:31:30Z Siddhant 270584 clean up using [[Project:AutoWikiBrowser|AWB]] {{unsolved|computer science|'''''Do one-way functions exist?'''''}} A '''one-way function''' is a [[function (mathematics)|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 [[PP (complexity)|probabilistic polynomial-time]] algorithm can compute a [[preimage]] of f(x) with better than [[negligible function (cryptography)|negligible probability]], when x is chosen at random. Note that unlike hardness in most of complexity theory (e.g., [[NP-hard]]ness), "hard" in the context of one-way functions refers to [[Best, worst and average case|average-case]] hardness rather than [[Best, worst and average case|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'') = ''x''<sup>2</sup> 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. == Existence of one-way functions == The existence of one-way functions is an open conjecture. In fact, their existence would imply [[P = NP problem|P≠NP]], resolving the foremost unsolved question of computer science. This is easy to show by showing the [[contrapositive]]: if P=NP, then [[FP (complexity)|FP]] = [[FNP (complexity)|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 generator]]s; *[[Pseudorandom function]] families; *[[commitment scheme|Bit commitment schemes]]; *Private-key encryption schemes secure against [[adaptive chosen-ciphertext attack]]; * [[Message authentication code]]s; * [[Digital signature scheme]]s (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 function|injective]] and [[surjection|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. == 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. === 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 factorization|(integer) factoring algorithm]], the best algorithms known for factoring an integer <math>N</math> run in time <math>2^{O({(\log N)^{1/3} (\log \log N})^{2/3})}</math>, which is only [[pseudo-polynomial time|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. ===Rabin 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 [[computational complexity theory#Intractability|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 [[computational complexity theory#Intractability|intractable]] is that of extracting [[discrete logarithm]]s 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. ===Other candidates=== Other candidates for one-way functions have been based on the hardness of the decoding of random [[linear code]]s, the [[subset sum problem]] ([[Naccache-Stern knapsack cryptosystem]]), [[travelling salesman problem]]{{Fact|date=June 2007}}, or other [[NP-complete]] problems. ==Universal one-way function== There is an explicit function which has been demonstrated to be one-way [[iff]] one-way functions exist.<ref name="HCPred">{{cite paper | author = [[Leonid Levin]] | title = The Tale of One-Way Functions | publisher = ACM | year = 2003 | url = http://arxiv.org/abs/cs.CR/0012023 }} </ref> 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. ==References== {{reflist|2}} ==Further reading== * Oded Goldreich (2001). ''Foundations of Cryptography: Volume 1, Basic Tools''. Cambridge University Press. ISBN 0-521-79172-3. Fragments available at the [http://www.wisdom.weizmann.ac.il/~oded/frag.html author's web site]. * Jonathan Katz and Yehuda Lindell (2007). ''Introduction to Modern Cryptography''. CRC Press. ISBN 1-584-88551-3. * {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = ISBN 0-534-94728-X}} Section 10.6.3: One-way functions, pp.374&ndash;376. * {{cite book|author = [[Christos Papadimitriou]] | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st edition | id = ISBN 0-201-53082-1}} Section 12.1: One-way functions, pp.279&ndash;298. ==See also== * [[One-way compression function]] * [[Cryptographic hash function]] [[Category:Cryptography]] [[Category:Cryptographic primitives]] [[cs:Jednocestná funkce]] [[de:Einwegfunktion]] [[es:Funciones de un solo sentido]] [[fr:Fonction à sens unique]] [[ko:일방향함수]] [[he:פונקציה חד-כיוונית]] [[ja:一方向性関数]] [[pl:Funkcja jednokierunkowa]] [[ru:Односторонняя функция]]