Download A primer on pseudorandom generators by Oded Goldreich PDF

By Oded Goldreich

A clean examine the query of randomness used to be taken within the idea of computing: A distribution is pseudorandom if it can't be exotic from the uniform distribution by means of any effective process. This paradigm, initially associating effective systems with polynomial-time algorithms, has been utilized with appreciate to quite a few ordinary periods of distinguishing tactics. The ensuing conception of pseudorandomness is appropriate to technological know-how at huge and is heavily concerning primary parts of computing device technological know-how, resembling algorithmic layout, complexity thought, and cryptography. This primer surveys the speculation of pseudorandomness, beginning with the final paradigm, and discussing numerous incarnations whereas emphasizing the case of general-purpose pseudorandom turbines (withstanding any polynomial-time distinguisher). extra themes contain the "derandomization" of arbitrary probabilistic polynomial-time algorithms, pseudorandom turbines withstanding space-bounded distinguishers, and a number of other typical notions of special-purpose pseudorandom turbines. The primer assumes uncomplicated familiarity with the idea of effective algorithms and with uncomplicated chance thought, yet offers a simple creation to all notions which are really used. for that reason, the primer is basically self-contained, even supposing the reader is every now and then said different assets for extra element

Show description

Read or Download A primer on pseudorandom generators PDF

Similar machine theory books

Numerical computing with IEEE floating point arithmetic: including one theorem, one rule of thumb, and one hundred and one exercises

Are you acquainted with the IEEE floating element mathematics common? do you want to appreciate it larger? This booklet supplies a extensive evaluation of numerical computing, in a historic context, with a different concentrate on the IEEE commonplace for binary floating element mathematics. Key rules are built step-by-step, taking the reader from floating aspect illustration, thoroughly rounded mathematics, and the IEEE philosophy on exceptions, to an figuring out of the the most important suggestions of conditioning and balance, defined in an easy but rigorous context.

Robustness in Statistical Pattern Recognition

This publication is anxious with vital difficulties of strong (stable) statistical pat­ tern acceptance while hypothetical version assumptions approximately experimental information are violated (disturbed). development acceptance thought is the sector of utilized arithmetic within which prin­ ciples and strategies are developed for class and id of gadgets, phenomena, procedures, occasions, and indications, i.

Bridging Constraint Satisfaction and Boolean Satisfiability

This e-book offers an important step in the direction of bridging the parts of Boolean satisfiability and constraint delight by means of answering the query why SAT-solvers are effective on convinced periods of CSP cases that are tough to unravel for traditional constraint solvers. the writer additionally supplies theoretical purposes for selecting a specific SAT encoding for numerous very important periods of CSP circumstances.

A primer on pseudorandom generators

A clean examine the query of randomness used to be taken within the concept of computing: A distribution is pseudorandom if it can't be special from the uniform distribution by means of any effective method. This paradigm, initially associating effective systems with polynomial-time algorithms, has been utilized with admire to a number of normal sessions of distinguishing tactics.

Additional resources for A primer on pseudorandom generators

Example text

3): The ith hybrid, denoted Hki , is a function i ensemble consisting of 22 ·k functions {0, 1}k → {0, 1}k , each determined by 2i random k-bit strings, denoted s = sβ β∈{0,1}i . The value of such a function hs at x = αβ, where |β| = i, is defined to equal Gα (sβ ). Pictorially, the function hs is defined by placing the strings in s in the corresponding vertices of level i, and labeling vertices of lower levels using the very rule used in the definition of fs . , Hk0 ≡ fUk and Hkk is a truly random function), and the indistinguishability of neighboring hybrids follows from our indistinguishability hypothesis.

To show that the existence of pseudorandom generators imply the existence of oneway functions, consider a pseudorandom generator G with stretch function ℓ(k) = 2k. def For x, y ∈ {0, 1}k , define f (x, y) = G(x), and so f is polynomial-time computable (and length-preserving). It must be that f is one-way, or else one can distinguish G(Uk ) from U2k by trying to invert f and checking the result: inverting f on the distribution f (U2k ) corresponds to operating on the distribution G(Uk ), whereas the probability that U2k has an inverse under f is negligible.

1 Background: one-way functions One-way functions are functions that are easy to compute but hard to invert (in an average-case sense). 9 (one-way functions): A function f : {0, 1}∗ → {0, 1}∗ is called oneway if the following two conditions hold: 1. Easy to evaluate: There exists a polynomial-time algorithm A such that A(x) = f (x) for every x ∈ {0, 1}∗. 2. 7) where the probability is taken uniformly over the possible choices of x ∈ {0, 1}n and over the internal coin tosses of algorithm A′ . , |f (x)| = O(log |x|)).

Download PDF sample

Rated 4.79 of 5 – based on 23 votes