Cryptography Reference
In-Depth Information
A
(
,
−
)
2.
is given
pk
and oracle access to
Dec
sk
and it outputs a pair of messages
of the same length,
m
0
,
m
1
, belonging to the plaintext space.
3. A random bit
b
is chosen and the challenge ciphertext
c
←
Enc
(
pk
,
m
b
)
is
computed and given to
A
.
4.
A
continues having oracle access to
Dec
(
sk
,
−
)
but is not allowed to query it on
outputs a bit
b
.
5. The output of the experiment is defined to be 1 if
b
=
the challenge ciphertext. Then
A
b
and 0 otherwise. In the
first case we say that
A
succeeded.
The corresponding security definition is then the following:
Definition 8.8
The public-key encryption scheme
is said to have
indistinguish-
able encryptions under a chosen ciphertext attack
(or to be CCA secure or IND-CCA
secure) if, for every PPT adversary
E
A
, there exists a negligible function
negl
such that
PubK
ind-cca
Pr
(
(
n
)
=
1
)
≤
1
/
2
+
negl
(
n
).
A
,
E
Remarks 8.3
Chosen ciphertext attacks are often subdivided into two classes: CCA1
and CCA2. In a CCA1 attack the adversary can obtain decryptions of arbitrary
ciphertexts of its choice before it gets the challenge ciphertext. This resembles a
scenario in which the adversary obtains access to the decryption device (as a black
box) while the legitimate user is away at lunch. Afterwards, the legitimate user
returns and the adversary is given the challenge ciphertext which it has to decrypt
without further access to the decryption box. Because of this analogy CCA1 attacks
are often called 'lunchtime attacks'. Since the queries to the oracle cannot depend
on the challenge ciphertext, CCA1 attacks are also called
non-adaptive
or
indifferent
chosen ciphertext attacks, and another termused for them is
apriori
chosen ciphertext
attacks ([87]).
In a CCA2 attack the adversary has the additional capability of continued access
to the decryption device after it has received the challenge ciphertext. Thus it can
query the decryption box about ciphertexts that might be related to or in some way
suggested by the challenge ciphertext (with the restriction that it cannot ask for
decryption of the challenge ciphertext itself). Therefore CCA2 attacks (also called
adaptive
or
a posteriori
chosen ciphertext attacks) form a much stronger class of
attacks than CCA1.
Observe that in the definition of
PubK
ind-cca
A,E
(
)
n
it is stated that the adversary
A
after being given the challenge cipher-
text, so IND-CCA security is the same as what is called IND-CCA2 security in the
finer classification. This is the strongest notion of security we consider and is the one
at which the design of public-key encryption schemes should aim.
The construction of CCA secure public-key schemes is an important problem.
There are some constructions that are rather complex and inefficient and thus they
are not used in practice. As for efficient schemes, the first one to be provedCCAsecure
(under the DDH assumption according to which the DDH problem is hard) in the
standard security model is due to Cramer and Shoup [59] and we study it in Sect.
8.6
.
continues having oracle access to
Dec
(
k
,
−
)