The Upper Bounds On (?)-SC(3,M,q)s And Their Related Constructions

In2002,Trappe et.al proposed a t-resilient anti-collusion code(t-ACC),it can be used to construct fingerprints resistant to collusion attacks on multimedia contents. They also introduced the definition of t-resilient AND anti-collusion coOde(t-AND-ACC)to hinder averaging attack which is favoured by pirates.The number of codewords corresponds to the number of fingerprints assigned to the authorized users.In2011,Cheng et.al introduced a new anti-collusion code:t-resilient logical anti-collusion code(t-LACC), which has weaker requirements than that of a t-AND-ACC but has the same traceability as a t-AND-ACC does. So,given parameters t and n,a t-LACC can get larger number of codewords than that of a t-AND-ACC.Cheng et.al introduced the definition of t-separable code(-t-SC)to construct t-LACC in2011.Then the study of t-SC becomes a hot topic in multimedia information copyright protection.Furthermore,there exists a close relationship between t-SCs and classic tracing codes such as identifiable parent property codes(IPP code),frameproof codes(FPC) and so on.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 ci is called a codeword.For any subset of codewords C0(?)C,the descendant code of C0can be defined as desc(C0)={x=(x1,x2,…,xn)T∈Qn|T∈C0(i),1≤i≤n}, where C0(i)={ci∈Q|c=(c1,c2,…,cn)T∈C0},1≤i≤n.Definition1.1Let C be an(n,M,q)code and t≥2be an integer.C is a t-(n,Mg) separable code,or t-SC(n,M,q),if for any distinct C1,C2(?) C such that|C1|≤and|C2|≤t, we have desc(C1)≠desc(C2).Let M(t,n,q)=max{M|there exists a t-SC(n,M,q)}.A t-SC(n,M,q)is optimal if M=M(t,n,q). Cheng et.al have discussed the cases of t=2and n=2,3respectively. When t>2and n≥3,Cheng et.al also obtained the following upper bound.According to the upper bound above,we have upper bound M(3,3,q)≤(3q(3q-1))/4=(9q2)/4-(3q)/4which is not tight.The structure of t-SC(n,M,q)is too complex that there are few results to our knowledge. In this thesis, we mainly consider3-SC(3, M, q) and obtain the following results.Theorem1.1For any3-SC(3,M, q), C, it can be checked that the following sets, C1and C2, do not belong to C. where|{a,b}|=|{c,d}|=2, e (?){f,g} and|{ai,bi,ci}|=3,1≤i≤3. We call such C1and C2forbidden configurations of C. Given a subcode C’ C C, conjugates of C’ are subsets of Q3defined by changing any two coordinates of C’.Theorem1.2Let C be a3-SC(3, M, q), if only if it satisfies the two conditions(1)C is a2-FPC(3,M,q);(2) Configurations (i),(ii) and their conjugates are the forbidden configurations of C.Theorem1.3M(3,3,q)≤[(3q-)/4] holds for each integer q≤2.Theorem1.4Let q be an odd integer and q≠0(mod3). If there exists a (q, s,1) cyclic difference set, then we have a3-SC(3, qs.q).Theorem1.5There exists a3-SC(3.q3/2,q) for each integer r≥2, where q=r2.Theorem1.6Let k be an even integer and q=k4, then there exists a3-SC(3, q3/2+q5/4,q).This thesis is organized as follows:Related definitions and main results are presented in Chapter1. From the forbidden configurations of3-SC(3,M,q), a tighter upper bound is derived in Chapter2. In Chapter3, two constructions for3-SC(3,M, q) are provided by means of combinatorial design theory. Finally, conclusion is drawn.