Cryptography Reference
In-Depth Information
Instantiating Traceability Codes
It is possible to generate a w-TA code out of an error correcting code that
has a suitably high distance. We first define the error correcting codes.
Definition 1.12. An [`,n,d]
q
error-correcting code C is a set of n vectors
from the set Q
`
, where |Q| = q, with the following condition: for all x,y ∈C,
distance(x,y) ≥ d where distance(x,y) = |{i : x
i
6= y
i
}|, and x
i
∈ Q is the i-th
element of vector x.
Theorem 1.13. If C is an [`,n,d]
q
error-correcting that satisfies d > `(1 −
1
w
2
), then C is a w-TA (`,n,q) code.
Since I(x,y) = |{i : x
i
= y
i
}| is the complement of the function distance(·,·),
i.e., their sum equals to the length of the code `, we obtain:
∀x,y ∈C I(x,y) ≤ `−d < `−`(1−
1
`
w
2
w
2
) =
(1.9)
We will now prove that C is a w-TA code by showing the following: for
any T ⊆ [n] with |T|≤ w and for any x ∈ desc(C
T
),
∃y ∈C
T
s.t. ∀z ∈C\C
T
I(x,y) > I(x,z) (1.10)
Towards proving the existence of such codeword, first observe the following:
for any T ⊆ [n] with |T|≤ w, and any x ∈ desc(C
T
), the sum
P
v∈C
T
I(x,v) ≥ `.
Hence, if we denote the codeword within C
T
that has maximal overlap with the
codeword x by y
x,T
= max
v∈C
T
(I(x,v)), we have that satisfies I(x,y
x,T
) ≥ `/w.
We claim that for any z ∈ C\C
T
it holds that I(z,x) < `/w. Due to the
holds that I(x,z) ≤ w·`/w
2
. Finally, we have I(x,z) < `/w.
This completes the proof, since the codeword y
x,T
satisfies the condition
given in
1.10
with `/w being the actual threshold.
Reed-Solomon codes can be used to construct w-TA codes in the fash-
ion suggested in the theorem above. A Reed-Solomon code over a finite field
Q := F
q
includes all vectors of the form hp(f
1
),...,p(f
q−1
)i where p(·) is a
polynomial of degree r−1 in t
he field, and f
i
∈ F
q
for i = 1,...,q−1. This
yields a w-TA code with w ≤
p
(q−1)/(r−1) and q
r
codewords. One would
notice the immediate downside in this construction in its high lower bound
on the alphabet size : it should grow at least quadratically with the collusion
threshold w and even if q = O(w
2
) the number of users that can be accommo-
dated can be rather small. We will improve in this situation in section
1.4.2
where we will show that we can reduce alphabet size much closer to w. For
smaller alphabet values though we will stumble upon the following limitation.
