Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes

Fingerprinting provides a means of tracing unauthorized redistribution of digital data by individually marking each authorized copy with a personalized serial number. In order to prevent a group of users from collectively escaping identification, collusion-secure fingerprinting codes have been proposed. In this paper, we introduce a new construction of a collusion-secure fingerprinting code which is similar to a recent construction by Tardos but achieves shorter code lengths and allows for codes over arbitrary alphabets. We present results for ‘symmetric’ coalition strategies. For binary alphabets and a false accusation probability , a code length of symbols is provably sufficient, for large c ₀, to withstand collusion attacks of up to c ₀ colluders. This improves Tardos’ construction by a factor of 10. Furthermore, invoking the Central Limit Theorem in the case of sufficiently large c ₀, we show that even a code length of is adequate. Assuming the restricted digit model, the code length can be further reduced by moving from a binary alphabet to a q-ary alphabet. Numerical results show that a reduction of 35% is achievable for q = 3 and 80% for q = 10.      

A generalized Gleason–Pierce–Ward theorem

The Gleason–Pierce–Ward theorem gives constraints on the divisor and field size of a linear divisible code over a finite field whose dimension is half of the code length. This result is a departure point for the study of self-dual codes. In recent years, additive codes have been studied intensively because of their use in additive quantum codes. In this work, we generalize the Gleason–Pierce–Ward theorem on linear codes over GF(q), q = p ^m , to additive codes over GF(q). The first step of our proof is an application of a generalized upper bound on the dimension of a divisible code determined by its weight spectrum. The bound is proved by Ward for linear codes over GF(q), and is generalized by Liu to any code as long as the MacWilliams identities are satisfied. The trace map and an analogous homomorphism on GF(q) are used to complete our proof.      

Gray Codes,Loopless Algorithm and Partitions

The generation of efficient Gray codes and combinatorial algorithms that list all the members of a combinatorial object has received a lot of attention in the last few years. Knuth gave a code for the set of all partitions of [n] = {1,2,...,n}. Ruskey presented a modified version of Knuth’s algorithm with distance 2. Ehrlich introduced a looplees algorithm for the set of the partitions of [n]; Ruskey and Savage generalized Ehrlich’s results and introduced two Gray codes for the set of partitions of [n]. In this paper, we give another combinatorial Gray code for the set of the partitions of [n] which differs from the aforementioned Gray codes. Also, we construct a different loopless algorithm for generating the set of all partitions of [n] which gives a constant time between successive partitions in the construction process.      

Construction of Extremal Type II Codes over ℤ4

In this paper, we give a pseudo-random method to construct extremal Type II codes overℤ₄ . As an application, we give a number of new extremal Type II codes of lengths 24, 32 and 40, constructed from some extremal doubly-even self-dual binary codes. The extremal Type II codes of length 24 have the property that the supports of the codewords of Hamming weight 10 form 5−(24,10,36) designs. It is also shown that every extremal doubly-even self-dual binary code of length 32 can be considered as the residual code of an extremal Type II code over ℤ₄.     

An intrinsical description of group codes

A (left) group code of length n is a linear code which is the image of a (left) ideal of a group algebra via an isomorphism which maps G to the standard basis of . Many classical linear codes have been shown to be group codes. In this paper we obtain a criterion to decide when a linear code is a group code in terms of its intrinsical properties in the ambient space , which does not assume an “a priori” group algebra structure on . As an application we provide a family of groups (including metacyclic groups) for which every two-sided group code is an abelian group code. It is well known that Reed–Solomon codes are cyclic and its parity check extensions are elementary abelian group codes. These two classes of codes are included in the class of Cauchy codes. Using our criterion we classify the Cauchy codes of some lengths which are left group codes and the possible group code structures on these codes. Research supported by D.G.I. of Spain and Fundación Séneca of Murcia.     

On the existence of self-dual permutation codes of finite groups

Motivated by a research on self-dual extended group codes, we consider permutation codes obtained from submodules of a permutation module of a finite group of odd order over a finite field, and demonstrate that the condition “the extension degree of the finite field extended by n’th roots of unity is odd” is sufficient but not necessary for the existence of self-dual extended transitive permutation codes of length n + 1. It exhibits that the permutation code is a proper generalization of the group code, and has more delicate structure than the group code.     

On the classification of perfect codes: side class structures

The side class structure of a perfect 1-error correcting binary code (hereafter referred to as a perfect code) C describes the linear relations between the coset representatives of the kernel of C. Two perfect codes C and C′ are linearly equivalent if there exists a non-singular matrix A such that AC = C′ where C and C′ are matrices with the code words of C and C′ as columns. Hessler proved that the perfect codes C and C′ are linearly equivalent if and only if they have isomorphic side class structures. The aim of this paper is to describe all side class structures. It is shown that the transpose of any side class structure is the dual of a subspace of the kernel of some perfect code and vice versa; any dual of a subspace of a kernel of some perfect code is the transpose of the side class structure of some perfect code. The conclusion is that for classification purposes of perfect codes it is sufficient to find the family of all kernels of perfect codes.     

New Extremal Type I Codes of Lengths 40, 42, and 44

It is known that it is possible to construct a generator matrix for a self-dual code of length 2n+2 from a generator matrix of a self-dual code of length 2n. With the aid of a computer, we construct new extremal Type I codes of lengths 40, 42, and 44 from extremal self-dual codes of lengths 38, 40, and 42 respectively. Among them are seven extremal Type I codes of length 44 whose weight enumerator is 1+224y ⁸+872y ¹⁰+·. A Type I code of length 44 with this weight enumerator was not known to exist previously.     

The nonexistence of near-extremal formally self-dual codes

A code is called formally self-dual if and have the same weight enumerators. There are four types of nontrivial divisible formally self-dual codes over , and . These codes are called extremal if their minimum distances achieve the Mallows-Sloane bound. S. Zhang gave possible lengths for which extremal self-dual codes do not exist. In this paper, we define near-extremal formally self-dual (f.s.d.) codes. With Zhang’s systematic approach, we determine possible lengths for which the four types of near-extremal formally self-dual codes as well as the two types of near-extremal formally self-dual additive codes cannot exist. In particular, our result on the nonexistence of near-extremal binary f.s.d. even codes of any even length n completes all the cases since only the case 8|n was dealt with by Han and Lee.      

On the code generated by the incidence matrix of points and hyperplanes in <Emphasis Type="Italic">PG</Emphasis>(<Emphasis Type="Italic">n</Emphasis>,<Emphasis Type="Italic">q</Emphasis>) and its dual

In this paper, we study the p-ary linear code C(PG(n,q)), q = p ^h , p prime, h ≥ 1, generated by the incidence matrix of points and hyperplanes of a Desarguesian projective space PG(n,q), and its dual code. We link the codewords of small weight of this code to blocking sets with respect to lines in PG(n,q) and we exclude all possible codewords arising from small linear blocking sets. We also look at the dual code of C(PG(n,q)) and we prove that finding the minimum weight of the dual code can be reduced to finding the minimum weight of the dual code of points and lines in PG(2,q). We present an improved upper bound on this minimum weight and we show that we can drop the divisibility condition on the weight of the codewords in Sachar’s lower bound (Geom Dedicata 8:407–415, 1979). G. Van de Voorde’s research was supported by the Institute for the Promotion of Innovation through Science and Technology in Flanders (IWT-Vlaanderen).     

On binary self-dual codes of lengths 60, 62, 64 and 66 having an automorphism of order 9

A method for constructing binary self-dual codes having an automorphism of order p ² for an odd prime p is presented in (S. Bouyuklieva et al. IEEE. Trans. Inform. Theory, 51, 3678–3686, 2005). Using this method, we investigate the optimal self-dual codes of lengths 60 ≤ n ≤ 66 having an automorphism of order 9 with six 9-cycles, t cycles of length 3 and f fixed points. We classify all self-dual [60,30,12] and [62,31,12] codes possessing such an automorphism, and we construct many doubly-even [64,32,12] and singly-even [66,33,12] codes. Some of the constructed codes of lengths 62 and 66 are with weight enumerators for which the existence of codes was not known until now.      

Maximum distance holey packings and related codes

The notion of a maximum distance holey packing is introduced and used to construct optimal ternary (n, 3, 3) codes for all lengthsn=2 (mod 3) andn≥8. Combining this with Etzion’s result, the existence problem for an optimal ternary (n,3,3) code is solved completely. Project supported by the National Natural Science Foundation of China (Grant No. 19671064).     

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n^{2 + max(α, β)}) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(n^max(α, β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a “Monge property” and that the SMAWK algorithm on monotone matrices can therefore be applied.     

On the maximality of linear codes

We show that if a linear code admits an extension, then it necessarily admits a linear extension. There are many linear codes that are known to admit no linear extensions. Our result implies that these codes are in fact maximal. We are able to characterize maximal linear (n, k, d) _q -codes as complete (weighted) (n, n − d)-arcs in PG(k − 1, q). At the same time our results sharply limit the possibilities for constructing long non-linear codes. The central ideas to our approach are the Bruen-Silverman model of linear codes, and some well known results on the theory of directions determined by affine point-sets in PG(k, q).      

Asymptotic bound on binary self-orthogonal codes

We present two constructions for binary self-orthogonal codes. It turns out that our constructions yield a constructive bound on binary self-orthogonal codes. In particular, when the information rate R = 1/2, by our constructive lower bound, the relative minimum distance δ ≈ 0.0595 (for GV bound, δ ≈ 0.110). Moreover, we have proved that the binary self-orthogonal codes asymptotically achieve the Gilbert-Varshamov bound. This work was supported by the China Scholarship Council, National Natural Science Foundation of China (Grant No.10571026), the Cultivation Fund of the Key Scientific and Technical Innovation Project of Ministry of Education of China, and the Specialized Research Fund for the Doctoral Program of Higher Education (Grant No. 20060286006)     

Testing algebraic geometric codes

Property testing was initially studied from various motivations in 1990’s. A code C  GF (r)n is locally testable if there is a randomized algorithm which can distinguish with high possibility the codewords from a vector essentially far from the code by only accessing a very small (typically constant) number of the vector’s coordinates. The problem of testing codes was firstly studied by Blum, Luby and Rubinfeld and closely related to probabilistically checkable proofs (PCPs). How to characterize locally te...     

Chinese remainder codes

Chinese remainder codes are constructed by applying weak block designs and the Chinese remainder theorem of ring theory. The new type of linear codes take the congruence class in the congruence class ring R/I ₁ ∩ I ₂ ∩ ··· ∩ I _n for the information bit, embed R/J _i into R/I ₁ ∩ I ₂ ∩ ··· ∩ I _n, and assign the cosets of R/J _i as the subring of R/I ₁ ∩ I ₂ ∩ ··· ∩ I _n and the cosets of R/J _i in R/I ₁ ∩ I ₂ ∩ ··· ∩ I _n as check lines. Many code classes exist in the Chinese remainder codes that have high code rates. Chinese remainder codes are the essential generalization of Sun Zi codes. Selected from Journal of Mathematical Research and Exposition, 2004, 24(2): 347–352     

Hill’s potentials in weighted Sobolev spaces and their spectral gaps

We describe a new, short proof of some facts relating the gap lengths of the spectrum of a potential q of Hill’s equation, −y′′ + qy = λy, to its regularity. For example, a real potential is in a weighted Gevrey-Sobolev space if and only if its gap lengths, γ _n , belong to a similarly weighted sequence space. An extension of this result to complex potentials is proven as well. We also recover Trubowitz results about analytic potentials. The proof essentially employs the implicit function theorem.     

A coding problem in steganography

To study how to design a steganographic algorithm more efficiently, a new coding problem—steganographic codes (abbreviated stego-codes)—is presented in this paper. The stego-codes are defined over the field with q(q ≥ 2) elements. A method of constructing linear stego-codes is proposed by using the direct sum of vector subspaces. And the problem of linear stego-codes is converted to an algebraic problem by introducing the concept of the tth dimension of a vector space. Some bounds on the length of stego-codes are obtained, from which the maximum length embeddable (MLE) code arises. It is shown that there is a corresponding relation between MLE codes and perfect error-correcting codes. Furthermore the classification of all MLE codes and a lower bound on the number of binary MLE codes are obtained based on the corresponding results on perfect codes. Finally hiding redundancy is defined to value the performance of stego-codes.      

New quantum codes from evaluation and matrix-product codes

Stabilizer codes obtained via the CSS code construction and the Steane's enlargement of subfield-subcodes and matrix-product codes coming from generalized Reed–Muller, hyperbolic and affine variety codes are studied. Stabilizer codes with good quantum parameters are supplied; in particular, some binary codes of lengths 127 and 128 improve the parameters of the codes in http://www.codetables.de. Moreover, non-binary codes are presented either with parameters better than or equal to the quantum codes obtained from BCH codes by La Guardia or with lengths that cannot be reached by them.