Cryptography Reference
In-Depth Information
satisfies
1
2
Below, we provide a more efficient implementation of A . Combining it with a more
refined averaging argument than the one used in Claim 2.5.2.1, we obtain the following:
[ A ( f ( U n )) = U n ] ε G ( n )
Pr
2 ·
Proposition 2.5.4: Let G, t G :
N→N
, and
ε G :
N →
[0
,
1] be as before, and de-
( n ) def
G ( n )) . Then there exists an algorithm A that runs in expected
fine
=
log 2 (1
time O ( n 2
( n ) 3 )
·
·
t G ( n ) and satisfies
Pr
[ A ( f ( U n )) = U n ] = ( ε G ( n ) 2 )
Thus, the time-versus-success ratio of A is poly( n )
G ( n ) 2 , which (in some sense) is
optimal up to a poly( n ) factor; see Exercise 30.
( n ) def
def
=
E
Proof Sketch: Let
ε
= ε G ( n ), and
log 2 (1
( n )). Recall that
[ s ( X n )]
=
0 . 5 + ε ( n ), where s ( x ) def
[ G ( f ( x ) , R n ) = b ( x , R n )] (as in Claim 2.5.2.1). We
first replace Claim 2.5.2.1 by a more refined analysis.
= Pr
n of cardinality
Claim 2.5.4.1: There exists an i ∈{ 1 ,..., } and a set S n ⊆{ 0 , 1 }
at least (2 i 1
· ε ( n )) · 2 n
such that for every x S n , it holds that
1
2 +
1
2 i + 1
= Pr
s ( x )
[ G ( f ( x )
,
R n )
=
b ( x
,
R n )]
·
def
={ x : s ( x )
1
1
2 i + 1
n ,we
Proof: Let A i
2 +
} . For any non-empty set S ⊆{ 0 , 1 }
let a ( S ) def
) def
=
max x S { s ( x )
.
}
=
0
5
, and a (
0. Assuming, to the contrary, that the
| A i | <
(2 i 1
· ε
·
2 n
for i =
,...,
claim does not hold (i.e.,
( n ))
1
), we get
E
[ s ( X n )
0
.
5]
Pr
[ X n
A 1 ]
·
a ( A 1 )
2 Pr
+
[ X n ( A i \ A i 1 )] · a ( A i \ A i 1 )
i =
n
n
+ Pr
[ X n
(
{
0
,
1
}
\
A )]
·
a (
{
0
,
1
}
\
A )
1
2 +
1
2 i
1
2 + 1
(2 i 1
( n ) ·
· ε ( n )) ·
+ 1 ·
i = 2
= ε
( n )
2 + ( 1) · ε
( n )
2
2
2
+
= ε ( n )
E
which contradicts
[ s ( X n ) 0 . 5] = ε ( n ).
def
=
Fixing any i that satisfies Claim 2.5.4.1, we let
ε
2 i 1
/
and consider the
def
={ x : s ( x )
corresponding set S n
0
.
5
+ ε }
. By suitable setting of parameters,
we obtain that for every x
S n , algorithm A runs in time O ( n 3
4 )
·
t G ( n ) and
1
retrieves x from f ( x ) with probability at least
2 . Our next goal is to provide a
Search WWH ::




Custom Search