Cryptography Reference
In-Depth Information
8.2.1 Definitions of Security
The strongest form of security for private-key encryption schemes is perfect security
and we could try to define the analogous concept for public-key encryption. However,
it is easy to see that a perfectly secret public-key encryption scheme cannot exist,
because a computationally unbounded adversary can recover the plaintext encrypted
as ciphertext
c
just by encrypting all plaintexts in the message space and comparing
the resulting ciphertexts with
c
. This will work even if encryption is probabilistic
because the adversary can try all possible choices of random bits, of which there will
be only a finite number.
Recall that, when defining security in the private-key setting, there exists an impor-
tant distinction between security notions based on the assumption that the adversary
is a passive eavesdropper and the stronger notion in which the adversary is able to
mount a chosen plaintext attack (IND-CPA). This distinction no longer makes sense
in the public-key setting because the adversary knows the public key
pk
and hence
has access to an encryption oracle that will return the ciphertext corresponding to
any message. Thus it is readily apparent that in this situation any reasonable concept
of security against an eavesdropper will actually be equivalent to the corresponding
notion of security against a chosen plaintext attack. Therefore we will deal only with
the latter.
We will make a first attempt at defining security for a public-key encryption
scheme taking as a starting point the idea that the adversary should be unable to
recover the message from a given ciphertext. In this case the adversary goal is to
invert the encryption function and hence this kind of security should be attained if
the encryption functions are a family of trapdoor permutations. We have already
mentioned the shortcomings of modeling the encryption scheme this way and the
fact that the security level thus attained is very low. However, this kind of security
is a first step that can be proved under reasonable assumptions for some simple
schemes and is also a necessary condition for stronger security goals which we shall
subsequently define, so we start by formalizing it. First of all, we introduce the
probabilistic experiment that we will use for the definition:
Definition 8.3
The
public-key CPA one-wayness experiment
PubK
ow-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
n
1.
.
2. A message
m
is randomly chosen in the plaintext space and the corresponding
ciphertext
c
Gen
is run to obtain keys
(
pk
,
sk
)
←
Gen
(
)
←
Enc
(
pk
,
m
)
is computed.
3. Adversary
A
is given
pk
and the
challenge ciphertext c
.
outputs a message
m
.
5. The output of the experiment is defined to be 1 if
m
4.
A
=
m
and 0 otherwise. If
PubK
ow-cpa
A,E
(
)
=
A
n
1 then we say that
succeeded
.
Based on this experiment, we define one-way security:
