Cryptography Reference
In-Depth Information
on input C
T
= {c
j
| j ∈ T} outputs a codeword p from the descendant set
desc(C
T
) that is defined as follows:
desc(C
T
) = {x ∈ Q
`
: x
i
∈{a
i
: a ∈C
T
},1 ≤ i ≤ `}
where x
i
,a
i
are the i-th symbols of the related vectors.
In the context of fingerprinting codes, the set desc(C
T
) is the set of code-
words that can be produced by a pirate using the codewords of the set C
T
.
Therefore in an (`,n,q)-code C, forging would correspond to producing a pi-
rate codeword p ∈ Q
`
out of the codewords available to a traitor coalition
T. A q-ary fingerprinting code is a pair of algorithms (CodeGen,Identify)
that generates a code for which it is possible to trace back to a traitor for any
pirate codeword. Formally we have,
• CodeGen is an algorithm that given input 1
n
, it samples a pair (C,tk) ←
CodeGen(1
n
) where C is an (`,n,q)-code defined over an alphabet Q with
` as a function of n and q, and the identifying key tk is some auxiliary
information to be used by Identify that may be empty. We may use `
as a superscript in the notation CodeGen
`
, to emphasize the fact that
CodeGen produces output a set of strings of length ` that might be a
function of n, q and other parameters if such are present.
• Identify is an algorithm that on input the pair (C,tk) ← CodeGen(1
n
)
and the codeword c ∈ Q
`
, it outputs a codeword-index t ∈ [n] or it fails.
Remark. Note that CodeGen can be either deterministic or probabilistic
and we will name the fingerprinting code according to the properties of the
underlying CodeGen procedure. Each codeword can be considered as the
unique identifier of the corresponding user. If c is constructed by a traitor
coalition, the objective of the Identify algorithm is to identify a codeword
that was given to one of the traitors who took role in the forgery.
Definition 1.5. We say a q-ary fingerprinting code hCodeGen,Identifyi is
(α,w)-identifier if the following holds :
• For any Forging algorithm that satisfies the marking assumption and
(tk,C) ← CodeGen(1
n
) it holds that
∀T ⊆ [n] s.t. |T|≤ w Prob[∅ * Identify(tk,p) ⊆ T] ≥ 1−α
where C = {c
1
,...,c
n
} is an (`,n,q)-code and p ∈ Q
`
is the output of the
Forging algorithm on input C
T
= {c
j
| j ∈ T}.
The probability is taken over all random choices of CodeGen and Identify
algorithms when appropriate. We say the fingerprinting code is w-identifier
if the failure probability α = 0. The above definition supports identification
for traitor coalitions of size up to w, and thus such fingerprinting codes will
be called w-collusion resistant codes. By expanding the choice of T in the
