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:
“The hypothesis I wish to advance is that ... the language of morality is in ... grave disorder.... What we possess, if this is true, are the fragments of a conceptual scheme, parts of which now lack those contexts from which their significance derived. We possess indeed simulacra of morality, we continue to use many of the key expressions. But we have—very largely if not entirely—lost our comprehension, both theoretical and practical, of morality.”
—Alasdair Chalmers MacIntyre (b. 1929)
“The power to guess the unseen from the seen, to trace the implications of things, to judge the whole piece by the pattern, the condition of feeling life in general so completely that you are well on your way to knowing any particular corner of it—this cluster of gifts may almost be said to constitute experience.”
—Henry James (1843–1916)
“The mind is a finer body, and resumes its functions of feeding, digesting, absorbing, excluding, and generating, in a new and ethereal element. Here, in the brain, is all the process of alimentation repeated, in the acquiring, comparing, digesting, and assimilating of experience. Here again is the mystery of generation repeated.”
—Ralph Waldo Emerson (1803–1882)