Cryptography Reference
In-Depth Information
I(x,y) > I(x,z)
(1.4)
holds for any z ∈C\C
T
0
. Given that there can be many codewords y with
this property we choose one that maximizes the function I(x,·). We claim that
for this codeword the following holds:
\
{y}⊆
C
T
(1.5)
{T:x∈desc(C
T
)∧|T|≤w}
Provided that the above claim hold then the code satisfies the identifiable
parent property since the above equation holds for any x that belongs to the
set desc
w
(C).
Suppose that Equation
1.5
does not hold. In other terms there exists some
T
∗
with |T
∗
|≤ w for which x ∈ desc(C
T
∗
) but y ∈C
T
∗
.
On the other hand, the traceability property of the code ensures the exis-
tence of a user codeword y
∗
∈C
T
∗
for which I(x,y
∗
) > I(x,z) for any z ∈C\C
T
∗
;
given that y 6∈C
T
∗
we obtain I(x,y
∗
) > I(x,y).
is a contradiction. Therefore it follows that y
∗
∈C
T
0
. Nevertheless, now given
that I(x,y
∗
) > I(x,y) we derive a contradiction on the choice of y which was
assumed to maximize I(x,·). This contradiction suggests our claim in Equa-
tion
1.5
holds, i.e., the identifiable parent property is proven.
An important observation relates the size q of the code-alphabet and the
size w of the traitor coalition for which the code is resistant:
Theorem 1.9. If an (`,n,q)-code C over an alphabet Q is w-IPP then it holds
that w < q.
pose that a code C = {c
1
,...,c
n
} over an alphabet Q is w-IPP while at the
same time w ≥ q = |Q|.
Consider now a traitor coalition T = {t
1
,...,t
w
}⊆ [n] with w ≥ q, and a
receiver-index u ∈ [n] \T, denote the set T
i
= T\{t
i
}∪{u} for i = 1,...,w,
and also say T
0
= T.
We will now consider a specific pirate codeword m
T,u
that is constructed
by picking the the symbols most frequent for each position, i.e., m
T,u
=
hm
1
,...,m
`
i where m
i
= b ∈ Q such that b is the element with a maxi-
mal |{j ∈ T∪{u} : c
i
= b}| (ties are broken arbitrarily). Since w ≥ q, and
the size of the set T∪{u} is w + 1, for each i = 1,...,` we have
|{j ∈ T∪{u} : c
i
= m
i
}|≥ 2
(1.6)
Observe now that m
T,u
∈ desc(C
T
j
) holds for each j = 0,1,...,w. Indeed,
pirate codeword m
T,u
is descendant of the codewords of the coalition T
j
.