Cryptography Reference
In-Depth Information
The implications of the above definitions in terms of identification is as
follows:
• For any pirate codeword in a w-frameproof code C, that is produced by a
codeword coalition of size at most w, the pirate codeword is identical to
a user-codeword if and only if that user is involved in piracy. This means
that the marking assumption makes it impossible to trace an innocent
user.
• If two different sets of coalitions with size less than w are capable of pro-
ducing the same pirate codeword, then w-secure frameproof code implies
that these two coalitions are not disjoint. While this property is necessary
for absolute identification it is not su
cient : it is possible for example to
have three different sets with their descendant sets having a non-empty
intersection while themselves share only elements pairwise. In such case,
it would still be impossible to identify a traitor codeword. This motivates
the next property called the identifiable parent property.
• If any number of different coalitions with size less than w are capable
of producing the same pirate codeword, then the w-identifiable parent
property implies that there is at least one common user codeword in all
of the coalitions. Under such circumstance on input a pirate codeword,
an identification algorithm becomes feasible as follows: all possible sets of
coalitions which produces the given pirate codeword are recovered. The w-
identifiable parent property implies the existence of at least one codeword
that is contained in the intersection of all those sets. This is the output of
the algorithm (note that this algorithm is not particularly e
cient but it
achieves perfect correctness - we provide a formal description below).
• For any pirate codeword in a w-traceability code, that is produced by
a codeword coalition of size at most w, there exists a simple procedure
that is linear in n and recovers at least one traitor. This procedure simply
considers all codewords z as possible candidates and calculates the function
I(x,z) with the pirate codeword x. The codewords with the highest value
are the traitor codewords.
The above properties are hiearachical; in fact, it is quite easy to observe
that identifiable parent property implies the secure frameproof property which
in turn also implies the frameproof property. Here, we will give the proof for
the first link which states that the traceability property implies the identifiable
parent property.
Theorem 1.8. If an (`,n,q)-code C over an alphabet Q is w-TA q-ary code,
then the code satisfies the w-identifiable parent property.
alphabet Q is w-TA. Now pick x ∈ desc
w
(C). There is some T
0
such that
x ∈ desc(C
T
0
) and T
0
⊆ [n] with |T
0
| ≤ w. Due to the w-TA property there
exists a user codeword y ∈C
T
0
such that
