FACTOID # 15: A mere 0.8% of West Virginians were born in a foreign country.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Pseudorandom generator

Let G be a deterministic polynomial time function from N<? to N<? with stretch function In computer science, a deterministic algorithm is an algorithm which, in informal terms, behaves predictably. ... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...

l:N ? N,

so that if x has length n then G(x) has length l(n). Then let Gn be the distribution on strings of length l(n) defined by the output of G on a randomly selected string of length n selected by the uniform distribution. The word random is used to express lack of purpose, cause, order, or predictability in non-scientific parlance. ... In mathematics, the uniform distributions are simple probability distributions. ...

Then we say G is a pseudorandom generator if

{Gn}n ? N

is pseudorandom. A pseudorandom process is a process that appears random but is not. ...

In effect, G translates a random input of length n to a pseudorandom output of length l(n). Assuming

l(n) > n,

this expands a random sequence (and can be applied multiple times, since Gn can be replaced by the distribution of G(G(x))).

Often, we are concerned not with the behavior of G on all strings, but only on strings of some prescribed length. This case allows a slightly easier definition:

A function $G_l: left {0,1right}^n rightarrow left {0,1right}^m,$ with $n < m,$ is a pseudorandom generator if

• $G_l,$ can be computed in $poly(n),$ time, and
• $G_l(x),$ is pseudorandom.

It is an open problem whether or not pseudorandom generators exist. It is known that if one-way functions or hard-core predicates exist, then pseudorandom generators exist. It is also known that if Unsolved problems in computer science: Do one-way functions exist? A one-way function is a function that is easy to compute but hard to invert. ... In cryptography, a hard-core predicate of a one-way function f(x) is a predicate b(x) which is easy to compute given x but is hard to compute given f(x). ...

l(n) > n,

there is some other pseudorandom generator with

l(n) > p(n)

for any polynomial, p(n). This follows from the following theorem:

Theorem: If there is a pseudorandom generator

$G_l: left {0,1right}^{n} rightarrow left {0,1right}^{n+1},$

then for any $m = poly(n) ,$, there is a pseudorandom generator

$G_l: left {0,1right}^n rightarrow left {0,1right}^m,$

Pseudorandom generators have numerous applications. In cryptography, a simple application is providing an efficient analog of `one time pads'. It is well known that in order to encrypt a message m in a way that the cipher text provides no information on the plaintext, the key k used should be random over strings of length |m|. Then m can be encrypted via $c=koplus m$. This operation is very costly in terms of key length. Key length can be reduced if we compromise on semantic security. Then, given G, which expands by a polynomial nc + 1, then a sequence of nc messages of length n can be encrypted by xor-ing each with the corresponding area of G(k) (inspired the idea of stream chipers). Pseudorandom generators may also be used to construct symmetric key cryptosystems, where any polynomial number of messages can be `safely' encrypted under the same key, that is, the polynomial nc is not apriority known at time of key generation. Such a construction can be based on a generalization of pseudo random generators, called pseudorandom functions. A family of pseudorandom functions (PRF's) is a collection of efficiently computable keyed functions, which `act randomly' in the scene that no efficient algorithm can distinguish between an oracle to a function corresponding to a random key, and an oracle to a random function. It's known that if PRG's exist, than so do PRF's (for more details see pseudorandom function). One application of PRF's is in learning. Loosely speaking, given a sequence of examples $(x_1,f(x_1)),(x_2,f(x_2)),ldots,(x_m,f(x_m)))$ e.t.c, the goal is to efficiently find a succinct representation of a function f out of a given class of functions consistent with the examples. PRF families (if exist) are a natural example of a class of functions with small representation size, but are not learnable. Semantic security is a widely-used definition for security in an asymmetric key encryption algorithm. ... In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: No efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are... In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: No efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are...

Another application is to derandomizing algorithms. A nice pseudorandom generator is a pseudorandom number generator,

$G:{0,1}^nrightarrow{0,1}^m$

with

$n=O(log m),$.

If a nice pseudorandom generator exists, then P=BPP. In fact, this strong derandomization result follows assuming the existence of a weaker type of pseudorandom generators, Nisan-Wigderson type generator with exponential stretch. Their definition weakens the definition of PRG above in two essential ways. First, it allows Gl to run in exponential in n time. Another important difference is that the output distribution is only required to be indistinguishable from uniform for circuits of size S'(n) for some fixed exponential S' which is smaller than S, as opposed to generators as in the definition above. It's easy to see that the existence of nice pseudorandom generators of this kind for some polynomial S(n) is sufficient to imply P=BPP, and follows from plausible hardness assumptions (that some problems in EXP don't have sub exponential circuits). In a nutshell, the idea is to replace the randomness used by a BPP algorithm A, by G(s), where s is a short (O(log(n))) random string. By pseudorandomness of G, the behavior of A on any given x will not change much, so we can count the number of 1's output by A obtained iterating over the s, and answer according to the majority. That is, $A(x,cdot)$ can be viewed as a non uniform distinguisher of proper size. For more details on this result and other derandomization results see BPP. In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... This article is about the complexity class. ... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... This article is about the complexity class. ... Exp, in Role-Playing Games, stands for experience points. ... This article is about the complexity class. ...

For more on these and other applications of PRG's, see chapters 10,17 in a draft of a book by Aurora and Barak available at http://www.cs.princeton.edu/theory/complexity/

Results from FactBites:

 Pseudorandom number generator - Wikipedia, the free encyclopedia (1891 words) A pseudorandom number generator (PRNG) is an algorithm that generates a sequence of numbers which are not truly random. Although truly random numbers are believed to be generatable using hardware random number generators, pseudo-random numbers are important in practice for simulations (eg, of physical systems with the Monte Carlo method), and are central in the practice and so in the theory of cryptography. crng: Random-number generators (RNGs) implemented as Python extension types coded in C. http://eeyore.wu-wien.ac.at/src/ prng: A collection of algorithms for generating pseudorandom numbers as a library of C functions, released under the GPL.
 Cryptographically secure pseudorandom number generator - Wikipedia, the free encyclopedia (1172 words) On the other hand, generation of a master key requires a higher quality, such as more entropy. Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from a high quality source, which might be a hardware random number generator or perhaps unpredictable system processes — though unexpected correlations have been found in several such ostensibly independent processes. Most stream ciphers work by generating a pseudorandom stream of bits that are combined (almost always XORed) with the plaintext; this stream can sometimes be used as a good CSPRNG (though not always: see RC4 cipher).
More results at FactBites »

Share your thoughts, questions and commentary here

Want to know more?
Search encyclopedia, statistics and forums:

Press Releases |  Feeds | Contact