Cryptography Reference
In-Depth Information
Definition 3.25
We define the
private-key CCA indistinguishability experiment
PrivK
ind-cca
A,E
(
)
E
=
(
,
,
)
A
n
, where
Gen
Enc
Dec
is a private-key encryption scheme,
a PPT adversary, and
n
any value of the security parameter, as follows:
1
n
is given input 1
n
and oracle access to both
1. A key
k
←
Gen
(
)
is generated.
A
Enc
(
k
,
−
)
and
Dec
(
k
,
−
)
. Then
A
outputs a pair of messages of the same length:
m
1
.
2. A random bit
b
is chosen and the
challenge ciphertext c
m
0
,
←
Enc
(
k
,
m
b
)
is com-
puted and given to
A
.
3.
A
continues having oracle access to
Enc
(
k
,
−
)
and
Dec
(
k
,
−
)
but is not allowed
outputs a bit
b
.
to query the latter on the challenge ciphertext. Afterwards
A
4. The output of the experiment is defined to be 1 if
b
=
b
and 0 otherwise. If
PrivK
ind-cca
A,E
(
n
)
=
1 then we say that
A
succeeded
.
The encryption scheme
is said to have
indistinguishable encryptions under a chosen
ciphertext attack
(or that it is IND-CCA secure, or CCA secure) if, for every PPT
adversary
E
A
, there exists a negligible function
negl
such that
PrivK
ind-cca
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.
Remarks 3.10
1. Note that, in the experiment above,
A
has free access to the decryption oracle (i.e.,
temporary access to the decryptionmachine as a 'black box') except that it cannot
request the decryption of the challenge ciphertext. Of course, if this exception
were not included, then no encryption scheme would satisfy the definition.
2. Although this security definition is much stronger than the preceding ones there
are, again, plausible scenarios where such an attack might be implemented in
practice. For example, if authentication is not used, it might be possible for an
adversary to impersonate one of the honest parties and receive decryptions that
might help in the decryption of further messages. This situation is more likely to
occur in a public-key setting where one party may communicate with multiple
parties with which there may not have been previous contact. In fact, as we
will see later, one such attack, described a few years ago, forced a change in a
public-key encryption scheme used by web browsers.
3. CCA security is much stronger than CPA security and, in particular, it implies
the
non-malleability property
which means that an adversary cannot modify a
given ciphertext in order to obtain another legal ciphertext whose corresponding
plaintext is related to the plaintext of the first one. The stronger requirements
make CCA security harder to achieve but we will later indicate how a CCA
secure scheme may be built; in view of the previous remark it is not surprising
that this construction involves authentication in addition to encryption.
4. The idea to prove that CCA security implies non-malleability is the following.
Suppose that the latter property does not hold, i.e., that the encryption scheme
