Cryptography Reference
In-Depth Information
0
n
0
n
•
(
Enc
1
(
,
),
Enc
2
(
,
m
0
))
(
Enc
1
(
,
),
pk
k
is indistinguishable from
pk
Enc
2
(
E
2
is indistinguishable to eavesdroppers and
k
is a key
chosen uniformly at random about which
Enc
1
(
,
m
1
))
k
. This is because
0
n
does not give any informa-
tion (this was the reason why the 0-string, which is unrelated to
k
, was introduced).
Observe that we are using for
pk
,
)
E
2
the IND-EAV hypothesis which, for private-key
schemes such as this one is weaker than IND-CPA. But this is enough to ensure
the indistinguishability of these ciphertext pairs under a CPA attack because each
symmetric key
k
used by
is randomly generated for each new encryption and
hence there are no multiple encryptions with the same
k
.
•
(
E
0
n
Enc
1
(
pk
,
),
Enc
2
(
k
,
m
1
))
is
indistinguishable from
(
Enc
1
(
pk
,
k
),
Enc
2
(
k
,
m
1
))
. This follows, again, from the CPA security of
E
1
. Composing the three
steps we see that
(
Enc
1
(
pk
,
k
),
Enc
2
(
k
,
m
0
))
is indistinguishable from
(
Enc
1
(
pk
,
k
),
Enc
2
(
k
,
m
1
))
and hence that
E
is CPA secure.
Remark 8.1
Because of this theorem, the relative inefficiency of public-key
encryption schemes is not a big concern. Indeed, we do not have to worry about
encrypting long messages, as it is always possible to use for them an efficient hybrid
scheme which is CPA secure if so is the underlying public-key scheme and the
underlying private-key scheme satisfies the even milder requirement of being indis-
tinguishable to eavesdroppers.
8.3 RSA
The first public-key encryption scheme was publicly introduced in [164], published
in 1978, just two years after the publication of the seminal Diffie-Hellman paper. It is
calledRSAafter the initials of its inventors, R. Rivest, A. Shamir and L. Adleman and,
with many variants included in several standards, it is still today the most important
and widely used public-key encryption algorithm. We next discuss this scheme and
its security properties.
8.3.1 The RSA Assumption
From the very beginning of public-key cryptography, i.e., since the publication of
[67], it was clear that the search for a public-key encryption scheme should be cen-
tered on finding an appropriate hard computational problem. One number-theoretic
problem that was considered hard—and still is today—is the integer factorization
problem directly for an encryption scheme and Rivest, Shamir, and Adleman found
another closely related problem that was useful for this purpose: the RSA problem.
The idea is that if
n
=
pq
, where
p
and
q
are two distinct large primes and
∈ Z
φ(
n
)
e
, then the function
RSA
)
: Z
n
−→ Z
n
(
n
,
e
