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:
“Post-structuralism is among other things a kind of theoretical hangover from the failed uprising of ‘68Ma way of keeping the revolution warm at the level of language, blending the euphoric libertarianism of that moment with the stoical melancholia of its aftermath.”
—Terry Eagleton (b. 1943)
“When it had long since outgrown his purely medical implications and become a world movement which penetrated into every field of science and every domain of the intellect: literature, the history of art, religion and prehistory; mythology, folklore, pedagogy, and what not.”
—Thomas Mann (1875–1955)
“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)