American Institute of Mathematical Sciences

Recently, several classes of cyclic codes with three nonzero weights were constructed. With the generic construction presented by C. Ding, T. Helleseth, T. Kløve and X. Wang, we present new systematic authentication codes based on these cyclic codes. In this paper, we study three special classes of cyclic codes and their authentication codes. With the help of exponential sums, we calculate the maximum success probabilities of the impersonation and substitution attacks on the authentication codes. Our results show that these new authentication codes are better than some of the authentication codes in the literature. As a byproduct, the number of times that each element occurs as the coordinates in the codewords of the cyclic codes is settled, which is a difficult problem in general.

The problem of private set-intersection (PSI) has been traditionally treated as an instance of the more general problem of multi-party computation (MPC). Consequently, in order to argue security, or compose these protocols one has to rely on the general theory that was developed for the purpose of MPC. The pursuit of efficient protocols, however, has resulted in designs that exploit properties pertaining to PSI. In almost all practical applications where a PSI protocol is deployed, it is expected to be executed multiple times, possibly on related inputs. In this work we initiate a dedicated study of PSI in the multi-interaction (MI) setting. In this model a server sets up the common system parameters and executes set-intersection multiple times with potentially different clients. We discuss a few attacks that arise when protocols are naïvely composed in this manner and, accordingly, craft security definitions for the MI setting and study their inter-relation. Finally, we suggest a set of protocols that are MI-secure, at the same time almost as efficient as their parent, stand-alone, protocols.

Combinatorial batch codes were defined by Paterson, Stinson, and Wei as purely combinatorial versions of the batch codes introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai. There are \begin{document}$n$\end{document} items and \begin{document}$m$\end{document} servers, each of which stores a subset of the items. A batch code is an arrangement for storing items on servers so that, for prescribed integers \begin{document}$k$\end{document} and \begin{document}$t$\end{document}, any \begin{document}$k$\end{document} items can be retrieved by reading at most \begin{document}$t$\end{document} items from each server. Silberstein defined an erasure batch code (with redundancy \begin{document}$r$\end{document}) as a batch code in which any \begin{document}$k$\end{document} items can be retrieved by reading at most \begin{document}$t$\end{document} items from each server, while any \begin{document}$r$\end{document} servers are unavailable (failed).

In this paper, we investigate erasure batch codes with \begin{document}$t = 1$\end{document} (each server can read at most one item) in a combinatorial manner. We determine the optimal (minimum) total storage of an erasure batch code for several ranges of parameters. Additionally, we relate optimal erasure batch codes to maximum packings. We also identify a necessary lower bound for the total storage of an erasure batch code, and we relate parameters for which this trivial lower bound is achieved to the existence of graphs with appropriate girth.

In practice, when a frequency-hopping sequence (FHS) set is applied in a frequency-hopping multiple-access (FHMA) system, its periodic partial Hamming correlation (PPHC) rather than its periodic Hamming correlation (PHC) within the whole period is used to evaluate the system performance. Moreover, FHS sets with low hit zone (LHZ) can be well applied in quasi-synchronous (QS) FHMA systems in which some relative time delay among different users within a zone around the origin can be allowed. Therefore, it is very urgent to conduct research on LHZ FHS sets with optimal PPHC property in depth. In this paper, we first derive a new tighter lower bound on the maximum PPHC of an LHZ FHS set. Then we present a new class of optimal one-coincidence FHS sets. Finally we have a construction of LHZ FHS sets which can be optimal with respect to our new lower bound.

Power decoding, or "decoding using virtual interleaving" is a technique for decoding Reed-Solomon codes up to the Sudan radius. Since the method's inception, it has been an open question if it is possible to use this approach to decode up to the Johnson radius - the decoding radius of the Guruswami-Sudan algorithm. In this paper we show that this can be done by incorporating a notion of multiplicities. As the original Power decoding, the proposed algorithm is a one-pass algorithm: decoding follows immediately from solving a shift-register type equation, which we show can be done in quasi-linear time. It is a "partial bounded-distance decoding algorithm" since it will fail to return a codeword for a few error patterns within its decoding radius; we investigate its failure behaviour theoretically as well as give simulation results.

Shiromoto (Linear Algebra Applic 295 (1999) 191-200) obtained the basic exact sequence for the Lee and Euclidean weights of linear codes over \begin{document}$ \mathbb{Z}_{\ell}$\end{document} and as an application, he found the Singleton bounds for linear codes over \begin{document}$ \mathbb{Z}_{\ell}$\end{document} with respect to Lee and Euclidean weights. Huffman (Adv. Math. Commun 7 (3) (2013) 349-378) obtained the Singleton bound for \begin{document}$ \mathbb{F}_{q}$\end{document}-linear \begin{document}$ \mathbb{F}_{q^{t}}$\end{document}-codes with respect to Hamming weight. Recently the theory of \begin{document}$ \mathbb{F}_{q}$\end{document}-linear \begin{document}$ \mathbb{F}_{q^{t}}$\end{document}-codes were generalized to \begin{document}$ R$\end{document}-additive codes over \begin{document}$ R$\end{document}-algebras by Samei and Mahmoudi. In this paper, we generalize Shiromoto's results for linear codes over \begin{document}$ \mathbb{Z}_{\ell}$\end{document} to \begin{document}$ R$\end{document}-additive codes. As an application, when \begin{document}$ R$\end{document} is a chain ring, we obtain the Singleton bounds for \begin{document}$ R$\end{document}-additive codes over free \begin{document}$ R$\end{document}-algebras. Among other results, the Singleton bounds for additive codes over Galois rings are given.

While analyzing \begin{document}$ S$\end{document}-boxes, or vectorial Boolean functions, it is of interest to approximate its component functions by affine functions. In the usual attack models, it is assumed that all input vectors to an \begin{document}$ S$\end{document}-box are equiprobable. The nonlinearity of an \begin{document}$ S$\end{document}-box is defined, subject to this assumption. In this paper, we explore the possibility of linear cryptanalysis of an \begin{document}$ S$\end{document}-box by introducing biased inputs and thus propose a generalized notion of nonlinearity along with a generalization of the Walsh-Hadamard spectrum of an \begin{document}$ S$\end{document}-box.

Irreducible constacyclic codes constitute an important family of error-correcting codesand have applications in space communications.In this paper, we provide a trace description of irreducible constacyclic codes of length \begin{document}$n$\end{document} over the finite field \begin{document}$\mathbb{F}_{q}$\end{document} of order \begin{document}$q,$\end{document} where \begin{document}$n$\end{document} is a positive integer and \begin{document}$q$\end{document} is a prime power coprime to \begin{document}$n.$\end{document} As an application, we determine Hamming weight distributions of some irreducible constacyclic codes of length \begin{document}$n$\end{document} over \begin{document}$\mathbb{F}_{q}.$\end{document} We also derive a weight-divisibility theorem for irreducible constacyclic codes, and obtain both lower and upper bounds on the non-zero Hamming weights in irreducible constacyclic codes. Besides illustrating our results with examples, we list some optimal irreducible constacyclic codes that attain the distance bounds given in Grassl's Table [8].

Motivated by previous computations in Garcia, Stichtenoth and Xing (2000) paper [11], we discuss the spectrum \begin{document}$\mathbf{M}(q^2)$\end{document} for the genera of maximal curves over finite fields of order \begin{document}$q^2$\end{document} with \begin{document}$7≤ q≤ 16$\end{document}. In particular, by using a result in Kudo and Harashita (2016) paper [22], the set \begin{document}$\mathbf{M}(7^2)$\end{document} is completely determined.

We introduce the Multilevel Erasure Channel (MEC) for binary extension field alphabets. The channel model is motivated by applications such as non-volatile multilevel read storage channels. Like the recently proposed \begin{document}$q$\end{document}-ary partial erasure channel (QPEC), the MEC is designed to capture partial erasures. The partial erasures addressed by the MEC are determined by erasures at the bit level of the \begin{document}$q$\end{document}-ary symbol representation. In this paper we derive the channel capacity of the MECand give a multistage decoding scheme on the MEC using binary codes. We also present a low complexity multistage \begin{document}$p$\end{document}-ary decoding strategy for codes on the QPEC when \begin{document}$q = p^k$\end{document}.We show that for appropriately chosen component codes, capacity on the MEC and QPEC may be achieved.

A \begin{document}${\mathbb{Z}}_{p^r}{\mathbb{Z}}_{p^s}$\end{document}-additive code, \begin{document}$r≤ s$\end{document}, is a\begin{document} ${\mathbb{Z}}_{p^s}$\end{document}-submodule of \begin{document}${{\mathbb{Z}}_{p^r}^α× {\mathbb{Z}}_{p^s}^β}$\end{document}. We introduce \begin{document}${\mathbb{Z}}_{p^r}{\mathbb{Z}}_{p^s}$\end{document}-additive cyclic codes. These codes can be seen as \begin{document}${\mathbb{Z}}_{p^s}[x]$\end{document}-submodules of \begin{document}${\mathcal{R}^{α,β}_{r,s}}= \frac{{\mathbb{Z}}_{p^r}[x]}{\langle x^α-1\rangle}×\frac{{\mathbb{Z}}_{p^s}[x]}{\langle x^β-1\rangle}$\end{document}. We determine the generator polynomials of a code over \begin{document}${\mathcal{R}^{α,β}_{r,s}}$\end{document} and a minimal spanning set over \begin{document}${{\mathbb{Z}}_{p^r}^α× {\mathbb{Z}}_{p^s}^β}$\end{document} in terms of the generator polynomials. We also study the duality in the module \begin{document}${\mathcal{R}^{α,β}_{r,s}}$\end{document}.Our results generalise those for \begin{document}${\mathbb{Z}}_{2}{\mathbb{Z}}_{4}$\end{document}-additive cyclic codes.

We present a new family of one-coincidence sequence sets suitable for frequency hopping code division multiple access (FH-CDMA) systems with dispersed (low density) sequence elements. These sets are derived from one-coincidence prime sequence sets, such that for each one-coincidence prime sequence set there is a new one-coincidence set comprised of sequences with dispersed sequence elements, required in some circumstances, for FH-CDMA systems. Getting rid of crowdedness of sequence elements is achieved by doubling the size of the sequence element alphabet. In addition, this doubling process eases control over the distance between adjacent sequence elements. Properties of the new sets are discussed.

We study complementary information set codes of length \begin{document}$tn$\end{document} and dimension \begin{document}$n$\end{document} of order \begin{document}$t$\end{document} called (\begin{document}$t-$\end{document}CIS code for short). Quasi-cyclic (QC) and quasi-twisted (QT) \begin{document}$t$\end{document}-CIS codes are enumerated by using their concatenated structure. Asymptotic existence results are derived for one-generator and fixed co-index QC and QT codes depending on Artin's primitive root conjecture. This shows that there are infinite families of rate \begin{document}$1/t$\end{document} long QC and QT \begin{document}$t$\end{document}-CIS codes with relative distance satisfying a modified Varshamov-Gilbert bound. Similar results are defined for the new and more general class of quasi-polycyclic codes introduced recently by Berger and Amrani.

In this paper, we discuss a point about applying known decomposition techniques in their most general form. Three versions of these methods, which are useful for obtaining upper bounds on the optimal information ratios of access structures, are known as: Stinson's $λ$-decomposition, $(λ, ω)$-decomposition and $λ$-weighted-decomposition, where the latter two are generalizations of the first one. We continue by considering the problem of determining the exact values of the optimal information ratios of the reduced access structures with exactly four minimal qualified subsets on six participants, which remained unsolved in Martí-Farré et al.'s paper [Des. Codes Cryptogr. 61 (2011), 167-186]. We improve the known upper bounds for all the access structures, except four cases, determining the exact values of the optimal information ratios. All three decomposition techniques are used while some cases are handled by taking full advantage of the generality of decompositions.

Finite length sequences with large nonlinear complexity over \begin{document}$\mathbb{Z}_{p}\, (p≥ 2)$\end{document} are investigated in this paper. We characterize all \begin{document}$p$\end{document}-ary sequences of length \begin{document}$n$\end{document} having nonlinear complexity \begin{document}$n-j$\end{document} for \begin{document}$j=2, 3$\end{document}, where \begin{document}$n$\end{document} is an integer satisfying \begin{document}$n≥ 2j$\end{document}. For \begin{document}$n≥ 8$\end{document}, all binary sequences of length \begin{document}$n$\end{document} with nonlinear complexity \begin{document}$n-4$\end{document} are obtained. Furthermore, the numbers and \begin{document}$k$\end{document}-error nonlinear complexity of these sequences are completely determined, respectively.