A Primer on Pseudorandom Generators (University Lecture by Oded Goldreich

By Oded Goldreich

A clean examine the query of randomness was once taken within the concept of computing: A distribution is pseudorandom if it can't be individual from the uniform distribution through any effective process. This paradigm, initially associating effective systems with polynomial-time algorithms, has been utilized with recognize to a number of typical periods of distinguishing strategies. The ensuing idea of pseudorandomness is appropriate to technology at huge and is heavily on the topic of relevant parts of desktop technology, corresponding to algorithmic layout, complexity conception, and cryptography. This primer surveys the idea of pseudorandomness, beginning with the final paradigm, and discussing a variety of incarnations whereas emphasizing the case of general-purpose pseudorandom turbines (withstanding any polynomial-time distinguisher). extra themes comprise the "derandomization" of arbitrary probabilistic polynomial-time algorithms, pseudorandom turbines withstanding space-bounded distinguishers, and several other common notions of special-purpose pseudorandom turbines. The primer assumes simple familiarity with the thought of effective algorithms and with straightforward likelihood conception, yet presents a easy creation to all notions which are truly used. therefore, the primer is basically self-contained, even if the reader is now and then observed different assets for extra element.

Show description

Read Online or Download A Primer on Pseudorandom Generators (University Lecture Series) PDF

Similar machine theory books

Theoretische Informatik: Eine kompakte Einführung (Springer-Lehrbuch) (German Edition)

Diese kompakte Einführung in die Theoretische Informatik stellt die wichtigsten Modelle für zentrale Probleme der Informatik vor. Dabei werden u. a. folgende Fragestellungen behandelt: Welche Probleme sind algorithmisch lösbar? (Theorie der Berechenbarkeit und Entscheidbarkeit) Wie schwierig ist es algorithmische Probleme zu lösen?

Web Reasoning and Rule Systems: 8th International Conference, RR 2014, Athens, Greece, September 15-17, 2014. Proceedings (Lecture Notes in Computer Science)

This booklet constitutes the refereed complaints of the eighth overseas convention on internet Reasoning and Rule structures, RR 2014, held in Athens, Greece in September 2014. The nine complete papers, nine technical communications and five poster shows awarded including three invited talks, three doctoral consortial papers have been rigorously reviewed and chosen from 33 submissions.

Advances in Computational Complexity Theory

This selection of fresh papers on computational complexity conception grew out of actions in the course of a different 12 months at DIMACS. With contributions via the various best specialists within the box, this e-book is of lasting price during this fast-moving box, supplying expositions now not came across somewhere else. even though aimed essentially at researchers in complexity thought and graduate scholars in arithmetic or computing device technological know-how, the ebook is obtainable to somebody with an undergraduate schooling in arithmetic or laptop technological know-how.

Extra resources for A Primer on Pseudorandom Generators (University Lecture Series)

Sample text

Let def Gσ|s| ···σ2 σ1 (s) = Gσ|s| (· · · Gσ2 (Gσ1 (s)) · · ·), def define fs (x1 x2 · · · xk ) = Gxk ···x2 x1 (s), and consider the function ensemble {fs : {0, 1}|s| → {0, 1}|s|}s∈{0,1}∗ . Pictorially, the function fs is defined by k-step walks down a full binary tree of depth k having labels at the vertices. The root of the tree, hereafter referred to as the level 0 vertex of the tree, is labeled by the string s. If an internal vertex is labeled r, then its left child is labeled G0 (r) whereas its right child is labeled G1 (r).

This seemingly stronger notion of unpredictability is actually equivalent to the one we use, because both notions are equivalent to pseudorandomness. 9 Given the popularity of the term, we deviate from our convention of not specifying credits in the main text. Indeed, this construction originates in [11]. 6. 14 (on the existence of pseudorandom generators): Pseudorandom generators exist if and only if one-way functions exist. To show that the existence of pseudorandom generators imply the existence of oneway functions, consider a pseudorandom generator G with stretch function ℓ(k) = 2k.

2, we get BPtime(t) ⊆ Dtime(T ), where T (n) = −1 poly(2ℓ (t(n)) · t(n)) = poly(t(n)). , tG (k) > ℓ(k)2 is allowed). Furthermore, tG (k) > 2k was also allowed. 5 We stress that the latter distinguisher is a uniform algorithm (and it works by invoking G on all possible seeds). In contrast, for a general-purpose pseudorandom generator G (as discussed in Chapter 2) it holds that tG (k) = poly(k), while for every polynomial p it holds that G(Uk ) is indistinguishable from Uℓ(k) in time p(tG (k)). 2 yields an algorithm AG that is defined such that AG (x, s) = A(x, G′ (s)), where |s| = ℓ−1 (t(|x|)) and G′ (s) denotes the t(|x|)-bit long prefix of G(s).

Download PDF sample

Rated 4.81 of 5 – based on 36 votes