One-way function
|
|
Template:Unsolved 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 <math>f<math> with the following properties:
- Computing <math>f(x)<math>, given <math>x<math>, is tractable (i.e., <math>f<math> is computable by a polynomial-time algorithm; see complexity theory).
- Computing any preimage of <math>f(x)<math> (i.e., an element <math>y<math> such that <math>f(y)=f(x)<math>), given only <math>f(x)<math> for some random <math>x<math>, 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 functions. It is also not clear if the existence of one-way functions implies the existence of one-to-one one-way functions. 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. Another example is the square function modulo <math>n<math>, where <math>n<math> is the product of two primes.
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 (http://www.wisdom.weizmann.ac.il/~oded/frag.html).
de:Einwegfunktion fr:Fonction à sens unique ja:一方向性関数
Question here for Bit Streams Cryptology: { For mathematical equations in the lowest representation systems the binary systems of bits like "0" and "1", as like the equations with equal signs like "A = B", could we conclude that it is impossible to have one-way function because "B = A" as well and there is no imaginary number, no fractional number, no transcendental number, etc? What we have are only bit streams, hence it is an issues of Electricity Supply, CPU Computing Power, Memory Space, Data Transmission Speed, etc. The encrypted bit streams is in fact needing only a matching table to decode the hidden information. This is because certain blocks of bit streams are assigned to represent certain concepts. }