Cryptography Reference
In-Depth Information
As a warm-up, prove that f
XOR
(xy)
, is not one-way.
Guideline (Part 2):
Do not try to capitalize on the possibility that prime(N) is too
large (e.g., larger than N
+
poly(log N)). It is unlikely that such a (number-theoretic)
result can be proved. Furthermore, it is generally believed that there exists a constant c
such that for all integer N
≥
2, it holds that prime(N)
<
N
+
(log
2
N)
c
. Hence, it is likely
that f
add
is polynomial-time-computable. The point is that it can be shown to be easily
invertible.
x
⊕
y, where
|
x
|
=
|
y
|
=
Exercise 8:
One-way functions based on hardness of factoring: Throughout this
exercise, assume that it is infeasible to factor composite numbers that are the products
of two primes of polynomially related lengths. That is, for every probabilistic polynomial-
time alg
o
rithm A, for every positive polynomial p, for all sufficiently large n's, and for
every
√
n
n
2
,
<
m
<
1
p(n)
Pr[ A(P
m
·
Q
n
)
P
m
]
<
=
where P
m
and Q
n
are uniformly and independently distributed primes of length mand
n, respectively. (Recall the density-of-primes theorem, which guarantees that at least a
1
nfraction of the n-bit integers are primes [7].)
1.
Let f
mult
(x, y)
/
.
(a)
(Easy) Prove that f
mult
is weakly one-way.
(b)
(Hard) Prove that f
mult
is strongly one-way.
Guideline:
Use the fact that, with overwhelmingly high probability, when uniformly se-
lecting an n-bit-lon
g
integer and considering the product of all its prime factors that
are smaller than 2
√
n
, this product is smaller than 2
n
/
3
. Next, argue that if f
mult
can be
inverted with non-negligible probability, then with non-negligible probability this hap-
pe
n
s when each of the two parts of the pre-image has a prime factor of size at least
2
√
n
. At this point, a reducibility argument can be applied. (The number-theoretic fact
used earlier can be proved by relying on known results regarding the distribution of
smooth numbers; see [47] for the latter.)
2.
Let f
mmult
(x
1
,...,x
n
2
)
=
n
2
x
·
y, where
|
x
|
=
|
y
|
=
1
, where
|
x
i
|
=
nfor all i's. Prove that f
mmult
is strongly one-
i
=
way.
Guideline:
Show how to use an algorithm that inverts f
mmult
with non-negligible probability
in order to factor the products of two n-bit primes. Remember the need to feed the former
algorithm with a distribution as in the hypothesis (or sufficiently close to it).
Exercise 9
(suggested by Bao Feng):
Refute the following conjecture:
For every (length-preserving) one-way function f, the function f
(x)
def
=
f(x)
⊕
x
is also one-way.
Guideline:
Let g be a (length-preserving) one-way function, and consider f defined on
pairs of strings of the same length, so that f(y, z)
def
=
(g(y)
⊕
z, z).
Exercise 10:
Prove that one-way functions cannot have polynomial-size ranges.
Namely, prove that if f is (even weakly) one-way, then for every polynomial p(
·
) and all
n
sufficiently large n's, it holds that
|{
f(x):x
∈{
0, 1
}
}| >
p(n).
