Traitor Tracing - Encryption for Digital Content - page 142

Assume there exists A, a probabilistic polynomial time algorithm that takes
as input the public-key and the secret-keys sk i 1 ,...,sk i t with t ≤ `− 1 and
returns a vector δ ∈ Z q so that (i) δ is a representation of h 0 base h 1 ,...,h ` ,
and (ii) δ is not a linear combination of sk i 1 = b i 1 γ i 1 ,...,sk i t = b i t γ i t . Then
the discrete logarithm problem over hgi is solvable in polynomial-time.

Proof. (of Lemma 3.25 ) Let g,h ∈hgi be an instance of the discrete-logarithm
problem in the group G. We construct a modified public-key as follows: sup-
pose a 0 ,...,a ` are selected as specified by KeyDist BF ` (1 n ); then we set
the modified public-key to be the vector hh 0 ,h 1 ,...,h ` i where h 0 = g a 0 and
h 1 = g a 1 h b 1 ,...,h ` = g a ` h b ` where b = hb 1 ,...,b v i is selected so that (i)
δ i v · b = 0 for all v = 1,...,t, and (ii) b 6= 0. Note that these conditions
suggest that b is a non-trivial solution to a homogenous system of t linear
equations. Such a b can be found by computing the kernel of the matrix of
the system and picking an arbitrary non-zero element in it; we note that the
condition of the lemma that t ≤ `−1 is critical for finding such a non-zero b
vector.
Next, we simulate A on H,Γ,sk i 1 ,...,sk i t to obtain the vector δ. Since
δ is not a linear combination of δ i 1 ,...,δ i t it follows that δ · b 6= 0 with
probability at least 1−1/q. This happens because conditioning on the public-
key the vector b has at least one remaining degree of freedom from the point
of view of the adversarial procedure A. From this it follows that log g h =
(δ ·b) −1 (a 0 −δ ·a) where a = ha 1 ,...,a ` i.

We next recall the construction of the user keys in the Boneh-Franklin
scheme and motivate the choice of the matrix M.

Lemma 3.26. Consider the (n−`)×n matrix M that is constructed by defin-
ing the j-th column as a vector h1,2 j−1 ,...,n j−1 i. For such matrix we have
the following:

1. Any vector in the span of the rows of M (also called the rowspan) corre-
sponds to a polynomial in Z q [x] of degree at most n−`− 1 evaluated at
the points 1,...,`.
2. The rowspan of M is a linear code that is e ciently decodable for up
to 2 errors. Specifically given any vector Z q that differs in at most `/2
positions from a vector in the rowspan it is possible to recover such vector
by a polynomial-time algorithm.

Proof. Regarding the first item of the lemma, let w = hw 1 ,...,w n i be a
vector in the span of the rows of the matrix M, i.e. there exists a set of

coe cients {µ 0 ,µ 1 ,...,µ n−`−1 } such that w v = P n−`−1

i=0 µ i v i . Observe that
the value w v corresponds to the evaluation of v on the polynomial f(x) =
µ 0 + µ 1 x + µ 2 x 2 + ... + µ n−`−1 x n−` 1 .
Regarding the second item, let ν ∈ Z q be a vector that differs from a
vector w in the rowspan of the matrix M in up to 2 locations. Provided that