# New Bounds on 2-Frameproof Codes of Length 4

Authors: Penying Rochanakul
Journal: International Journal of Mathematics and Mathematical Sciences
 (2020)

---

## Abstract

Frameproof codes were first introduced by Boneh and Shaw in 1998 in the context of digital fingerprinting to protect copyrighted materials. These digital fingerprints are generally denoted as codewords inQn, where Q is an alphabet of size q and n is a positive integer. A 2-frameproof code is a code C such that any 2 codewords in C cannot form a new codeword under a particular rule. Thus, no pair of users can frame a user who is not a member of the coalition. This paper concentrates on the upper bound for the size of a q-ary 2-frameproof code of length 4. Our new upper bound shows that C≤2q2−2q+1 when q is odd and q>10.


---

## Body

## 1. Introduction

In order to protect a digital content, a distributor marks each copy with a codeword. This marking discourages users from releasing an unauthorized copy, since a mark allows the distributor to detect any unauthorized copy and trace it back to the user. However, a coalition of users may detect some of the marks, namely, the ones where their copies differ. Thus, they can forge a new copy by changing these marks arbitrarily. To prevent a coalition of users from “framing” a user outside the coalition, Boneh and Shaw [1] defined the concept of frameproof codes. A w-frameproof code has the property that no coalition of at most w users can frame a user not in the coalition. Frameproof codes are defined as follows.Letq and n be positive integers. Let Q be a set of size q, and let C⊆Qn be a set of words of length n over the alphabet Q. Each codeword x∈C can be represented as x=x1,x2,…,xn, where xi∈Q for all i∈1,2,…,n. The set of descendants of X⊆C, descX, is defined as(1)descX=c∈Qn:ci=xifor somex∈X.Definition 1.
Letw be an integer such that w≥2. A w-frameproof code is a subset C⊆Qn such that for all X⊆C with X≤w, we have that descX∩C=X.Example 1.
LetC=0,0,0,0,0,1,2,2,0,2,1,2,0,2,2,1,1,1,1,1,1,2,0,0,1,0,0,2,1,0,2,0,2,2,2,2,2,0,1,1,2,1,0,1,2,1,1,0. Then, C is a 3-ary 2-frameproof code of length 4.
As the number of codewords in the code corresponds to the number of authorized users in the digital copyright protection system, one of the classical question regarding frameproof codes is what is the largest cardinalityMn,wq of a w-frameproof code of length n over an alphabet of size q? This paper concentrates on the special case when w=2, n=4, and q is large.
There has been extensive study on the upper bound and lower bound on the size of frameproof codes [2–11]. Some of those are in separating hash families’ language [3, 6, 10, 11]. Previous bounds are restated as follows.Theorem 1 (see [2]).
Letq, n, and w be positive integers such that q≥2 and 2≤n≤w. Then,(2)Mn,wq=nq−1.Theorem 2 (see [2]).
Letn be a positive even integer such that n≥4. Let m be a prime power such that m≥n+1. Let q=m2+1. There exists a q-ary 2-frameproof code of length n of size(3)2q−1n/21−1/2q−1.Theorem 3 (see [4]).
There exists aq-ary w-frameproof code of length w+2 of size(4)w+2wq−12+1,for all odd q, when w=2, and for all q≡4mod6, when w=3.For 2-frameproof codes of length 4, Theorem3 only gives lower bound for odd q. For even q, we first use only q−1 symbols to construct a q−1-ary 2-frameproof code of size 2q−22+1. Then, add a codeword α,α,α,α to the code, where α is the unused symbol. Thus, the following result on the lower bound of M4,2q is obtained.Corollary 1 (see [4]).
For any positive integerq,(5)M4,2q≥2q−12+1,whenqis odd,2q−22+2,whenqis even.In 2003, Blackburn proved the following upper bound ofw-frameproof codes.Theorem 4 (see [2]).
For any positive integersq, n, and w≥2, if C is a q-ary w-frameproof code of length n, then(6)C≤maxqn/w,rqn/w−1+w−rqn/w−1,where r is a unique integer in 0,1,2,…,w−1 such that r=nmodw.Whenn=4 and w=2, the following result on the upper bound of M4,2q is obtained.Corollary 2.
For any positive integerq,(7)M4,2q≤2q2−2.Much later on, in 2019, Cheng et al. proved the following theorem, which is the best previously known result on the upper bound of 2-frameproof code of length 4.Theorem 5 (see [5]).
For any positive integerq>48, if C is a q-ary 2-frameproof code of length 4, then(8)C≤2q2−2q+7.Our result is the improved version of Theorem5. We aim to prove the following theorem.Theorem 6.
For any odd positive integerq>10, if C is a q-ary 2-frameproof code of length 4, then(9)C≤2q2−2q+1.We analyze the combinatorial structure of a code, setting up an optimization problem, deriving some constraints, and solving this optimization problem to obtain Theorem6. The gap between the lower bound of odd and even q in Corollary 1 is the key motivation for proving the main result. The rest of this paper is ordered as follows. In Section 2, the essential·notations are defined. Necessary conditions of a q-ary 2-frameproof code of length 4 are also stated. In Section 3, the proof of Theorem 6 is provided. We conclude the result in the last section.


## 2. Preliminaries

In this section, we define some notations and state relating lemmas that are useful for proving the main theorem.Let4=1,2,3,4. For x=x1,x2,x3,x4∈C, for i∈4, and for any non-empty set I⊆4,(i)
letfix=xi(ii)
letfiX=xi:x∈X, for any X⊆C(iii)
letfIx=fjxj∈I(iv)
letfIX=fIx:x∈X, for any X⊆CWe sayx is unique under I if z∈C:fIz=fIx=1, and we say x is nonunique under I when z∈C:fIz=fIx>1.For anyI⊆4, let UI=x∈C:xis unique underI and VI=x∈C:xnonunique  underI.Remark.
It is easy to see that for any nonempty subsetsI,J⊂4, the following conditions hold:(i)
UI∩VI=∅(ii)
C=UI∪VI(iii)
UI⊆UJ, for any I⊆J⊆4Lemma 1.
LetC be a q-ary 2-frameproof code of length 4. For any x=x1,x2,x3,x4∈C and any nonempty subset I⊂4, if x∈VI, then x∈UI′, where I′=4\I.Proof.
Letx∈VI. Then, there exists y∈C\x such that fIx=fIy.
Assumex∉UI′. Then, x∈VI′. Thus, there exists z∈C\x such that fI′x=fI′z. Hence, x∈descy,z. This contradicts the 2-frameproof property of C.
For convenience, we set up some parameters. Leth1=V2,3,4, h2=V1,3,4, h3=V1,2,4, and h4=V1,2,3. Without loss of generality, we assume h1≥h2≥h3≥h4.
Consider(10)C=U1,2,3∪V1,2,3=U1,2,3∩C∪V1,2,3=U1,2,3∩U3,4∪V3,4∪V1,2,3=U1,2,3∩U3,4∪U1,2,3∩V3,4∪V1,2,3.
From Lemma 1, we can see thatV3,4⊆U1,2⊆U1,2,3. Therefore, U1,2,3∩V3,4=V3,4. Since U1,2,3∩U3,4,V3,4, and V1,2,3 are all pairwise disjoints, we have(11)C=U1,2,3∩U3,4+V3,4+h4.
Hence, we can deduce upper bound ofC from the upper bounds of U1,2,3∩U3,4, V3,4, and V1,2,3. The following sections are dedicated to the upper bounds of U1,2,3∩U3,4, V3,4, and V1,2,3.


### 2.1. Upper Bound ofU1,2,3∩U3,4

This section gives the upper bound of the first component of equation (11).Lemma 2.
SupposeC is a q-ary 2-frameproof code of length 4. Then,(12)U1,2,3∩U3,4≤q2−qh4−f3,4V3,4.Proof.
Assumex∈U1,2,3. Then, we have that x∈U1,2,3 and thus f4x∉f4V1,2,3. Clearly, there are at most qq−h4 choices of f3,4x. Thus,(13)f3,4U1,2,3∩U3,4+f3,4U1,2,3∩V3,4≤q2−qh4.
From the definition ofU3,4, all x in U3,4 has different values of f3,4x. This makes f3,4U1,2,3∩U3,4=U1,2,3∩U3,4. So,(14)U1,2,3∩U3,4+f3,4U1,2,3∩V3,4≤q2−qh4.
SinceU1,2,3∩V3,4=V3,4, then f3,4U1,2,3∩V3,4=f3,4V3,4. Therefore,(15)U1,2,3∩U3,4≤q2−qh4−f3,4V3,4,as required.
We use this lemma to find constrains on the upper bound ofVi,j,k. Then, after Section 2.3, we eliminate the term qh4 before proving the main theorem.


### 2.2. Upper Bound ofV3,4

This section gives the upper bound of the second component of equation (11). It gives the same results as [5]. We put it here for completeness. We find an upper bound of V3,4 by counting elements in f1,2,3C.Lemma 3.
SupposeC is a q-ary 2-frameproof code of length 4. Then,(16)V3,4≤q2−U1,2,3∩U3,4q−h1+h2q−1+h1h2.Proof.
Assumex∈U1,2,3∩V3,4. Then, x is nonunique under 3,4. Therefore, x must be unique under 1,2. Thus, when c≠f3x, the triple f1x,f2x,c is a forbidden value in f1,2,3C. We say x contributes at least q−1 forbidden values in f1,2,3C. And hence we can eliminate(17)V3,4q−1,values from f1,2,3C.
Here, we reduce the size off1,2,3C further. Let h1=U1,2,3∩V2,3,4=V2,3,4 and h2=U1,2,3∩V1,3,4=V1,3,4. Assume x∈V2,3,4. Then, x must be an element of U1. Therefore, x must be unique under 1. Thus, when b,c≠f2,3x, the triple f1x,b,c is a forbidden values in f1,2,3C. We say x contributes at least q2−1 forbidden values in f1,2,3C. To sum up, V2,3,4 contributes at least(18)h1q2−1,forbidden values in f1,2,3C. Similarly, V1,3,4 contributes at least(19)h2q2−1,forbidden values in f1,2,3C. However, the triple in the form of f1x,f2y,c, where x∈V2,3,4,y∈V1,3,4,andc∈Q will be counted twice. Thus, together, V2,3,4 and V1,3,4 eliminate(20)h1+h2q2−1−h1h2q,values from f1,2,3C.
Furthermore,V2,3,4 and V1,3,4 are subsets of V3,4. This makes h1+h2q−1 forbidden values counted twice in equations (17) and (20). Thus, we obtain at least(21)V3,4q−1+h1+h2qq−1−h1h2q,different forbidden values in f1,2,3C from this step.
Hence,(22)f1,2,3C≤q3−V3,4q−1−h1+h2qq−1+h1h2q.
SinceU1,2,3∩U3,4 and V3,4 form a partition of U1,2,3, we have(23)f1,2,3U1,2,3=V3,4+U1,2,3∩​U3,4.
From equations (22) and (23), we have(24)V3,4+U1,2,3∩​U3,4≤f1,2,3C≤q3−V3,4q−1−h1+h2qq−1+h1h2q.
Thus,(25)V3,4≤q2−U1,2,3∩U3,4q−h1+h2q−1+h1h2.
We use this lemma to find constrains on the upper bound ofVi,j,k in the next section.


### 2.3. Upper Bound ofVi,j,k

This section aim to eliminate the third component of equation (11). Recall that we define h1=V2,3,4, h2=V1,3,4, h3=V1,2,4, and h4=V1,2,3.Lemma 4.
SupposeC is a q-ary 2-frameproof code of length 4 such that q≥3.
Ifh1≥h2≥h3≥h4, then h2=h3=h4=0 and h1∈0,2,3.Proof.
From equation (11), Lemma 2 and Lemma 3, we have(26)C=U1,2,3∩U3,4+V3,4+h4≤U1,2,3∩U3,4+q2−U1,2,3∩U3,4q−h1+h2q−1+h1h2+h4=U1,2,3∩U3,41−1q+q2−h1+h2q−1+h1h2+h4≤q2−qh4−f3,4V3,41−1q+q2−h1+h2q−1+h1h2+h4=2q2−q−h4q−2−f3,4V3,41−1q−h1+h2q−1+h1h2≤2q2−q−f3,4V3,41−1q−h1+h2q−1+h1h2.
From Corollary1, we have that there always exists a q-ary 2-FP code of size 2q−12+1 for any positive odd integer q. So, we have(27)2q−12+1≤C≤2q2−q−f3,4V3,41−1q−h1+h2q−1+h1h2≤2q2−q−h1+h2q−1+h1h2,which can be rewritten as(28)3q−1≥h1+h2q−1−h1h2.
Note that ifh1=q or h2=q, there are at most q codewords in C. We then only consider the case 0≤h1andh2≤q−1. We have(29)3q−1≥h1+h2q−1−q−1h2≥h1q−1.
Hence,(30)0≤h2≤h1≤3.
Substitute in equation (28), we obtain(31)3q−1≥h1+h2q−1−9.
Thus,(32)0≤h1+h2≤3,when q>10.
Since it is impossible to have a single codeword inC, that is, nonunique under i,j,k, then hℓ≠1 for all ℓ∈4. Therefore, if h1≠0, then h1≥2. Thus, with the maximal of h1, we have h2=h3=h4=0. Furthermore, there are only 3 possible cases for h1, which are h1=3, h1=2, and h1=0.Remark.
Note that the conditionq>10 can be removed by substituting corresponding values into equations (28) and (32) repeatedly until a contradiction is reached.


## 2.1. Upper Bound ofU1,2,3∩U3,4

This section gives the upper bound of the first component of equation (11).Lemma 2.
SupposeC is a q-ary 2-frameproof code of length 4. Then,(12)U1,2,3∩U3,4≤q2−qh4−f3,4V3,4.Proof.
Assumex∈U1,2,3. Then, we have that x∈U1,2,3 and thus f4x∉f4V1,2,3. Clearly, there are at most qq−h4 choices of f3,4x. Thus,(13)f3,4U1,2,3∩U3,4+f3,4U1,2,3∩V3,4≤q2−qh4.
From the definition ofU3,4, all x in U3,4 has different values of f3,4x. This makes f3,4U1,2,3∩U3,4=U1,2,3∩U3,4. So,(14)U1,2,3∩U3,4+f3,4U1,2,3∩V3,4≤q2−qh4.
SinceU1,2,3∩V3,4=V3,4, then f3,4U1,2,3∩V3,4=f3,4V3,4. Therefore,(15)U1,2,3∩U3,4≤q2−qh4−f3,4V3,4,as required.
We use this lemma to find constrains on the upper bound ofVi,j,k. Then, after Section 2.3, we eliminate the term qh4 before proving the main theorem.


## 2.2. Upper Bound ofV3,4

This section gives the upper bound of the second component of equation (11). It gives the same results as [5]. We put it here for completeness. We find an upper bound of V3,4 by counting elements in f1,2,3C.Lemma 3.
SupposeC is a q-ary 2-frameproof code of length 4. Then,(16)V3,4≤q2−U1,2,3∩U3,4q−h1+h2q−1+h1h2.Proof.
Assumex∈U1,2,3∩V3,4. Then, x is nonunique under 3,4. Therefore, x must be unique under 1,2. Thus, when c≠f3x, the triple f1x,f2x,c is a forbidden value in f1,2,3C. We say x contributes at least q−1 forbidden values in f1,2,3C. And hence we can eliminate(17)V3,4q−1,values from f1,2,3C.
Here, we reduce the size off1,2,3C further. Let h1=U1,2,3∩V2,3,4=V2,3,4 and h2=U1,2,3∩V1,3,4=V1,3,4. Assume x∈V2,3,4. Then, x must be an element of U1. Therefore, x must be unique under 1. Thus, when b,c≠f2,3x, the triple f1x,b,c is a forbidden values in f1,2,3C. We say x contributes at least q2−1 forbidden values in f1,2,3C. To sum up, V2,3,4 contributes at least(18)h1q2−1,forbidden values in f1,2,3C. Similarly, V1,3,4 contributes at least(19)h2q2−1,forbidden values in f1,2,3C. However, the triple in the form of f1x,f2y,c, where x∈V2,3,4,y∈V1,3,4,andc∈Q will be counted twice. Thus, together, V2,3,4 and V1,3,4 eliminate(20)h1+h2q2−1−h1h2q,values from f1,2,3C.
Furthermore,V2,3,4 and V1,3,4 are subsets of V3,4. This makes h1+h2q−1 forbidden values counted twice in equations (17) and (20). Thus, we obtain at least(21)V3,4q−1+h1+h2qq−1−h1h2q,different forbidden values in f1,2,3C from this step.
Hence,(22)f1,2,3C≤q3−V3,4q−1−h1+h2qq−1+h1h2q.
SinceU1,2,3∩U3,4 and V3,4 form a partition of U1,2,3, we have(23)f1,2,3U1,2,3=V3,4+U1,2,3∩​U3,4.
From equations (22) and (23), we have(24)V3,4+U1,2,3∩​U3,4≤f1,2,3C≤q3−V3,4q−1−h1+h2qq−1+h1h2q.
Thus,(25)V3,4≤q2−U1,2,3∩U3,4q−h1+h2q−1+h1h2.
We use this lemma to find constrains on the upper bound ofVi,j,k in the next section.


## 2.3. Upper Bound ofVi,j,k

This section aim to eliminate the third component of equation (11). Recall that we define h1=V2,3,4, h2=V1,3,4, h3=V1,2,4, and h4=V1,2,3.Lemma 4.
SupposeC is a q-ary 2-frameproof code of length 4 such that q≥3.
Ifh1≥h2≥h3≥h4, then h2=h3=h4=0 and h1∈0,2,3.Proof.
From equation (11), Lemma 2 and Lemma 3, we have(26)C=U1,2,3∩U3,4+V3,4+h4≤U1,2,3∩U3,4+q2−U1,2,3∩U3,4q−h1+h2q−1+h1h2+h4=U1,2,3∩U3,41−1q+q2−h1+h2q−1+h1h2+h4≤q2−qh4−f3,4V3,41−1q+q2−h1+h2q−1+h1h2+h4=2q2−q−h4q−2−f3,4V3,41−1q−h1+h2q−1+h1h2≤2q2−q−f3,4V3,41−1q−h1+h2q−1+h1h2.
From Corollary1, we have that there always exists a q-ary 2-FP code of size 2q−12+1 for any positive odd integer q. So, we have(27)2q−12+1≤C≤2q2−q−f3,4V3,41−1q−h1+h2q−1+h1h2≤2q2−q−h1+h2q−1+h1h2,which can be rewritten as(28)3q−1≥h1+h2q−1−h1h2.
Note that ifh1=q or h2=q, there are at most q codewords in C. We then only consider the case 0≤h1andh2≤q−1. We have(29)3q−1≥h1+h2q−1−q−1h2≥h1q−1.
Hence,(30)0≤h2≤h1≤3.
Substitute in equation (28), we obtain(31)3q−1≥h1+h2q−1−9.
Thus,(32)0≤h1+h2≤3,when q>10.
Since it is impossible to have a single codeword inC, that is, nonunique under i,j,k, then hℓ≠1 for all ℓ∈4. Therefore, if h1≠0, then h1≥2. Thus, with the maximal of h1, we have h2=h3=h4=0. Furthermore, there are only 3 possible cases for h1, which are h1=3, h1=2, and h1=0.Remark.
Note that the conditionq>10 can be removed by substituting corresponding values into equations (28) and (32) repeatedly until a contradiction is reached.


## 3. Main Results

In this section, we aim to prove Theorem6, which is the main theorem.By applying the conditionh2=h3=h4=0 from Lemma 4 to equations (11) and (26), we obtain new equations:(33)C=U1,2,3∩U3,4+V3,4,(34)C≤2q2−q−f3,4V3,41−1q−h1q−1.We also obtain the following corollary from Lemma2.Corollary 3. SupposeC is a q-ary 2-frameproof code of length 4. Then,(35)U1,2,3∩U3,4≤q2−f3,4V3,4.Using equations (33) and (34) and Corollary 3, we now prove Theorem 6.Proof of the Theorem6. Here, f3,4V3,4 is the number of different order pairs f3x,f4x, where x is nonunique in the last two positions. If we remove all codewords in V2,3,4 from C, then h1 symbols from f1V2,3,4 are also eliminated from the first position of the remaining codewords. The condition h2=0 implies V1,3,4=∅. Thus, each order pair in f3,4V3,4 is used at most q−h1 times in the last two positions of remaining codewords. Thus,(36)V3,4−h1≤q−h1f3,4V3,4So, by equations (33) and (36) and Corollary 3, we have(37)C=U1,2,3∩U3,4+V3,4=U1,2,3∩U3,4+V3,4−h1+h1≤q2−f3,4V3,4+q−h1f3,4V3,4+h1.Thus, by Corollary1,(38)2q−12+1≤C≤q2+q−1−h1f3,4V3,4+h1.Hence,(39)f3,4V3,4≥1q−1−h12q−12+1−q2−h1=q,forh1=3,q−1−2q−3,forh1=2,q−3,forh1=0,≥q−3.However, whenq−3≤f3,4V3,4≤q−2, we have C=U1,2,3∩U3,4+V3,4≤U1,2,3∩U3,4+qf3,4V3,4≤q2−q−3+qq−2<2q2−2q. Thus, we only have yet to consider the case that f3,4V3,4≥q−1.Substitutef3,4V3,4≥q−1 in (34), we obtain(40)C≤2q2−q−f3,4V3,41−1q−h1q−1≤2q2−q−q−11−1q=2q2−2q+2−1q.SinceC must be an integer, C≤2q2−2q+1 as required.We show thatC≤2q2−2q+1 for odd q>10. Thus, 2q2−4q+3≤M4,2q≤2q2−2q+1.Example1 gives a 3-ary 2-frameproof of size 12=2q2−2q for q=3, which is very close to the obtained upper bound. However, things could be different for larger q.Considerh1 from the proof of Theorem 6. Notice that for h1≥2, f3,4V3,4 must be an integer. We can conclude that f3,4V3,4≥q−1 for h1=2. Hence, for h1≥2, we have C≤2q2−4q+4−1/q. This implies C≤2q2−4q+3 which is equal to the lower bound. Thus, this could also be investigated further whether it is possible to push the upper bound down to 2q2−4q+3 when h1=0.


## 4. Conclusion

In this paper, we investigate the bounds of 2-frameproof codes with length 4 by observing the structure of a code. The improvement of the upper bound for the case of oddq is derived from the difference between the known lower bound of odd and even q. The paper shows that C≤2q2−2q+1 in the case when q is odd and q>10. Then, if q is large, 2q2−4q+3≤M4,2q≤2q2−2q+1 when q is odd and 2q2−8q+10≤M4,2q≤2q2−2q+7 when q is even. Example 1, for q=3, suggests that the upper bound might be tighter than the lower bound; however, the case of larger q is yet to be determined.



---

*Source: 4879108-2020-01-23.xml*