Cryptography Reference
In-Depth Information
polynomial p ( · ), and all suciently large n 's
Pr A ( f ( x ))= b ( x ) < 1
2 + 1
p ( n )
where the probability is taken uniformly over all the possible choices
of x
n and all the possible outcomes of the internal coin tosses
of algorithm A .
∈{
0 , 1
}
} ,
there exist obvious algorithms that guess b ( x )from f ( x )withsuccess
probability at least one half (e.g., the algorithm that, obliviously of its
input, outputs a uniformly chosen bit). Also, if b is a hard-core predicate
(for any function) then it follows that b is almost unbiased (i.e., for a
uniformly chosen x , the difference | Pr[ b ( x )=0] Pr[ b ( x )=1] | must be
a negligible function in n ). Finally, if b is a hard-core of a 1-1 function
f that is polynomial-time computable then f is a one-way function.
} →{
} →{
Note that for every b :
{
0 , 1
0 , 1
}
and f :
{
0 , 1
0 , 1
Theorem 2.5. ((72), see simpler proof in (65, Sec. 2.5.2)): For any
one-way function f , the inner-product mod 2 of x and r is a hard-core
of f ( x, r )=( f ( x ) ,r ).
The proof is by a so-called “reducibility argument” (which is used to
prove all conditional results in the area). Specifically, we reduce the task
of inverting f to the task of predicting the hard-core of f , while mak-
ing sure that the reduction (when applied to input distributed as in the
inverting task) generates a distribution as in the definition of the pre-
dicting task. Thus, a contradiction to the claim that b is a hard-core of f
yields a contradiction to the hypothesis that f is hard to invert. We stress
that this argument is far more complex than analyzing the correspond-
ing “probabilistic” situation (i.e., the distribution of the inner-product
mod 2 of X and r , conditioned on a uniformly selected r
n ,where
X is a random variable with super-logarithmic min-entropy, which rep-
resents the “effective” knowledge of x ,whengiven f ( x )). 3
∈{
0 , 1
}
3 The min-entropy of X is defined as min v { log 2 (1 / Pr[ X = v ]) } ;thatis,if X has min-entropy
m then max v {
=2 −m . The Leftover Hashing Lemma (120; 27; 87) implies that,
in this case, Pr[ b ( X, U n )=1
Pr[ X = v ]
}
|U n ]= 2 ±
2 Ω( m ) ,where U n denotes the uniform distribution
n ,and b ( u, v ) denotes the inner-product mod 2 of u and v .
over
{
0 , 1
}           Search WWH ::

Custom Search