Cryptography Reference
In-Depth Information
A
(
,
−
)
3.
continues having oracle access to
Enc
k
and, after obtaining encryptions
chooses, outputs a bit
b
.
4. The output of the experiment is defined to be 1 if
b
A
of several messages
=
b
and 0 otherwise. If
PrivK
ind-cpa
A
,
E
(
n
)
=
1 then we say that
A
succeeded
.
Then the encryption scheme
is said to have
indistinguishable encryptions under a
chosen plaintext attack
(or that it is IND-CPA secure or, briefly, CPA secure) if, for
every PPT adversary
E
A
, there exists a negligible function
negl
such that
PrivK
ind-cpa
A,E
Pr
(
(
n
)
=
1
)
≤
1
/
2
+
negl
(
n
),
where the probability is taken over the random bits used by
A
, as well as the random
bits used elsewhere in the experiment.
The following result is a straightforward consequence of the definitions:
Proposition 3.3
If a symmetric encryption scheme has indistinguishable encryp-
tions under a chosen plaintext attack then it also has indistinguishable encryptions
in the presence of an eavesdropper.
Another straightforward consequence of the definitions is the following
Proposition 3.4
be a symmetric encryption scheme such
that
Enc
is a deterministic function of the key and the message. Then
Let
E
=
(
Gen
,
Enc
,
Dec
)
E
is not CPA
secure.
It suffices to observe that, in experiment
PrivK
ind-cpa
A,E
Proof
(
n
)
, after receiving the
challenge ciphertext
c
←
Enc
(
k
,
m
b
)
,
A
can query the oracle about the messages
m
0
,
m
1
. The oracle will respond by providing
A
with
c
0
:=
Enc
(
k
,
m
0
)
and
c
1
:=
Enc
c
1
. Since the encryption
function is deterministic, one of these two possibilities must hold and
(
k
,
m
1
)
and then
A
may check whether
c
=
c
0
or
c
=
A
outputs
b
=
i
where
c
=
c
i
, succeeding with probability 1.
Remarks 3.9
1. As happens with multiple encryptions in the presence of an eavesdropper, note
that also here the encryption scheme
might be CPA secure without being prob-
abilistic in case it is stateful, but this possibility is excluded in the statement of
the previous proposition, as we require there that
Enc
is a deterministic function
of the key and the message only.
2. In a way similar to eavesdropper indistinguishability,
E
PrivK
ind-cpa
A
,
E
|
Pr
(
(
n
)
=
, so that an encryption
scheme is CPA secure if any PPT adversary with oracle access to encryptions
has only negligible CPA advantage. In the previous proposition we have seen
that if encryption is a deterministic function of the key and the message, then
the CPA advantage of the adversary is equal to 1/2.
3. As in the case of eavesdropping adversaries one might define CPA security for
multiple encryptions just by letting the adversary
1
)
−
1
/
2
|
is called the CPA advantage of the adversary
A
A
output a pair of sequences
