Cryptography Reference
In-Depth Information
Exercise 25:
Ahard-corepredicatefora1-1functionimpliesthatthefunctionisone-
way: Let f be a 1-1 function (you may assume for simplicity that it is length-preserving),
and suppose that bis a hard-core for f.
1.
Prove that if f is polynomial-time-computable, then it is strongly one-way.
2.
Prove that (regardless of whether or not f is polynomial-time-computable) the func-
tion f must be at least “weakly hard to invert”; that is, for some positive polynomial p,
every probabilistic polynomial-time algorithm Amust satisfy Pr[ A( f(U
n
))
p(n)
for all sufficiently large n's. Furthermore, prove that for every positive polynomial p,every
probabilistic polynomial-time algorithm A must satisfy Pr[ A( f(U
n
))
=
U
n
]
>
1
/
U
n
]
<
1
2
1
p(n)
for
=
+
all sufficiently large n's.
Guideline:
Use the inverting algorithm for predicting the hard-core. Distinguish the case
in which you can check that the inverting algorithm is correct (i.e., in Item 1) from the case
in which you cannot do so (i.e., in Item 2).
Exercise 26:
An unbiased hard-core predicate (suggested by Erez Petrank):
Assuming the existence of one-way functions, prove the existence of hard-core
predicates (for such functions) that are unbiased (i.e., the predicate b satisfies
Pr[b(U
n
)
=
1]
=
1
2
).
Guideline:
Slightly modify the predicate defined in Theorem 2.5.2 (i.e., you need to modify
it only on all-zero x). Alternatively, convert any hard-core bfor a function f into b
(x,
σ
)
=
σ ⊕
b(x)for f
(x,
σ
)
=
(f(x),
σ
).
Exercise 27:
Universalhard-corepredicate: A polynomial-time-computable predicate
b:
}
∗
→{
is called a universal hard-core predicate if for every one-way
function f, the predicate b is a hard-core of f. Note that the predicate presented in
Theorem 2.5.2 is “almost universal” (i.e., for every one-way function f, that predicate is
a hard-core of f
(x, r)
{
0, 1
0, 1
}
(f(x), r), where
|
x
|
=
|
r
|
). Prove that there exists no universal
=
hard-core predicate.
Guideline:
Let bbe a candidate universal hard-core predicate, and let f be an arbitrary
one-way function. Then define the (one-way) function f
(x)
=
( f(x), b(x)).
Exercise 28:
Theorem 2.5.2, an alternative perspective (suggested by Russell
Impagliazzo, Madhu Sudan, and Luca Trevisan): The hard-core predicate of
Theorem 2.5.2 can be viewed as b(x, i) equaling the ith bit in the Hadamard code
of x, where the Hadamard code is the most redundant (non-repeating) linear code
(i.e., a string x
∈{
0, 1
}
n
is mapped to the values obtained from all possible 2
n
lin-
ear combinations of its bits). Let H(x) denote the codeword associated with x by the
Hadamard code. The argument presented in the proof of Theorem 2.5.2 actually pro-
vides a “list-decoding” algorithm for the Hadamard code. Specifically, given oracle ac-
cess to the bits of a string y
2
n
∈{
0, 1
}
and a parameter
ε>
0, we recover, within
n
such that H(x) and ydiffer on at most (
2
− ε
2
n
poly(
n
/ε
) time, all strings x
∈{
0, 1
}
)
·
locations.
1.
Verify the foregoing claim, that is, that a “list-decoding” algorithm (for the Hadamard code)
with the stated features is implicit in the proof of Theorem 2.5.2.
2.
Let C be an error-correcting code mapping n-bit strings to
(n)-bit strings. What require-
ments should C satisfy so that b(x, i), defined as the ith bit in C(x), would constitute a
hard-core predicate of f
(x, i)
=
( f(x), i) for every one-way function f.
