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.