One way function Guide, Meaning , Facts, Information and Description

A one way function is a function which 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. One way functions are useful in cryptography for public key encyption and digital signatures.

Formally, a one way function is a computable function f with the following properties:

• The computation of is tractable (which generally means that a polynomial algorithm for the computation is known, see complexity theory).
• The computation of the preimage of (denoted ), on a random x, is not tractable (i.e. no polynomial time algorithm exists) given only .

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 function. It is also not clear if the existence of one-way function implies the existence of one-to-one one-way function. There are several (classes of) functions that are candidates for one way functions. Multiplication of two large primes is one such: this is because integer factorization is thought to be a hard problem. Another is exponentiation in certain groupss: this one relies on the presumed hardness of the computing the discrete logarithm.

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.

A cryptographic hash function is like a one way function except that it is not required to be bijective and has more stringent requirements for hardness of inversion.

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.

This is an Article on One way function. Page Contains Information, Facts Details or Explanation Guide About One way function

	Web www.E-paranoids.com