Cryptography Reference
In-Depth Information
8.4 Rabin Encryption
We have seen that several variants of RSA enjoy security properties under the RSA
assumption, i.e., under the hypothesis that the RSA problem is hard. However, the
RSA problem is not as well understood as the integer factorization problem, which
is presumed hard after having been studied for a longer time in different contexts not
necessarily related to cryptography. Moreover, while the hardness of the factorization
problem is a necessary condition for the hardness of the RSA problem, the converse
is still unproven, so basing the security of RSA encryption schemes on the presumed
hardness of factoring relies on two conjectures: that factoring is hard and that the RSA
problem is as hard as factoring. Because of this, an interesting question is whether the
second of these hypothesis may be withdrawn, i.e., whether we can obtain a public-
key encryption scheme whose security relies only on the hardness of factoring. The
answer is affirmative and such a scheme was first described by M. Rabin in 1979.
The Rabin encryption scheme is based on the family of Rabin functions
R
n
, with
R
n
(
x
2
mod
n
for
x
∈ Z
n
and
n
pq
a product of two distinct primes or, in
a variant due to Williams, on the family of Blum-Williams permutations that were
shown to be one-way (assuming that factoring is hard) in Theorem 3.8.
x
)
=
=
8.4.1 Plain Rabin Encryption
=
Recall that, if
n
is a Blum integer, i.e.,
n
pq
where
p
and
q
are distinct odd primes
which are
≡
3
(
mod 4
)
(Blum primes), then the Blum-Williams function:
BW
n
−→
QR
n
QR
n
x
2
mod
n
x
−→
is a permutation, and the family
is a family of one-way permutations under
the factoring assumption (the PPT algorithm that outputs the modulus
n
is similar to
the RSA key generation algorithm with the restriction that the prime factors of
n
are
Blum primes). We can see that this family is, furthermore, trapdoor one-way if we
set as trapdoor for
n
,
t
{
BW
n
}
. Indeed, as we have seen in Algorithm 2.8 and
the subsequent discussion, computing square roots modulo a prime is easy and, as a
consequence, computing modular square roots modulo
n
(
n
)
=
(
p
,
q
)
pq
, where
p
and
q
are
primes, is also easy when the factorization of
n
is known. We next give an explicit
description of the algorithm that computes the inverse function
BW
−
1
n
=
:
QR
n
→
QR
n
when
n
pq
is a Blum integer. This algorithm consists of first applying
Algorithm 2.8 to compute the square roots of
c
=
∈
QR
n
modulo the primes
p
and
q
,
which is done with just a modular exponentiation in each case (by Proposition 2.15,
the square roots of
c
modulo
p
are
c
(
p
+
1
)/
4
mod
p
), and then
using the Chinese remainder theorem to recover the four square roots of
c
modulo
n
. Once these square roots have been found, we know from Proposition 2.14 that the
±
m
p
, where
m
p
=
