Cryptography Reference
In-Depth Information
collect all coupons in at least β` ln` = ` ln`/ε
0
trials is at most
(`)
1−β
= (`)
−
ln 1/ε
0
ln `
= (`)
− log
`
1/ε
0
= ε
0
Hence a number λ ≥ ` log `/ε
0
of transmissions will be su
cient to receive
a response from all ` columns with probability 1 −ε
0
. Let m
1
, m
2
,... m
λ
be
the responses of the adversary in all these transmissions where a certain m
j
might also be ⊥ standing for a refusal to decrypt or decrypting incorrectly.
Given a su
ciently high σ and limited crossover with γ we can derive that
with high probability all the responses are consistent with the traitor coalition
keys and thus we identify a unique traitor key for each column. Subsequently
the fingerprinting code identification algorithm will provide a traitor identity.
Hence, we argue that it is possible to identify a traitor with failure probability
bounded by ε
f
+ ε
0
.
In the next chapter in Section
4.3
we discuss a trace and revoke scheme
with a similar relation to the choice of γ and σ. We refer the reader there
for more insights in formulating the precise number of transmissions that are
required in terms of the bounds γ and σ.
3.5.3 Traceability of the Boneh-Franklin Scheme
We will first revisit the key space of the Boneh-Franklin scheme to elaborate
on the set of key material that is useful for decryption of a transmission.
Recall that the scheme is based on group generation algorithm Gen that
on input 1
k
produces G,q,g where g ∈G is an element of order q where q is a
k-bit prime. The public-key of the scheme as sampled by KeyDist is an object
of the form G
`+1
×Z
n×
q
. The space of secret-keys contains objects of the form
Z
`+
q
. Finally, K
ek
contains elements of Z
q
that satisfy the following: if the
tracing-key is tk = ha
0
,a
1
,...,a
`
i and the encryption key is ek = hH,Γi with
H = hg
a
0
,...,g
a
`
i, it holds that δ ∈ K
sk
if and only if a
0
= δ ·ha
1
,...,a
`
i
(where “·” here stands for the inner product over Z
q
vectors).
We next consider what are the capabilities of an adversary to produce new
key material in K
ek
while in possession of some keys in K
ek
. In particular we
show that any probabilistic a lgorithm that is polynomial-time bounded and
is given a number of decryption keys cannot produce a new decryption-key
that is not a linear combination of the given keys. This restricts the search
space of possible keys that a tracer needs to take into account when trying to
win the tracing game.
Lemma 3.25. Let n ∈ N, and htk,ek,sk
1
,...sk
n
i be distributed according
to KeyDist
BF
`
(1
n
) where tk = ha
0
,a
1
,...,a
`
i and ek = hH,Γi with H =
(g
a
0
,...,g
a
`
) where g ∈ G and (G,q,g) ← Gen(1
k
). Here Γ is an (`,n,q)-
code over an alphabet Z
q
for some k-bit prime number q. The secret key sk
u
is
computed as a vector δ
u
= b
u
·γ
u
with b
u
= a
0
(
P
i=1
a
i
γ
i
)
−1
for u = 1,...,n.
