Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes.
In this paper, we investigate combinatorial properties and constructions of two recent topics of cryptographic interest, namely frameproof codes for digital fingerprinting and traceability schemes for broadcast encryption. We first give combinatorial descriptions of these two objects in terms of set systems and also discuss the Hamming distance of frameproof codes when viewed as error-correcting codes. From these descriptions, it is seen that existence of a c-traceability scheme implies the existence of a c-frameproof code. We then give several constructions of frameproof codes and traceability schemes by using combinatorial structures such as t-designs, packing designs, error-correcting codes, and perfect hash families. We also investigate embeddings of frameproof codes and traceability schemes, which allow a given scheme to be expanded at a later date to accommodate more users. Finally, we look briefly at bounds which establish necessary conditions for existence of these structures.
Introduction
Traceability schemes for broadcast encryption were defined by Chor, Fiat and Naor [8], and
frameproof codes for digital fingerprinting were proposed by Boneh and Shaw [4]. Although
these two objects were designed for different purposes, they have some similar aspects. One
of the purposes of this paper is to investigate the relations between traceability schemes and
frameproof codes. We first give combinatorial descriptions of these two objects in terms of
set systems, and also discuss the Hamming distance of frameproof codes when viewed as
error-correcting codes. From these descriptions, it is seen that existence of a c-traceability
scheme implies the existence of a c-frameproof code.
In [4, 8], some constructions of frameproof codes and traceability schemes were pro-
vided. We will provide new (explicit) constructions by using combinatorial structures such
as t-designs, packing designs, error-correcting codes and perfect hash families. We also
investigate embeddings of frameproof codes and traceability schemes, which allow a given
scheme to be expanded at a later date to accommodate more users. Finally, we look briefly
at bounds which establish necessary conditions for existence of these structures.
In this rest of this section we review the definitions of c-frameproof codes and c-
traceability schemes which were given in [4] and [8], respectively.
1.1 Frameproof codes
In order to protect a product (such as computer software, for example), a distributor marks
each copy with some codeword and then ships each user his data marked with that codeword
(for some examples of how this might be done in practice, see [5]). This marking allows
the distributor to detect any unauthorized copy and trace it back to the user. Since a
marked object can be traced, the users will be deterred from releasing an unauthorized
copy. However, a coalition of users may detect some of the marks, namely the ones where
their copies differ. They can then change these marks arbitrarily. To prevent a group of
users from "framing" another user, Boneh and Shaw [4] defined the concept of c-frameproof
codes. A c-frameproof code has the property that no coalition of at most c users can frame
a user not in the coalition.
Let v and b be positive integers (b denotes the number of users in the scheme). A set
is called a (v; b)-code and each w (i) is called a codeword.
So a codeword is a binary v-tuple. We can use a b \Theta v matrix M to depict a (v; b)-code, in
which each row of M is a codeword in \Gamma.
\Gamma be a (v; b)-code. Suppose \Gamma. For
we say that bit position i is undetectable for C if
Let U(C) be the set of undetectable bit positions for C. Then
is called the feasible set of C. (If then we define F .) The feasible
set F (C) represents the set of all possible v-tuples that could be produced by the coalition
C by comparing the d codewords they jointly hold. If there is a codeword w (j) 2 F (C)nC,
then user j could be "framed" if the coalition C produces the v-tuple w (j) . The following
definition from [4] is motivated by the desire for this situation not to occur.
Definition 1.1 A (v; b)-code \Gamma is called a c-frameproof code if, for every W ' \Gamma such that
We will say that \Gamma is a c-FPC(v; b) for short.
Thus, in a c-frameproof code, the only codewords in the feasible set of a coalition of at
most c users are the codewords of the members of the coalition. Hence, no coalition of at
most c users can frame a user who is not in the coalition.
Example 1.1 ([4]) For any integer b, there exists a b-FPC(b; b). The matrix depicting the
code is a b \Theta b identity matrix.
Example 1.2 There exists a 2-FPC(3; 4). The matrix depicting the code is as
1.2 Traceability schemes
In many situations, such as a pay-per-view television broadcast, the data is only available
to authorized users. To prevent an unauthorized user from accessing the data, the data
supplier will encrypt the data and give the authorized users keys to decrypt it. Some
unauthorized users (pirate users) might obtain some decryption keys from a group of one
or more authorized users (called traitors). Then the pirate users can decrypt data that
they are not entitled to. To prevent this, Chor, Fiat and Naor [8] devised a traitor tracing
scheme, called a traceability scheme, which will reveal at least one traitor on the confiscation
of a pirate decoder.
Suppose there are a total of b users. The data supplier generates a base set T of v keys
and assigns k keys to each user. These k keys comprise a user's personal key, and we will
denote the personal key for user U by P (U ). A message consists of an enabling block and a
cipher block. A cipher block is the encryption of the actual plaintext data using some secret
S. The enabling block consists of data, which is encrypted using some or all of the v
keys in the base set, the decryption of which will allow the recovery of S. Every authorized
user should be able to recover S using his or her personal key, and then decrypt the cipher
block using S to obtain the plaintext data.
Some traitors may conspire and give an unauthorized user a "pirate decoder", F . The
pirate decoder F will consist of k base keys, chosen from T , such that F ' [U2C P (U ),
where C is the coalition of traitors. An unauthorized user may be able to decrypt S using a
pirate decoder F . The goal of the data supplier is to assign keys to the users in such a way
that when a pirate decoder is captured and the keys it possesses are examined, it should be
possible to detect at least one traitor in the coalition C, provided that jCj - c (where c is a
predetermined threshold).
Traitor detection would be done by computing jF "P (U)j for all users U . If jF "P (U)j -
users V 6= U , then U is defined to be an exposed user.
Definition 1.2 Suppose any exposed user U is a member of the coalition C whenever a
pirate decoder F is produced by C and jCj - c. Then the scheme is called a c-traceability
scheme and it is denoted by c-TS(k; b; v).
Let us now briefly discuss the difference between our scheme and that of [8]. In [8],
nk for some integer n, and the set T of base keys is partitioned into k subsets S i , each
of size n. We will denote S Each personal key P (U) is
a transversal of (S contains exactly one key from each S i ). Suppose the
secret key S is chosen from an abelian group G. To encrypt S, the data supplier splits
G such that
every share r i with each of the n keys in S i by computing t . The nk values t i;j
comprise the enabling block. Each authorized user has one key from S i , so he or she can
decrypt every r i , and thus compute S.
In our definition, we do not require that each personal key be a transversal. A personal
key can be made up of any selection of k base keys from the set T . The data supplier can
use a k out of v threshold scheme (such as the Shamir scheme [13], for example) to construct
v shares of the key S, and then encrypt each share r i with the key s i , for every s
Note that our definition is a generalization of the one given in [8]. However, the generalization
has to do with the way that the enabling block is formed, and not with the
traceability property of the scheme. Our definition of the traceability property is the same
as in [8].
Example 1.3 We present a 2-TS(5; 21; 21). The set of base keys is Z 21 . The personal key
for user i (0 - i - 20) is
where all arithmetic is done in Z 21 . (This is an application of a construction we will present
in Theorem 3.5.) It can be shown that any two base keys occur together in exactly one
personal key. Now, consider what happens when two traitors U and V construct a pirate
decoder, F . The pirate decoder F must contain at least three personal keys from P (U) or
However, for any other user W 6= U; V , 2. Hence either U or V will
be the exposed user if the pirate decoder F is examined.
1.3 Previous results
In the construction of frameproof codes and traceability schemes, the main goal is to accommodate
as many users as possible. In other words, we want to find constructions with b as
large as possible, given values for the parameters c and v (and k, in the case of traceability
schemes). In general, we would prefer explicit constructions for these objects as opposed to
non-constructive existence results.
For example, Boneh and Shaw [4] proved the following interesting result.
Theorem 1.1 For any integers c; v ? 0, there exists a c-FPC
However, as noted in [4], the proof is not constructive. Hence, they also provide an explicit
construction for a c-FPC
Similarly, Chor, Fiat and Naor [8] gave an interesting non-constructive existence result
for traceability schemes, as follows.
Theorem 1.2 For any integers c; v ? 0, there exists a c-TS(v=(2c 2
We will provide several explicit constructions for frameproof codes and traceability
schemes later in this paper. Although our constructions may not be as good asymptotically
as those in [4] and [8], they will often be better for relatively small values of c and
v. (For example, in order to obtain b - 2 in Theorem 1.1, it is necessary to take v - 16c 2 ,
so the construction is not useful for small values of v.) As well, our constructions are very
simple and could be implemented very easily and efficiently.
Combinatorial descriptions
In this section, we give combinatorial descriptions of c-frameproof codes and c-traceability
schemes. From these descriptions, it is fairly easy to see that the existence of a c-TS(k; b; v)
implies the existence of a c-FPC(v; b).
We will use the terminology of set systems. A set system is a pair (X; B) where X is a
set of elements called points, and B is a set of subsets of X, the members of which are called
blocks. A set system can be described by an incidence matrix. Let (X; B) be a set system
g. The incidence matrix of (X; B) is
the b \Theta v matrix
ae
Conversely, given an incidence matrix, we can define an associated set system in an obvious
way.
2.1 Description of c-frameproof codes
Since a c-FPC(v; b) is a b \Theta v (0; 1)-matrix, we can view a frameproof code as an incidence
matrix or as a set system, as defined above. We have the following characterization of
frameproof codes as set systems.
Theorem 2.1 There exists a c-FPC(v; b) if and only if there exists a set system (X; B)
such that and for any subset of d - c blocks there does
not exist a block B 2 BnfB such that
d
d
Proof. Suppose are d codewords in a c-FPC(v; b) (d - c). Without loss
of generality, assume that in these codewords the first s bit positions are 0, the next t bit
positions are 1, and in every other bit position at least one of the d codewords has the value
0 and at least one has the value 1. (Hence, the undetectable bit positions are the first s
bit positions.) Then, it is not hard to see that the frameproof property is equivalent to
saying that any other codeword w has at least one 1 in the first s bit positions, or at least
one 0 in the next t bit positions. In other words, there does not exist a codeword with 0's
in the first s bit positions and 1's in the next t bit positions.
are the blocks in the set system corresponding to the d codewords
d
and
d
Hence the frameproof condition is equivalent to saying that there does not exist a block B
such that "B
2.2 Description of c-traceability schemes
Since a c-TS(k; b; v) consists of b k-subsets of a v-set, we can think of it as a set system,
where X is the set of base keys and B is the set of personal keys.
Theorem 2.2 There exists a c-TS(k; b; v) if and only if there exists a set system (X; B)
such that B, with the property that for every
choice of d - c blocks for any k-subset F ' [ d
there does not
exist a block B 2 BnfB such that
Proof. Suppose (X; B) is a c-TS(k; b; v). For every set of d - c personal
B, for any k-subset F ' [ d
(i.e., a pirate decoder) and for any other personal key
B, there exists a d) such that there is no block
d. The converse is also
straightforward.
2.3 Relationship of traceability schemes and frameproof codes
We prove the following theorem relating traceability schemes and frameproof codes.
Theorem 2.3 If there exists a c-TS(k; b; v), then there exists a c-FPC(v; b).
Proof. Let (X; B) be the set system corresponding to a c-TS(k; b; v). We prove that (X; B)
is a c-FPC(v; b). Suppose not; then there exist d - c blocks, B, and a block
such that
But this contradicts Theorem 2.2 (letting
2.4 Hamming distance of 2-frameproof codes
Now we investigate some properties of the Hamming distance of c-frameproof codes. For
any (v; b)-code, let d(x; y) denote the Hamming distance of two codewords x; y.
Denote
and
Theorem 2.4 A (v; b)-code \Gamma is 2-frameproof if and only if
for all i
Proof. Let w (i) ; w (j) and w (h) be any three distinct codewords. Without loss of generality,
assume that U(fw (i) ; w (j) so the first r bits of w (i) and w (j) are the same.
We have that d(w (i) ; w (j) Hamming distance is a metric, we have that
it will be the case that
if and only if there is at least one bit position within the first r bit positions such that w (h)
is different from w (i) and w (j) . But this is just the condition that the code is 2-frameproof
(as stated in the proof of Theorem 2.1).
The following result is an immediate corollary of the previous lemma.
Corollary 2.5 A (v; b)-code \Gamma is 2-frameproof if d
We give an example to illustrate the application of this corollary. In [6], a simple
explicit construction is given for a (q; (q
prime power q. Hence, for q ? 81, we see that d
In fact, we have verified by computer that d for the codes produced by this
construction for all odd prime powers q such that 31 - q - 79. Applying Corollary 2.5, we
obtain the following result.
Theorem 2.6 For any odd prime power q - 31, there exists a 2-FPC(q; (q
3 Constructions from combinatorial structures
In this section, we will give some constructions of frameproof codes and traceability schemes
from certain combinatorial designs, including t-designs, packing designs and orthogonal
arrays. All the results on design theory that we require can be found in standard references
such as the CRC Handbook of Combinatorial Designs [9].
3.1 Constructions using t-designs
First we give the definition of a t-design.
Definition 3.1 A t-(v; k; -) design is a set system (X; B), where
B, and every t-subset of X occurs in exactly - blocks in B.
Note that, by simple counting, the number of the blocks in a t-(v; k; 1) design is
. We will use t-(v; k; 1) designs to construct frameproof codes and traceability
schemes, as described in the following theorems.
Theorem 3.1 If there exists a t-(v; k; 1) design, then there exists a c-FPC(v;
proof. Denote distinct blocks, and let
g. If
there exists a d, such that
t. Since we have a t-design with
Hence, for any B 2 BnfB g, we have that B 6' [ d
. The t-design is a set
system satisfying the conditions of Theorem 2.1, so the conclusion follows.
Similarly, we can construct traceability schemes from t-(v; k; 1) designs; the value of c
obtained is smaller, however.
Theorem 3.2 If there exists a t-(v; k; 1) design, then there exists a c-TS(k;
proof. Suppose there exists a t-(v; k; 1) design (X; B). Let d be d - c distinct
blocks. g. If F ' [ d
there exists a B i ,
d, such that
c
r
On the other hand, since we have
Hence, it follows that This shows that the t-design is a set system
satisfying the conditions of Theorem 2.2, and the conclusion follows.
There are many known results on existence and construction of t-(v; k; 1) designs for
3. On the other hand, no is known to exist for
t - 6. However, known infinite classes of 2- and 3-designs provide some nice infinite classes
of frameproof codes and traceability schemes. We illustrate with a few samples of typical
results that can be obtained.
First, for 3 - k - 5, a 2-(v; k; 1) design exists if and only if v j 1 or k mod
[9, Chapter I.2]. Hence, we obtain the following.
Theorem 3.3 There exist frameproof codes as follows:
1. There exists a 2-FPC(v; v(v \Gamma 1)=6) for all v j
2. There exists a 3-FPC(v;
3. There exists a 4-FPC(v;
Similarly, we have the following theorem about the existence of 2-traceability schemes
(note that to get c - 2 when Theorem 3.2, we need k - 5).
Theorem 3.4 There exists a 2-TS(5; v(v \Gamma 1)=20; v), for all v j
A design is known as a projective plane of order q; such a design
exists whenever q is a prime power (see [9, Chapter VI.7]). In a projective plane we have
so the frameproof codes obtained from it are not interesting (in view of Example 1.1,
which does better). However, the traceability schemes will be of interest.
Theorem 3.5 There exists a b p qc-TS(q 1), for all prime powers q.
Example 1.3 is in fact obtained from the case Theorem 3.5.
We give another class of examples derived from 3-(q 2 +1; q +1; 1) designs (these designs
are called inversive planes and exist if q is a prime power; see [9, Chapter VI.7]).
Theorem 3.6 For any prime power q, there exists a
3.2 Constructions using packing designs
Another type of combinatorial design which can be used to construct frameproof codes and
traceability schemes are packing designs. We give the definition as follows.
Definition 3.2 A t-(v; k; -) packing design is a set system (X; B), where
for every B 2 B, and every t-subset of X occurs in at most - blocks in B.
Using the same argument as in the proof of Theorem 3.1, we have the following construction
for frameproof codes.
Theorem 3.7 If there exists a t-(v; k; 1) packing design having b blocks, then there exists
a c-FPC(v; b), where
Similarly, we have the following construction for traceability schemes, using the same
argument as in the proof of Theorem 3.2.
Theorem 3.8 If there exists a t-(v; k; 1) packing design having b blocks, then there exists
a c-TS(k; b; v), where
We mentioned previously that no t-(v; k; 1) designs are known to exist if v
However, for any t, there are infinite classes of packing designs with a "large" number of
blocks (i.e., close to
). These can be obtained from designs known as orthogonal
arrays, which are defined as follows.
Definition 3.3 An orthogonal array OA(t; k; s) is a k \Theta s t array, with entries from a set
of s - 2 symbols, such that in any t rows, every t \Theta 1 column vector appears exactly once.
It is easy to obtain a packing from an orthogonal array, as shown in the next lemma.
Lemma 3.9 If there is an OA(t; k; s), then there is a t-(ks; k; 1) packing design that contains
blocks.
proof. Suppose that there is a OA(t; k; s) with entries from the set f0;
1g. For every column (y in the
orthogonal array, define a block consist of the
blocks thus constructed. It is easy to check that (X; B) is a t-(ks; k; 1) packing design.
The following lemma ([9, Chapter VI.7]) provides infinite classes of orthogonal arrays,
for any integer t.
Lemma 3.10 If q is a prime power and t ! q, then there exists an OA(t; q
hence a t-
packing design with q t blocks exists.
From Theorem 3.7 and Lemma 3.10, we obtain the following.
Theorem 3.11 For any prime power q and any integer t ! q, there exists a
In this construction, b - 2
2c (for frameproof codes) and b - 2
traceability
schemes). Also, the resulting traceability schemes are of the "transversal type" considered
in [8].
3.3 Constructions using perfect hash families
In this section, we present another method to construct frameproof codes, which uses a
perfect hash family.
Definition 3.4 An (n; m;w)-perfect hash family is a set of functions F such that f :
ng ! f1; ng such that
there exists at least one f 2 F such that f j X is one-to-one.
When , an (n; m;w)-perfect hash family will be denoted by PHF(N ; n; m;w).
Observe that a PHF(N ; n; m;w) can be depicted as an N \Theta n matrix with entries from
having the property that in any w columns there exists at least one row such
that the w entries in the given w columns are distinct. Results on perfect hash families
can be found in numerous textbooks and papers. Mehlhorn [12] is a good textbook source;
more recent constructions can be found in the papers [2] and [3].
The following theorem tells us how to use a perfect hash family to enlarge a frameproof
code.
Theorem 3.12 If there exists a PHF(N ; n; m; c + 1) and a c-FPC(v; m), then there exists
a c-FPC(Nv; n).
proof. be a c-FPC(v; m), and let F be a PHF(N ; n; m; c+1).
be the (Nv; n)-code consisting of the n codewords
means concatenation of strings. We will show that \Gamma 0 is a c-
FPC(Nv;n).
g. Recall that U(W ) is the set of undetectable
bit positions of W . Assume that there exists a codeword u (i c+1
F is a PHF(N ; n; m; c + 1), there exists
an h 2 F such that hj C is one-to-one, where g. Thus we have c
different codewords w 1, such that w (h(i c+1 )) is in the feasible set of
cg. This contradicts the fact that \Gamma is c-frameproof.
In [4], the following construction of c-frameproof codes from error-correcting codes is
given.
Theorem 3.13 If there exists a c-FPC(v; q) and an (N; n) q-ary code with minimum Hamming
distance d min ? there exists a c-FPC(vN; n).
Alon [1] gave a construction of perfect hash families from error-correcting codes. We
observe that if we use a perfect hash family constructed by Alon's method to obtain a c-
frameproof code by applying Theorem 3.12, then the resulting code is essentially the same as
the one constructed using Theorem 3.13. However, it is possible to use other constructions
for perfect hash families to obtain new examples of frameproof codes. We provide one
illustration now, which uses the following recursive construction from [3].
Lemma 3.14 Suppose there exists a PHF(N
1. Then
there exists a PHF
for any integer j - 1.
Example 3.1 There exists a PHF(2; 5; 4; 3) as follows:
Theorem 3.15 For any integer j - 1, there exists a 2-FPC(6 \Theta 4
proof. From Lemma 3.14 and Example 3.1, we obtain a PHF(2 \Theta 4
Combine this perfect hash family with the 2-FPC(3; 4) given in Example 1.2, and apply
Theorem 3.12.
4 Embeddings
In many cases the number of users of a scheme will increase after the system is set up.
Initially, the data supplier will constuct a scheme that will accommodate a fixed number of
users (which we denoted by b). If the number of users eventually surpasses b, we would like
a simple method of extending the scheme which is "compatible" with the existing scheme.
In the case of a traceability scheme, we do not want to change the personal keys already
issued when the scheme is expanded. In the case of a frameproof code, we do not want to
have to recall software that has already been sold.
To solve this problem, we will introduce the concept of embedding frameproof codes and
traceability schemes in larger ones.
Definition 4.1 Let \Gamma be a c-FPC(v; b) and let \Gamma 0 be a c-FPC(v
Suppose that, for every codeword w 2 \Gamma, there exists a codeword w such that the first
bit positions of w 0 are the same as w, and the remaining v positions of w 0 are all
0's. Then we say that \Gamma is embedded into
Initially, the distributor could use the code \Gamma to mark the products. When the number
of users surpasses b, then codewords in \Gamma 0 n\Gamma are used. Note that the embedding property
ensures that the codewords in \Gamma do not have to be changed when we proceed to the larger
code.
A similar definition can be given for traceability schemes.
Definition 4.2 Let T be the set of v base keys of a c-TS(k; b; v), and let T 0 be the set of v 0
base keys of a c-TS(k; b Suppose that every personal
key of the c-TS(k; b; v) is also a personal key of the c-TS(k; b we say that the
first scheme is embedded into the second scheme.
Note that the definition of embedding is even simpler if we consider the set system
formulation of frameproof codes and traceability schemes. Namely, we say that (X; B) is
embedded into
Since t-designs and packing designs are set systems, the above definition of embedding
applies. In fact, embeddings of combinatorial designs have been extensively studied, so we
have a convenient method of constructing embeddible frameproof codes and traceability
schemes.
For example, in the case of 2-designs, we have the following result.
Theorem 4.1 If there exists a 2-(v; k; 1) design that can be embedded into a 2-(v
design, then there exists a that can be embedded into a
\Xip
that can
be embedded into a
\Xip
We give a couple of illustrations of this idea. For necessary and sufficient
conditions for embedding 2-(v; k; 1) designs into 2-(v designs are known, namely v j
result is known as the "Doyen-Wilson Theorem" [9, Chapter I.4]; for
III.1].) This provides a convenient way of embedding 2- and 3-frameproof codes into larger
ones by application of Theorem 4.1. The following theorems are obtained.
Theorem 4.2 For all v j 6 such that v 0 - 2v+1, there exists
a 2-FPC(v; (v that can be embedded into a 2-FPC(v
Theorem 4.3 For all v j
exists a 3-FPC(v; (v that can be embedded into a 2-FPC(v
Here is a small example to illustrate.
Example 4.1 Given an embedding of a 2-(7; 3; 1) design into a 2-(15; 3; 1) design, a 2-
FPC(7; 7) can be embedded into a 2-FPC(15; 35). The 35 codewords of the 2-FPC(15; 35)
are given in Figure 1 (the first seven codewords, when restricted to the first seven bit
positions, form the embedded 2-FPC(7; 7)).
@
1101000 00000000
1000000 00110000
0100000 00011000
1000000 00001010
0100000 10000100
0001000 10100000
1000000 01000100
0010000 10010000
0001000 01001000
1000000 10000001
A

Figure

1: A 2-FPC(7; 7) embedded into a 2-FPC(15; 35).
It is also well-known that for any prime power q and for any integers i - j, there exists
a which can be embedded into a 2-(q j ; q; 1) design (in other words, the
affine geometry AG(i; q) is a subgeometry of AG(j; q); see [9, Chapter VI.7]). The following
result is obtained.
Theorem 4.4 Let q be a prime power, and let i and j be positive integers such that i - j.
Then there exists a which can be embedded into a
can be embedded into a
5 Bounds
In this section, we investigate necessary conditions for existence for frameproof codes and
traceability schemes. These take the form of upper bounds on b, as a function of c and v
(and k, in the case of traceability schemes).
First we will give a bound for frameproof codes. be a c-
FPC(v; b). Recall that U(C) denotes the set of undetectable bit positions for a subset
denotes the feasible set of C. For 1 - d - c, let
We begin by stating and proving a simple lemma.
Lemma 5.1 Suppose is a c-FPC(v; b), and suppose t are as
defined above. Then
proof. Suppose t be such that
g. Clearly U(C) ' U(C 0 ); however, since
which contradicts
Definition 1.1.
The next result provides an upper bound on b which depends on t c\Gamma1 .
Theorem 5.2 Suppose is a c-FPC(v; b), and suppose t are as
defined above. Then
l t c\Gamma1m
proof. Let W ' \Gamma be chosen such that jW
any codeword w (i) 2 \GammanW , let R It is easy to see that R i ' R for all
which contradicts the fact that \Gamma is c-frameproof). In other words,
the subsets R i constructed above form a Sperner family with respect to the ground set R.
By Sperner's Theorem (see, for example [11, Theorem 6.3]), we see that
dt
1, the result follows.
The following bound on b is an immediate corollary.
Corollary 5.3 If \Gamma is a c-FPC(v; b), then
proof. From Lemma 5.1, we have that t 2. The conclusion follows from
Theorem 5.2.
Recall that Example 1.1 gave a construction for c-FPC(c; c), and we constructed a
FPC(3; in Example 1.2. In both of these examples, the bound of Corollary 5.3 is met
with equality.
Now we turn our attention to traceability schemes, where we provide an upper bound
on b. In [8], it was shown that b - v k=c if a c-TC(k; v; b) exists. We give a stronger bound,
which is also based on the following observation made in [8].
Lemma 5.4 Suppose (X; B) is a c-TC(k; v; b). Then, for any subset of d - c blocks
there does not exist a block B 2 BnfB such that B '
proof. The proof is essentially the same as the proof of Theorem 2.3.
For obvious reasons, the collection of subsets B is called c-cover-free. Now, applying [10,
Proposition 2.1], which gives an upper bound on the cardinality of a c-cover-free collection
of sets, the following result is immediate.
Theorem 5.5 If a c-TS(k; b; v) exists, then the following bound holds:
c e.
6 Comments
Further results on frameproof codes can be found in the PhD thesis of Yeow Meng Chee [7,
Chapter 9]. Chee gives a probabilistic construction for 2-frameproof codes that improves
upon results in [4], and provides efficient explicit constructions for frameproof codes using
the idea of superimposed codes.

Acknowledgements

We thank the referee for several helpful comments. The authors' research is supported by
NSF grant CCR-9402141.



--R

Explicit construction of exponential sized family of k-independent sets

Some recursive constructions for perfect hash families

Electronic marking and identification techniques to discourage document copying.
On a class of constant weight codes


CRC Handbook of Combinatorial Designs

A Course in Combinatorics
Data Structures and Algorithms
How to share a secret
--TR

--CTR
Sylvia Encheva , Grard Cohen, Frameproof codes against limited coalitions of pirates, Theoretical Computer Science, v.273 n.1-2, p.295-304, February 2002
Omer Berkman , Michal Parnas , Jii Sgall, Efficient dynamic traitor tracing, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.586-595, January 09-11, 2000, San Francisco, California, United States
Yan Zhu , Wei Zou , Xinshan Zhu, Collusion secure convolutional fingerprinting information codes, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan
J. Lfvenberg, Binary Fingerprinting Codes, Designs, Codes and Cryptography, v.36 n.1, p.69-81, July      2005
Maura Paterson, Sliding-window dynamic frameproof codes, Designs, Codes and Cryptography, v.42 n.2, p.195-212, February  2007
Alexander Barg , Gregory Kabatiansky, A class of I.P.P. codes with efficient identification, Journal of Complexity, v.20 n.2-3, p.137-147, April/June 2004
Tran Van Trung , Sosina Martirosyan, On a Class of Traceability Codes, Designs, Codes and Cryptography, v.31 n.2, p.125-132, February 2004
G. Cohnen , S. Encheva , S. Litsyn , H. G. Schaathun, Intersecting codes and separating codes, Discrete Applied Mathematics, v.128 n.1, p.75-83, 15 May
Wen-Guey Tzeng , Zhi-Jia Tzeng, A Public-Key Traitor Tracing Scheme with Revocation Using Dynamic Shares, Designs, Codes and Cryptography, v.35 n.1, p.47-61, April     2005
Satoshi Obana , Kaoru Kurosawa, Bounds and Combinatorial Structure of
Yevgeniy Dodis , Nelly Fazio , Aggelos Kiayias , Moti Yung, Scalable public-key tracing and revoking, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.190-199, July 13-16, 2003, Boston, Massachusetts
Tran Van Trung , Sosina Martirosyan, New Constructions for IPP Codes, Designs, Codes and Cryptography, v.35 n.2, p.227-239, May       2005
Yevgeniy Dodis , Nelly Fazio , Aggelos Kiayias , Moti Yung, Scalable public-key tracing and revoking, Distributed Computing, v.17 n.4, p.323-347, May 2005
X. Ma , R. Wei, On a Bound of Cover-Free Families, Designs, Codes and Cryptography, v.32 n.1-3, p.303-321, May-July 2004
Dan Boneh , Brent Waters, A fully collusion resistant broadcast, trace, and revoke system, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
Dan Boneh , Brent Waters, A fully collusion resistant broadcast, trace, and revoke system, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
Carlo Blundo , Paolo Darco , Alfredo De Santis , Massimiliano Listo, Design of Self-Healing Key Distribution Schemes, Designs, Codes and Cryptography, v.32 n.1-3, p.15-44, May-July 2004
Stelvio Cimato , Antonella Cresti , Paolo D'Arco, A unified model for unconditionally secure key distribution, Journal of Computer Security, v.14 n.1, p.45-64, January 2006
Charles J. Colbourn, Multiple access communications using combinatorial designs, Theoretical aspects of computer science: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2002
traceability scheme;hash family;frameproof code;t-design