Theoretical Implications of One-way Functions
If f is a one-way function, then the inversion of f would be a problem whose output is hard to compute (by definition) but easy to check (just by computing f on it). Thus, the existence of a one-way function implies that FP≠FNP, which in turn implies that P≠NP. However, it is not known whether P≠NP implies the existence of one-way functions.
The existence of a one-way function implies the existence of many other useful concepts, including:
- Pseudorandom generators
- Pseudorandom function families
- Bit commitment schemes
- Private-key encryption schemes secure against adaptive chosen-ciphertext attack
- Message authentication codes
- Digital signature schemes (secure against adaptive chosen-message attack)
The existence of one-way functions also implies that there is no natural proof for P≠NP.
Read more about this topic: One-way Function
Famous quotes containing the words theoretical, implications and/or functions:
“There are theoretical reformers at all times, and all the world over, living on anticipation.”
—Henry David Thoreau (1817–1862)
“Philosophical questions are not by their nature insoluble. They are, indeed, radically different from scientific questions, because they concern the implications and other interrelations of ideas, not the order of physical events; their answers are interpretations instead of factual reports, and their function is to increase not our knowledge of nature, but our understanding of what we know.”
—Susanne K. Langer (1895–1985)
“Those things which now most engage the attention of men, as politics and the daily routine, are, it is true, vital functions of human society, but should be unconsciously performed, like the corresponding functions of the physical body.”
—Henry David Thoreau (1817–1862)