Cryptography Reference
In-Depth Information
TA Identifying Algorithm The class of w-IPP codes can be paired with an
exponential time algorithm; naturally this is not very useful and more e
cient
solutions are to be sought. In contrast with general w-IPP codes, the subclass
of w-TA codes can be paired with an algorithm that has computation time
linear in the product of the size and the length of the code. The idea is to score
each of receiver according to the number of overlaps between its codeword and
the pirate codeword; the receiver with the highest score would be necessarily
among the traitors assuming that the traitor coalition has size less than w
(compare this also with the proof of Theorem
1.8
).
We will, now, define an identifying algorithm Identify
TA
that given a
pirate codeword p ∈ Q
`
, with |Q| = q, and an (`,n,q) code C = {c
1
,...,c
n
},
it outputs an index t ∈ [n]. The algorithm first computes the score s
j
for each
codeword index j ∈ [n] as follows:
s
j
= |{i : p
i
= c
i
}|
The algorithm returns the index for which the score is maximal; i.e. the
index corresponding to the score max
j∈[n]
{s
1
,...,s
n
}. Observe that the score
of a user with index j ∈ [n] is equal to I(p,c
j
).
Theorem 1.11. Provided that (CodeGen(1
n
) generates a w-TA code for all
n ∈ N; the q-ary fingerprinting code hCodeGen,Identify
TA
i is w-identifier.
(C,tk) ← CodeGen(1
n
), we assume without loss of generality that the iden-
tifying key tk = is empty and C = {c
1
,...,c
n
} is a w-TA q-ary code. The
traceability property of the code implies the following:
∀T ⊆ [n] with |T|≤ w and ∀x ∈ desc(C
T
)
∃y ∈C
T
∀z ∈C\C
T
s.t. I(x,y) > I(x,z)
(1.8)
Consider now a Forging adversary that is subject to the marking assump-
tion as given in Definition
1.4
. The adversary chooses a traitor coalition with
index-set T which satisfies |T|≤ w. The adversary is given the traitor code-
words C
T
= {c
j
| j ∈ T} and finally outputs a pirate codeword p ∈ desc(C
T
).
Due to the fact that the code is w-TA, the pirate codeword p satisfies the
the user index with a maximum score that belongs to the traitor coalition T.
Recall that the score of a user with index j ∈ [n] is equal to I(p,c
j
).
This concludes the fact that no matter what the strategy of the forging al-
gorithm, on input traitor set T ⊆ [n] with |T|≤ w, outputs a pirate codeword
p it holds that Prob[∅6=⊆ Identify
TA
(C,p) ⊆ T] = 1, i.e. the fingerprinting
code hCodeGen,Identify
TA
i is w-identifier provided that CodeGen(1
n
)
generates a w-TA code.
