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).
Now in case y 6∈C T 0 from Equation 1.4 , we obtain I(x,y) > I(x,y ) which
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.
Proof of Theorem 1.9 : We will prove the statement by contradiction. Sup-
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,
1.6 ensures that no matter what j ∈{0,1,...,w}, the i-th symbol m i of the
pirate codeword m T,u is descendant of the codewords of the coalition T j .
 
 
 
 
Search WWH ::




Custom Search