Limitations On The Provability of Pseudorandom Generators
The pseudorandom generators used in cryptography and universal algorithmic derandomization have not been proven to exist, although their existence is widely believed. Proofs for their existence would imply proofs of lower bounds on the circuit complexity of certain explicit functions. Such circuit lower bounds cannot be proved in the framework of natural proofs assuming the existence of stronger variants of cryptographic pseudorandom generators.
Read more about this topic: Pseudorandom Generator
Famous quotes containing the words limitations on and/or limitations:
“... art transcends its limitations only by staying within them.”
—Flannery O’Connor (1925–1964)
“Growing up means letting go of the dearest megalomaniacal dreams of our childhood. Growing up means knowing they can’t be fulfilled. Growing up means gaining the wisdom and skills to get what we want within the limitations imposed by reality—a reality which consists of diminished powers, restricted freedoms and, with the people we love, imperfect connections.”
—Judith Viorst (20th century)