I'm trying to wrap my head around what a one-way function is. The definition I found is complicated to understand (for me anyways) and it states the following:
Informally, a function is a one-way 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 P-problem succeeds in inverting with negligible probability.
The existence of one-way functions is not proven. If true, it would imply . Therefore, it would answer the complexity theory NP-problem question of whether all apparently NP-problems are actually P-problems. Yet a number of conjectured one-way functions are routinely used in commerce and industry. For example, it is conjectured, but not proved, that the following are one-way 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.
Mar 28th 2013, 06:22 PM
Re: One-way Function
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.