Cryptography Reference
In-Depth Information
E
=
(
,
,
)
Definition 8.4
A public-key encryption scheme
is
one-way
secure against chosen plaintext attacks
(OW-CPA secure, for short) if, for every PPT
adversary
Gen
Enc
Dec
A
, there exists a negligible function
negl
such that
PubK
ow-cpa
A,E
Pr
(
(
n
)
=
1
)
≤
negl
(
n
),
where the probability is taken over the random bits used in the experiment.
We stress again the main weaknesses of this definition. First of all, it only requires
that the ciphertext of a plaintext which is randomly chosen in the message space is
hard to decrypt, but this is not meaningful if the challenge ciphertext comes from a
message chosen from a smaller subset of the message space that might be known
to the adversary. Also, it is only required that the recovery of the entire message is
hard but this leaves open the possibility that the adversary might learn a lot of partial
information about the message. We will mention this security concept again when
discussing the RSA encryption scheme in Section
8.3
.
Since one-wayness is insufficient for providing a reasonable level of security, we
will now look at indistinguishability which, as we have remarked in our discussion of
security in the private-key setting, provides an adequate tool to formalize the intuitive
idea that the ciphertext does not leak any partial information about the plaintext.
Definition 8.5
The
public-key CPA indistinguishability experiment
PubK
ind-cpa
A,E
(
)
n
,
where
E
=
(
Gen
,
Enc
,
Dec
)
is a public-key encryption scheme,
A
a PPT adversary,
and
n
any value of the security parameter, is the following:
1.
1
n
Gen
is run to obtain keys
(
pk
,
sk
)
←
Gen
(
)
.
2. Adversary
A
is given
pk
. The adversary outputs two messages of the same length:
m
1
.
3. A random bit
b
is chosen and the challenge ciphertext
c
m
0
,
←
Enc
(
pk
,
m
b
)
is
computed and given to
A
.
outputs a bit
b
.
5. The output of the experiment is defined to be 1 if
b
4.
A
=
b
and 0 otherwise. If
PubK
ind-cpa
A,E
(
n
)
=
1 then we say that
A
succeeded.
This leads to the following security definition:
Definition 8.6
A public-key encryption scheme
has
indis-
tinguishable encryptions under a chosen plaintext attack
(or is IND-CPA secure or,
simply, CPA secure) if, for every PPT adversary
E
=
(
Gen
,
Enc
,
Dec
)
A
, there exists a negligible function
negl
such that
PubK
ind-cpa
A
,
E
Pr
(
(
n
)
=
1
)
≤
1
/
2
+
negl
(
n
).
Remarks 8.2
1. The difference between OW-CPA security and IND-CPA security rests only on
the stronger goal that the adversary has to achieve in the latter. We have not
