American Institute of Mathematical Sciences

In the present study we consider two variants of Schnorr-Shevchenko method (SS) for solving hard knapsack problems, which are on average faster than the SS method. Furthermore, we study the compact knapsack problem i.e. the solution space is not {0, 1} as in knapsack problem but some larger set, and we present an algorithm to attack this problem. Finally, we provide a three move sound id-scheme based on the compact knapsack problem.

The hulls of linear and cyclic codes have been extensively studied due to their wide applications. The dimensions and average dimension of the Euclidean hull of linear and cyclic codes have been well-studied. In this paper, the average dimension of the Hermitian hull of constacyclic codes of length \begin{document}$n$\end{document} over a finite field \begin{document}$\mathbb{F}_{q^2}$\end{document} is determined together with some upper and lower bounds. It turns out that either the average dimension of the Hermitian hull of constacyclic codes of length \begin{document}$n$\end{document} over \begin{document}$\mathbb{F}_{q^2}$\end{document} is zero or it grows the same rate as \begin{document}$n$\end{document}. Comparison to the average dimension of the Euclidean hull of cyclic codes is discussed as well.

In large scale distributed storage systems (DSS) deployed in cloud computing, correlated failures resulting in simultaneous failure (or, unavailability) of blocks of nodes are common. In such scenarios, the stored data or a content of a failed node can only be reconstructed from the available live nodes belonging to the available blocks. To analyze the resilience of the system against such block failures, this work introduces the framework of Block Failure Resilient (BFR) codes, wherein the data (e.g., a file in DSS) can be decoded by reading out from a same number of codeword symbols (nodes) from a subset of available blocks of the underlying codeword. Further, repairable BFR codes are introduced, wherein any codeword symbol in a failed block can be repaired by contacting a subset of remaining blocks in the system. File size bounds for repairable BFR codes are derived, and the trade-off between per node storage and repair bandwidth is analyzed, and the corresponding minimum storage regenerating (BFR-MSR) and minimum bandwidth regenerating (BFR-MBR) points are derived. Explicit codes achieving the two operating points for a special case of parameters are constructed, wherein the underlying regenerating codewords are distributed to BFR codeword symbols according to combinatorial designs. Finally, BFR locally repairable codes (BFR-LRC) are introduced, an upper bound on the resilience is derived and optimal code construction are provided by a concatenation of Gabidulin and MDS codes. Repair efficiency of BFR-LRC is further studied via the use of BFR-MSR/MBR codes as local codes. Code constructions achieving optimal resilience for BFR-MSR/MBR-LRCs are provided for certain parameter regimes. Overall, this work introduces the framework of block failures along with optimal code constructions, and the study of architecture-aware coding for distributed storage systems.

We introduce a new measure of pseudorandomness, the (periodic) Hamming correlation of order \begin{document}$\ell$\end{document} which generalizes the Hamming autocorrelation (\begin{document}$\ell = 2$\end{document}). We analyze the relation between the Hamming correlation of order \begin{document}$\ell$\end{document} and the periodic analog of the correlation measure of order \begin{document}$\ell$\end{document} introduced by Mauduit and Sárközy. Roughly speaking, the correlation measure of order \begin{document}$\ell$\end{document} is a finer measure than the Hamming correlation of order \begin{document}$\ell$\end{document}. However, the latter can be much faster calculated and still detects some undesirable linear structures. We analyze examples of sequences with optimal Hamming correlation and show that they have large Hamming correlation of order \begin{document}$\ell$\end{document} for some very small \begin{document}$\ell>2$\end{document}. Thus they have some undesirable linear structures, in particular in view of cryptographic applications such as secure communications.

We provide sufficient conditions to guarantee that a translation based cipher is not vulnerable with respect to the partition-based trapdoor. This trapdoor has been introduced, recently, by Bannier et al. (2016) and it generalizes that introduced by Paterson in 1999. Moreover, we discuss the fact that studying the group generated by the round functions of a block cipher may not be sufficient to guarantee security against these trapdoors for the cipher.

Let \begin{document}$q$\end{document} be a prime greater than 4. In this paper, we determine the coefficients of the discrete Fourier transform over the finite field \begin{document}$\mathbb {F}_q$\end{document} of two classes of quaternary sequences of even length with optimal autocorrelation. They are quaternary sequence with period \begin{document}$2p$\end{document} derived from binary Legendre sequences and quaternary sequence with period \begin{document}$2p(p+2)$\end{document} derived from twin-prime sequences pair. As applications, the linear complexities over the finite field \begin{document}$\mathbb {F}_q$\end{document} of both of the quaternary sequences are determined.

In this paper, we propose a novel method for constructing new uncorrelated asymmetric zero correlation zone (UA-ZCZ) sequence sets by interleaving perfect sequences. As a type of ZCZ sequence set, an A-ZCZ sequence set consists of multiple sequence subsets. Different subsets are correlated in conventional A-ZCZ sequence set but uncorrelated in our scheme. In other words, the cross-correlation function (CCF) between two arbitrary sequences which belong to different subsets has quite a large zero cross-correlation zone (ZCCZ). Analytical results demonstrate that the UA-ZCZ sequence set proposed herein is optimal with respect to the upper bound of ZCZ sequence set. Specifically, our scheme enables the flexible selection of ZCZ length, which makes it extremely valuable for designing spreading sequences for quasi-synchronous code-division multiple-access (QS-CDMA) systems.

This text gives a first definition of the $θ$-duadic codes where \begin{document}$θ$\end{document} is an automorphism of \begin{document}$\mathbb{F}_q$\end{document}. A link with the self-orthogonal \begin{document}$θ$\end{document}-cyclic codes is established. A construction and an enumeration are provided when \begin{document}$q$\end{document} is the square of a prime number \begin{document}$p$\end{document}. In addition, new self-dual binary codes \begin{document}$ [72, 36, 12] $\end{document} are obtained from extended $θ$-duadic codes defined on \begin{document}$\mathbb{F}_4$\end{document}.

In this paper, we study LCD BCH codes over the finite field GF\begin{document}$(q)$\end{document} with two types of lengths \begin{document}$n$\end{document}, where \begin{document}$n = q^l+1$\end{document} and \begin{document}$n = (q^l+1)/(q+1)$\end{document}. Several classes of LCD BCH codes are given and their parameters are determined or bounded by exploring the cyclotomic cosets modulo \begin{document}$n$\end{document}. For \begin{document}$n = q^l+1$\end{document}, we determine the dimensions of the codes with designed distance \begin{document}$δ$\end{document}, where \begin{document}$q^{\lfloor\frac{l+1}{2}\rfloor}+1 ≤ δ ≤q ^{\lfloor\frac{l+3}{2}\rfloor}+1$\end{document}. For \begin{document}$n = (q^l+1)/(q+1)$\end{document}, the dimensions of the codes with designed distance \begin{document}$δ$\end{document} are presented, where \begin{document}$2 ≤ δ ≤q ^\frac{l-1}{2}+1$\end{document}.

In this work we focus on a connection between sumsets and covering codes in an arbitrary finite module. For this purpose, bounds on a new problem on sumsets are obtained from well-known results of additive number theory, namely, the Cauchy-Davenport theorem, the Vosper theorem and a theorem due to Hamidoune-Rødseth. As an application, the approach is able to extend the Blokhuis-Lam theorems and a construction of covering codes by Honkala to an arbitrary module.

A construction of designs acted on by simple primitive groups is used to find some 1-designs and associated self-orthogonal, decomposable and irreducible codes that admit the simple group \begin{document}${\rm He}$\end{document} of Held as an automorphism group. The properties of the codes are given and links with modular representation theory are established. Further, we introduce a method of constructing self-orthogonal binary codes from orbit matrices of weakly self-orthogonal designs. Furthermore, from the support designs of the obtained self-orthogonal codes we construct strongly regular graphs with parameters (21, 10, 3, 6), (28, 12, 6, 4), (49, 12, 5, 2), (49, 18, 7, 6), (56, 10, 0, 2), (63, 30, 13, 15), (105, 32, 4, 12), (112, 30, 2, 10) and (120, 42, 8, 18).