Cryptography Reference
In-Depth Information
experiment can be at most γ. On the other hand, observe that for all l ∈
{1,...,`} it holds that p
q,l
≤ γ. This is because the ciphertexts transmitted
in this case are entirely hiding the plaintext that is needed to return in order
for the experiment to succeed. Based on the limited crossover probability we
have that it can only happen with probability at most γ that the adversary
recovers this other plaintext.
We continue now with the description of the tracer. For each l, the tracer
finds the smallest s ∈ [q] for which it holds that |ρ
s−1,j
−ρ
s,j
|≥ K(σ−2γ)/5q
and sets w
j
= s. Finally the tracer constructs a codeword p = hw
1
,...,w
`
i.
It then outputs Identify(tk,p) where
F
= (CodeGen,Identify).
Now using lemma
3.18
we have that the choice K ≥
75q
2
·ln(8`/ε)
(σ−2γ)
2
su
ces to
locate a value w
j
∈{1,...,q}, for all j = 1,...,`, such that |p
w
j
−1,j
−p
w
j
,j
|≥
σ−2γ
5q
holds with probability 1−ε. Via the reasoning of Lemma
3.20
it holds
that the key material k
w
j
,j
belongs to the traitor coalition for j = 1,...,` if
the adversary succeeds in decrypting with probability σ > 10qε
p
+2γ. Finally
for the codeword p = hw
1
,...,w
`
i it holds that Identify(tk,p) ∈ C with
probability at least 1−ε
f
.
This completes the proof of the theorem.
Alfresco Tracing Against History-Recording Decoders
We may consider a variant of the Kiayias-Yung scheme that supports alfresco
tracing against history recording decoders for the price of increasing the suc-
cess probability σ that is required of the adversary. That lower bound on the
success probability emerges in a similar way as in the traceability arguments
of the Boneh-Naor scheme earlier in this chapter. Without detailed analysis
we will describe the scheme as follows: we consider the q-ary version of the
Kiayias-Yung scheme where on input vector hm
1
,...,m
q
i the transmission is
prepared so that m
0
i
= m
i
holds for i = 1,...,q in the l-th column ( which is
sampled randomly from the set {1,...,`}). We assume the plaintexts follow-
ing the distribution M
q
with limited crossover γ. By choosing σ su
ciently
high, each transmission will have to be decrypted correctly by the adversary
with some probability that is a function of σ and ` so that the adversary
outputs a plaintext value for the chosen column.
In order to achieve traceability in the history-recording setting, the tracer
will refrain from interfering with the way regular transmissions are formed and
it will wait to receive a su
cient number of responses from all columns (recall
that the column used for variating the plaintext is randomly selected at each
step). The number of queries needed to span all columns can be computed as
an instance of coupon-collector problem, lemma
1.3
.
In order to complete tracing the tracer needs to collect a su
cient number
of responses from each column l. Thinking of columns as coupons, the failure
probability would be the event that more than λ sample trials are needed to
collect all ` coupons. Considering the coupon collector lemma with ` coupons
and β = 1 +
ln 1/ε
0
ln`
we have that the probability of the event of failing to
