mathematics

Pseudorandom generator theorem

Pseudorandom generator theorem is a mathematics topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Pseudorandom generator theorem rather than just read about it. In short: In computational complexity theory and cryptography, the existence of pseudorandom generators is related to the existence of one-way functions through a number of theorems, collectively referred to as the pseudorandom generator theorem. Introduction Pseudorandomness A distribution is considered pseudorandom if no efficient computation can distinguish it from the true uniform distribution by a non-negligible advantag…

Key takeaways

Pseudorandom generator theorem belongs to mathematics; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect Pseudorandom generator theorem to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of Pseudorandom generator theorem from memory before moving on to harder problems.

Reference excerpt

In computational complexity theory and cryptography, the existence of pseudorandom generators is related to the existence of one-way functions through a number of theorems, collectively referred to as the pseudorandom generator theorem.

Introduction

Pseudorandomness 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 any polynomial size circuit C, and any ε inversely polynomial in n

|Probx∈U [C(x)=1] − Probx∈D [C(x)=1] | ≤ ε.

Pseudorandom generators A function Gl: {0,1}l → {0,1}m, where l < m is a pseudorandom generator if:

Gl can be computed in time polynomial in l Gl(x) is pseudorandom, when x is uniformly random.

One additional pseudorandom bit implies polynomially more pseudorandom bits It can be shown that if there is a pseudorandom generator Gl: {0,1}l → {0,1}l+1, i.e. a generator that adds only one pseudorandom bit, then for any m = poly(l), there is a pseudorandom generator G'l: {0,1}l → {0,1}m. The idea of the proof is as follows: first s bits from uniform distribution Ul are picked and used as the seed to the first instance of Gl, which is known to be a pseudorandom generator. Next, the output of the first instance of Gl is divided into two parts: first l bits are fed into the second instance of Gl as a seed, while the last bit becomes the first bit of the output. Repeating this process for m times yields an output of m pseudorandom bits. It can be shown that such G'l, that consists of m instances of Gl, is indeed a pseudorandom generator by using a hybrid approach and proof by contradiction as follows: Consider m+1 intermediate distributions Hi: 0 ≤ i ≤ m, where first i bits are chosen from the uniform distribution, and last m − i bits are chosen from the output of G'l. Thus, H0 is the full output of G'l and Hm is a true uniform distribution Um. Therefore, distributions Hi and Hi+1 will be different in only one bit (bit number i+1). Now, assume that G'l is not a pseudorandom distribution; that is, there exists some circuit C that can distinguish between G'l and Um with an advantage ε = 1/poly(l). In other words, this circuit can distinguish between H0 and Hm. Therefore, there exists such i that the circuit C can distinguish between Hi and Hi+1 by at least ε / m. Note, that since m are polynomial in l, then ε / m is also polynomial in l and is still a non-negligible advantage. Now, assume we are given l+1 bits that are either output of Gl or a drawn from uniform distribution. Let's reuse the approach of building large pseudorandom generators out of instances of Gl and construct a string of pseudorandom bits of length m−i−1 in the same way the G'l was constructed above using the first l given bits as the seed. Then, let's create a string consisting of i bits drawn from uniform, concatenated with the last one of the given bits, followed by the created m−i−1 bits. The resulting output is either Hi or Hi+1, since the i+1 bit is either drawn from uniform or from Gl. Since by assumption we can distinguish between Hi and Hi+1 with non-negligible advantage, then we can distinguish between U and Gl, which implies that Gl is not a pseudorandom generator, which is a contradiction to the hypothesis. Q.E.D. Now, let's illustrate that if exists, the circuit for distinguishing between Gl and Ul+1 does not have to toss random coins. As we showed above, if exists a circuit C for distinguishing between G'l and Um, where m = poly(l), then exists a circuit C' for distinguishing between Gl and Ul+1 that uses i random bits. For this circuit C' : | Probu, s [C' (u1,...,ui,Gl(s)) = 1 ] − Probu, y [C' (u1,>,...,ui,y) = 1] | ≥ ε / m, where u is a string of i uniformly random bits, s is a string of l uniformly random bits, and y is a string of l+1 uniformly random bits. Then, Probu[ | Probs [C' (u1,...,ui,Gl(s)) = 1] - Proby [C' (u1,...,ui,y) = 1] | ] ≥ ε / m; Which means, there exists some fixed string u of i bits that can be used as an "advice" to circuit C' for distinguishing between Gl and Ul+1.

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

Definitions

One-way functions Intuitively one-way functions are functions that are easy to compute and hard to invert. In other words, the complexity (or circuit size) of the function is much smaller than that of its inverse. Formally: A function ƒ: {0,1}n → {0,1}n is (S,ε) one-way if for any circuit C of size ≤ S, Prob[ƒ(C(ƒ(x))) = ƒ(x)] ≤ ε. Moreover, ƒ is a one-way function if

ƒ can be computed in polynomial time ƒ is (poly(n), 1/poly(n)) one-way

Hard-core predicate Function B: {0,1}n → {0,1} is a hard-core predicate for function ƒ if

B can be computed in polynomial time for any polynomial size circuit C and any non-negligible ε = 1/poly(n), Probx~U [C(ƒ(x)) = B(x)] ≤ 1/2+ε In other words, it is hard to predict B(x) from function ƒ(x).

Proof Here an outline of the proof is given. Please see references for detailed proofs.

… excerpt ends here. Continue reading the full article.

Worked examples

Example 1 — a first encounter with Pseudorandom generator theorem

Start with the simplest possible case. Write down what Pseudorandom generator theorem claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In mathematics, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Pseudorandom generator theorem before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Pseudorandom generator theorem ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Pseudorandom generator theorem

In research: Pseudorandom generator theorem appears in mathematics research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses Pseudorandom generator theorem in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: Pseudorandom generator theorem is common in secondary-school and first-year university syllabi. It links to neighbouring topics Pseudorandomness, Theorems in computational complexity theory, so understanding it makes those chapters shorter.
In everyday life: Look for Pseudorandom generator theorem outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Pseudorandom generator theorem” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Pseudorandom generator theorem in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what Pseudorandom generator theorem means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain Pseudorandom generator theorem out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Pseudorandom generator theorem in simple terms?

Why does Pseudorandom generator theorem matter?

Because it connects several mathematics ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Pseudorandom generator theorem?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Pseudorandom generator theorem.