Cryptography Reference
In-Depth Information
1.3.1 Security of encryption
We now give precise definitions for the security of public key encryption. An
adversary
is a
randomised polynomial-time algorithm that interacts with the cryptosystem in some way. It
is necessary to define the
attack model
, which specifies the way the adversary can interact
with the cryptosystem. It is also necessary to define the
attack goal
of the adversary. For
further details of these issues see Sections 10.2 and 10.6 of Katz and Lindell [
300
], Section
1.13 of Menezes, van Oorschot and Vanstone [
376
] or Section 15.1 of Smart [
513
].
We first list the
attack goals for public key encryption
. The most severe one is the
total
break
, where the adversary computes a private key. There are three other commonly studied
attacks, and they are usually formulated as
security properties
(the security property is the
failure of an adversary to achieve its attack goal).
The word
oracle
is used below. This is just a fancy name for a magic box that takes
some input and then outputs a correct answer in constant time. Precise definitions are given
in Section
2.1.3
.
One-way encryption (OWE):
Given a challenge ciphertext
c
the adversary cannot
compute the corresponding message
m
.
Semantic security:
An adversary learns no information at all about a message from its
ciphertext, apart from possibly the length of the message.
This concept is made precise as follows: assume all messages in
M
κ
have the same
length. A
semantic security adversary
is a randomised polynomial-time algorithm
A
that first chooses a function
f
:
M
κ
→{
0
,
1
}
such that the probability, over uniformly
chosen
m
1is1
/
2. The adversary A then takes as input a challenge
(
c
,
pk
) where
c
is the encryption of a randomly chosen message
m
∈
M
κ
, that
f
(
m
)
=
∈
M
κ
, and outputs a
bit
b
. The adversary is
successful
if
b
f
(
m
).
Note that the standard definition of semantic security allows messages
m
=
M
κ
to be
drawn according to any probability distribution. We have simplified to the case of the
uniform distribution on
M
κ
.
∈
Indistinguishability (IND):
An adversary cannot distinguish the encryption of any two
messages
m
0
and
m
1
, chosen by the adversary, of the same length.
This concept is made precise by defining an
indistinguishability adversary
to be a
randomised polynomial-time algorithm
A
that plays the following game with a challenger:
first, the challenger generates a public key and gives it to
A
. Then (this is the “first phase”
of the attack)
A
performs some computations (and possibly queries to oracles) and outputs
two equal length messages
m
0
and
m
1
. The challenger computes the
challenge ciphertext
c
(which is an encryption of
m
b
where
b
is randomly chosen) and gives it to
A
.
In the “second phase”, the adversary
A
performs more calculations (and possibly oracle
queries) and outputs a bit
b
. The adversary is
successful
if
b
∈{
0
,
1
}
b
.
=
For a fixed value
κ
one can consider the probability that an adversary is successful over
all public keys
pk
output by KeyGen, and (except when studying a total break adversary)
