Transcript Randomized_Iterate.pps

On the Power of the
Randomized Iterate
Iftach Haitner, Danny Harnik, Omer Reingold
1
Pseudorandom generators.
 Hardness amplification.

The Randomized Iterate [GKL88]
2
Pseudorandom Generators (PRG)
[BM82, Yao82]
Eff. computable function G:{0,1}n ! {0,1}n’
x


G(x)
Increases Length (n’ > n)
Output is computationally indistinguishable from
random.
G(Un) wC Un’

Central in cryptography, implies bit-commitment [Naor91],
pseudorandom functions [GGM86], pseudorandom
permutations [LR88] and …
3
PRG Based on General Hardness
Assumptions
One-way permutations [BM82,Yao82]. O(n)
O(n3)
 Regular one-way functions [GKL88].
n!{0,1}n is a one-way function (OWF) if
Def:
f:{0,1}
n
n is function

Any !{0,1}
one-way
[HILL89].
f:{0,1}
regular if all
images have the O(n8)

Efficiently
computable
same
preimage
size
-1(f(x))
n it holds
-1(f(x))|

for
any
x2{0,1}
that
|f
=

.
2.
Hard
to
invert:
hard
to
find
an
inverse
f
n
Input Blowup: The input length of the resulting
for a
random
f(x). to the underlying OWF.
PRG
grows
compared
1.
If n is efficiently-computable then f is known regular.
• Central
to the security of the construction.
n, then it is
If f is•also
a
permutation
on
{0,1}
denote the input length of the OWF by n
a one-way permutation (OWP).
4
Example: We trust a OWF to be secure only
for 100 bit inputs.
 [BMY] is insecure for seed < 100 bits.
 [GKL] is insecure seed < 1,000,000 bits.
 [HILL] is insecure for seed < 1016 bits!
Goal: Reduce input length blowup.

[Holens06] One-way function with
5)
O(n
exponential hardness (2-Cn for some C>0)
5
Our Results
Pseudorandom generators from:
 Regular one-way functions O(n log n)
 Any one-way function O(n7)
 One-way function with exponential
hardness O(n2)
6
Hardness amplification
Def: -weak one-way functions - No PPT can invert with
probability better than 1-.
Goal: Strong OWF from weak OWF.
 General one-way functions [Yao82] O(n2/).
 One-way permutations [GILVZ90] O(n).
 Known regular one-way functions [GILVZ90] between
O(n) to O(n2) (depends on the hardness of the function).
 Regular one-way functions [DI99] O(n) in the public
randomness model.

Our Result:
From weak (unknown) regular OWF O(n log n).
7
The Plan of the Talk
Present our construction of PRG from
regular one-way functions.
 Give some highlights on the other two
results:

 More
efficient PRG for any one-way function.
 Efficient hardness amplification for regular
one-way functions.
8
PRG from Regular OWF.
Motivation - The BMY generator.
 The Randomized Iterate.
 PRG with seed length O(n2).
 Derandomize the construction to get a
PRG with seed length O(n log n).

9
The BMY PRG
OWP f:{0,1}n!{0,1}n
x
G(x) = b(x)
f
f(x)
b(f1(x))
f
f2(x)
b(f2(x))
…
f
…
fn(x)
f
fn+1(x)
b(fn(x))
Claim:Hardcore-predicate
G is a PRG. of f: given f(x) it
is hard to predict b(x).
10
given z = fk(x) it is hard to
find y such that f(y) = z
One-Way on Iterates:
[Levin]: If 8k it is hard to invert fk
Then
b(x),b(f(x)),…,b(fm(x)) is pseudorandom.
11
Applying BMY to any OWF
When f is any OWF, inverting fi might be easy
(even when f is regular). Example:
f
f
Easy inputs
12
The Randomized Iterate
Idea: use “randomization steps” between the
iterations of f to prevent the convergence of the
outputs into easy instances.
The Randomized Iterate [GKL]:
x
f
0(x)
f0f(x,h)
h1
f
f1(x,h)
h2
f
f2(x,h)
h3
f
…
h = (h1,...,hn)
h1,...,hn 2H - a family of k-wise independent hash functions
n ! {0,1}n s.t. 8x ,..., x and a random h2H
from
{0,1}
k ,...,h
G(x,h) = b(f0(x,h)),...,b(f1n(x,h)),h
(h(x1),h(x2),...,h(xk)) is uniform over 1{0,1}nkn.
 The description of hi is of length O(nk).
13
[GKL] prove it for n-wise independent hash
functions. (O(n3) bits to describe h1,...,hn)
 We simplify the proof.
 Apply the proof to pairwise independent
hash functions, thus we need only O(n2) bits
to describe h1,...,hn.
 Derandomized the selection of h1,...,hn using
only O(n log n) bits.

14
Lemma 1: (Last randomized iteration is hard to invert) Let f
be a regular OWF and H be family of pairwise independent
hash functions, then no PPT can invert fk given h1,...,hk.
Corollary: Let f be a regular OWF and H be family of
pairwise independent hash functions, then
G(x,h) = b(f0(x,h)),b(f1(x,h)),…,b(fn(x,h)),h
is a PRG with seed length O(n2).
15
Proof of Lemma 1
f1(x,h)
h
Pr[f(h(y))= f1(x,h)] > 
( = 1/poly)
Contradition!
A
A’ inverts f itself!y
Pr[f(h’(y))= f1(x,h)] > ’
(’ = 2/2)
A'
f1(x,h)
h’ÃH
A
y
16
Claim: A inverts (f1(x,h),h)  A inverts (f1(x,h),h’) 
A’ inverts f1(x,h).
 (f1(Un,H),H) ¼ (f1(Un,H),H’)

CP(f1(Un,H),H) ¼ CP(f1(Un,H),H’)
CP(f1(Un,H),H) · 2¢CP(f1(Un,H),H’)
H and H’ are uniform distributions
Def: The collision-probability of a distribution
D, is the
over H
1(U ,H),H)
probability
choosing
the same
twice while
 Lemma
2: of
If CP(f
< nC.element
CP(f1(Un,H),H’)
then:
n
1(U ,H),H)
drawing
two random
elements
from
T
is noticeable
w.r.t. (f
 D.
n
T is noticeable w.r.t. (f1(Un,H),H’)
f
Im(f)£H
T
h
f
T = {(z,h) | A inverts (z,h)}
This is the only place we use the
regularity of f!
17
CP(f1(Un,H),H) · 2¢ CP(f1(Un,H),H’)
CP(f1(Un,H),H) ·
= 2¢CP(f(Un)/|H|.
1/|H| (CP(f(Un) + CP(f(Un))
 CP(f1(Un,H),H’) = CP(f(Un)/|H|.

f
fºh
18
D = (f1(Un,H),H)
Proving Lemma 2
S = Im(f)H
Claim: Let D be a distribution over a set S
s.t. CP(D) < nC.CP(US). For every TµS
if PrxÃD[T] ¸  then PrxÃUs[T] ¸ 2n-C.
Proof: CP(D) ¸ 2 ¢ 1/|T|
|T| ¸ 2/ CP(D)
inside T, the
2/(n
C.CP(Uof )) = 2n-COnce
probability
|T| ¸ the
|S|
S
probability of hitting the
hitting T twice
PrxÃUs[T] ¸ 2n-C.
same element twice
19


Lemma 1: Let f be a regular OWF and H be
family of pairwise independent hash functions, then
no PPT can invert fk given h1,...,hk.
Corollary: Let f be a regular OWF and H be
family of pairwise independent hash functions, then
G(x,h) = b(f0(x,h)),b(f1(x,h)),…,b(fn(x,h)),h
is a PRG with seed length O(n2).
20
Derandomizing the PRG
fk(Un,Hk) = f(Un).
 CP(fk(Un,Hk),Hk) = .
Both properties can be “verified” by an algorithm
(branching-program) that uses O(n) space.

Can choose h1,...,hk using a generator that fools
Collision
verifier. adversaries
bounded-space
input
tape: h1,...,hk. with space bound 2n and error 2-n.
 [Nisan92],[INW94]
 Choose
two random
x1,x22{0,1}
The
seed length
on the elements
new generator
is O(nn. log n).

 Could
Returnbe
“1”O(n)
iff fkgiven
(x1,h1better
,...,hk) bounded-space
= fk(x2,h1,...,hk)
generators.
21
The Plan of the Talk
Present our construction of PRG from
regular one-way functions.
 Give some highlights on the other two
results:

 More
efficient PRG for any one-way
function.
 Efficient hardness amplification for regular
one-way functions.
22
PRG from Any OWF
Can we apply the randomized iterate to any
OWF?
 No,
security deteriorates with every iteration.
 However:
Lemma: It is hard to invert fi over a set of
density at least 1/i.
 Does not seem enough for an efficient PRG
from any OWF.
 2Cn-hard OWF implies PRG with seed O(n2).
23
Pseudo-Entropy Pair (PEP)
Def: A pair of a function and a predicate (g,b) is a
(,)-PEP if
1. H(b(Un) | g(Un)) · .
b has entropy 
2. b is a ( + )-hard predicate of g.
b has pseudoentropy  + 
[HILL]
It is hard to predict b(Un) given
g(Un
) with
probabilitywhere
better than
1. OWF
(,1/n)-PEP,
is unknown.
– PRG,
( + )/2
2. (,1/n)-PEP1
where  is known.
24
Dealing with Unknown 



8i 2 [n], “guess” that  = i/n and construct Gi.
G(x1,...,xn) = G1(x1)© G2(x2) © ... © Gn(xn).
First apply standard length extending method [GGM] to
each of the Gi, so that its output length is n2+1.
This increases the seed length by a factor of O(n)
3).
and increases
the
complexity
by
a
factor
of
O(n
G
G
...
25
Using the randomized iterate to
construct a (1/2,1/n)-PEP
f1 = f(h(f0(x,h))) = f(h(f(x)))
x
f
f0
f ºh
f1
Let b’(x,h) = b(f0(x,h)) and let g(x,h) = f1(x,h),h
Lemma: (g,b’) is a (1/2,1/n)-PEP.
The Goldreich-Levin
predicate
26
f1 = f(h(f0)) = f(h(f(x)))
Lemma:
1. If Df(f0) ¸ Df(f1) then f0 is w.h.p. Information
theoretically determined by (f1,h). *
2. Df(f0) · Df(f1) implies that it is hard to compute f0
-1(y))|e.
1,h).
Df(y) (f
= dlog|(f
given
Claim:
Pr[Df(f0) · Df(f1)] = Pr[Df(f0) ¸ Df(f1)] ¸ ½ +1/n.
“Proof”: Df(f0) and Df(f1) are two i.i.d. over [n].
Therefore,

H(b(f(x)) | (f1(x,h),h)) · ½.

b’ is a (½ +1/n)-hard predicate of g.
27
The Plan of the Talk
Present our construction of PRG from
regular one-way functions.
 Give some highlights on the other two
results:

 More
efficient PRG for any one-way function.
 Efficient hardness amplification for regular
one-way functions.
29
From weak regular to OWF
Def: an -weak one-way function f - No PPT
can invert with probability better than 1-.
Claim: Any PPT A and polynomial p has a
failing-set SAµIm(f) of weight /2,
 PryÃf(Un)
[A(y)2f-1(y) | y2SA]· 1/p.
30
Hitting every Failing-Set
x1
ffºfh1
fºfhf’(x
ffºhm), f(x )...,f(x )
2
,x
,...,x
)
=
f(x
1 2
m
1
2
m
A inverts f’ ! M inverts f
fm(x,h1,...,hm),h1,...,hm
x2
On input y2 Im(f):
 Might be possible to find a different pre-image.
8i2[m]
 From our proof for
regular OWF, inverting
(x1,...,x
à A(f(U
fm(x,h1,...,hm) is hard
even
given
h1,...,hmn))
.
m) when
n),...,y,...,f(U
if(f(x
i) ==isy)too long.
 The description of h
,...,h
1
m

xm
retrun x
i
Use derandomization to get O(n log
n)
m = O(n/)
31
Further issues



Linear (O(n)) constructions for the regular OWF
PRG and weak-OWF amplification.
*through better bounded-space generator?
BMY-like PRG for any (for any hardness) OWF?
Efficient hardness amplification for any weak
OWF.
32