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
.
Search WWH ::




Custom Search