Cryptography Reference
In-Depth Information
breaking Rabin under passive atacks to be as hard as factoring. However, giving a precise
security proof involves taking care of the redundancy scheme.
Theorem 24.2.13
Let N
=
pq, where p
≡
q
≡
3(mod4)
are primes, and define S
N,l
=
1
,
2
l
∈ Z
N
−
{
1
≤
x<N
: gcd(
x,N
)
=
|
(
x
+
1)
}
. Assume the probability, over x
S
N,l
,
y
2
(mod
N
)
,is
1
/
2
l
−
1
. Then breaking the
one-way encryption security property of the Rabin cryptosystem with the “redundancy
in the message” redundancy scheme where l
y but x
2
that there exists y
∈
S
N,l
with x
=
≡
=
O
(log(log(
N
)))
under passive attacks is
equivalent to factoring Blum integers.
Theorem 24.2.14
Breaking the one-way encryption security property of the Rabin cryp-
tosystem with the “extra bits” redundancy scheme under passive attacks is equivalent to
factoring products N
=
pq of primes p
≡
q
≡
3(mod4)
.
Theorem 24.2.15
Breaking the one-way encryption security property of the Rabin cryp-
tosystem with the Williams redundancy scheme under passive attacks is equivalent to
factoring products N
=
pq of primes p
≡
q
≡
3(mod4)
, p
≡±
q
(mod 8)
.
Note that Theorem 24.2.13 gives a strong security guarantee when
l
is small, but in
that case decryption failures are frequent. Indeed, there is no choice of
l
for the Rabin
scheme with redundancy in the message that provides both a tight reduction to factoring
and negligible probability of decryption failure.
We prove the first and third of these theorems and leave Theorem
24.2.14
as an
exercise.
Proof
(Theorem
24.2.13
)Let
A
be an oracle that takes a Rabin public key
N
and a ciphertext
c
(with respect to the “redundancy in the message” padding scheme) and returns either the
corresponding message
m
or an invalid ciphertext symbol
⊥
.
∈ Z
N
such that neither
x
nor
N
Choose a random
x
−
x
satisfy the redundancy scheme
x
2
(i.e., the
l
least significant bits are not all 1). Set
c
=
(mod
N
) and call the oracle
A
on
⊥
c
. The oracle
A
answers with either a message
m
or
.
According to the (heuristic) assumption in the theorem, the probability that exactly one
of the two (unknown) square roots of
c
modulo
N
has the correct
l
least significant bits is
2
−
(
l
−
1)
. If this is the case then calling the oracle
A
on
c
will output a value
m
such that,
writing
x
=
2
l
m
(2
l
1), we have (
x
)
2
x
2
(mod
N
) and
x
≡±
+
−
≡
x
(mod
N
). Hence,
gcd(
x
−
x,N
) will split
N
.
We expect to require approximately 2
l
−
1
trials before factoring
N
with this method.
Hence, the reduction is polynomial-time if
l
=
O
(log(log(
N
))).
Proof
(Proof of Theorem
24.2.15
; following Williams [
566
]) Let
A
be an oracle that takes
a Rabin public key
N
and a ciphertext
c
(with respect to the Williams redundancy scheme)
and returns either the corresponding message
m
or an invalid ciphertext symbol
⊥
.