Cryptography Reference
In-Depth Information
for queries of type Transmit
L
(ek,m). This suggests that the tracer can pro-
gressively randomize the pattern of the ciphertext until a position is identified
that the pirate-box fails to decrypt successfully whenever it queries the tracing
ciphertext.
The soundness of the above argumentation is supported by the following
lemma:
Lemma 3.17. Assuming that s ∈ C, any probabilistic polynomial time ad-
versary A, given {k
i
}
i∈C
, distinguishes the distributions Transmit
s−
L
(ek,m)
and Transmit
L
(ek,m) with probability at most 2ε
p
where it holds (tk,ek,sk
1
,
...,sk
n
) ← KeyDist(1
n
) assuming that the underlying encryption scheme
(
E
,
D
) is ε
p
-insecure in the sense of Definition
2.5
.
Proof. Consider the following CCA1 key encapsulation adversary B that will
be able to break the symmetric encryption scheme (
E
,
D
) in the sense of Defi-
nition
2.5
with probability at least ε
p
by simulating the adversary A and the
multiuser encryption center.
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 distribution Transmit
L
(ek,m). Let B be given the
challenge (c,m) where either m is the proper plaintext of c or it is randomly
selected. B will prepare a transmission for A by setting the s-th location of the
challenge transmission with c and the remaining positions from s + 1,...,n
with the appropriate encryptions of m.
Based on the assumption on the underlying encryption scheme we have
that |Prob[Exp
ke
B
(1
n
)]−1/2|≤ ε
p
. We observe that in the key encapsulation
attack of B in the conditional space b = 0, the adversary B
kem
(1
n
) operates
identically to the distribution Transmit
s−
L
(ek,m) while in the conditional
space b = 1 it operates identically to the distribution Transmit
L
(ek,m).
Based on this derive the proof of the statement given in the lemma.
Let us define p
s
as the probability that the box decodes the special tracing
ciphertext Transmit
L
(ek,m). Suppose, now, that the key k
s
is not available
to the adversary. As we show in lemma
3.17
it holds that the pirate de-
coder can distinguish between the random variables Transmit
L
(ek,m) and
Transmit
s−
L
(ek,m) only with small probability that is related to the inse-
curity of the underlying encryption scheme
E
(·). As a result, it holds that
|p
s−1
−p
s
| is relatively small assuming that the advantage ε
p
in being suc-
cessful in security game of the underlying encryption primitive is also small.
On the other hand, for a pirate decoder we postulate that it holds that
p
0
≥ σ due to the constraint placed on A as detailed in the tracing game. On
