Cryptography Reference
In-Depth Information
sequence. Each receiver is able to receive a unique path in such content se-
quence.
In this setting, the marking assumption of definition
1.4
will be enforced
by a robustness condition of the underlying watermarking technique so that
the pirate neither removes the mark nor alters it into another variation which
is not available to that pirate. For the sake of concreteness we will define the
type of watermarking that would be useful to us. A watermark embedding
algorithm is used to embed marks in the objects that are to be distributed.
In a certain setting where arbitrary objects O are distributed, the robustness
condition is defined as a property of a watermarking embedding function
Emb that postulates that it is impossible for an attacker, that is given a set
of marked objects derived from an original object, to generate an object that
is similar to the original object whose mark cannot be identified as one of the
marks that were embedded in the objects given to the adversary. Specifically
we formalize the above property as follows:
Definition 1.6. A watermarking embedding Emb : {1,...,q}×O→O satis-
fies the robustness condition with respect to a similarity relation Sim ⊆O×O,
alphabet size q and security parameter λ = log(
ε
) if there exists a watermark
reading algorithm Read such that for any subset of A ⊆ [q] the following holds
for any probabilistic polynomial time adversary A and for any object
a
∈O,
Prob[A({Emb(a,
a
) | a ∈ A}) =
e
∧ (
e
,
a
) ∈ Sim∧Read(
e
) ∈ A] ≤ ε
Note that it is assumed that (Emb(a,
a
),
a
) ∈ Sim for all objects
a
∈O) and
symbols a ∈ [q].
The robustness condition would enforce the marking assumption and thus
enable us to apply the identification algorithm of the fingerprinting code.
1.4 Constructions
1.4.1 Combinatorial Constructions
Combinatorial Properties of the Underlying Codes.
Consider an (`,n,q)-code. A pirate codeword can be any codeword of length
` over the same alphabet Q. Based on the marking assumption, a pirate code-
word p ∈ Q
`
will be related to a set of user-codewords which are capable
of producing this pirate codeword through combination of their components.
p ∈ desc(C
T
), where C
T
= {c
i
| i ∈ T} is defined as the total set of codewords
available to the traitor coalition specified by the traitor user set T.
Traitor identification, in some sense, amounts to evaluating similarities
between the pirate codeword and the user codewords. However it might be
impossible through such calculations to identify a traitor. To illustrate such
