Cryptography Reference
In-Depth Information
← Z
n
, computing
x
2
mod
n
∈
QR
n
, and calling the
choosing random elements
x
x
2
mod
n
.
∈
QR
n
such that
BW
n
(
)
=
PPT algorithm that inverts
BW
n
to obtain
y
y
This procedure is repeated until finding
x
,
y
such that
x
≡±
y
(
mod
n
)
(or pick,
such that
n
=−
← Z
n
in polynomial time, a random element
x
1 and compute
x
2
mod
n
, which, since
n
=−
1,
n
=
y
∈
QR
n
such that
BW
n
(
y
)
=
1, and
−
n
=
1, satisfies
x
≡±
y
(
mod
n
)
). Then gcd
(
x
−
y
,
n
)
is a nontrivial factor of
n
.
Remarks 8.11
The same factoring algorithm used to prove the preceding proposition
serves to prove that the Rabin functions are one-way under the factoring assumption
and hence that, under this hypothesis, the variant of Rabin encryption with plaintexts
in
Z
n
is OW-CPA secure. If we compare it with plain RSA, we notice that plain Rabin
encryption has the advantage that its OW-CPA security depends on the hardness of
factoring (to which it is, in fact, equivalent) instead of the hardness of the RSA
problem. However, as far as security is concerned, we cannot go much further with
this simple encryption scheme because, as happens with plain RSA, encryption is
deterministic and hence the scheme is not IND-CPA secure. On the other hand, if we
consider a variant inwhich redundancy is added to themessages in
Z
n
in order tomake
the probability that two distinct plaintexts have the same square in
Z
n
—and hence
produce the same ciphertext—negligible, then the hardness of factoring no longer
implies that recovering the plaintext is hard, because if we take, as before, a random
x
∈ Z
n
, the probability that the algorithm breaking the OW-CPA security finds an
element
y
∈ Z
n
(whichwould have to be a valid plaintext) such that
x
2
y
2
≡
(
mod
n
)
but
x
would be negligible.
Since plain Rabin encryption is not CPA secure, it cannot be CCA secure either
but, actually, the situation is even worse in this respect in comparison with plain
RSA. Indeed, we have seen that plain RSA is vulnerable to a CCA attack that can
recover the entire plaintext but no CCA attack against RSA is known that is capable
of recovering the private key (in the absence of specific weaknesses such as a small
decryption exponent, etc.). In contrast, the very feature that makes inverting the
Blum-Williams function as hard as factoring, gives rise to a CCA attack against
plain Rabin encryption that is able to recover the private key and hence all the
messages subsequently encrypted with this key. This attack proceeds as the factoring
algorithm outlined in the proof of Proposition 8.6 except that, instead of calling a
PPT algorithm that inverts the Blum-Williams function (which now is not assumed
to exist), it queries the decryption oracle to obtain the square root
y
≡±
y
(
mod
n
)
∈
QR
n
of
∈ Z
n
such that
n
=−
x
2
mod
n
,for
x
1, and computes gcd
(
x
−
y
,
n
)
which gives
Z
n
a nontrivial (prime) factor of
n
. Similarly, if the Rabin function on
is being used
for encryption, a square root of
x
2
mod
n
∈ Z
n
which is distinct from
±
x
mod
n
will
1
be found with probability at least 1
2
t
after
t
trials giving, as before, a nontrivial
factor of
n
. Of course, this attack does not work if the message space is a sparse subset
of
−
Z
n
for the same reason that we cannot prove the equivalence between breaking
the scheme and factoring the modulus in that case.
