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)
“Let us stop being afraid. Of our own thoughts, our own minds. Of madness, our own or others’. Stop being afraid of the mind itself, its astonishing functions and fandangos, its complications and simplifications, the wonderful operation of its machinery—more wonderful because it is not machinery at all or predictable.”
—Kate Millett (b. 1934)