Cryptogr. Commun. DOI 10.1007/s12095-016-0182-9

Asymptotically optimal 2-separable codes with length 4 Minquan Cheng1 · Jing Jiang2 · Xiaohu Tang1

Received: 6 July 2015 / Accepted: 19 January 2016 © Springer Science+Business Media New York 2016

Abstract Multimedia fingerprinting is an effective technique to trace the sources of pirate copies of copyrighted multimedia information. Separable codes can be used to construct fingerprints resistant to the averaging collusion attack on multimedia contents. In this paper, we first show an equivalent condition of a 2-SC(4, M, q), and then construct two infinite families of 2-SCs of length 4, one of which is asymptotically optimal. Keywords Multimedia fingerprinting · Separable code · Asymptotically optimal Mathematics Subject Classification (2010) 94B25 · 68P30

1 Introduction Let n, M and q be positive integers, and Q an alphabet with |Q| = q. A set C = {c1 , c2 , . . . , cM } ⊆ Qn is called an (n, M, q) code and each c = (c1 , c2 , . . . , cn ) ∈ C is

 Jing Jiang

[email protected] Minquan Cheng [email protected] Xiaohu Tang [email protected] 1

Information Security and National Computing Grid Laboratory, Southwest Jiaotong University, Chengdu, China

2

Guangxi Key Laboratory of Multi-source Information Mining & Security, Guangxi Normal University, Guilin, China

Cryptogr. Commun.

called a codeword. Without loss of generality, we may assume Q = {0, 1, . . . , q −1}. When Q = {0, 1}, we also use the word “binary”. For any code C ⊆ Qn , we define the set of ith coordinates of C as

C (i) = {ci ∈ Q | c = (c1 , c2 , . . . , cn ) ∈ C } for any 1 ≤ i ≤ n. For any subset of codewords C0 ⊆ C , we define the descendant code of C0 by desc(C0 ) = {(c1 , c2 , . . . , cn ) ∈ Qn | ci ∈ C0 (i), 1 ≤ i ≤ n},

that is, desc(C0 ) = C0 (1) × C0 (2) × . . . × C0 (n).

The set desc(C0 ) consists of the n-tuples that could be produced by a coalition holding the codewords in C0 . Using the notions of descendant codes and sets of ith coordinates of codes, we can define the following class of codes. Definition 1 Suppose that C is an (n, M, q) code and t ≥ 2 is an integer. C is a t-separable code, or t-SC(n, M, q), if for any C1 , C2 ⊆ C such that |C1 | ≤ t, |C2 | ≤ t and C1  = C2 , we have desc(C1 ) = desc(C2 ), that is, there is at least one coordinate i, 1 ≤ i ≤ n, such that C1 (i) = C2 (i). Separable codes can be used to construct multimedia fingerprint codes which can effectively identify the sources of pirate copies of copyrighted multimedia data, see, e.g., [5, 6, 11]. They are of interest in combinatorics and can be also used to study the classic digital fingerprint codes like identifiable parent property (IPP) codes [8, 9], frameproof codes (FPCs) [1, 3], perfect hash families (PHFs) [10] and so on. Cheng and Miao [6] pointed that IPP codes, FPCs, PHFs and some other structures in digital fingerprinting are in fact special examples of separable codes. Since the size M of t-SC(n, M, q) corresponds to the number of fingerprints assigned to authorized users, we should try to construct separable codes with size M as large as possible, given length n. Let M(t, n, q) = max{M | there exists a t − SC(n, M, q)}. A tSC(n, M, q) is said to be optimal if M = M(t, n, q), and a family of q-ary t-SCs of length M = 1. n is asymptotically optimal if lim q→∞ M(t,n,q) ·

Cheng and Miao [6] first gave an upper bound on the size of a t-SC(n, M, q). Lemma 1 [5] M(t, n, q) ≤ q n−1 + any positive integer q.

q(q−1) 2 .

Furthermore, M(2, 3, q) = q 2 +

q(q−1) 2

for

However, the upper bound is not tight sometimes. For example, for the case (t, n) = (2, 2), an even tighter upper bound can be obtained. Furthermore, some optimal 2-SCs of length 2 were obtained.

Cryptogr. Commun. √ 4q−3 , and 2

Theorem 1 [4] For any positive integer q, M(2, 2, q) ≤ qk +t, where k = 1+ ⎧ 0 ⎪ √ ⎪ ⎪ ⎪ (3k2 +k−1)− 5k 4 +6k 3 −k 2 −2k+1 ⎪  ⎨ 2 t = (k−1)q  (k+1)2 −(q+1) ⎪ ⎪ ⎪ ⎪ k2 − k ⎪ ⎩ 2 k

if k 2 − k + 1 ≤ q ≤ k 2 − 1; if if if if

q = k2 ; k 2 + 1 ≤ q ≤ k 2 + k − 2; q = k 2 + k − 1; q = k 2 + k.

Furthermore, M(2, 2, q) = qk +h if q ∈ {k 2 −1, k 2 +k −2, k 2 +k −1, k 2 +k, k 2 +k +1} for any prime power k ≥ 2. From Lemma 1 and Theorem 1, Gao and Ge [7] derived two upper bounds by “grouping coordinates” of a separable code. n

n

Lemma 2 [7] Suppose n ≥ 3 and n = 4. Then M(t, n, q) ≤ 32 q 2 3 − 12 q 3 . √ c 4q −3 , 2

Lemma 3 [7] Let c = n2 . Then M(2, n, q) ≤ kq c + s, where k = 1+ ⎧ 0 ⎪ √ ⎪ ⎪ ⎪ (3k 2 +k−1)− 5k 4 +6k 3 −k 2 −2k+1 ⎪  ⎨ 2 c s = (k−1)q ⎪ (k+1)2 −(q c +1)  ⎪ ⎪ 2 ⎪ ⎪ ⎩ k2 − k k

and

if q c ≥ k 2 − k + 1 and q c ≤ k 2 − 1; if q c if q c if q c if q c

= k2; ≤ k 2 + k − 2 and q c ≥ k 2 + 1; = k 2 + k − 1; = k 2 + k.

Recently, Blackburn [2] improved the upper bound in Lemma 2. 2n

n

n

Lemma 4 [2] M(2, n, q) ≤ q 3 + 12 q 3  (q 3  − 1). For more details on separable codes, the interested reader may refer to [2, 4–7]. Consider the case (t, n) = (2, 4). Applying Lemma 4 with n = 4, we can have M(2, 4, q) ≤ q 3 + q(q−1) 2 . Gao and Ge [7] showed that a 2-SC(4, M, q) with M = 8 1 3 8 (3q

4

− q 3 ) exists. In this paper, we mainly study 2-SCs with codeword length 4. First a equivalent condition of a 2-SC(4, M, q) is derived. Based on this condition, we give a recursive construction of 2-SCs of length 4. Then we propose a construction of a family of 2-SC(4, M, q) with M ∼ q 3 for any prime power q. Clearly, this family of SCs is asymptotically optimal according to Lemma 4.

2 Conditions for a length 4 code to be 2-SC In this section, we first give a necessary and sufficient condition for a 2-SC(4, M, q). Then we give a recursive construction of 2-SCs of length 4. In order to present our main results, the following notations are needed.

Cryptogr. Commun.

For any (n, M, q) code C over Q, we define the 3-tuple vector sets A1i and 2-tuple vector sets A1,2 i,k for i, k ∈ Q as follows:

A1i = {(c2 , c3 , c4 )| (c1 , c2 , c3 , c4 ) ∈ C , c1 = i}, A1,2 i,k = {(c3 , c4 ) | (c1 , c2 , c3 , c4 ) ∈ C , c1 = i, c2 = k}. j

j ,j2

1 Similarly, Ai 1 and Ai,k

j

j

j

for 1 ≤ j1 = j2 ≤ 4 can be also defined. Obviously, Ai11 ⊆ Q3 j

j ,j

1 and |A01 | + |A11 | + . . . + |Aq−1 | = M for any integer j1 ∈ {1, 2, 3, 4}. Ai11,k12 ⊆ Q2 and

j ,j

j ,j

j ,j

1 2 1 2 1 2 | + |A0,1 | + . . . + |Aq−1,q−1 | = M hold for any integers j1 , j2 , where 1 ≤ j1  = |A0,0 j2 ≤ 4.

Theorem 2 A (4, M, q) code C is a 2-SC(4, M, q) on Q if and only if the following two conditions hold. j  j (1) |Ai11 Ai21 | ≤ 1 holds for any positive integer j1 ∈ {1, 2, 3, 4} and distinct i1 , i2 ∈ Q. j ,j  j ,j (2) |Ai11,k12 Ai21,k22 | ≤ 1 holds for any vector (j1 , j2 ) ∈ {(1, 2), (1, 3), (1, 4)} and i1 , i2 , k1 , k2 ∈ Q, where i1 = i2 and k1 = k2 . Proof First, let C be a 2-SC(4, M, q). (I)

(II)

Suppose that there exist j1 ∈ {1, 2, 3, 4} and distinct i1 , i2 ∈ Q, such that j  j |Ai11 Ai21 | ≥ 2. Without loss of generality, we may assume j1 = 1. Let a1  and a2 be two distinct elements of A1i1 A1i2 , then desc({(i1 , a1 ), (i2 , a2 )}) = desc({(i1 , a2 ), (i2 , a1 )}), which is a contradiction to the definition of a 2-SC. Suppose that there exist (j1 , j2 ) ∈ {(1, 2), (1, 3), (1, 4)} and i1 , i2 , k1 , k2 ∈ Q, where j ,j  j ,j i1 = i2 and k1 = k2 , such that |Ai11,k12 Ai21,k22 | ≥ 2. Without loss of generality, we  1,2 Ai2 ,k2 , then desc({(i1 , k1 , b1 ), may assume (j1 , j2 ) = (1, 2). Let {b1 , b2 } ⊆ A1,2 i1 ,k1 (i2 , k2 , b2 )}) = desc({(i1 , k1 , b2 ), (i2 , k2 , b1 )}), which is a contradiction to the definition of a 2-SC.

Conversely, suppose that conditions (1) and (2) always hold. We want to show that C is a 2-SC(4, M, q). Assume that C is not a 2-SC(4, M, q). Then there exist C1  = C2 ⊆ C , such that desc(C1 ) = desc(C2 ). (I) (II)

|C1 | = 1 or |C2 | = 1. Obviously, in this case, we can obtain C1 = C2 , a contradiction. |C1 | = 2 or |C2 | = 2. Suppose that C1 = {a, b} and C2 = {c, d}, where a = (a1 , a2 , a3 , a4 ), b = (b1 , b2 , b3 , b4 ), c = (c1 , c2 , c3 , c4 ), d = (d1 , d2 , d3 , d4 ). If b = d, then {a1 , b1 } = {b1 , c1 }, {a2 , b2 } = {b2 , c2 }, {a3 , b3 } = {b3 , c3 } and {a4 , b4 } = {b4 , c4 }, that is, a1 = c1 , a2 = c2 , a3 =  c3 and a4 = c4 . This implies a = c, a contradiction. Hence we can suppose that C1 C2 = ∅. This can be divided into the following subcases: {a1 , b1 } = {c1 , d1 }: (1.1) a1 = b1 = c1 = d1 ; (1.2) a1  = b1 , a1 = c1 , b1 = d1 ; (1.3) a1 = b1 , a1 = d1 , b1 = c1 . (2) {a2 , b2 } = {c2 , d2 }: (2.1) a2 = b2 = c2 = d2 ; (2.2) a2  = b2 , a2 = c2 , b2 = d2 ; (2.3) a2 = b2 , a2 = d2 , b2 = c2 . (3) {a3 , b3 } = {c3 , d3 }: (3.1) a3 = b3 = c3 = d3 ; (3.2) a3  = b3 , a3 = c3 , b3 = d3 ; (3.3) a3 = b3 , a3 = d3 , b3 = c3 .

(1)

Cryptogr. Commun.

(4)

{a4 , b4 } = {c4 , d4 }: (4.1) a4 = b4 = c4 = d4 ; (4.2) a4  = b4 , a4 = c4 , b4 = d4 ; (4.3) a4 = b4 , a4 = d4 , b4 = c4 .

So we only need to check each of 81 cases {(1.i1 ), (2.i2 ), (3.i3 ), (4.i4 )} for a, b, c and d, where i1 , i2 , i3 , i4 ∈ {1, 2, 3, 4}. Let us consider the 4-tuple vector (i1 , i2 , i3 , i4 ). In fact, we can divide the 81 cases into 15 classes based on the following notation. For each vector (i1 , i2 , i3 , i4 ), let S(i1 ,i2 ,i3 ,i4 ) contain all the vectors which can be obtained by changing some coordinates of (i1 , i2 , i3 , i4 ). Then S(1,1,1,1) = {(1, 1, 1, 1)}; S(1,1,1,2) = {(1, 1, 1, 2), (1, 1, 2, 1), (1, 2, 1, 1), (2, 1, 1, 1)}; S(1,1,1,3) = {(1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), (3, 1, 1, 1)}; S(1,1,2,2) = {(1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 1), (2, 1, 1, 2), (2, 1, 2, 1), (2, 2, 1, 1)}; S(1,1,2,3) = {(1, 1, 2, 3), (1, 1, 3, 2), (1, 2, 1, 3), (1, 2, 3, 1), (1, 3, 1, 2), (1, 3, 2, 1), (2, 1, 1, 3), (2, 1, 3, 1), (2, 3, 1, 1), (3, 1, 1, 2), (3, 1, 2, 1), (3, 2, 1, 1)}; S(1,1,3,3) = {(1, 1, 3, 3), (1, 3, 1, 3), (1, 3, 3, 1), (3, 1, 1, 3), (3, 1, 3, 1), (3, 3, 1, 1)}; S(1,2,2,2) = {(1, 2, 2, 2), (2, 1, 2, 2), (2, 2, 1, 2), (2, 2, 2, 1)}; S(1,2,2,3) = {(1, 2, 2, 3), (1, 2, 3, 2), (1, 3, 2, 2), (2, 1, 2, 3), (2, 1, 3, 2), (2, 2, 1, 3), (2, 2, 3, 1), (2, 3, 1, 2)(2, 3, 2, 1), (3, 1, 2, 2), (3, 2, 1, 2), (3, 2, 2, 1)}; S(1,2,3,3) = {(1, 2, 3, 3), (1, 3, 2, 3), (1, 3, 3, 2), (2, 1, 3, 3), (2, 3, 1, 3), (2, 3, 3, 1), (3, 1, 2, 3), (3, 1, 3, 2), (3, 2, 1, 3)(3, 2, 3, 1), (3, 3, 1, 2), (3, 3, 2, 1)}; S(1,3,3,3) = {(1, 3, 3, 3), (3, 1, 3, 3), (3, 3, 1, 3), (3, 3, 3, 1)}; S(2,2,2,2) = {(2, 2, 2, 2)}; S(2,2,2,3) = {(2, 2, 2, 3), (2, 2, 3, 2), (2, 3, 2, 2), (3, 2, 2, 2)}; S(2,2,3,3) = {(2, 2, 3, 3), (2, 3, 2, 3), (2, 3, 3, 2), (3, 2, 2, 3), (3, 2, 3, 2), (3, 3, 2, 2)}; S(2,3,3,3) = {(2, 3, 3, 3), (3, 2, 3, 3), (3, 3, 2, 3), (3, 3, 3, 2)}; S(3,3,3,3) = {(3, 3, 3, 3)}. Furthermore, we can divide these 15 cases into the following 3 classes. (A)

The cases S(1,1,1,1) , S(1,1,1,2) , S(1,1,1,3) , S(1,1,2,2) , S(1,1,3,3) , S(1,2,2,2) , S(1,3,3,3) , S(2,2,2,2) and S(3,3,3,3) can not occur because the subsets {a, b} and {c, d} would not be disjoint. (B) For the case S(2,2,3,3) , we take (2, 2, 3, 3) as an example. That is, C1 and C2 satisfy {(1.2), (2.2), (3.3), (4.3)} mentioned earlier. In this case, {(a3 , a4 ), (b3 , b4 )} ⊆  1,2  1,2 A1,2 Ab1 ,b2 , a contradiction to the assumption that |A1,2 Ab1 ,b2 | ≤ 1. a1 ,a2 a1 ,a2 Similarly, we can check that the other cases in S(2,2,3,3) are impossible. (C) We claim that the cases S(1,1,2,3) , S(1,2,2,3) , S(1,2,3,3) , S(2,2,2,3) , S(2,3,3,3) can not occur. For the case S(1,2,2,3) , we take (1, 2, 2, 3) as an example. That is, C1 and C2 satisfy {(1.1), (2.2), (3.2), (4.3)} mentioned earlier. In this case,  {(a1 , a2 , a3 ), (a1 , b2 , b3 )} ⊆ A4a4 A4b4 , a contradiction to the assumption that  |A4a4 A4b4 | ≤ 1. Similarly, we can check that the other cases in S(1,2,2,3) are impossible. We can also prove that the cases S(1,1,2,3) , S(1,2,3,3) , S(2,2,2,3) , S(2,3,3,3) can not occur with the same method. Therefore, C is a 2-SC(4, M, q).

Cryptogr. Commun.

3 A recursive construction j  j Theorem 3 Let B be a 2-SC(4, M, q) on Q. If |Ai11 Ai21 | = 0 always holds for any positive integer j1 ∈ {1, 2, 3, 4} and i1 = i2 ∈ Q , then there exists a 2-SC(4, s 2 M, sq) for any odd integer s.

Proof We construct the desired 2-SC(4, s 2 M, sq) on Zs × Q as follows. Let

C = {((i  , i), (k  , k), (x  , x), (y  , y)) |(i, k, x, y) ∈ B , i  , k  , x  , y  ∈ Zs , x  = i  + k  , y  = −i  + k  }. Obviously, |C | = s 2 M. We will show that C is a 2-SC(4, s 2 M, sq) on Zs × Q. Assume that C is a not a 2-SC(4, s 2 M, sq). Then from Theorem 2, there is at least one of the following cases should occur. (1)

Suppose there exist two distinct pairs (i1 , i1 ) and (i2 , i2 ) ∈ Zs × Q such that   |A1(i  ,i ) A1(i  ,i ) | ≥ 2. Let ((k  , k), (x  , x), (y  , y)) ∈ A1(i  ,i ) A1(i  ,i ) . Then 1 1

2 2

1 1

2 2

((i1 , i1 ), (k  , k), (x  , x), (y  , y)), ((i2 , i2 ), (k  , k), (x  , x), (y  , y)) ∈ C . From our construction, we can derive that (i1 , k, x, y), (i2 , k, x, y) ∈ B and i1 = x  − k  = i2 ,   which implies i1 = i2 . Then we have (k, x, y) ∈ A1i1 A1i2 and |A1i1 A1i2 | ≥ 1, a contradiction to our assumption.  j j Similarly, we can prove that |A(i  ,i ) A(i  ,i ) | ≤ 1 for any j ∈ {2, 3, 4}, and any two 1 1

distinct pairs (i1 , i1 ) and (i2 , i2 ) ∈ Zs × Q. (2)

2 2

Suppose there exist (i1 , i1 ) = (i2 , i2 ), (k1 , k1 ) = (k2 , k2 ) ∈ Zs × Q such that  1,2 |A1,2 A(i  ,i ),(k ,k ) | ≥ 2. (i  ,i ),(k  ,k ) 1 1

1

1

2 2

2

2

Let ((x1 , x1 ), (y1 , y1 )) = ((x2 , x2 ), (y2 , y2 )) ∈ A1,2 (i  ,i

 1 1 ),(k1 ,k1 )



A1,2 (i  ,i

 2 2 ),(k2 ,k2 )

.

Then ((i1 , i1 ), (k1 , k1 ), (x1 , x1 ), (y1 , y1 )), ((i1 , i1 ), (k1 , k1 ), (x2 , x2 ), (y2 , y2 )), (k2 , k2 ), (x1 , x1 ), (y1 , y1 )), ((i2 , i2 ), (k2 , k2 ), (x2 , x2 ), (y2 , y2 )) ∈ C . From our construction, we can derive that ((i2 , i2 ),

(i1 , k1 , x1 , y1 ), (i1 , k1 , x2 , y2 ), (i2 , k2 , x1 , y1 ), (i2 , k2 , x2 , y2 ) ∈ B and x1 = x2 = i1 + k1 = i2 + k2 , y1 = y2 = −i1 + k1 = −i2 + k2 . That is 2i1 = 2i2 . Since s is odd, we have i1 = i2 . Hence i1  = i2 and k1 = k2 ,  1,2 which implies k1 = k2 . Then we have (x1 , y1 ), (x2 , y2 ) ∈ A1,2 Ai2 ,k2 . Since i1 ,k1 ((x1 , x1 ), (y1 , y1 )) = ((x2 , x2 ), (y2 , y2 )), x1 = x2 and y1 = y2 , we have (x1 , y1 )  =  1,2 (x2 , y2 ). That is |A1,2 Ai2 ,k2 | ≥ 2, a contradiction to the fact that B is a 2-SC. i1 ,k1 Similarly, we can also prove that for any (i1 , i1 ) = (i2 , i2 ), (k1 , k1 )  = (k2 , k2 ) ∈ Zs ×Q, ≤ 1 always holds, where (j1 , j2 ) ∈ {(1, 3), (1, 4)}.

 j ,j j ,j |A(i1 ,i2 ),(k  ,k ) A(i1 ,i2 ),(k  ,k ) | 1 1 1 1 2 2 2 2

Based on the discussions above, we have C is a 2-SC(4, s 2 M, sq). This completes the proof.

Cryptogr. Commun.

4 Constructions In this section, from Theorem 2, a sufficient condition of a 2-SC(4, M, q) is obtained. We then construct a family of asymptotically optimal 2-SCs of length 4 based on the sufficient condition. The Hamming distance between two codewords c1 and c2 , denoted by d(c1 , c2 ), is the number of positions where c1 and c2 have different symbols. The minimum distance of a code is then defined to be the smallest distance between two distinct codewords. (i)

(i)

Lemma 5 Let C be a (4, M, q) code, where c = (i, k, x, ak,x ) ∈ C , i, k, x, ak,x ∈ Q. Then C is a 2-SC(4, M, q) if it satisfies the following conditions: (a) (b)

The minimum distance of C is at least 2; (i ) (i ) For any i1 = i2 , k1 = k2 ∈ Q, there exists at most one x ∈ Q such that ak11,x = ak22,x ;

(c)

For any i1 = i2 , x1 = x2 ∈ Q, there exists at most one k ∈ Q such that ak,x1 1 = ak,x2 2 ;

(d)

For any i1 = i2 ∈ Q and any (k1 , x1 ) = (k2 , x2 ) ∈ Q2 , (ak11,x1 , ak12,x1 )  =

(i )

(i )

(i )

(i )

(i ) (i ) (ak21,x2 , ak22,x2 ).

Proof Now we check the conditions of Theorem 2. j  j (1) According to condition (a), |Ai11 Ai21 | ≤ 1 always holds for any positive integer j1 ∈ {1, 2, 3, 4} and distinct i1 , i2 ∈ Q.  1,2 (2) Suppose there exist i1 = i2 , k1 = k2 ∈ Q, such that |A1,2 Ai2 ,k2 | ≥ 2. i1 ,k1 1,2  1,2 Let (x1 , y1 ) = (x2 , y2 ) ∈ Ai1 ,k1 Ai2 ,k2 . Then (i1 , k1 , x1 , y1 ), (i1 , k1 , x2 , y2 ), (i )

(i )

(i )

(i )

(i2 , k2 , x1 , y1 ), (i2 , k2 , x2 , y2 ) ∈ C , so ak11,x1 = ak22,x1 = y1 , ak11,x2 = ak22,x2 = y2 , and x1 = x2 from the fact d((i1 , k1 , x1 , y1 ), (i1 , k1 , x2 , y2 )) ≥ 2. This is a contradiction to condition (b).  1,3  1,4 Ai2 ,k2 | ≤ 1 and |A1,4 Ai2 ,k2 | ≤ 1 always Similarly, we can prove that |A1,3 i1 ,k1 i1 ,k1 hold. According to Theorem 2, C is a 2-SC(4, M, q). This completes the proof. According to Lemma 5, we construct 2-SCs of length 4 as follows.

Theorem 4 There exists a 2-SC(4, (q − 2)(q 2 − q), q) for any prime power q > 2. Proof Let Q = GF(q). We can define a (4, M, q) code as follows: (i) (i) C = {(i, k, x, ak,x ) | ak,x = (x − k)i + k, x, k, i ∈ GF (q) \ {0, 1}, x  = k}.

We only need to check the conditions in Lemma 5. (a) (b)

Obviously, according to the construction, any three coordinates fix a codeword, which implies condition (a) in Lemma 5 holds. Suppose there exist i1 = i2 ∈ GF(q) \ {0, 1}, k1 = k2 , such that there exist x1  = x2 ∈ GF(q) satisfying that kh = xl , 1 ≤ h, l ≤ 2 , ak(i11,x) 1 = ak(i22,x) 1 and ak(i11,x) 2 = ak(i22,x) 2 . Then we have (x1 − k1 )i1 + k1 = (x1 − k2 )i2 + k2

Cryptogr. Commun.

and (x2 − k1 )i1 + k1 = (x2 − k2 )i2 + k2 .

(c) (d)

This implies (x1 − x2 )(i1 − i2 ) = 0, a contradiction to our assumptions x1  = x2 and i1 = i2 . Similar to the above, condition (c) in Lemma 5 holds. Suppose there exist i1 = i2 ∈ GF(q) \ {0, 1}, (k1 , x1 )  = (k2 , x2 ) ∈ GF(q) × GF(q), such that kh = xl , 1 ≤ h, l ≤ 2, and (ak(i11,x) 1 , ak(i12,x) 1 ) = (ak(i21,x) 2 , ak(i22,x) 2 ). That is ak(i11,x) 1 = (i )

(i )

(i )

ak21,x2 and ak12,x1 = ak22,x2 . Then we have (x1 − k1 )i1 + k1 = (x2 − k2 )i1 + k2 and (x1 − k1 )i2 + k1 = (x2 − k2 )i2 + k2 . That is ((x1 − x2 ) + (k2 − k1 ))i1 + (k1 − k2 ) = 0 and ((x1 − x2 ) + (k2 − k1 ))i2 + (k1 − k2 ) = 0. Since i1 and i2 are two distinct elements of Q, we have (x1 − x2 ) + (k2 − k1 ) = 0 and (k1 − k2 ) = 0. This implies (k1 , x1 ) = (k2 , x2 ), a contradiction to our assumption (k1 , x1 )  = (k2 , x2 ). Clearly, M = (q − 2)(q 2 − q). From Lemma 5, C is a 2-SC(4, (q − 2)(q 2 − q), q). This completes the proof. In fact, the above family of 2-SCs is asymptotically optimal, as lim

q→∞

(q − 2)(q 2 − q) q3 +

q(q−1) 2

2q 3 − 6q 2 + 4q = 1. q→∞ 2q 3 + q 2 − q

= lim

The following result comes from Theorems 3 and 4. Corollary 1 For any odd positive integer s and prime power q, there exists a 2-SC(4, s 2 (q− 2)(q 2 − q), sq).

5 Conclusions In this paper, we first obtained an equivalent condition of a 2-SC(4, M, q). Based on this condition, we gave a recursive construction of 2-SCs of length 4. Then we proposed a construction of a family of 2-SCs of length 4 with the size M = (q − 2)(q 2 − q), which is asymptotically optimal. Acknowledgments The authors express their sincere thanks to the two anonymous reviewers for their valuable comments and suggestions in revising this paper, and to the editor for his/her excellent editorial job.This work is in part supported by NSFC (No.11301098), Guangxi Natural Science Foundations

Cryptogr. Commun. (No.2013GXNSFCA019001 and 2014GXNSFDA118001), Guangxi Higher Institutions’ Program of Introducing 100 High-Level Overseas Talents, Guangxi Collaborative Innovation Center of Multi-source Information Integration and Intelligent Processing, and Guangxi “Bagui Scholar” Teams for Innovation and Research.

References 1. Blackburn, S.R.: Frameproof codes. SIAM J. Discret. Math. 16, 499–510 (2003) 2. Blackburn, S.R.: Probabilistic existence results for separable codes. IEEE Trans. Inf. Theory 61, 5822– 5827 (2015) 3. Boneh, D., Shaw, J.: Collusion-secure fingerprinting for digital data. IEEE Trans. Inf. Theory 44, 1897– 1905 (1998) 4. Cheng, M., Fu, H.-L., Jiang, J., Lo, Y.-H., Miao, Y.: New bounds on 2-separable codes of length 2. Des. Codes Cryptogr. 74, 31–40 (2015) 5. Cheng, M., Ji, L., Miao, Y.: Separable codes. IEEE Trans. Inf. Theory 58, 1791–1803 (2012) 6. Cheng, M., Miao, Y.: On anti-collusion codes and detection algorithms for multimedia fingerprinting. IEEE Trans. Inf. Theory 57, 4843–4851 (2011) 7. Gao, F., Ge, G.: New bounds on separable codes for multimedia fingerprinting. IEEE Trans. Inf. Theory 60, 5257–5262 (2014) 8. Hollmann, H.D.L., Lint, J.H., Linnartz, J.-P., Tolhuizen, L.M.G.M.: On codes with the identifiable parent property. J. Combin. Theory, Ser. A 82, 121–133 (1998) 9. Staddon, J.N., Stinson, D.R., Wei, R.: Combinatorial properties of frameproof and traceability codes. IEEE Trans. Inf. Theory 47, 1042–1049 (2001) 10. Stinson, D.R., van Trung, T., Wei, R.: Secure frameproof codes, key distribution pattern, group testing algorithms and related structures. J. Stat. Plan. Inference 86, 595–617 (2000) 11. Trappe, W., Wu, M., Wang, Z.J., Liu, K.J.R.: Anti-collusion fingerprinting for multimedia. IEEE Trans. Signal Process 51, 1069–1087 (2003)