Cryptography Reference
In-Depth Information
an impossibility, consider two disjoint set of codewords T
1
,T
2
⊆ C such that
T
1
∩T
2
= ∅, and further suppose that their descendant sets contain a common
codeword p, i.e. p ∈ desc(T
1
) ∩ desc(T
2
). Provided that the pirate codeword
observed is the codeword p, no traitor identification can be successful in this
unfortunate circumstance. This is the case, since p is possibly constructed by
a pirate who has given the codeword set T
1
or the set T
2
and it is impossible
to distinguish between these two cases.
In order to rule out such problems and obtain positive results, a useful
measure is to bound the coalition size; without specifying an upper bound on
the size of sets T
1
and T
2
, it can be quite hard to avoid the above failures in
some cases (nevertheless we will also demonstrate how it is possible to achieve
unbounded results - later in this chapter). Hence, we will start discussing some
necessary requirements that are parameterized with a positive integer w. This
parameter specifies the upper bound on the size of the traitors corrupted by
the pirate, or in other terms the size of the traitor coalition. For a code C, we
define the set of w-descendant codewords of C, i.e. the set of codewords that
could be produced by the pirate corrupting at most w traitors, denoted by
desc
w
(C) as follows:
[
desc
w
(C) =
desc(C
T
)
T⊆[n],|T|≤w
We, now, formally define a set of combinatorial properties of codes that
are related to the task of achieving identification:
Definition 1.7. Let C = {c
1
,...,c
n
} be an (`,n,q)-code and w ≥ 2 be an
integer.
1. C is a w-FP (frameproof ) q-ary code if for any x ∈ desc
w
(C) the following
holds: Given that x ∈ desc(C
T
)∩C with T ⊆ [n],|T|≤ w, then it holds that
x = c
i
for some i ∈ T; i.e. for any T ⊆ [n] that satisfies |T|≤ w, we have
desc(C
T
) ∩C ⊆C
T
.
2. C is a w-SFP (secure-frameproof ) q-ary code if for any x ∈ desc
w
(C) the
following holds: Given that x ∈ desc(C
T
1
) ∩ desc(C
T
2
) for T
1
6= T
2
with
|T
1
|,|T
2
|≤ w, it holds that T
1
∩T
2
6= ∅.
3. C is a w-IPP (identifiable parent property) q-ary code if for any x ∈
desc
w
(C), it holds that
\
C
T
6= ∅
{T:x∈desc(C
T
)∧|T|≤w}
4. C is a w-TA (traceability) q-ary code if for any T ⊆ [n] with |T| ≤ w
and for any x ∈ desc(C
T
), there is at least one codeword y ∈C
T
such that
I(x,y) > I(x,z) holds for any z ∈C\C
T
where we define I(a,b) = |{i : a
i
=
b
i
}| for any a,b ∈ Q
`
.
