Cryptography Reference
In-Depth Information
type v, Exp
1
, be the one where the encryption is computed so that the first v
keys are over a random plaintext while the remaining keys encode the correct
message. More specifically, the 4th line is replaced with:
c = h
E
k
1
(R
1
),...,
E
k
v
(R
v
),E
k
v+1
(m
1
),...,E
k
n
(m
1
)i
where R
i
is a random string of the same length as the message m
1
for
i = 1,...,v.
Let p
1
be the probability that the experiment Exp
1
returns 1 and similarly
let p
0
be the probability that the experiment Exp
0
returns 1. Observe that in
the case v ≥ n, the sequence of encryptions no longer contains any information
on b, and the same is true for all other information given to the adversary. It
follows that the adversary's view is independent of b and therefore it is easy
to derive that p
1
=
2
.
On the other hand, let us assume that the adversary has advantage of
at least ε in being succesful on the original experiment Exp
0
, i.e. we obtain
p
0
= p
1
≥
2
+ ε. It follows that there is a gap of ε between p
1
and p
1
and
by applying the triangular inequality we obtain that there must exist some
0 < v
0
≤ n such that
1
|≥
ε
n
| p
v
0
−1
1
−p
v
0
We next claim that for any v = 1,...,n,
|p
v−
1
−p
1
|≤ 2ε
p
We prove the claim. Consider the following CCA1 key encapsulation adver-
sary B with a parameter v. B will be able to break the symmetric encryption
scheme (
E
,
D
) in the sense of Definition
2.5
with probability at least ε
p
by
simulating the adversary A and the multiuser encryption sender.
To break the security claim of the underlying symmetric encryption scheme
(
E
,
D
), B, is given access to encryption-decryption oracle of the primitive. B
has also access to the decryption/encryption under a key k that is unknown
to her. She is then challenged with plaintext-ciphertext pair (c,m) for which
either c =
E
k
(m) or c =
E
k
(R) for some random string R that has the same
length with m. She is asked to test if the pair is a correct plaintext-ciphertext
pair.
B will simulate the experiment Exp
1
. In the initial stage, it will simulate A
as in the experiment Exp
1
by answering all queries except those that involve
the key k
v
that will be answered by the encryption and decryption oracle
available to B. In the second stage, B, will be given the challenge (c,m) where
either m is the proper plaintext of c or it is randomly selected. B will prepare
a challenge for A in the security game Exp
1
by setting the v-th location of
the challenge ciphertext with c and the remaining positions from v + 1,...,n
with the appropriate encryptions of m. The simulation of the second stage
