Cryptography Reference
In-Depth Information
Using this experiment we may define the hardness of computing square roots:
Definition 3.17
We say that
computing square roots modulo a product of two ran-
dom k-bit primes is hard
if, for every PPT algorithm
A
, there exists a negligible
function
negl
such that
Pr
(
Sqr
A
(
k
)
=
1
)
≤
negl
(
k
).
We next show that computing square roots modulo
n
, where
n
is a product of two
random
k
-bit primes, is as hard as factoring
n
:
Theorem 3.7
Under the factoring assumption, computing square roots modulo a
product of two random k-bit primes is hard.
A
Proof
Let
be a PPT algorithm that tries to compute a square root modulo
n
.To
show that Pr
(
Sqr
A
(
k
)
=
1
)
is negligible as a function of
k
, we consider the following
algorithm
A
f
that tries to factor a modulus
n
by using
A
as a subroutine:
A
f
:
1. Choose a random
x
Algorithm
← Z
n
and compute
u
x
2
mod
n
.
=
2. Run
A
on input
(
n
,
u
)
to obtain as output
y
:=
A(
n
,
u
)
.
3. Check whether
x
≡±
y
(
mod
n
)
. If this is not the case then output gcd
(
x
−
y
,
n
)
;
otherwise go to step 1.
Observe that
A
f
runs correctly if
y
is a square root of
u
modulo
n
.Thisis
because then
x
2
y
2
(mod
n
) and so
≡
(
x
+
y
)(
x
−
y
)
≡
0(mod
n
) or, equivalently,
n
|
(
x
+
y
)(
x
−
y
)
.But
x
≡±
y
(mod
n
)impliesthat
n
does not divide either of these
factors and hence gcd
must be a nontrivial factor of
n
. Moreover, since
x
was randomly chosen,
x
is equally likely to be each of the four square roots of
u
from the point of view of
(
x
−
y
,
n
)
A
(there are indeed four square roots by Corollary 2.7).
Therefore,
x
is uniformly distributed among the square roots of
u
and, assuming that
the output
y
of
A
is one of them, the probability that
x
≡±
y
(mod
n
)is1
/
2. Thus
we have that the probability that
A
f
factors
n
is just one-half the probability that
A
outputs a square root of
u
, that is:
1
2
Pr
Pr
(
Fact
A
f
(
k
)
=
1
)
=
(
Sqr
A
(
k
)
=
1
).
Hence we obtain:
Pr
(
Sqr
A
(
k
)
=
1
)
=
2Pr
(
Fact
A
f
(
k
)
=
1
)
≤
2
negl
(
k
),
where
negl
is the negligible function from the factoring assumption, completing
the proof.
Remark 3.8
The converse of the preceding theorem is also true, i.e., if computing
square roots modulo a product of two equal-length random primes is hard then
