Cryptography Reference
In-Depth Information
f is the polynomial corresponding to the vector w, we will now provide an
e
cient algorithm that on input ν it computes the polynomial f (and hence
the vector w).
Let g be a polynomial of degree at most `/2 such that g(i) = 0 for all
i = 1,...,n for which f(i) 6= ν
i
(where ν
i
is the i-th component of ν). Then
we know that for all i = 1,...,n we have f(i) · g(i) = g(i) ·ν
i
(in Z
q
). The
polynomial fg has degree at most n − `/2 − 1. Hence, we get n equations
(for each i = 1,...,n) in n variables (the variables are the coe
cients of the
polynomials fg and g; where the leading coe
cient of g is 1.) Let h and g be
a solution where g is a non-zero polynomial: h is a polynomial of degree at
most n − `/2 − 1 and g is of degree at most `/2. We know that whenever
w
i
= ν
i
(i.e. at n−`/2 points i) we have h(i) = g(i)ν
i
= g(i)f(i). It follows
that f = h/g.
We are now ready to prove that
ME
BF
`
is a non-black box traitor trac-
ing scheme, i.e., there exists a tracer that makes the corresponding tracing
game for `/2-coalitions winnable against any probabilistic polynomial time
adversary A.
Theorem 3.27. The Boneh-Franklin multiuser encryption scheme
ME
BF
`
is
a non-black box traitor tracing scheme for
2
-coalitions with success probability
α against σ-pirate for any choice of σ,α that satisfies σ ≥ α.
Proof. We need to present a tracing party T that works for any adversary A
and allows the recovery of any traitor set S that is fed to A. Let u
1
,...,u
t
∈
{1,...,N} be a set of rows S of B (that correspond to the keys of the traitors).
Based on Lemma
3.25
and the fact that A is polynomial-time we know that the
output of A on the keys of the traitors must be of the form η =
P
i=1
µ
i
δ
u
i
,
where µ
1
,...,µ
t
∈ Z
q
, assuming that t ≤ `−1.
By the definition of η it holds that there exists a vector ν = hν
1
,...,ν
n
i
with ν
u
v
= µ
v
for all v = 1,...,t and ν
i
= 0 for i 6∈ {u
1
,...,u
t
}, with the
property hν
1
,...,ν
n
i·B = η.
The tracing algorithm proceeds as follows: first it computes an arbitrary
vector ξ ∈ Z
q
that satisfies the system of equations ξ · B = η. Note that
such ξ can be found easily since ξ ·B = η is a system of ` equations with
n unknowns, n > `, and B contains a minor of size ` (due to the fact that
the matrix B is of full rank). It is easy to verify that the vector w =
df
ξ −ν
belongs to the linear code M: indeed, w·B = ξ ·B−ν ·B = η −η = 0. As
a result the vector ξ can be expressed as ξ = w + ν.
Provided that t ≤
2
it holds that the Hamming weight of ν is less or equal
to `/2 and as a result ξ is a n-vector that differs in at most
2
positions from
the vector w that belongs in M. Due to the lemma
3.26
the linear code M
is e
ciently decodable i.e., it holds that w can be recovered e
ciently if we
feed ξ to the decoding procedure for M. The recovery of w, immediately will
result in the recovery of ν = ξ−w. The set S can be thus recovered e
ciently
by observing the non-zero entries of ν.
