Transcript Pseudorandom Generators

Slides by Vera Asodi & Tomer Naveh.
Updated by : Avi Ben-Aroya & Alon Brook
Adapted from Oded Goldreich’s course lecture notes
ACT
by Sergey Benditkis, Boris Temkin
and Il’ya Safro.
1
Introduction
In this lecture we’ll cover:
Definition of pseudorandom generators
 Computational indistinguishability
 Statistical closeness
 Multiple samples
 Application of pseudorandom generators
 Amplification of the stretch function
 One-way function
 Hard-core predicate

ACT
2
Definition of PRG
A Pseudorandom Generator is an efficient program
which stretches short random seeds into long
pseudorandom sequences.
Efficiency
Seed
PRG
Stretching
Mmmm…
They
look the
same to
me!
Pseudorandom Sequence
Random Sequence
ACT
Efficient
Algorithm
3
13.1
Computational Indistinguishability
Def: A probability ensemble X is a family X =
{Xn}nN such that Xn is a probability
distribution on some finite domain.
Def: Two probability ensembles, {Xn}nN and
{Yn}nN , are called computationally
indistinguishable if for any probabilistic
polynomial-time algorithm A, for any
positive polynomial p(.), and for all
sufficiently large n’s
PrxXn Ax   1  PryYn Ay   1  p1n 
ACT
4
Defining PRG
13.2
Def: A deterministic polynomial-time algorithm G is
called a pseudorandom generator if there exists
a stretching function l:NN, s.t. the following
two probability ensembles, denoted {Gn}nN and
{Rn}nN, are computationally indistinguishable
1. Distribution Gn is defined as the output of
G on a uniformly selected seed in {0,1}n.
2. Distribution Rn is defined as the uniform
distribution on {0,1}l(n).
ACT
5
Statistical Closeness
13.3
Def (statistical closeness): The statistical
difference between two distributions, X
and Y, is defined as
X, Y   21  PrX    PrY  

Two probability ensembles {Xn}nN and
{Yn}nN are statistically close if
for all polynomials p(.) and for all
sufficiently large n
Xn , Yn   p1n 
ACT
Prop: If two probability ensembles are
statistically close then they are
computationally indistinguishable.
6
Poly-time Constructible
13.4
Def: An ensemble {Zn}nN is probabilistic polynomialtime constructible if there exists a probabilistic
polynomial-time algorithm S such that for every n,
S(1n) = Zn
ACT
7
Independent Samples
Thm: Let {Xn} and {Yn} be computational
indistinguishable and probabilistic polynomialtime constructible.
Let t(.) be a positive polynomial.
Define {Xn’} and {Yn’} as follows:
Xn’ = Xn1  Xn2 …  Xnt(n)
Yn’ = Yn1  Yn2 …  Ynt(n)
ACT
where the Xni’s (Yni’s) are independent copies
of Xn (Yn).
Then {Xn’} and {Yn’} are computationally
indistinguishable
8
Hybrid Distribution
Proof:
Assume a distinguisher D for {Xn’} and {Yn’} s.t.
Prx~X'n Dx   1  Pry~Y'n Dy   1  p1n 
for a polynomial p(.) and all sufficiently large n’s.
Define the hybrid distributions for 0it(n):
Hn(i)=(Xn(1) Xn(2)…Xn(i) Yn(i+1)… Yn(t(n)))
Note that Hn(0)= Y’n and Hn(t(n))= X’n
Define an algorithm D’ as follows:
For  taken from Xn or Yn
D’()=D(Xn(1) Xn(2)…Xn(i-1)Yn(i+1)… Yn(t(n)))
where i is chosen uniformly in {1,2,…,t(n)}
ACT
9
Hybrid Argument

Therefore,
Prx~Xn D'x   1 

1
t n 

1
t n 
According to the definition of D’
‘i’ is chosen uniformly from {1..t(n)}
 t n  
1 
i1 
i1 
  1 
 Prx~Xn DXn  ...  Xn  x  Yn  ...  Yn
t n 
i1
t n 
 Prx'~Hni  Dx'  1
i1
and
Pry~Yn D'y   1 
ACT

1
t n 

1
t n 
According to the
definition of Hn(i)
 t n  
1 
i1 
i1 
  1 
 Pry~Yn DXn  ...  Xn  y  Yn  ...  Yn
t n 
i1
t n 
 Pry'~Hni1  Dy'  1
i1
Note: only up to i-1 we
have X’s so we get Hn(i-1)
10
Hybrid Argument

It’s a telescopic sum
Thus,




Pr D'x~Xn x   1  Pr D'y~Yn y   1 
ACT
t n 
t n 
i1
i1
 Prx'~Hni  Dx'  1   Pry'~Hni1  Dy'  1 

1
t n 

1
t n 
Prx'~H t n   Dx'  1  Pry'~H 0  Dy'  1 

1
t n 
Pr Dx'~X'n x'  1  Pry'~Y'n Dy'  1 

n

n
1
t n p n 
11
Application of PRG
13.5
Let A be a probabilistic algorithm, and (n)
denote a polynomial upper bound on its
randomness complexity.
Let A(x,r) denote the output of A on input x
and coin tosses sequence r{0,1}(n).
Let G be a pseudorandom generator with
stretching function l:NN
Then AG is a randomized algorithm that, on
input x
ACT
• Sets k=k(|x|) to be the smallest integer s.t.
l(k) (|x|)
• Uniformly selects s{0,1}k
• Outputs A(x,r), where r is the (|x|)-bit long
prefix of G(s)
12
Application of PRG (2)
Thm: Let A and G be as above. Then for every pair of
probabilistic polynomial-time algorithms, a finder F and a
distinguisher D, every positive polynomial p(.) and all
sufficiently large n’s
n
 n PrF1   x  A,D x   p1n 
x0,1
where
A,D x   Prr~U n  Dx, Ax, r  1  Prs~Uk n  Dx, AG x, s   1
and the probabilities are taken over the Um’s as well as
over the coin tosses of F and D.
ACT
13
Amplifying the Stretch Function (2)
n
Output Sequence
G
n
1
G
n
1
G
n
ACT
1
14
Amplifying the Stretch Function
13.6
Thm: Let G be a pseudorandom generator with
stretch function l(n)=n+1, and l’ be any
polynomially bounded stretch function,
which is polynomial-time computable.
Let G1(x) denote the |x|-bit long prefix of
G(x), and G2(x) denote the last bit of G(x).
Then
G’(s)=12…l’(|s|)
where x0=s, i=G2(xi-1) and xi=G1(xi-1), is a
pseudorandom generator with stretch
function l’.
ACT
The theorem is proven using the hybrid
technique.
15
One-Way Functions
13.7
Def: A one-way function, f, is a polynomial-time
computable function s.t. for every probabilistic
polynomial-time algorithm A’, every positive polynomial
p(.), and all sufficiently large n’s
Prx~Un A'fx   f1 fx   p1n 
where Un is the uniform distribution over {0,1}n.
Popular candidates for one-way functions are based on
the conjectured intractability of:
 Integer factorization
 Discrete logarithm problem
 Decoding of random linear code
ACT
16
Hard-Core Predicate
13.8
Def (hard-core predicate): A polynomial-time
computable predicate b:{0,1}*{0,1} is called a
hard-core of a function f if for every
probabilistic polynomial-time algorithm A’,
every positive polynomial p(.), and all
sufficiently large n’s
Prx~U A'fx   bx   21  p1n 
n
Thm (generic hard-core): Let f be an arbitrary
one-way function, and let g be defined by
g(x,r)=(f(x),r), where |x|=|r|. Let b(x,r) denote
the inner-product mod 2 of the binary vectors
x and r. Then b is a hard-core of g.
ACT
17
Hard-Core Predicate (2)
Thm: Let b be a hard-core predicate of a polynomialtime computable 1-1 function f. Then, G(s)=f(s)b(s) is
a pseudorandom generator.
Proof Sketch: Clearly the |s|-bit long prefix of G(s) is
uniformly distributed (since f is 1-1 and onto {0,1}|s|).
Hence, we only have to show that distinguishing
f(s)b(s) from f(s), where  is a random bit,
contradicts the hypothesis that b is a hard-core of f.
Intuitively, such a distinguisher also distinguishes
f(s)b(s) from f(s)b(s) , and so yields an algorithm for
predicting b(s) based on f(s).
ACT
18
The Existence of PRG
13.9
Thm: Pseudorandom generators exist iff one-way
functions exist.
Proof:
1)
Let G be a pseudorandom generator with stretch
function l(n)=2n. For x,y{0,1}n, define f(x,y)=G(x),
and so f is polynomial-time computable. Suppose, by
way of contradiction, that f is not one-way. Then
there exists an algorithm A’ such that
PrxU2n A'fx   f1 fx   p1n  for some polynomial
p(.). We define the following polynomial-time
algorithm D: For an input z{0,1}2n,
ACT
19
The existence of PRG (2)
 1 if fA'z   z
Dz   
0 otherwise
So we have PrxUn DGx   1  p1n  ,
n
2
while PrzU2n Dz   1  PrzU2n z  Imf  22n  2n .
Therefore, D distinguishes G(Un) from U2n, with
contradiction to the hypothesis that G is a
pseudorandom generator.
2)
ACT
Proof outline: Suppose f is a one-way function. f
is not necessarily 1-1, so the construction
G(s)=f(s)b(s) where b is a hard-core of f cannot
be used directly.
20
The Existence of PRG (3)
One idea is to hash f(Un) to an almost uniform string of
length related to its entropy, using universal hash
functions. But this means shrinking the length of the
output to some n’<n.
Thus, we can add n-n’+1 bits by extracting them from the
seed Un, by hashing Un. The adding of this hash value
does not make the inverting task any easier.
f
hash
function
n-bit seed
n bits
hash
function
ACT
n bits
21