Cryptography Reference
In-Depth Information
1
|M|
, Lemma
3.20
implies that the key
material k
w
j
,j
belongs to the traitor coalition. Following lemma
3.18
, the
number of tracing queries for each symbol needs to be at least
75q
2
·ln(8`/ε)
Recall that given σ
j
> 10qε
p
+
(σ
j
−1/|M|)
2
to
succeed with probability 1−ε/`. Finally, the codeword p = hw
1
,...,w
`
i is in
the descendant set of the traitor coalition with probability at least 1−ε, and
it holds that Identify(tk,p) ∈ C with probability at least 1−ε
f
.
To give an upper bound on tracing overhead we consider the following:
since
P
j∈[`]
σ
j
= σ, we also have σ
j
≥ `σ − ` + 1. Hence we obtain the
following upper bound:
1
`
`
X
75(q + 1)q
2
· ln(8`/ε)
(σ
j
−1/|M|)
2
`q
3
· ln(`/ε)
(`σ−` + 1−1/|M|)
2
)
= O(
j=1
This completes the proof of the theorem.
Traceability of Kiayias-Yung Scheme
We next consider the Kiayias-Yung scheme
ME
KY [
F
]
where
F
= (CodeGen,
Identify) is a q-ary fingerprinting code that produces an (`,n,q) code. The
scheme is a binary multiuser encryption scheme, i.e., each receiver is capa-
ble of receiving a single message from the transmission of the input-vector
M = hm
0
,m
1
i. Recall that the transmission, by using a symmetric encryp-
tion scheme (
E
,
D
), is of the following form:
2
E
k
1
(r
1
)
E
k
1
(r
2
) ...
E
k
1
(m
0
1
−
P
i6=l
r
i
) ...
E
k
1
(r
`
)
3
E
k
2
(r
1
)
E
k
2
(r
2
) ...
E
k
2
(m
0
2
−
P
i6=l
r
i
) ...
E
k
2
(r
`
)
.
4
5
.
.
.
.
.
E
k
q
(r
1
)
E
k
q
(r
2
) ...
E
k
q
(m
0
q
−
P
i6=l
r
i
) ...
E
k
q
(r
`
)
where r
1
,...,r
`
are drawn from the plaintext space, m
0
1
= ... = m
0
s
=
m
1−b
, m
0
s+1
= ... = m
0
q
= m
b
, while (l,s) is sampled from the set
{1,...,`}×{0} randomly and b ←{0,1}. During tracing the transmissions will
be modified : in particular the tracer will variate s ∈{0,1,...,q}. Note that
this means that the ciphertexts will be potentially decrypted differently by
different users (but still this does not violate correctness in a binary scheme).
For the objectives of tracing we will further put forth the following notion.
Definition 3.23. For a q ∈ N and plaintext space M a q-ary plaintext distri-
bution M with limited crossover γ ∈ (0,1) over M
q
satisfies that for any A
and any i
0
∈{1,...,q}, it holds that the probability A
M
({m
i
}
i6=i
0
) = m
i
0
is at
most γ, where hm
1
,...,m
q
i is sampled from M.
We will assume that the plaintexts used follow a plaintext distribution
with limited crossover. This is a reasonable assumption that for example is
trivially satisfied by the distribution of cryptographic keys.
