Cryptography Reference
In-Depth Information
Challenger
Adversary
K
p
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→
x
0
,
x
1
←−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
generate
K
p
,
K
s
select
x
0
,
x
1
}
compute
y
=
Enc
(
x
b
)
pick
b
∈
R
{
,
0
1
y
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→
b
←−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
guess
b
Figure 9.9.
Semantic Security Game.
4. The challenger picks uniformly at random a bit
b
. He encrypts
x
b
and sends the
ciphertext
y
to the adversary.
5. The adversary tries to guess
b
.
When the cryptosystem is secure, the adversary cannot guess
b
with a significant
advantage, so we often say that the two messages are indistinguishable. The indistin-
guishability notion is denoted IND. As it will be explained below, semantic security is
denoted IND-CPA.
Note that our definition does not provide so much information to the adversary
who only has the public key and a ciphertext. So he cannot do anything but encrypt
messages himself. We call this a CPA adversary as for “chosen plaintext attack.” The
semantic security notion is thus denoted IND-CPA.
Semantic security generalizes the notion of “bit security” to all bits. Indeed, if
there is any function bit from the plaintext space to
such that bitdec(
y
) is easily
computable without the secret key, where bitdec is defined by bitdec(y)
{
0
,
1
}
bit(Dec(y))
then we can mount an attack that can win in the semantic security game: the adversary
selects two random plaintexts
x
0
and
x
1
such that bit(
x
i
)
=
=
i
for
i
=
0
,
1 and deduce
b
from
b
=
bitdec(
y
).
Note that all notions of security require that the encryption is nondeterministic.
Indeed, if the encryption were deterministic, the adversary would easily encrypt
x
0
and
x
1
with the public key and compare both results to
y
. He would be able to guess
b
with
a 100% chance. We can extend this notion of semantic security to adversaries that are
given more resources. First of all, we can consider adversaries who can play during
“lunch time” with a decryptor. Indeed, prior to the selection of
x
0
and
x
1
, we assume
that the adversary can play with a decryption oracle as he likes. After this phase (after
lunch), the adversary has no longer access to this oracle. He selects the two plaintexts and
plays like in the previous game. This notion of adversary is denoted CCA1 and called
“nonadaptive chosen ciphertext attack.” The security notion is denoted IND-CCA1.
We have yet another adversary who is more powerful and denoted CCA2 (or
simply CCA). Here the adversary keeps access to the decryption oracle even after
having received the challenge ciphertext
y
. The only restriction is that he is not allowed
to send
y
to the oracle. This leads to the stronger security notion IND-CCA.
Search WWH ::
Custom Search