Pseudorandom generator

Pseudorandom generator

In theoretical computer science, a pseudorandom generator is a deterministic method of generating a large amount of pseudorandom, or apparently random, data, from a small amount of initial random data. The initial data is commonly known as a random seed.

Formal definition

Let "G" be a deterministic polynomial time function from N to N with "stretch function"

:"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.

Then "G" is a pseudorandom generator if

:{"Gn"}"n ∈ "N

is pseudorandom.

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, the subject of concern is 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,1 ight}^n ightarrow left {0,1 ight}^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

:"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,1 ight}^{n} ightarrow left {0,1 ight}^{n+1},then for any m = poly(n) ,, there is a pseudorandom generator:::G_l: left {0,1 ight}^n ightarrow left {0,1 ight}^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 n^{c+1}, then a sequence of n^c messages of length n can be encrypted by xor-ing each with the corresponding area of G(k) (inspired the idea of stream ciphers).

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 n^c 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, then so do PRF's (for more details see pseudorandom function). One application of PRF's is to understanding learning theory. 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.

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

:G:{0,1}^n ightarrow{0,1}^m


: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 ofpseudorandom generators, Nisan-Wigderson type generator with exponential stretch. Their definition weakens the definition of PRG above in two essential ways. First, it allows G_l 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 behaviorof 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.

ee also

* BPP (describing Bounded-error, Probabilistic, Polynomial time derandomization algorithms)

Further reading

* For more on these and other applications of PRG's, see chapters 10,17 in a draft of a book by Arora and Barak: []

Wikimedia Foundation. 2010.

См. также в других словарях:

  • Pseudorandom generator theorem — In computational complexity a distribution is considered pseudorandom if no efficient computation can distinguish it from the true uniform distribution by a non negligible advantage. Formally, a family of distributions Dn is pseudorandom if for… …   Wikipedia

  • Pseudorandom number generator — A pseudorandom number generator (PRNG), also known as a deterministic random bit generator (DRBG),[1] is an algorithm for generating a sequence of numbers that approximates the properties of random numbers. The sequence is not truly random in… …   Wikipedia

  • Pseudorandom function family — 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… …   Wikipedia

  • Generator — may refer to: * Electrical generator * Engine generator, an electrical generator, but with its own engine. * Generator (mathematics), any of several closely related usages in mathematics.Music * Generator (song), a song by The Foo Fighters *… …   Wikipedia

  • Pseudorandom number sequence — A Pseudorandom number sequence is a sequence of numbers that has been computed by some defined arithmetic process but is effectively a random number sequence for the purpose for which it is required. Although a pseudorandom number sequence in… …   Wikipedia

  • Pseudorandom noise — In cryptography, pseudorandom noise (PRN[1][2]) is a signal similar to noise which satisfies one or more of the standard tests for statistical randomness. Although it seems to lack any definite pattern, pseudorandom noise consists of a… …   Wikipedia

  • pseudorandom number generator — pseudoatsitiktinių skaičių generatorius statusas T sritis informatika apibrėžtis Programos komponentas, generuojantis ↑pseudoatsitiktinius skaičius. Skaičių eilė kuriama grynai programiniu būdu be išorinių, galinčių būti atsitiktiniais, veiksnių …   Enciklopedinis kompiuterijos žodynas

  • pseudorandom number generator — noun A device or algorithm that deterministically produces a succession of values that appear in an unpredictable sequence or apparently random order …   Wiktionary

  • Cryptographically secure pseudorandom number generator — A cryptographically secure pseudo random number generator (CSPRNG) is a pseudo random number generator (PRNG) with properties that make it suitable for use in cryptography. Many aspects of cryptography require random numbers, for example: Key… …   Wikipedia

  • Blum-Blum-Shub-Generator — Der Blum Blum Shub Generator (BBS Generator; auch „s² mod n Generator“) ist ein Pseudozufallszahlengenerator, entwickelt 1986 von Lenore Blum, Manuel Blum und Michael Shub. Anwendung findet das System u. a. in der Kryptologie im Entwurf… …   Deutsch Wikipedia

Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»