Cryptography Reference
In-Depth Information
Exercise 3:
One-way functions and the
P
-versus-
NP
question (Part 2): Assuming
that
, construct a function f such that the following three claims hold:
1.
Function f is polynomial-time-computable.
2.
There is no polynomial-time algorithm that always inverts f (i.e., successfully inverts f
on every yin the range of f).
3.
Function f is not one-way. Furthermore, there exists a polynomial-time algorithm that
inverts f with exponentially small failure probability, where the probability space is (as
usual) uniform over all possible choices of input (i.e., f(x)) and the internal coin tosses
for the algorithm.
Guideline:
Consider the function f
sat
defined so that f
sat
(
P
=
NP
φ
,
τ
)
(
φ
,1)if
τ
is a satisfying
=
assignment to propositional formulae
, 0) otherwise. Modify this
function so that it is easy to invert in most instances, yet inverting f
sat
is reducible to
inverting its modification. (Hint: The modified function f
coincides with f
sat
on a negligible
fraction of the domain of f
and is easy to invert on the rest of the domain.)
φ
, and f
sat
(
φ
,
τ
)
(
φ
=
Exercise 4:
Suppose that f is a one-way function and that for some function
: N
→
N
the following conditions hold:
1.
|
f(x)
|
=
(
|
x
|
) for all x's;
2.
(n)
=
(m) only if n
=
m(i.e.,
is 1-1);
3.
(n)
≥
nfor all n's.
Show that given f(x), one can generate 1
|
x
|
, in time polynomial in
|
x
|
.
Guideline:
The foregoing conditions guarantee that
|
x
|≤|
f(x)
|
and that
|
x
|
is uniquely
determined by
|
f(x)
|
=
|
f(1
|
x
|
)
|
.
Exercise 5:
Let f be a strongly one-way function. Prove that for every probabilistic
polynomial-time algorithm Aand for every positive polynomial p(
·
), the set
x :Pr
A(f(x))
f
−
1
(f(x))
1
p(
|
x
|
)
B
A, p
def
∈
≥
=
has negligible density in the set of all strings (i.e., for every polynomial q(
·
) and all
sufficiently large n, it holds that
|
B
A, p
∩{
0,1
}
n
|
1
<
q(n)
.
2
n
Exercise 6:
Anotherdefinitionofnon-uniformlyone-wayfunctions: Consider the defi-
nition resulting from Definition 2.2.6 by allowing the circuits to be probabilistic (i.e., have
an auxiliary input that is uniformly selected). Prove that the resulting new definition is
equivalent to the original one.
Exercise 7:
Additioniseasilyreversible:We associate bit strings with positive integers
in some natural manner (e.g., the n-bit-long string
σ
n
−
1
···σ
0
is associated with the
+
n
−
1
integer 2
n
2
i
):
1.
Define f
add
:
{
0, 1
}
∗
→{
0, 1
}
∗
such that f
add
(xy)
=
x
+
y, where
|
x
|
=
|
y
|
. Prove that
f
add
is not a one-way function (not even in the weak sense).
2.
Redefine f
add
:
{
0, 1
}
∗
→{
0, 1
}
∗
such that f
add
(xy)
=
prime(x)
+
prime(y), where
|
x
|
=
|
y
|
and prime(z) is the smallest prime that is larger than z. Prove that f
add
is not a one-way
function.
i
=
0
σ
i
·
