one way function

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. With rare exceptions, almost the entire field of public key cryptography rests on the existence of one way functions. Formally, a one-way function is a computable function

f

with the following properties:

Computing $f(x)$ , given $x$ , is tractable (i.e., $f$ is computable by a polynomial-time algorithm; see complexity theory).
Computing any preimage of $f(x)$ (i.e., an element $y$ such that $f(y)=f(x)$ ), given only $f(x)$ for some random x, is not tractable (i.e. no probabilistic polynomial time algorithm exists).

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. However, it has been shown that P≠UP (a subclass of NP) implies the existence of one-to-one one-way functions; see UP for more. 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).

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 groups: 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 distinct but related concept in cryptography is that of the cryptographic hash function.

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.

<< Previous

Word Browser

Next >>

state president of south africa
zymology
kagome higurashi
warp coil
rutland railroad
pope john xii
hikaru sulu
damn yankees
america first party (1940)
george takei
pope john xi

pope john x
pope john ix
monthon
pope john vii
alternative comedy
deadsy
pete doherty
pope john vi
pope john xvii
julien temple
pope john xviii

duce
bruce foxton
julian clary
church of iceland
ethidium bromide
ruby wax
sham 69
niagara regional municipality, ontario
hugh edwin strickland
stiv bators
list of oldest universities in continuous operation

arnold brown
canonical correlation
slaughter & the dogs
newtonian fluid
rik mayall
sharp shinned hawk
nakhon nayok province
the comedians
charles wilson (politician)
june rowlands
cooperative baptist fellowship