Cryptography Reference
In-Depth Information
We have seen that a similar result holds for RSA-OAEP but if we look at the results
of Boneh in more detail, it is readily apparent that Rabin-SAEP
+
is preferable also
in this aspect.
We shall not include the security reduction here and for its details we refer to
[34]. We give, however, a brief explanation of the security result and of the reasons
why it is especially strong. One fundamental ingredient of the security reduction is
Coppersmith's efficient algorithm for finding small zeros of polynomials modulo
n
which, given a monic polynomial of degree
d
,
f
(
x
)
∈ Z
n
[
x
]
, finds all
x
0
∈ Z
such
n
1
/
d
. This is a powerful result that was also
used in the reductionist security proof for RSA-OAEP and, to put it in perspective,
observe that, for
n
composite, finding the nontrivial roots of
x
2
that
f
(
x
0
)
≡
0
(
mod
n
)
and
|
x
0
|
<
≡
1
(
mod
n
)
(i.e.,
the roots distinct from
1) gives a nontrivial factor of
n
and hence is hard in general.
However, this does not contradict Coppersmith
's
result because these nontrivial roots
are not “small”, as their absolute value is
±
≥
√
n
.
In order to state Boneh's security result, let
T
C
(
n
,
d
)
be the running time of
Coppersmith's algorithm and let's use the name '
-CCA attack' for
an algorithm running in time
t
that makes at most
q
D
decryption queries to the
decryption oracle,
q
G
queries to the hash function
G
and
q
H
queries to the hash
function
H
. Then Boneh's result is the following:
(
t
,
q
D
,
q
G
,
q
H
)
Consider the
Rabin
-
SAEP
+
Theorem 8.3
encryption scheme with G and H mod-
eled as random oracles and l
pq is a modulus generated by
the
Gen
algorithm in Definition 8.15 on input the security parameter
1
k
. Suppose
that
+
s
0
≤
k
/
2
, where n
=
A
is a
(
t
,
q
D
,
q
G
,
q
H
)
-CCA attack which, for the modulus n, has advantage
ε
(i.e., with probability of success
that
factors n with the following running time and the following advantage (where the
advantage adv
≥
1
/
2
+
ε
). Then there is a PPT algorithm
B
(B)
is, in this case, the probability of success):
time
(B)
=
t
+
O
(
q
D
+
q
G
+
q
H
T
C
(
n
,
2
)),
1
6
·
ε(
2
s
0
2
s
1
adv
(B)
≥
1
−
q
D
/
−
q
D
/
).
This result implies theCCAsecurity of Rabin-SAEP
+
under the factoring assump-
tion because it says that if there is a PPT adversary that succeeds in the CCA indis-
tinguishability experiment with non-negligible advantage, then there exists a PPT
algorithm for factoring the modulus
n
. Note that, in practice,
s
0
and
s
1
will be
128
and the number of queries
q
D
will be small in comparison to 2
128
, so the probability
of success of the factoring algorithm will be close to
6
·
ε
≥
.
This security reduction has two clear advantages in comparison to the one for
RSA-OAEP. On the one hand, it relies on the hardness of the factorization problem,
which is a potentially weaker assumption than the RSA problem and, moreover, has
been more extensively studied and is presumably better understood. On the other
hand, this reduction is tight, which is not the case for the RSA-OAEP reduction. It
has been pointed out, for example in [109] and in [120], that the reasons why the more
secure versions or Rabin encryption are much less used than the RSA-based ones are
