Cryptography Reference
In-Depth Information
is easy to imagine a situation where recovering some partial information about the
plaintext—even a single bit in the most extreme cases—could be very valuable for
the adversary. We see that there are many possible properties that lead to insecurity
and this makes it difficult—or even impossible in practice—to characterize security
in terms of the absence of these properties.
Ideally, one would like to regard an encryption scheme as secure if, given the
ciphertext, the adversary has no information about the plaintext. But it is easy to see
that this requirement would be too strong because often there is
apriori
information
about the message: it might have some known format, it might be known that it is an
English text or that it is taken from a very small set of possible messages, etc. In an
extreme case, if the one-time pad was used, the adversary might even know that the
plaintext is either 1 or 0 (or, for example, 'yes' or 'no'). Then the adversary would
have a lot of information about the message but this would not violate the fact that
the system is perfectly secret, which is the strongest form of security.
Bearing these remarks in mind, the concept of security we are aiming for is that an
adversary (with limited computing power), on seeing a ciphertext, will not gain with
non-negligible probability any significant partial information about the plaintext (in
addition to the a priori information it might already have). This idea is formalized
in the definition of
semantic security
, which was the first definition of encryption
security to be proposed. But this definition is difficult to work with and we will use
another definition based on the concept of
indistinguishability
which is much simpler
and is, in fact, equivalent to semantic security (see also [87, 109] for more details).
The idea underlying the indistinguishability concept is to consider an adver-
sary that chooses two messages of the same length. Then one of these messages
is encrypted and the resulting ciphertext is given to the adversary. The encryption
scheme is considered secure if the adversary cannot distinguish which of the two
messages was the one actually encrypted.
In order to define indistinguishability (also called polynomial indistinguishabil-
ity), we first define an experiment parameterized by a security parameter.
Definition 3.21
Let
E
=
(
Gen
,
Enc
,
Dec
)
be a private-key encryption scheme,
A
an adversary (i.e., a PPT algorithm), and
n
a positive integer. The
private-key
eavesdropping indistinguishability experiment
,
PrivK
ind-eav
A
,
E
(
n
)
, is the following:
is given input 1
n
and outputs two messages of the same length:
1. The adversary
A
m
1
.
2. A key
k
is generated by running
Gen
m
0
,
1
n
(
)
and a random bit
b
is chosen. The
challenge ciphertext c
←
Enc
(
k
,
m
b
)
is computed and given to
A
.
outputs a bit
b
.
4. The output of the experiment is defined to be 1 if
b
A
3.
=
b
and 0 otherwise. If
PrivK
ind-eav
A,E
(
)
=
A
n
1 then we say that
succeeded
.
m
1
,have
the same length. This is necessary because we assume that the encryption scheme can
encrypt messages of arbitrary length and, usually, different length messages produce
different length ciphertexts, so that information about plaintext length leaks allowing
Note that in the experiment above we require that the two messages
m
0
,
