
Oneway Function
I'm trying to wrap my head around what a oneway function is. The definition I found is complicated to understand (for me anyways) and it states the following:
Informally, a function is a oneway function if
1. The description of is publicly known and does not require any secret information for its operation.
2. Given , it is easy to compute .
3. Given , in the range of , it is hard to find an such that . More precisely, any efficient algorithm solving a Pproblem succeeds in inverting with negligible probability.
The existence of oneway functions is not proven. If true, it would imply . Therefore, it would answer the complexity theory NPproblem question of whether all apparently NPproblems are actually Pproblems. Yet a number of conjectured oneway functions are routinely used in commerce and industry. For example, it is conjectured, but not proved, that the following are oneway functions:
1. Factoring problem: , for randomly chosen primes .
2. Discrete logarithm problem:
for a generator of for some prime .
3. Discrete root extraction problem: , for in , in and relatively prime to , and primes. This is the function commonly known as RSA encryption.
4. Subset sum problem: , for , and bit integers .
5. Quadratic residue problem.
I was wondering if someone could explain it a little better? Thanks.

Re: Oneway Function
Hey rhymin.
If we are talking about functions that are reversible (as opposed to those that are not like hash functions), then the main idea of a one way function is that its easy to compute, but hard to invert.
In a function that is invertible, you have an inverse map which is f^(1)(x) where you can use f^(1)(f(x)) = x to get back your original input. This is what happens in cryptography where you encode something by using h = f(x) and then you apply f^(1)(h) = x to get back your original data.
If it is hard to undo (or invert) it means that the computational complexity for undoing is going to be high (like exponentially high or greater than polynomial).
The class of problems that are hard to compute or find but easy to check are called NP problems. You can check the solution very quickly, but finding the solution probabilistically will take a long time.

Re: Oneway Function