A class of minimal cyclic codes over finite fields

Let ${\mathbb{F}}_q$ be a finite field of odd order $q$ and $n=2^a{p}_1^{a_1}{p}_2^{a_2}$, where $a,a_1,a_2$ are positive integers, $p_1,p_2$ are distinct odd primes and $4p_1{p}_2|q?1$. In this paper, we study the irreducible factorization of $x^n?1$ over ${\mathbb{F}}_q$ and all primitive idempotents in the ring ${\mathbb{F}}_q\left[x\right]∕〈x^n?1〉$.Moreover, we obtain the dimensions and the minimum Hamming distances of all irreducible cyclic codes of length $n$ over ${\mathbb{F}}_q$.     

Some properties of skew codes over finite fields

After recalling the definition of some codes as modules over skew polynomial rings, whose multiplication is defined by using an endomorphism and a derivation, and some basic facts about them, in the first part of this paper we study some of their main algebraic and geometric properties. Finally, for module skew codes constructed only with an automorphism, we give some BCH type lower bounds for their minimum distance.     

Optimal complexity of secret sharing schemes with four minimal qualified subsets

The complexity of a secret sharing scheme is defined as the ratio between the maximum length of the shares and the length of the secret. This paper deals with the open problem of optimizing this parameter for secret sharing schemes with general access structures. Specifically, our objective is to determine the optimal complexity of the access structures with exactly four minimal qualified subsets. Lower bounds on the optimal complexity are obtained by using the known polymatroid technique in combination with linear programming. Upper bounds are derived from decomposition constructions of linear secret sharing schemes. In this way, the exact value of the optimal complexity is determined for several access structures in that family. For the other ones, we present the best known lower and upper bounds.     

On quasi-twisted codes over finite fields

In coding theory, quasi-twisted (QT) codes form an important class of codes which has been extensively studied. We decompose a QT code to a direct sum of component codes – linear codes over rings. Furthermore, given the decomposition of a QT code, we can describe the decomposition of its dual code. We also use the generalized discrete Fourier transform to give the inverse formula for both the nonrepeated-root and repeated-root cases. Then we produce a formula which can be used to construct a QT code given the component codes.     

Galois LCD codes over finite fields

In this paper, we generalize the linear complementary dual codes (LCD codes for short) to k-Galois LCD codes, and study them by a uniform method. A necessary and sufficient condition for linear codes to be k-Galois LCD codes is obtained, two classes of k-Galois LCD MDS codes are exhibited. Then, necessary and sufficient conditions for λ-constacyclic codes being k-Galois LCD codes are characterized. Some classes of k-Galois LCD λ-constacyclic MDS codes are constructed. Finally, we study Hermitian LCD λ-constacyclic codes, and present a class of Hermitian LCD λ-constacyclic MDS codes.     

Quadratic spaces over finite fields and codes

Let V be a finite-dimensional quadratic space over a finite field GF(?) of characteristic different from 2. It is shown that, even if V is singular, the geometry of V is completely determined by the number of points on the unit sphere, the “sphere of the nonsquares,” and the “0-sphere.” For ? = 3, this implies that two codes over GF(3) with the same weight enumerator are isometric.     

New MDS self-dual codes over finite fields

In this paper we construct MDS Euclidean and Hermitian self-dual codes which are extended cyclic duadic codes or negacyclic codes. We also construct Euclidean self-dual codes which are extended negacyclic codes. Based on these constructions, a large number of new MDS self-dual codes are given with parameters for which self-dual codes were not previously known to exist.     

Ideal secret sharing schemes whose minimal qualified subsets have at most three participants

One of the main open problems in secret sharing is the characterization of the access structures of ideal secret sharing schemes. Brickell and Davenport proved that every one of these ideal access structures is related in a certain way to a unique matroid. Specifically, they are matroid ports. In addition to the search of general results, this difficult open problem has been studied in previous works for several families of access structures. In this paper we do the same for access structures with rank 3, that is, structures whose minimal qualified subsets have at most three participants. We completely characterize and classify the rank-3 access structures that are matroid ports. We prove that all access structures with rank three that are ports of matroids greater than 3 are ideal. After the results in this paper, the only open problem in the characterization of the ideal access structures with rank three is to characterize the rank-3 matroids that can be represented by an ideal secret sharing scheme. A previous version of this paper appeared in Fifth Conference on Security and Cryptography for Networks, SCN 2006, Lecture Notes in Computer Science 4116 (2006) 201–215.     

On nonsystematic perfect codes over finite fields

The nonsystematic perfect q-ary codes over finite field F _q of length n = (q ^m − 1)/(q − 1) are constructed in the case when m ≥ 4 and q ≥ 2 and also when m = 3 and q is not prime. For q ≠ 3, 5, these codes can be constructed by switching seven disjoint components of the Hamming code H _q ⁿ ; and, for q = 3, 5, eight disjoint components.     

On full-rank perfect codes over finite fields

We propose a construction of full-rank q-ary 1-perfect codes. This is a generalization of the construction of full-rank binary 1-perfect codes by Etzion and Vardy (1994). The properties of the i-components of q-ary Hamming codes are investigated, and the construction of full-rank q-ary 1-perfect codes is based on these properties. The switching construction of 1-perfect codes is generalized to the q-ary case. We propose a generalization of the notion of an i-component of a 1-perfect code and introduce the concept of an (i, σ)-component of a q-ary 1-perfect code. We also present a generalization of the Lindström–Schönheim construction of q-ary 1-perfect codes and provide a lower bound for the number of pairwise distinct q-ary 1-perfect codes of length n.     

An explication of secret sharing schemes

This paper is an explication of secret sharing schemes, emphasizing combinatorial construction methods. The main problem we consider is the construction of perfect secret sharing schemes, for specified access structures, with the maximum possible information rate.In this paper, we present numerous direct constructions for secret sharing schemes, such as the Shamir threshold scheme, the Boolean circuit construction of Benaloh and Leichter (for general access structures), the vector space construction of Brickell, and the Simmons geometric construction. We discuss the connections between ideal schemes (i.e., those with information rate equal to one) and matroids. We also mention the entropy bounds of Capocelli et al. Then we give a very general construciton, called the decomposition construction, and numerous applications of it. In particular, we study schemes for access structures based on graphs and the many interesting bounds that can be proved; and we determine the exact value of the optimal information rate for all access structures on at most four participants.Research supported by NSERC (Canada) grant A9287.     

Geometric secret sharing schemes and their duals

Given a set of participants we wish to distribute information relating to a secret in such a way that only specified groups of participants can reconstruct the secret. We consider here a special class of such schemes that can be described in terms of finite geometries as first proposed by Simmons. We formalize the Simmons model and show that given a geometric scheme for a particular access structure it is possible to find another geometric scheme whose access structure is the dual of the original scheme, and which has the same average and worst-case information rates as the original scheme. In particular this shows that if an ideal geometric scheme exists then an ideal geometric scheme exists for the dual access structure.This work was supported by the Science and Engineering Research Council Grant GR/G 03359.This work was supported by the Australian Research Council.     

Random hypersurfaces and embedding curves in surfaces over finite fields

We use Poonen's closed point sieve to prove two independent results. First, we show that the obvious obstruction to embedding a curve in an unspecified smooth surface is the only obstruction over a perfect field, by proving the finite field analogue of a Bertini-type result of Altman and Kleiman. Second, we prove a conjecture of Vakil and Wood on the asymptotic probability of hypersurface sections having a prescribed number of singularities.