Pseudorandom Generator Theorem - Existence of Pseudorandom Generators

Existence of Pseudorandom Generators

The existence of pseudorandom generators is related to the existence of one-way functions and hard-core predicates. Formally, pseudorandom generators exist if and only if one-way functions exist, or

PRG ↔ OWF

Read more about this topic:  Pseudorandom Generator Theorem

Other articles related to "existence of pseudorandom generators, pseudorandom generator, existence of, generator, pseudorandom":

Pseudorandom Generator Theorem - Existence of Pseudorandom Generators - Proof - OWF → PRG
... One-way permutation → pseudorandom generator A one-way permutation is a one-way function that is also a permutation of the input bits ... A pseudorandom generator can be constructed from one-way permutation ƒ as follows Gl {0,1}l→{0,1}l+1 = ƒ(x).B(x), where B is hard-core predicate of ƒ and ... that by the theorem proven above, it is only needed to show the existence of a generator that adds just one pseudorandom bit ...

Famous quotes containing the word existence:

    Perfect present has no existence in our consciousness. As I said years ago in Erewhon, it lives but upon the sufferance of past and future. We are like men standing on a narrow footbridge over a railway. We can watch the future hurrying like an express train towards us, and then hurrying into the past, but in the narrow strip of present we cannot see it. Strange that that which is the most essential to our consciousness should be exactly that of which we are least definitely conscious.
    Samuel Butler (1835–1902)