Bounds and constructions for $\overline {3}$-strongly separable codes with length 3

Abstract

Separable code (SC, Cheng and Miao IEEE Trans. Inf. Theory 57, 4843–4851, 2011), frameproof code (FPC, Boneh and Shaw IEEE Trans. Inf. Theory 44, 1897–1905, 1998) and strongly separable code (SSC, Jiang et al. Des. Codes Cryptogr. 79:303–318, 2016) are used to construct anti-collusion codes. SSC is better than FPC and SC in the applications for multimedia fingerprinting since SSC has lower identifying complexity than that of SC (the same complexity as FPC) and weaker structure than that of FPC. In this paper, we first derive several upper bounds on the number of codewords of a $\overline {t}$-SSC. Then we focus on $\overline {3}$-SSCs with codeword length 3 and obtain the following two main results: (1) An equivalence between an SSC and an SC is derived; (2) An improved lower bound Ω(q ^5/3 + q ^4/3 − q) on the size of a q-ary SSC when $q={q_{1}^{6}}$ for any prime power q ₁ ≡ 1 (mod 6), which is better than the previously known bound $\lfloor \sqrt {q}\rfloor ^{3}$, is obtained by means of a difference matrix and a known result on the subsets of $\mathbb {F}^{n}_{q}$ containing no three points on a line.

1 Introduction

With the advancement of multimedia technologies, coupled with the development of an infrastructure of ubiquitous broadband communication networks, a large amount of multimedia content, such as image, video, audio and speech, is available in the digital marketplace. However, pirate copies are an increasingly serious problems in copyright protection of multimedia contents.

In order to against pirate copies, fingerprinting system, in which each multimedia content has a unique embedded fingerprint, has recently become quite popular in the field of copyright protection for multimedia content. Clearly each customer obtains an embedded version which consists of a unique fingerprint and the same content. Consequently attacks mounted by individuals are no longer a main security issue in digital rights management. However, multiuser could carry out attacks against the embedded fingerprints by comparing their different embedded versions collectively. There are a variety of embedding techniques such as [2, 12, 19]. Spread spectrum embedding technique which can be used to restrict multiuser’s attacking strategy as largely as possible [22], is widely used in fingerprinting systems [6, 12, 18, 22]. Such a system is called multimedia fingerprinting. Averaging attack is one of the most feasible approaches to perform a collusion attack in multimedia fingerprinting [17].

Cheng et al. [11] proposed a concept of a logical anti-collusion code (LACC), which can be used to against the averaging attack. They also showed that separable codes and frampeproof codes can be used to construct LACCs. There are several researches on separable codes and frameproof codes, for instances, [5, 7, 9,10,11, 14] and so on. The LACCs constructed by $\overline {t}$-separable codes can identify all colluders with computation complexity exponential in the number of authorized users, and those constructed by frameproof codes can identify all the colluders with computational complexity linear in the number of authorized users (by Theorem 5.5 and tracing algorithm LACCIdenAlg in [11]). This is in contrast to the fact that frameproof codes have no traceability properties under the embedding technique in [2]. In fact, the number of codewords in a frampeproof code is too small to be of practical use in most cases. Jiang et al. introduced a new concept of a strongly separable code which is weaker than a frameproof code but can also be used to identify all colluders with the same complexity (by Algorithm SSCTraceAlg(R) in [15]) as that of a frameproof code. Usually, strongly $\overline {t}$-separable codes have much more codewords than t-frameproof codes could have. So compared with frameproof codes, strongly separable codes have an advantage in copyright protection. In this paper, we will pay our attention to strongly separable codes.

When t = 2, some strongly $\overline {t}$-separable codes were studied in [15]. Especially the cases of codeword length 2 and 3 were discussed in detail. When t ≥ 3, the structure of a strongly $\overline {t}$-separable code becomes more complex so that little is known about strongly $\overline {t}$-separable codes. In this paper, we will focus on strongly $\overline {t}$-separable codes with t ≥ 3. First several upper bounds and a lower bound on the size of a strongly separable code are derived. Then we further improve the above lower bound when t and codeword length equal 3.

The remainder of the paper is organized as follows. Section 2 introduces preliminaries about separable codes, strongly separable codes and frameproof codes. In Section 3, several upper bounds on the size of strongly separable codes are derived by discussing the relationships among separable codes, strongly separable codes and frameproof codes. In Section 4, an improved lower bound Ω(q ^5/3 + q ^4/3 − q) on the size of a q-ary SSC when $q={q_{1}^{6}}$ for any prime power q ₁ ≡ 1 (mod 6), which is better than the previously known bound $\lfloor \sqrt {q}\rfloor ^{3}$, is obtained. Finally, conclusions are drawn in Section 5.

2 Preliminaries

Let n, M and q be positive integers, and Q an alphabet with |Q| = q. A set $\mathcal {C} =\{\mathbf {c}_{1},\mathbf {c}_{2},\ldots , \mathbf {c}_{M}\} \subseteq Q^{n}$ is called an (n,M,q) code and each c _i is 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 $\mathcal {C} \subseteq Q^{n}$, we define the set of i th coordinates of $\mathcal {C}$ as

$$\mathcal{C}(i) =\{ \mathbf{c}(i) \in Q \ | \ \mathbf{c}=(\mathbf{c}(1), \mathbf{c}(2), \ldots, \mathbf{c}(n))^{T} \in \mathcal{C}\}$$

for any 1 ≤ i ≤ n. For any subset of codewords $\mathcal {C}_{0}\subseteq \mathcal {C}$, we define the descendant code of $\mathcal {C}_{0}$ by

$$\mathsf{desc}(\mathcal{C}_{0}) = \{(\mathbf{x}(1),\mathbf{x}(2),\ldots,\mathbf{x}(n))^{T} \in Q^{n} \ |\ \mathbf{x}(i) \in \mathcal{C}_{0}(i), 1 \le i \le n\}, $$

that is,

$$\mathsf{desc}(\mathcal{C}_{0})=\mathcal{C}_{0}(1)\times \mathcal{C}_{0}(2)\times {\ldots} \times \mathcal{C}_{0}(n).$$

Clearly the set $\mathsf {desc}(\mathcal {C}_{0})$ consists of the n-tuples that could be produced by a coalition holding the codewords in $\mathcal {C}_{0}$.

Definition 1

([11, 15]) Let $\mathcal {C}$ be an (n,M,q) code and t ≥ 2 be an integer.

• $\mathcal {C}$ is a $\overline {t}$-separable code, or $\overline {t}$-SC (n,M,q), if for any $\mathcal {C}_{1}$, $\mathcal {C}_{2} \subseteq \mathcal {C}$ such that $1 \leq |\mathcal {C}_{1}| \leq t$, $1\leq |\mathcal {C}_{2}| \leq t$, and $\mathcal {C}_{1} \neq \mathcal {C}_{2}$, we have $\mathsf {desc}(\mathcal {C}_{1}) \neq \ \mathsf {desc}(\mathcal {C}_{2})$, that is there is at least one coordinate i, 1 ≤ i ≤ n, such that $\mathcal {C}_{1}(i)\neq \mathcal {C}_{2}(i)$.

• $\mathcal {C}$ is a strongly $\overline {t}$-separable code, or $\overline {t}$-SSC (n,M,q), if for any $\mathcal {C}_{0}\subseteq \mathcal {C}$ such that $1\leq |\mathcal {C}_{0}|\leq t$, we have $\bigcap _{\mathcal {C}^{\prime } \in S(\mathcal {C}_{0})}\mathcal {C}^{\prime }= \mathcal {C}_{0}$, where $S(\mathcal {C}_{0})=\{\mathcal {C}^{\prime }\subseteq \mathcal {C}| \mathsf {desc}(\mathcal {C}^{\prime }) = \mathsf {desc}(\mathcal {C}_{0})\}$.

• $\mathcal {C}$ is a t-frameproof code, or t-FPC (n,M,q), if for any $\mathcal {C}^{\prime } \subseteq \mathcal {C}$ such that $|\mathcal {C}^{\prime }| \le t$, it holds that $\mathsf {desc}(\mathcal {C}^{\prime }) \bigcap \mathcal {C} = \mathcal {C}^{\prime }$, that is, for any $\mathbf {c} =(\mathbf {c}(1),\ldots , \mathbf {c}(n))^{T}\in \mathcal {C} \setminus \mathcal {C}^{\prime }$, there is at least one coordinate i, 1 ≤ i ≤ n, such that $\mathbf {c}(i) \not \in \mathcal {C}^{\prime }(i)$.

Since the parameter M of a $\overline {t}$-SSC (n,M,q) corresponds to the number of fingerprints assigned to authorized users who purchased the right to access the copyrighted multimedia data, we should try to construct strongly separable codes with M as large as possible, given length n. Let $M(\overline {t},n,q) = {\max } \{M \ |$ there exists a $\overline {t}$-SSC (n,M,q)}. A $\overline {t}$-SSC (n,M,q) is said to be optimal if $M = M(\overline {t},n,q)$ . Similarly, a $\overline {t}$-SC (n,M,q) (or a t-FPC (n,M,q)) is optimal if M is the largest possible value given n, q and t.

3 Upper bounds

In this section, we first investigate the relationships among SC, SSC and FPC, and then derive the upper bounds on $M(\overline {t},n,q)$ according to these relationships.

3.1 SC, SSC and FPC

The relationship between SC and FPC was described in [11].

Lemma 1 (11)

Any t-FPC (n,M,q)is a $\overline {t}$ -SC (n,M,q), t ≥ 1. Conversely any $\overline {t}$ -SC (n,M,q)is a (t − 1)-FPC (n,M,q), t ≥ 2.

Jiang et al. [15] established the following relationships among SC, SSC and FPC.

Lemma 2 (15)

Any t-FPC (n,M,q)is a $\overline {t}$ -SSC (n,M,q).

The following example shows that the converse of Lemma 2 does not always hold.

Example 1

([15]) The following (3,4,2) code $\mathcal {C}$ is a $\overline {2}$-SSC (3,4,2), but is not a 2-FPC (3,4,2).

$$\begin{array}{@{}rcl@{}} \begin{array}{c} \mathbf{c}_{1} \ \mathbf{c}_{2} \ \mathbf{c}_{3} \ \mathbf{c}_{4} \\ \mathcal{C}= \left( \begin{array}{cccc} 0 \ & 1 \ & 0 \ & 0 \ \\ 0 \ & 0 \ & 1 \ & 0 \ \\ 0 \ & 0 \ & 0 \ & 1 \ \end{array}\right) \end{array} \end{array} $$

Lemma 3 (15)

Any $\overline {t}$ -SSC (n,M,q)is a $\overline {t}$ -SC (n,M,q).

Although, the converse of Lemma 3 does not always hold, when t = n = 2, Jiang et al. proved that the converse of Lemma 3 is also true.

Example 2 ([15])

Let c _i , 1 ≤ i ≤ 5, be the ith codeword of the following code $\mathcal {C}$, then $\mathcal {C}$ is a $\overline {2}$-SC (3,5,2), but not a $\overline {2}$-SSC (3,5,2), because d e s c({c ₁,c ₅) = d e s c({c ₂,c ₃,c ₄}).

$$\begin{array}{@{}rcl@{}} \mathcal{C}=\left( \begin{array}{ccccc} 0&1&0&0&1\\ 0&0&1&0&1\\ 0&0&0&1&1 \end{array} \right) \ \ \ \end{array} $$

Lemma 4 (15)

A (2,M,q)code $\mathcal {C}$ is a $\overline {2}$ -SSC (2,M,q)if and only if $\mathcal {C}$ is a $\overline {2}$ -SC (2,M,q).

Example 3

The following code $\mathcal {C}$ is an optimal $\overline {3}$-SC (3,3,2), and we can check that it is also a $\overline {3}$-SSC (3,3,2).

$$\begin{array}{@{}rcl@{}} \mathcal{C}=\left( \begin{array}{ccc} 0&1&1\\ 0&1&0\\ 0&0&1 \end{array} \right) \ \ \ \end{array} $$

Furthermore, it is very interesting that the converse of Lemma 3 also holds for t = n = 3 and q ≥ 3. We first state the two useful results. From Lemmas 1 and 3, the following statement holds.

Corollary 1

Any $\overline {t}$ -SSC (n,M,q)is a (t − 1)-FPC (n,M,q)where t ≥ 2.

Lemma 5

Suppose $\mathcal {C}$ is a $\overline {3}$ -SC (3,M,q). Then for any $\mathcal {C}_{0} \subseteq \mathcal {C}$ with $|\mathcal {C}_{0}| \leq 3$ , and any $\mathbf {c} \in \mathcal {C}_{0}$ , the Hamming distance d(c,c ^′) ≥ 2holds for any $\mathbf {c}^{\prime } \in \mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}\setminus \mathcal {C}_{0}$ .

Proof

By Lemma 1, $\mathcal {C}$ is a 2-FPC. By the definition of an FPC, we have $\mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}$ = $\mathcal {C}_{0}$ when $|\mathcal {C}_{0}|=1$, 2. This implies $\mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}\setminus \mathcal {C}_{0}=\emptyset$. Clearly the statement holds. So we only need to consider the case $|\mathcal {C}_{0}|=3$. For any $\mathcal {C}_{0}=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3}\}$, where c _i = (a _i ,b _i ,e _i )^T, 1 ≤ i ≤ 3, suppose that there exits one codeword $\mathbf {c}^{\prime }=(a^{\prime },b^{\prime },e^{\prime })^{T} \in \mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}\setminus \mathcal {C}_{0}$, such that d(c ₁,c ^′) = 1. Without loss of generality, assume a ₁ = a ^′, b ₁ = b ^′, e ₁≠e ^′. This implies that e ^′ equals e ₂ or e ₃ since $\mathbf {c}^{\prime } \in \mathsf {desc}(\mathcal {C}_{0})$. If e ^′ = e ₂ (or e ^′ = e ₃), we have c ^′∈d e s c({c ₁,c ₂}) (or c ^′∈d e s c({c ₁,c ₃})), a contradiction to the definition of a 2-FPC. So the statement also holds when $|\mathcal {C}_{0}|=3$. □

Theorem 1

For any q ≥ 3, a (3,M,q)code $\mathcal {C}$ is a $\overline {3}$ -SSC (3,M,q)if and only if $\mathcal {C}$ is a $\overline {3}$ -SC (3,M,q).

Proof

The necessity of the condition directly follows from Lemma 3. We now show that any $\overline {3}$-SC (3,M,q)$\mathcal {C}$ over Q is also a $\overline {3}$-SSC (3,M,q). That is, for any $\mathcal {C}_{0}\subseteq \mathcal {C}$, $|\mathcal {C}_{0}|\leq 3$, we should show $\bigcap _{\mathcal {C}^{\prime }\in S(\mathcal {C}_{0})}\mathcal {C}^{\prime }=\mathcal {C}_{0}$ from the definition of an SSC.

By Lemma 1, $\mathcal {C}$ is a 2-FPC. From Lemma 2, we have $\mathcal {C}$ is a $\overline {2}$-SSC. So when $|\mathcal {C}_{0}|=1$, 2, $\bigcap _{\mathcal {C}^{\prime }\in S(\mathcal {C}_{0})}\mathcal {C}^{\prime }=\mathcal {C}_{0}$ holds. Now we consider the case $|\mathcal {C}_{0}|=3$. For any $\mathcal {C}_{0}=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3}\}$, c _i = (a _i ,b _i ,e _i ), we have $\mathsf {desc}(\mathcal {C}_{0})$:

$$\begin{array}{@{}rcl@{}} \left( \begin{array}{ccccccccccccccccccccccccccc} a_{1} &\! a_{2} &\! a_{3} &\! a_{1} &\! a_{2} &\! a_{1} &\! a_{2} &\! a_{3} &\! a_{3} &\! a_{1} &\! a_{1} &\! a_{1} &\! a_{1} &\! a_{1} &\! a_{1} &\!a_{2}&\! a_{2} &\! a_{2} &\! a_{2} &\! a_{2} &\! a_{2} &\! a_{3} &\! a_{3} &\! a_{3} &\! a_{3} &\! a_{3} &\! a_{3} \\ b_{1} &\! b_{2} &\! b_{3} &\! b_{2} &\! b_{1} &\! b_{3} &\! b_{3} &\! b_{1} &\! b_{2} &\! b_{1} &\! b_{1} &\! b_{2} &\! b_{2} &\! b_{3} &\! b_{3} &\! b_{2} &\! b_{3} &\! b_{3} &\! b_{2} &\! b_{1} &\! b_{1} &\! b_{3} &\! b_{3} &\! b_{1} &\! b_{1} &\! b_{2} &\! b_{2} \\ e_{1} &\! e_{2} &\! e_{3} &\! e_{3} &\! e_{3} &\!e_{2} &\! e_{1} &\! e_{2} &\! e_{1} &\! e_{2} &\! e_{3} &\! e_{1} &\! e_{2} &\! e_{1} &\! e_{3} &\! e_{3} &\! e_{2} &\! e_{3} &\! e_{1} &\! e_{2} &\! e_{1} &\! e_{1} &\! e_{2} &\! e_{3} &\! e_{1} &\! e_{3} &\! e_{2} \end{array} \right) \ \ \ \end{array} $$

(1)

Let c _i , 1 ≤ i ≤ 27, be the ith codeword of $\mathsf {desc}(\mathcal {C}_{0})$ in (1).

According to Lemma 5, $\mathbf {c}_{i} \notin \mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}$, 10 ≤ i ≤ 27. Hence we have

$$\begin{array}{@{}rcl@{}} \mathsf{desc}(\mathcal{C}_{0})\bigcap \mathcal{C} \subseteq \left( \begin{array}{ccccccccccccccccccccccccccc} a_{1} & a_{2} & a_{3} & a_{1} & a_{2} & a_{1} & a_{2} & a_{3} & a_{3}\\ b_{1} & b_{2} & b_{3} & b_{2} & b_{1} & b_{3} &b_{3} & b_{1} & b_{2}\\ e_{1} & e_{2} & e_{3} & e_{3} & e_{3} & e_{2} & e_{1} & e_{2} & e_{1} \end{array} \right) \ \ \ \end{array} $$

(2)

Now we consider formula (2) by discussing cardinalities of sets $\mathcal {C}_{0}(i)$, 1 ≤ i ≤ 3.

• If there exists an integer 1 ≤ i ≤ 3 such that $|\mathcal {C}_{0}(i)| \leq 2$, without loss of generality, assume $|\mathcal {C}_{0}(1)| \leq 2$ and a ₁ = a ₂. According to Lemma 5, we have $\mathbf {c}_{i} \notin \mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}$, 4 ≤ i ≤ 7. So we only need to consider c ₈ and c ₉.

  • If a ₁ = a ₃, then $\mathbf {c}_{8}, \mathbf {c}_{9} \notin \mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}$ from Lemma 5. So $\cap _{\mathcal {C}^{\prime }\in S(\mathcal {C}_{0})}\mathcal {C}^{\prime }=\mathcal {C}_{0}$.

  • If a ₁≠a ₃,|{b ₁,b ₂,b ₃}| < 3 or |{e ₁,e ₂,e ₃}| < 3 holds, then c ₈,c ₉ $\notin {\mathsf {desc}}(\mathcal {C}_{0})\bigcap \mathcal {C}$ from Lemma 5. So $\cap _{\mathcal {C}^{\prime }\in S(\mathcal {C}_{0})}\mathcal {C}^{\prime }=\mathcal {C}_{0}$.

  • If a ₁≠a ₃ and |{b ₁,b ₂,b ₃}| = |{e ₁,e ₂,e ₃}| = 3, then $\mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}$ contains at most one of c ₈ and c ₉. Otherwise, we have d e s c({c ₁,c ₂,c ₈}) = d e s c({c ₁,c ₂,c ₉}), a contradiction to the definition of a $\overline {3}$-SC. Without loss of generality, suppose that $\mathbf {c}_{8} \in \mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}$ . We have $\mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3}$, c ₈}. Clearly S$(\mathcal {C}_{0})=\{\mathcal {C}_{0},\mathcal {C}_{1}\}$ where $\mathcal {C}_{1}=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3},\mathbf {c}_{8}\}$. It is easy to check that $\cap _{\mathcal {C}^{\prime } \in S(\mathcal {C}_{0})}\mathcal {C}^{\prime }=\mathcal {C}_{0}$.

• If $|\mathcal {C}_{0}(i)|=3$ for any 1 ≤ i ≤ 3, it is easy to check that $d(\mathbf {c}_{j_{1}},\mathbf {c}_{j_{2}})=2$ for all j ₁ = 1,2,3 and j ₂ = 4,5,…,9. If $\mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}=\mathcal {C}_{0}$, clearly it is a $\overline {3}$-SSC. Now we consider the case that there is at least one codeword $\mathbf {c}_{i} \in \mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}$, 4 ≤ i ≤ 9, without loss of generality, we assume $\mathbf {c}_{4} \in \mathsf {desc}(\mathcal {C}_{0})\bigcap \mathcal {C}$. By the distance, c _i , 5 ≤ i ≤ 9, can be divided into two subsets $\mathcal {C}_{1}=\{\mathbf {c}_{5},\mathbf {c}_{6},\mathbf {c}_{9}\}$ and $\mathcal {C}_{2}=\{\mathbf {c}_{7},\mathbf {c}_{8}\}$ such that d(c ₄,c) = 2 if $\mathbf {c}\in \mathcal {C}_{1}$ and d(c ₄,c) = 3 if $\mathbf {c}\in \mathcal {C}_{2}$.

  • If $\mathsf {desc}(\mathcal {C}_{0})\cap \mathcal {C}=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3}$, c ₄}, then S$(\mathcal {C}_{0})=\{\mathcal {C}_{0},\mathcal {C}^{\prime }\}$, where $\mathcal {C}^{\prime }=\{\mathbf {c}_{1},\mathbf {c}_{2}, \mathbf {c}_{3},\mathbf {c}_{4}\}$. Clearly $\cap _{\mathcal {C}^{\prime } \in S(\mathcal {C}_{0})}\mathcal {C}^{\prime }=\mathcal {C}_{0}$.

  • If $\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3},\mathbf {c}_{4},\mathbf {c}\}\subseteq \mathsf {desc}(\mathcal {C}_{0})\cap \mathcal {C},\mathbf {c}\in \mathcal {C}_{1}$, we claim that this case does not happen. We take c = c ₅ as an example. Then we have d e s c({c ₁,c ₂,c ₄}) = d e s c({c ₁,c ₂,c ₅}), a contradiction to the definition of a $\overline {3}$-SC.

  • If $\mathsf {desc}(\mathcal {C}_{0})\cap \mathcal {C}=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3},\mathbf {c}_{4},\mathbf {c}\},\mathbf {c}\in \mathcal {C}_{2}$, we claim that this case satisfies the conditions of $\overline {3}$-SSC. We take c = c ₇ as an example. Let $\mathcal {C}^{\prime }=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3},\mathbf {c}_{4}\},\mathcal {C}^{\prime \prime }=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3},\mathbf {c}_{7}\}$ and $\mathcal {C}^{\prime \prime \prime }=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3},\mathbf {c}_{4},\mathbf {c}_{7}\}$. It is easy to check that $S(\mathcal {C}_{0})=\{\mathcal {C}_{0},\mathcal {C}^{\prime },\mathcal {C}^{\prime \prime },\mathcal {C}^{\prime \prime \prime }\}$ and $\cap _{\mathcal {C}^{\prime } \in S(\mathcal {C}_{0})}\mathcal {C}^{\prime }=\mathcal {C}_{0}$.

  • If $\mathsf {desc}(\mathcal {C}_{0})\cap \mathcal {C}=\{\mathbf {c}_{1},\mathbf {c}_{2},\mathbf {c}_{3},\mathbf {c}_{4},\mathbf {c}_{7},\mathbf {c}_{8}\}$, then d e s c({c ₁,c ₂,c ₃}) = d e s c({c ₄,c ₇,c ₈}), a contradiction to the definition of a $\overline {3}$-SC.

From the above discussions, we know that $\mathcal {C}$ is a $\overline {3}$-SSC. Then the proof is complete. □

3.2 Upper bounds on $M(\overline {t},n,q)$

As an important class of anti-collusion codes in multimedia copyright protection, separable codes and frameproof codes were widely studied, e.g., [5, 7, 9,10,11, 14].

Lemma 6 (8)

Given a $\overline {t}$ -SC (n,M,q)with t ≥ 3and n ≥ 2, let r ∈{0,1,…,t − 2}be the remainder of n on division by t − 1. If M > q , then

$$M \le {\max}\left\{q^{\lceil n/(t-1) \rceil}, r(q^{\lceil n/(t-1) \rceil}-1)+(t-1-r)(q^{\lfloor n/(t-1) \rfloor}-1)\right\}.$$

Lemma 7 ([9])

For any positive integers t and q ≥ 2,

• when 2 ≤ n < t , there always exists an optimal $\overline {t}$ -SC (n,n(q − 1),q)and an optimal t-FPC (n,n(q − 1),q);

• when n = t , for any $\overline {t}$ -SC (n,M,q)we have M ≤ q ² if n ≤ q , otherwise M ≤ n q .

When t = 3,n = 3, Cheng et al. improved the above result.

Lemma 8 (9)

The maximum value of M in a $\overline {3}$ -SC (3,M,q)must be between $\lfloor \sqrt {q}\rfloor ^{3}$ and $\lfloor \frac {3q^{2}}{4}\rfloor$ , where q ≥ 4.

From Lemmas 3 and 6, the following upper bounds on $M(\overline {t},n,q)$ can be obtained.

Corollary 2

Let n,q and t be positive integers such that t ≥ 3and n ≥ 2, and r ∈{0,1,…,t − 2}the remainder of n on division by t − 1. If $M(\overline {t},n,q) > q$ , then

$$M(\overline{t},n,q) \le {\max}\left\{q^{\lceil n/(t-1) \rceil}, r(q^{\lceil n/(t-1) \rceil}-1)+(t-1-r)(q^{\lfloor n/(t-1) \rfloor}-1)\right\}.$$

From Lemmas 2, 3 and 7, the following statement holds.

Corollary 3

For any positive integers t, n and q ≥ 2,

• when 2 ≤ n < t , $M(\overline {t},n,q)=n(q-1)$ ;

• when n = t , $M(\overline {t},n,q)\leq q^{2}$ if n ≤ q , and otherwise $M(\overline {t},n,q)\leq nq$ .

From Theorem 1 and Lemma 8, we have the following result.

Corollary 4

$\lfloor \sqrt {q}\rfloor ^{3}\leq M(\overline {3},3,q)\leq \lfloor \frac {3q^{2}}{4}\rfloor$ holds for q ≥ 4.

To our best knowledge, the lower bound in [9] is the best known result on $\overline {3}$-SC (3,M,q). In the following section, we will improve the lower bound in Corollary 4 to Ω(q ^5/3 + q ^4/3 − q) for some prime powers q.

4 Construction

From Theorem 1, it is sufficient to consider $\overline {3}$-SC (3,M,q) for studying $\overline {3}$-SSC (3,M,q). First the following notations are necessary.

For any (3,M,q) code $\mathcal {C}$ defined on Q = {0,1,⋯ ,q − 1}, we define the column vector sets $\mathcal {A}_{i}^{(1)}$ for i ∈ Q as follows:

$$\begin{array}{@{}rcl@{}} \mathcal{A}_{i}^{(1)} = \{(x_{2}, x_{3})^{T} \ | \ (x_{1}, x_{2}, x_{3})^{T} \in \mathcal{C}, \ x_{1}=i\}. \end{array} $$

Obviously, $\mathcal {A}_{i}^{(1)} \subseteq Q^{2}$ for any i ∈ Q and $|\mathcal {A}_{0}^{(1)}|+ \cdots + |\mathcal {A}_{q-1}^{(1)}|=M$ hold. Similar to the above notation, vector sets ${\mathcal {A}}_{i}^{(j)}$ for j = 2, 3 can be also defined.

Lemma 9 (9)

A (3,M,q)code is a 2-FPC (3,M,q)if and only if $|{\mathcal {A}}_{i}^{(j)} \bigcap {\mathcal {A}}_{i^{\prime }}^{(j)}|\leq 1$ holds for any j ∈{1,2,3}and distinct i, i ^′∈ Q , where if $|\mathcal {A}_{i}^{(j)} \bigcap \mathcal {A}_{i^{\prime }}^{(j)}|= 1$ , then $|\mathcal {A}_{i}^{(j)}|=|\mathcal {A}_{i^{\prime }}^{(j)}|= 1$ .

Cheng et al. showed that for any $\overline {3}$-SC (3,M,q), $\mathcal {C}$, there is no subcode $\triangle _{i}\subseteq \mathcal {C}$ described in (3), a≠b, c≠d, e∉{f,g}, and there is no subcode $\nabla \subseteq \mathcal {C}$ described in (4), |{a _i ,b _i ,c _i }| = 3, i = 1, 2, 3.

$$\begin{array}{@{}rcl@{}} &\triangle_{1}=\left( \begin{array}{cccc} a & a & b & b \\ e & f & g & e \\ c & d & c & d \end{array} \right)\ \ \ \triangle_{2}=\left( \begin{array}{cccc} a & a & b & b \\ c & d & c & d \\ e & f & g & e \end{array} \right) &\triangle_{3}=\left( \begin{array}{cccc} e & f & g & e \\ a & a & b & b \\ c & d & c & d \end{array} \right) \end{array} $$

(3)

$$\begin{array}{@{}rcl@{}} \nabla=\left( \begin{array}{cccccc} a_{1} & b_{1} &c_{1} & a_{1}&b_{1} & c_{1}\\ a_{2} & b_{2} &c_{2} & b_{2}&c_{2} & a_{2}\\ a_{3} & b_{3} &c_{3} &c_{3}&a_{3} & b_{3} \end{array} \right) \end{array} $$

(4)

We call such △ _i and △forbidden configurations of $\mathcal {C}$.

Theorem 2 (9)

A (3,M,q)code $\mathcal {C}$ is a $\overline {3}$ -SC (3,M,q)if and only if it satisfies the following conditions:

• (i) $\mathcal {C}$ is a 2-FPC (3,M,q);

• (ii) Configurations in(3)and(4)are all the forbidden configurations of $\mathcal {C}$ .

In the following, for any prime power q, we will take advantage of difference matrices to construct $\overline {3}$-SC (3,M,q)s.

Definition 2

([3]) For any prime power q, a difference matrix (q,3,1)DM is a 3 × q matrix D = (d _j,i ) with $d_{j, i} \in \mathbb {F}_{q}$ such that for any 1 ≤ j ₁≠j ₂ ≤ 3, the differences $d_{j_{1},i}- d_{j_{2},i}$ over $\mathbb {F}_{q}$ , $i\in \mathbb {F}_{q}$ , comprise all the elements of $\mathbb {F}_{q}$.

Given a 3 × s matrix N with entries from $\mathbb {F}_{q}$ and s distinct columns n ₁,n ₂,…,n _s , we can define a (3,q s,q) code $\mathcal {C}$ on $\mathbb {F}_{q}$ as

$$\begin{array}{@{}rcl@{}} \mathcal{C}=\{N+g \ | \ g \in \mathbb{F}_{q}\} = \{\mathbf{n}_{i}+g \ | \ g \in \mathbb{F}_{q}, \ 1 \le i \le s\}. \end{array} $$

(5)

We say N is a base of $\mathcal {C}$, or $\mathcal {C}$ is constructed by N.

For any given (q,3,1)DM, D, we can obtain a (3,q ²,q) code $\mathcal {C}=\{D+g \ | \ g \in \mathbb {F}_{q}\}$. By the definition of a DM, we know that $|\mathcal {A}_{i_{1}}^{(j)} \cap \mathcal {A}_{i_{2}}^{(j)}|=0$ holds for any 1 ≤ j ≤ 3 and for any distinct $i_{1} ,i_{2} \in \mathbb {F}_{q}$, which implies that $\mathcal {C}$ is a 2-FPC (3,q ²,q) by Lemma 9. Unfortunately, this code is not always a $\overline {3}$-SC.

Example 4

The following code $\mathcal {C}$ is constructed by (3,3,1)DM in (5). Let c _i denote the ith codewode, 1 ≤ i ≤ 9. From the above discussion, $\mathcal {C}$ is a 2-FPC (3,9,3), but is not a $\overline {3}$-SC since d e s c({c ₁,c ₄,c ₇}) = d e s c({c ₂,c ₅,c ₈}).

$$\begin{array}{@{}rcl@{}} \mathcal{C}=\left( \begin{array}{ccccccccc} 0 & 0 & 0 & 1 & 1 & 1 & 2 & 2 & 2 \\ 0 & 1 & 2 & 1 & 2 & 0 & 2 & 0 & 1\\ 0 & 2 & 1 & 1 & 0 & 2 & 2 & 1 & 0 \end{array} \right) \end{array} $$

In fact, we can obtain the base of a $\overline {3}-\textit {SC}(3,M,q)$ by deleting some codewords of $\mathcal {C}$ constructed by (q,3,1)DM in (5). For any prime power q, if q ≥ 3, the following array D is a (q,3,1)DM

$$\begin{array}{@{}rcl@{}} D=\left( \begin{array}{cccc} 0 & 0 & ... & 0 \\ 0 & 1 & ...& \varepsilon^{q-2} \\ 0 & \alpha & ... & \alpha\varepsilon^{q-2} \end{array} \right), \end{array} $$

(6)

where ε is a primitive element of $\mathbb {F}_{q}$ and α is an element of $\mathbb {F}_{q}\setminus \{0,1\}$ [13]. For any subset $S\subseteq \mathbb {F}_{q}$, let sub-matrix N = D| _S obtained by deleting the columns $i\in \mathbb {F}_{q}\setminus S$. Clearly the code $\mathcal {C}$ constructed by N in (5) is a 2-FPC (3,q|S|,q). From Theorem 2, in order that $\mathcal {C}$ may be a $\overline {3}$-SC (3,M,q), we only need to consider the forbidden configurations in (3) and (4). Suppose $C \subseteq \mathcal {C}$,

• (I) When C ∈{△₁,△₂,△₃}, we may assume

  $$\begin{array}{@{}rcl@{}} C=\left( \begin{array}{cccc} k_{1}& k_{2}&k_{3}&k_{4} \\ x+k_{1}& y+k_{2}&z+k_{3}&w+k_{4} \\ \alpha x+k_{1}&\alpha y+k_{2}&\alpha z+k_{3}&\alpha w+k_{4} \ \ \ \end{array}\right), \end{array} $$

  where $x,y,z,w,k_{1},k_{2},k_{3},k_{4}\in \mathbb {F}_{q}$.

  • When C = △₁, we have

    $$k_{1} =k_{2}, \ x+k_{1}=w+k_{4}, \ \alpha y+k_{2}=\alpha w +k_{4}.$$

    This means

    $$\begin{array}{@{}rcl@{}} x+(\alpha-1)w=y\alpha \end{array} $$

    (7)

    with |{x,y,w}| = 3. In fact, if x = y, we have that the first codeword equals the second codeword of △₁, a contradiction to the assumption. This implies x≠y. Similarly we can check that x≠w and y≠w.

  • When C = △₂, we have

    $$k_{1} =k_{2},\ y+k_{2}=w+k_{4}, \ \alpha x+k_{1}=\alpha w +k_{4}.$$

    This means

    $$\begin{array}{@{}rcl@{}} y+(\alpha-1)w=x\alpha. \end{array} $$

    (8)

    It is easy to check that |{x,y,w}| = 3 holds in (8).

  • When C = △₃, we have

    $$k_{1} =k_{4},\ x+k_{1}=y+k_{2}, \ \alpha y +k_{2}=\alpha w +k_{4}.$$

    This means

    $$\begin{array}{@{}rcl@{}} x+(\alpha-1)y=w\alpha. \end{array} $$

    (9)

    It is easy to check that |{x,y,w}| = 3 holds in (9).

• (II) When C = ∇, we may assume

  $$\begin{array}{@{}rcl@{}} C =\left( \begin{array}{cccccc} k_{1} & k_{2} &k_{3} & k_{1} &k_{2} & k_{3}\\ x+k_{1} & y+k_{2} &z+k_{3} &u+ k_{1} &v+k_{2} &w+ k_{3}\\ \alpha x+k_{1}& \alpha y+k_{2}&\alpha z+k_{3}&\alpha u+ k_{1}&\alpha v+k_{2}&\alpha w+ k_{3} \end{array} \right) .\ \ \ \end{array} $$
  $$\begin{array}{@{}rcl@{}} \left\{\begin{array}{ll} x+k_{1}=w+k_{3}\\ y+k_{2}=u+k_{1}\\ z+k_{3}=v+k_{2}\\ \alpha x+ k_{1}=\alpha v+ k_{2}\\ \alpha y+ k_{2}=\alpha w+ k_{3}\\ \alpha z+ k_{3}=\alpha u+ k_{1} \end{array} \right.\Longrightarrow \left\{\begin{array}{lllll} k_{3}-k_{1}=x-w\\ k_{2}-k_{1}=u-y\\ k_{3}-k_{2}=v-z\\ k_{2}-k_{1}=\alpha x-\alpha v\\ k_{3}-k_{2}=\alpha y-\alpha w\\ k_{3}-k_{1}=\alpha u-\alpha z \end{array}. \right. \end{array} $$

  (10)

  This means

  $$\begin{array}{@{}rcl@{}} \left\{\begin{array}{ll} \alpha x +\alpha(\alpha-1)z=(\alpha-1)y+(\alpha^{2}-\alpha+1)u\\ \alpha w +\alpha(\alpha-1)u=(\alpha-1)v+(\alpha^{2}-\alpha+1)z \end{array} \right. \end{array} $$

  (11)

  Then we know {x,y,z}∩{u,v,w} = ∅ always holds.

  • x∉{u,v,w} always holds. If x = u, we have the first codeword equals the forth codeword of ∇, a contradiction to the assumption. Similarly, we can prove that x≠w, v always holds.

  • y∉{u,v,w} always holds. If y = u, we have k ₁ = k ₂ from y + k ₂ = u + k ₁. This implies that the second codeword equals the forth codeword of ∇, a contradiction to the assumption. Similarly, we can prove that y≠w, v.

  • z∉{u,v,w} always holds. If z = u, we have k ₁ = k ₃ from α z + k ₃ = α u + k ₁. This implies that the third codeword equals the forth codeword of ∇, a contradiction to the assumption. Similarly, we have z≠w, v.

For any prime power q ₁ and positive integer n, let $\mathbb {F}^{n}_{q_{1}}$ be the n-dimensional vector space over $\mathbb {F}^{n}_{q_{1}}$. When $q={q_{1}^{n}}$, it is well known that the element of $\mathbb {F}_{q}$ can be represented by the n-dimensional vector over $\mathbb {F}_{q_{1}}$. Suppose that S is a subset of $\mathbb {F}^{n}_{q_{1}}$, of which no three distinct elements are collinear. Then (7), (8) and (9) have no solution in S. This implies that $\mathcal {C}$ does not contain △₁, △₂ and △₃. Together with (11), we have the following result.

Theorem 3

For any subset $S\subseteq \mathbb {F}_{q}$ , of which no three distinct elements are collinear, if there is no solution of(11)in S, then the code constructed by N = D| _S in(5)is a $\overline {3}$ -SC (3,q|S|,q).

Combining forbidden configurations with subsets containing no nontrivial solution to certain equations is an efficient method. This similar idea was also used in [1] and [20]. Now, we focus on the formula (11). Let q ₁ = 6t + 1 be a prime power, and α be a primitive 6th root of unity in $\mathbb {F}_{q_{1}}$, where t ≥ 1. Clearly α is a root of f(x) = x ² − x + 1. Then (11) can be written as

$$\begin{array}{@{}rcl@{}} \left\{\begin{array}{ll} x +(\alpha-1)z=\alpha y \\ w +(\alpha-1)u=\alpha v \end{array} \right. \end{array} $$

(12)

From (12), if |{x,y,z}| < 3 (or |{u,v,w}| < 3), then |{x,y,z}| = 1 (or |{u,v,w}| = 1) always holds. Furthermore, from (10) we claim if x = y = z (or u = v = w), then |{u,v,w}| = 3 (or |{x,y,z}| = 3) always holds in (11). If x = y = z and u = v = w, then x + k ₁ = w + k ₃ and α x + k ₃ = α w + k ₁ hold by (10). We have (α + 1)x = (α + 1)w. This implies x = w, k ₁ = k ₃ since α≠ − 1. That is, the first codeword equals the sixth codeword in C, a contradiction. So we have

$$\begin{array}{@{}rcl@{}} &&|\{x,y,z,u,v,w\}|=6; or\\ &&|\{x,y,z\}|=3\ \ \text{and} \ \ |\{u,v,w\}|=1; or\\ &&|\{x,y,z\}|=1\ \ \text{and} \ \ |\{u,v,w\}|=3. \end{array} $$

(13)

According to (12) and (13), Theorem 3 can be written as follows.

Corollary 5

Let $q={q_{1}^{n}}$ , where q ₁ = 6t + 1is a prime power, t ≥ 1. For any subset $S\subseteq \mathbb {F}_{q}$ , of which no three distinct elements are collinear, the code constructed by N = D| _S in(5)is a $\overline {3}$ -SC (3,q|S|,q).

Denoting by $r({q_{1}^{n}})$ the maximum size of a subset of $\mathbb {F}^{n}_{q_{1}}$ that contains no three points on a line. There are many studies on the value of $r({q_{1}^{n}})$ over $\mathbb {F}^{n}_{q_{1}}$. The interested reader is referred to [4, 16, 21].

Lemma 10 (16)

For any prime power q ₁ ≥ 3, we have $r(\mathbb {F}^{6}_{q_{1}})={\Omega }({q_{1}^{4}}+{q_{1}^{2}}-1)$ .

From Corollary 5 and Lemma 10, the following lower bound can be obtained.

Theorem 4

For any prime power $q={q^{6}_{1}}$ , where q ₁ = 6t + 1is a prime power, there exists a $\overline {3}$ -SSC (3,M,q), where M = Ω(q ^5/3 + q ^4/3 − q).

5 Conclusion

In this paper, we first derived several upper bounds on the number of codewords of $\overline {t}$-SSC. Then we focused on $\overline {3}$-SSCs with codeword length 3, and obtained the following two main results: (1) An equivalence between an SSC and an SC was derived. (2) An improved lower bound Ω(q ^5/3 + q ^4/3 − q) on the size of a q-ary SSC when $q={q_{1}^{6}}$ for any prime power q ₁ ≡ 1 (mod 6), which is better than the previously known bound $\lfloor \sqrt {q}\rfloor ^{3}$, was obtained by means of a difference matrix and a known result on the subsets of $\mathbb {F}^{n}_{q}$ containing no three points on a line.

It would be of interest if we could improve the upper bounds $\lfloor \frac {3q^{2}}{4}\rfloor$ or the lower bound Ω(q ^5/3 + q ^4/3 − q). It would be also interesting if we could get more properties and constructions of strongly separable codes.