Cryptography Reference
In-Depth Information
probabilistic encryption). It is sometimes also described as
indistinguishability of
ciphertexts
. It basically means that ciphertexts can't be distinguished in the sense
that they can be attributed to plaintext messages that are more likely than others.
Semantic security (or indistinguishability of ciphertexts) is particularly useful when
one considers message spaces that are sparse (i.e., message spaces that contain only
a few possible messages, such as “yes” and “no” or “buy” and “sell”). This situation
is not unlikely for many practical applications of asymmetric encryption.
In order to better understand the notion of semantic security against adaptive
chosen-ciphertext attacks, let us consider the following experiment: somebody has
specified two plaintext messages
m
0
and
m
1
(e.g.,
m
0
=0and
m
1
=1)anden-
crypted both messages (using, of course, the same key). The resulting ciphertexts are
published in random order. Furthermore, we assume a polynomially bound adver-
sary who has access to a decryption oracle. This means that he or she can adaptively
choose ciphertexts and have them decrypted by the oracle at will (needless to say
that the adversary is not allowed to ask for the decryption of any of the encrypted
messages
m
0
and
m
1
). The adversary's job is to decide which ciphertext belongs
to which plaintext message. If the adversary has no significantly better chance than
guessing (to do the job), even if he or she can ask the oracle polynomially often,
then we say that the encryption system in use is
semantically secure
. Alternatively
speaking, the success probability of the adversary in the experiment only negligibly
deviates from 1
/
2.
Note that semantic security against adaptive chosen-ciphertext attacks only
makes sense for probabilistic (asymmetric) encryption systems (i.e., encryption
systems that don't employ a deterministic encryption algorithm). Otherwise, an
adversary can always compute himself or herself the ciphertexts of
m
0
and
m
1
.
Consequently, many practically relevant asymmetric encryption systems (that are
deterministic in nature) cannot be semantically secure. Examples include the RSA
and Rabin asymmetric encryption systems discussed in the next section. These
systems, however, can still be made semantically secure by applying an appropriate
padding scheme prior to encryption. We revisit this possibility when we elaborate
on the
optimal asymmetric encryption padding
(OAEP) scheme in Section 14.3.2.
Semantic security against adaptive chosen-ciphertext attacks is the commonly
accepted notion of security for (asymmetric) encryption systems. There are, how-
ever, also some other notions of security one may think of and come up with.
For example, a more intricate notion of security is
nonmalleability
[3]. Roughly
speaking, an asymmetric encryption system is
nonmalleable
if it is computationally
infeasible to modify a ciphertext so that it has a predictable effect on the plaintext
message. For example, when given the ciphertext of a bid in an auction, it must be
computationally infeasible for a polynomially bound adversary to come up with a
ciphertext of a smaller bid (at least not with a success probability that is greater
