American Institute of Mathematical Sciences

Alves, Panek and Firer (Error-block codes and poset metrics, Adv. Math. Commun., 2 (2008), 95-111) classified all poset block structures which turn the [8,4,4] extended binary Hamming code into a 1-perfect poset block code. However, the proof needs corrections that are supplied in this paper. We provide a counterexample to show that the extended binary Golay code is not 1-perfect for the proposed poset block structures. All poset block structures turning the extended binary and ternary Golay codes into 1-perfect codes are classified.

This paper is concerned with \begin{document} ${{\mathbb{Z}}_{2}}{{\mathbb{Z}}_{2}}{{\mathbb{Z}}_{4}}$ \end{document}-additive cyclic codes. These codes can be identified as submodules of the ring \begin{document} ${\mathbb{Z}}_{2}[x]/\langle x^r-1\rangle × {\mathbb{Z}}_{2}[x]/\langle x^s-1\rangle × {\mathbb{Z}}_{4}[x]/\langle x^t-1\rangle$ \end{document}. There are two major ingredients. First, we determine the generator polynomials and minimum generating sets of this kind of codes. Furthermore, we investigate their dual codes. We determine the structure of the dual of separable \begin{document} ${{\mathbb{Z}}_{2}}{{\mathbb{Z}}_{2}}{{\mathbb{Z}}_{4}}$ \end{document}-additive cyclic codes completely. For the dual of non-separable \begin{document} ${{\mathbb{Z}}_{2}}{{\mathbb{Z}}_{2}}{{\mathbb{Z}}_{4}}$ \end{document}-additive cyclic codes, we give their structural properties in a few special cases.

Let \begin{document} $\mathbb{F}_q$ \end{document} be a finite field with \begin{document} $q$ \end{document} elements and denote by \begin{document} $\theta : \mathbb{F}_q\to\mathbb{F}_q$ \end{document} an automorphism of \begin{document} $\mathbb{F}_q$ \end{document}. In this paper, we deal with skew constacyclic codes, that is, linear codes of \begin{document} $\mathbb{F}_q^n$ \end{document} which are invariant under the action of a semi-linear map \begin{document} $ \phi _{\alpha,\theta }:\mathbb{F}_q^n\to\mathbb{F}_q^n$ \end{document}, defined by \begin{document} $ \phi _{\alpha,\theta }(a_0,...,a_{n-2}, a_{n-1}): = (\alpha \theta (a_{n-1}),\theta (a_0),...,\theta (a_{n-2}))$ \end{document} for some \begin{document} $\alpha \in \mathbb{F}_q\setminus\{0\}$ \end{document} and \begin{document} $n≥2$ \end{document}. In particular, we study some algebraic and geometric properties of their dual codes and we give some consequences and research results on \begin{document} $1$\end{document}-generator skew quasi-twisted codes and on MDS skew constacyclic codes.

An \begin{document} $(n,N,k,m)$ \end{document}-combinatorial batch code (CBC) was defined by Paterson, Stinson and Wei as a purely combinatorial version of batch codes which were first proposed by Ishai, Kushilevitz, Ostrovsky and Sahai. It is a system consisting of \begin{document} $m$ \end{document} subsets of an \begin{document} $n$ \end{document}-element set such that any \begin{document} $k$ \end{document} distinct elements can be retrieved by reading at most one (or in general, \begin{document} $t$ \end{document}) elements from each subset and the number of total elements in \begin{document} $m$ \end{document} subsets is \begin{document} $N$ \end{document}. For given parameters \begin{document} $n,k,m$ \end{document}, the goal is to determine the minimum \begin{document} $N$ \end{document}, denoted by \begin{document} $N(n,k,m)$ \end{document}.

So far, for \begin{document} $k≥5$ \end{document}, \begin{document} $m+3≤ n< \binom{m}{k-2}$ \end{document}, precise values of \begin{document} $N(n,k,m)$ \end{document} have not been established except for some special parameters. In this paper, we present a lower bound on \begin{document} $N(n,k,k+1)$ \end{document}, which is tight for some \begin{document} $n$ \end{document} and \begin{document} $k$ \end{document}. Based on this lower bound, the monotonicity of optimal values of CBC and several constructions, we obtain \begin{document} $N(m+4,5,m)$ \end{document}, \begin{document} $N(m+4,6,m)$ \end{document} and \begin{document} $N(m+3,7,m)$ \end{document} in different ways.

Bent and vectorial bent functions have applications in cryptography and coding and are closely related to objects in combinatorics and finite geometry, like difference sets, relative difference sets, designs and divisible designs. Bent functions with certain additional properties yield partial difference sets of which the Cayley graphs are always strongly regular. In this article we continue research on connections between bent functions and partial difference sets respectively strongly regular graphs. For the first time we investigate relations between vectorial bent functions and partial difference sets. Remarkably, properties of the set of the duals of the components play here an important role. Seeing conventional bent functions as 1-dimensional vectorial bent functions, some earlier results on strongly regular graphs from bent functions follow from our more general results. Finally we describe a recursive construction of infinitely many partial difference sets with a secondary construction of p-ary bent functions.

Self-duality of Gabidulin codes was investigated in [10] and the authors provided an if and only if condition for a Gabidulin code to be equivalent to a self-dual maximum rank distance (MRD) code. In this paper, we investigate the analog problem for generalized twisted Gabidulin codes (a larger family of linear MRD codes including the family of Gabidulin codes). We observe that the condition presented in [10] still holds for generalized Gabidulin codes (an intermediate family between Gabidulin codes and generalized twisted Gabidulin codes). However, beyond the family of generalized Gabidulin codes we observe that some additional conditions are required depending on the additional parameters. Our tools are similar to those in [10] but we also use linearized polynomials, which leads to further tools and direct proofs.

In this paper, we study a class of skew-cyclic codes using a skew polynomial ring over \begin{document}$R = \mathbb{Z}_4+u\mathbb{Z}_4;u^2 = 1$ \end{document}, with an automorphism \begin{document}$θ$ \end{document} and a derivation \begin{document}$δ_θ$ \end{document}. We generalize the notion of cyclic codes to skew-cyclic codes with derivation, and call such codes as \begin{document}$δ_θ$ \end{document}-cyclic codes. Some properties of skew polynomial ring \begin{document}$R[x, θ, {δ_θ}]$ \end{document} are presented. A \begin{document}$δ_θ$ \end{document}-cyclic code is proved to be a left \begin{document}$R[x, θ, {δ_θ}]$ \end{document}-submodule of \begin{document}$\frac{R[x, θ, {δ_θ}]}{\langle x^n-1 \rangle}$ \end{document}. The form of a parity-check matrix of a free \begin{document}$δ_θ$ \end{document}-cyclic codes of even length \begin{document}$n$ \end{document} is presented. These codes are further generalized to double \begin{document}$δ_θ$ \end{document}-cyclic codes over \begin{document}$R$ \end{document}. We have obtained some new good codes over \begin{document}$\mathbb{Z}_4$ \end{document} via Gray images and residue codes of these codes. The new codes obtained have been reported and added to the database of \begin{document}$\mathbb{Z}_4$ \end{document}-codes [2].

Since 2013 there have been several developments in algorithms for computing discrete logarithms in small-characteristic finite fields, culminating in a quasi-polynomial algorithm. In this paper, we report on our successful computation of discrete logarithms in the cryptographically-interesting characteristic-three finite field \begin{document}$\mathbb{F}_{3^{6.509}}$\end{document}    using these new algorithms; prior to 2013, it was believed that this field enjoyed a security level of 128 bits. We also show that a recent idea of Guillevic can be used to compute discrete logarithms in the cryptographically-interesting finite field \begin{document}$\mathbb{F}_{3^{6.709}}$\end{document}    using essentially the same resources as we expended on the \begin{document}$\mathbb{F}_{3^{6.509}}$\end{document}    computation. Finally, we argue that discrete logarithms in the finite field \begin{document}$\mathbb{F}_{3^{6.1429}}$\end{document}    can feasibly be computed today; this is significant because this cryptographically-interesting field was previously believed to enjoy a security level of 192 bits.

The matrix description of a near-MDR code is given, and some judging criterions are presented for near-MDR codes. We also give the weight distribution of a near-MDR code and the applications of a near-MDR code to secret sharing schemes. Furthermore, we will introduce the chain condition for free codes over finite chain rings, and then present a formula for computing higher weights of tensor product of free codes satisfying the chain condition. We will also find a chain for any near-MDR code, and thus show that any near-MDR code satisfies the chain condition.

An interpolation-based decoding scheme for \begin{document}$L$\end{document}-interleaved subspace codes is presented. The scheme can be used as a (not necessarily polynomial-time) list decoder as well as a polynomial-time probabilistic unique decoder. Both interpretations allow to decode interleaved subspace codes beyond half the minimum subspace distance. Both schemes can decode \begin{document}$\gamma $\end{document} insertions and \begin{document}$\delta $\end{document} deletions up to \begin{document}$\gamma +L\delta \leq L({{n}_{t}}-k)$\end{document}, where \begin{document}${{n}_{t}}$\end{document} is the dimension of the transmitted subspace and \begin{document}$k$\end{document} is the number of data symbols from the field \begin{document}${{\mathbb{F}}_{{{q}^{m}}}}$\end{document}. Further, a complementary decoding approach is presented which corrects \begin{document}$\gamma $\end{document} insertions and \begin{document}$\delta $\end{document} deletions up to \begin{document}$L\gamma +\delta \leq L({{n}_{t}}-k)$\end{document}. Both schemes use properties of minimal Gröebner bases for the interpolation module that allow predicting the worst-case list size right after the interpolation step. An efficient procedure for constructing the required minimal Gröebner basis using the general Kötter interpolation is presented. A computationally- and memory-efficient root-finding algorithm for the probabilistic unique decoder is proposed. The overall complexity of the decoding algorithm is at most \begin{document}$\mathcal{O}\left( {{L}^{2}}n_{r}^{2} \right)$\end{document} operations in \begin{document}${{\mathbb{F}}_{{{q}^{m}}}}$\end{document} where \begin{document}${{n}_{r}}$\end{document} is the dimension of the received subspace and \begin{document}$L$\end{document} is the interleaving order. The analysis as well as the efficient algorithms can also be applied for accelerating the decoding of interleaved Gabidulin codes.

We investigate the \begin{document}$ k$\end{document}-error linear complexity of pseudorandom binary sequences of period \begin{document}$ p^{\mathfrak{r}} $\end{document} derived from the Euler quotients modulo \begin{document}$ p^{\mathfrak{r}-1} $\end{document}, a power of an odd prime \begin{document}$ p $\end{document} for \begin{document}$ \mathfrak{r}≥2 $\end{document}. When \begin{document}$ \mathfrak{r} = 2 $\end{document}, this is just the case of polynomial quotients (including Fermat quotients) modulo \begin{document}$p $\end{document}, which has been studied in an earlier work of Chen, Niu and Wu. In this work, we establish a recursive relation on the \begin{document}$ k $\end{document}-error linear complexity of the sequences for the case of \begin{document}$ \mathfrak{r}≥3 $\end{document}. We also state the exact values of the \begin{document}$ k $\end{document}-error linear complexity for the case of \begin{document}$ \mathfrak{r} = 3 $\end{document}. From the results, we can find that the \begin{document}$ k $\end{document}-error linear complexity of the sequences (of period \begin{document}$ p^{\mathfrak{r}} $\end{document}) does not decrease dramatically for \begin{document}$ k<p^{\mathfrak{r}-2}(p-1)^2/2 $\end{document}.

Codes in finite projective spaces equipped with the subspace distance have been proposed for error control in random linear network coding. Here we collect the present knowledge on lower and upper bounds for binary subspace codes for projective dimensions of at most \begin{document}$ 7 $\end{document}, i.e., affine dimensions of at most \begin{document}$ 8 $\end{document}. We obtain several improvements of the bounds and perform two classifications of optimal subspace codes, which are unknown so far in the literature.