Search

Security of linear ramp secret sharing schemes can be characterized by the relative generalized Hamming weights of the involved codes. In this paper, we elaborate on the implication of these parameters and devise a method to estimate their value for general one-point algebraic geometric codes. As it is demonstrated, for Hermitian codes, our bound is often tight. Furthermore, for these codes, the relative generalized Hamming weights are often much larger than the corresponding generalized Hamming weights. [ABSTRACT FROM AUTHOR]

The number-theoretic code is a class of codes defined by single or multiple congruences. These codes are mainly used for correcting insertion and deletion errors, and for correcting asymmetric errors. This paper presents a formula for a generalization of the complete weight enumerator for the number-theoretic codes. This formula allows us to derive the weight enumerators and cardinalities for the number-theoretic codes. As a special case, this paper provides the Hamming weight enumerators and cardinalities of the non-binary Tenengolts’ codes, correcting single insertion or deletion. Moreover, we show that the formula deduces the MacWilliams identity for the linear codes over the ring of integers modulo $r$. [ABSTRACT FROM AUTHOR]

We revisit and take a closer look at a (not so well known) result of a 2017 paper, showing that the differential uniformity of any vectorial function is bounded from below by an expression depending on the size of its image set. We make explicit the resulting tight lower bound on the image set size of differentially $\delta $ -uniform functions (which is the only currently known non-trivial lower bound on the image set size of such functions). We also significantly improve an upper bound on the nonlinearity of vectorial functions obtained in the same reference and involving their image set size. We study when the resulting bound is sharper than the covering radius bound. We obtain as a by-product a lower bound on the Hamming distance between differentially $\delta $ -uniform functions and affine functions, which we improve significantly with a second bound. This leads us to study what can be the maximum Hamming distance between vectorial functions and affine functions. We provide an upper bound which is slightly sharper than a bound by Liu, Mesnager and Chen when $m < n$ , and a second upper bound, which is much stronger in the case (happening in practice) where $m$ is near $n$ ; we study the tightness of this latter bound; this leads to an interesting question on APN functions, which we address (negatively). We finally derive an upper bound on the nonlinearity of vectorial functions by means of their Hamming distance to affine functions and make more precise the bound on the differential uniformity which was the starting point of the paper. [ABSTRACT FROM AUTHOR]

A classical method of constructing a linear code over \mathrm GF(q) with a $t$ -design is to use the incidence matrix of the $t$ -design as a generator matrix over \mathrm GF(q) of the code. This approach has been extensively investigated in the literature. In this paper, a different method of constructing linear codes using specific classes of 2-designs is studied, and linear codes with a few weights are obtained from almost difference sets, difference sets, and a type of 2-designs associated to semibent functions. Two families of the codes obtained in this paper are optimal. The linear codes presented in this paper have applications in secret sharing and authentication schemes, in addition to their applications in consumer electronics, communication and data storage systems. A coding-theory approach to the characterization of highly nonlinear Boolean functions is presented. [ABSTRACT FROM AUTHOR]

Boolean functions with high algebraic immunity are important cryptographic primitives in some stream ciphers. In this paper, two methodologies for constructing minimal binary codes from sets, Boolean functions and vectorial Boolean functions with high algebraic immunity, are proposed. More precisely, a general construction of new minimal codes using minimal codes contained in Reed-Muller codes and sets without nonzero low degree annihilators is presented. The other construction allows us to yield minimal codes from certain subcodes of Reed-Muller codes and vectorial Boolean functions with high algebraic immunity. Via these general constructions, infinite families of minimal binary linear codes of dimension $m$ and length less than or equal to $m(m+1)/2$ are obtained. Besides, a lower bound on the minimum distance of the proposed minimal linear codes is established. Conjectures and open problems are also presented. The results of this paper show that Boolean functions with high algebraic immunity have nice applications in several fields additionally to symmetric cryptography, such as coding theory and secret sharing schemes. [ABSTRACT FROM AUTHOR]

The puncturing and shortening techniques are two important approaches to constructing new linear codes from old ones. In the past 70 years, a lot of progress on the puncturing technique has been made, and many works on punctured linear codes have been done. Many families of linear codes with interesting parameters have been obtained with the puncturing technique. However, little research on the shortening technique has been done and there are only a handful references on shortened linear codes. The first objective of this paper is to prove some general theory for shortened linear codes. The second objective is to study some shortened codes of the Hamming codes, Simplex codes, some Reed-Muller codes, and ovoid codes. Eleven families of optimal shortened codes over finite fields are presented in this paper. As a byproduct, five infinite families of 2-designs are also constructed from some of the shortened codes presented in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we apply two-to-one functions over F2n in two generic constructions of binary linear codes. We consider two-to-one functions in two forms: (1) generalized quadratic functions; and (2) (x2t + x)e with gcd (t, n) = gcd(e, 2n−1) = 1. Based on the study of the Walsh transforms of those functions or their variants, we present many classes of linear codes with few nonzero weights, including one weight, three weights, four weights, and five weights. The weight distributions of the proposed codes with one weight and with three weights are determined. In addition, we discuss the minimum distance of the dual of the constructed codes and show that some of them achieve the sphere packing bound. Moreover, examples show that some codes in this paper have best-known parameters. [ABSTRACT FROM AUTHOR]

ChaCha has been one of the most prominent ARX designs of the last few years because of its use in several systems. The cryptanalysis of ChaCha involves a differential attack that exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, the single-bit distinguisher in this differential attack was found up to 3rd round. At Crypto 2020, Beierle et al. introduced for the first time the single bit distinguishers for 3.5th round, which contributed significantly to regaining the flow of the research work in this direction. This discovery became the primary factor behind the huge improvement in the key recovery attack complexity in that work. This was followed by another work at Eurocrypt 2021, where a single bit distinguisher at 3.5th round helped to produce a 7th round distinguisher of ChaCha and a further improvement in the key recovery. In this paper, first, we provide the theoretical framework for the distinguisher given by Beierle et al. We mathematically derive the observed differential correlation for the particular position where the output difference is observed at 3.5th round. Also, Beierle et al. mentioned the issue of the availability of proper IVs to produce such distinguishers, and pointed out that not all keys have such IVs available. Here we provide a theoretical insight of this issue. Next, we revisit the work of Coutinho et al. (Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed the distinguisher and the key recovery with complexities 2218 and $2^{228.51}$ respectively. We show that the differential correlation for the 3.5th round is much smaller than the claim of Coutinho et al. This makes the attack complexities much higher than their claim. [ABSTRACT FROM AUTHOR]

In 1991, Wei proved a duality theorem that established an interesting connection between the generalized Hamming weights of a linear code and those of its dual code. Wei’s duality theorem has since been extensively studied from different perspectives and extended to other settings. In this paper, we re-examine Wei’s duality theorem and its various extensions, henceforth referred to as Wei-type duality theorems, from a new Galois connection perspective. Our approach is based on the observation that the generalized Hamming weights and the dimension/length profiles of a linear code form a Galois connection. The central result of this paper is a general Wei-type duality theorem for two Galois connections between finite subsets of $\mathbb {Z}$ , from which all the known Wei-type duality theorems can be recovered. As corollaries of our central result, we prove new Wei-type duality theorems for $w$ -demi-matroids defined over finite sets and $w$ -demi-polymatroids defined over modules with a composition series, which further allows us to unify and generalize all the known Wei-type duality theorems established for codes endowed with various metrics. [ABSTRACT FROM AUTHOR]

Recently, subfield codes of geometric codes over large finite fields ${\mathrm {GF}}(q)$ with dimension 3 and 4 were studied and distance-optimal subfield codes over ${\mathrm {GF}}(p)$ were obtained, where $q=p^{m}$. The key idea for obtaining very good subfield codes over small fields is to choose very good linear codes over an extension field with small dimension. This paper first presents a general construction of $[q+1, 2, q]$ MDS codes over ${\mathrm {GF}}(q)$ , and then studies the subfield codes over ${\mathrm {GF}}(p)$ of some of the $[q+1, 2,q]$ MDS codes over ${\mathrm {GF}}(q)$. Two families of dimension-optimal codes over ${\mathrm {GF}}(p)$ are obtained, and several families of nearly optimal codes over ${\mathrm {GF}}(p)$ are produced. Several open problems are also proposed in this paper. [ABSTRACT FROM AUTHOR]

This paper generalizes the method proposed by Poulliat et al. for the determination of the optimal Galois field coefficients of a non-binary LDPC parity check constraint based on the binary image of the code. Optimal, or almost-optimal, parity check coefficients are given for check degree varying from 4 to 20 and Galois field varying from GF (64) up to GF (1024). For all given sets of coefficients, no codeword of Hamming weight two exists. A reduced complexity algorithm to compute the binary Hamming weight 3 of a parity check is proposed. When the number of sets of coefficients is too high for an exhaustive search and evaluation, a local greedy search is performed. Explicit tables of coefficients are given. The proposed sets of coefficients can effectively replace the random selection of coefficients often used in NB-LDPC construction. [ABSTRACT FROM AUTHOR]

Tietäväinen’s upper and lower bounds assert that for block-length- $n$ linear codes with dual distance $d$ , the covering radius $R$ is at most $({n}/{2})-(({1}/{2})-o(1))\sqrt {dn}$ and typically at least $({n}/{2})-\Theta (({dn\log {({n}/{d})}})^{1/2})$. The gap between those bounds on $R -({n}/{2})$ is a $\Theta (({\log {({n}/{d})}})^{1/2})$ factor related to the gap between the worst covering radius given $d$ and the sphere-covering bound. Our focus in this paper is on the case when $d = o(n)$ , i.e., when the code size is subexponential and the gap is $w(1)$. We show that up to a constant, the gap can be eliminated by relaxing the covering requirement to allow for missing $o(1)$ fraction of points. Namely, if the dual distance $d = o(n)$ , then for sufficiently large $d$ , almost all points can be covered with radius $R\leq ({n}/{2})-\Theta (({dn\log {({n}/{d})}})^{1/2})$. Compared with random linear codes, our bound on $R-({n}/{2})$ is asymptotically tight up to a factor less than 3. We give applications to dual-BCH codes. The proof builds on the author’s previous work on the weight distribution of cosets of linear codes, which we simplify in this paper and extend from codes to probability distributions on $\{0,1\}^{n}$ , thus enabling the extension of the earlier result to $(d-1)$ -wise independent distributions. [ABSTRACT FROM AUTHOR]

Codes with locality are a class of codes introduced by Gopalan et al. to efficiently repair a failed node, by minimizing the number of nodes contacted during repair. An $[n,k]$ systematic code is said to have information locality $r$ , if each message symbol can be recovered by accessing $\leq r$ other symbols. An $[n,k]$ code is said to have all-symbol locality $r$ , if each code symbol can be recovered by accessing $\leq r$ other symbols. In this paper, we consider a generalization of codes with all-symbol locality to the case of handling two erasures. We study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. We refer to these codes as sequential-recovery locally repairable codes (denoted by 2-seq LR codes). Earlier approaches to handling multiple erasures considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. We derive an upper bound on the rate of 2-seq LR codes. We provide constructions based on regular graphs which are rate-optimal with respect to the derived bound. We also characterize the structure of any rate-optimal code. By studying the Generalized Hamming Weights of the dual code, we derive a recursive upper bound on the minimum distance of 2-seq LR codes. We also provide constructions of a family of codes based on Turán graphs, that are optimal with respect to this bound. We also present explicit distance-optimal Turán graph based constructions of 2-seq LR codes for certain parameters. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case. [ABSTRACT FROM AUTHOR]

In this paper, a class of two-weight and three-weight linear codes over \mathrm GF(p) is constructed, and their application in secret sharing is investigated. Some of the linear codes obtained are optimal in the sense that they meet certain bounds on linear codes. These codes have applications also in authentication codes, association schemes, and strongly regular graphs, in addition to their applications in consumer electronics, communication and data storage systems. [ABSTRACT FROM PUBLISHER]

Universal security over a network with linear network coding has been intensively studied. However, previous linear codes and code pairs used for this purpose were linear over a larger field than that used on the network, which restricts the possible packet lengths of optimal universal secure codes, does not allow to apply known list-decodable rank-metric codes and requires performing operations over a large field. In this paper, we introduce new parameters (relative generalized matrix weights and relative dimension/rank support profile) for code pairs that are linear over the field used in the network, and show that they measure the universal security performance of these code pairs. For one code and non-square matrices, generalized matrix weights coincide with the existing Delsarte generalized weights, hence we prove the connection between these latter weights and secure network coding, which was left open. As main applications, the proposed new parameters enable us to: 1) obtain optimal universal secure linear codes on noiseless networks for all possible packet lengths, in particular for packet lengths not considered before, 2) obtain the first universal secure list-decodable rank-metric code pairs with polynomial-sized lists, based on a recent construction by Guruswami et al; and 3) obtain new characterizations of security equivalences of linear codes. Finally, we show that our parameters extend relative generalized Hamming weights and relative dimension/length profile, respectively, and relative generalized rank weights and relative dimension/intersection profile, respectively. [ABSTRACT FROM AUTHOR]

In this paper, we consider the maximum absolute value \Delta f in the autocorrelation spectrum (not considering the zero point) of a function f . In an even number of variables n , bent functions possess the highest nonlinearity with \Delta f = 0 . The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with \Delta f < 2^{n/2} . So far, there are only a few examples of such functions for n = 10, 14 , but no general construction technique is known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on n variables having absolute indicator strictly lesser than \delta n = 2^{n/2}-2^{(({n+6})/{4})} , nonlinearity strictly greater than \rho n = 2^{n-1} - 2^{n/2} + 2^{n/2-3} - 5\cdot 2^{(({n-2})/{4})} and algebraic degree n-1 , where n\equiv 2 \pmod 4 and n\geq 46 . While the bound n \geq 46 is required for proving the generic result, our construction starts from n = 18 and nonlinearity > 2^n-1 - 2^n/2 for n = 18, 22 , and 26. [ABSTRACT FROM PUBLISHER]

In this paper, we introduce the notion of generalized pair weights of an $[n, k]$ -linear code over the finite field $\mathbb {F}_{q}$ and the notion of pair $r$ -equiweight codes, where $1\le r\le k-1$. Some basic properties of generalized pair weights of linear codes over finite fields are derived. We obtain a necessary and sufficient condition for an $[n,k]$ -linear code to be a pair equiweight code, and we characterize pair $r$ -equiweight codes for any $1\le r\le k-1$. A necessary and sufficient condition for a linear isomorphism to preserve pair weights between two linear codes is obtained. At the end of this paper, an application of generalized pair weights of linear codes to symbol-pair read wire-tap channels of type II is introduced. [ABSTRACT FROM AUTHOR]

The notion of correlation immune functions has been introduced by Siegenthaler (1984) in symmetric cryptography in the framework of stream ciphers. At the conference CRYPTO’91 by Camion et al., it has been pointed out that this notion existed in statistics and combinatorics. It has recently been highlighted that such functions also play an important role in a new framework related to side-channel attack counter-measures. Since then, the interest in correlation immune Boolean functions has been renewed, and new challenges regarding these functions have appeared. Specifically, low Hamming weight correlation immune functions have been selected as useful for counter-measures to side-channel attacks. Despite their importance, the literature is not abundant in this research direction. Two very interesting articles in which such correlation immune functions were nicely explored, given this novel use of them. Carlet initiated the first one in 2013, and the second one is due to Carlet and Chen (2018). This paper deals with correlation immune Boolean functions aiming to produce more candidates of those processing low Hamming weights. We shall focus on correlation immune Boolean functions with Hamming weights power of 2 (which offer a flexibility to control the correlation immunity aspects) and present several methods of designing them. Some design methods are efficient and could be employed to derive such functions. Consequently, given two positive integers $n$ and $m$ , we derive new effective constructions of correlation immune Boolean functions with Hamming weight power of 2. Furthermore, an upper bound on the correlation immunity of the newly constructed $n$ -variable Boolean functions with Hamming weight $2^{m}$ was determined for $n-m\ge 0$. Besides, exact values and lower bounds on the maximum correlation immunity of those functions are explored and discussed, mainly when the values of $n$ and $m$ are very close. This paper also exhibits explicit examples of those correlation immune functions that illustrate our methods. [ABSTRACT FROM AUTHOR]

Consider a binary Reed–Muller code RM (r,m) defined on the m -dimensional hypercube \mathbb F2^{m} . In this paper, we study punctured Reed–Muller codes Pr(m,b) , whose positions are restricted to the m -tuples of a given Hamming weight b . In combinatorial terms, this paper concerns m -variate Boolean polynomials of any degree r , which are evaluated on a Hamming sphere of some radius b . Codes Pr(m,b) inherit some recursive properties of RM codes. In particular, they can be built from the shorter codes, by decomposing a spherical b -layer into sub-layers of smaller dimensions. However, these sub-layers have different sizes and do not form the classical Plotkin construction. We analyze recursive properties of the spherically punctured codes Pr(m,b) and find their distances for the arbitrary values of parameters $r,m$ , and $b$ . Finally, we describe recursive (successive cancellation) decoding of these codes. [ABSTRACT FROM AUTHOR]

Symbol-pair codes were introduced by Cassuto and Blaum in 2010 to protect pair errors in symbol-pair read channels. Recently Yaakobi, Bruck and Siegel (2016) generalized this notion to b-symbol codes in order to consider consecutive b errors for a prescribed integer b ≥ 2, and they gave constructions and decoding algorithms. Cyclic codes were considered by various authors as candidates for symbol-pair codes and they established minimum distance bounds on (certain) cyclic codes. In this paper we use algebraic curves over finite fields in order to obtain tight lower and upper bounds on b-symbol Hamming weights of arbitrary cyclic codes over Fq. Here b ≥ 2 is an arbitrary prescribed positive integer and Fq is an arbitrary finite field. We also present a stability theorem for an arbitrary cyclic code C of dimension k and length n: the b-symbol Hamming weight enumerator of C is the same as the k-symbol Hamming weight enumerator of C if k ≤ b ≤ n−1. Moreover, we give improved tight lower and upper bounds on b-symbol Hamming weights of some cyclic codes related to irreducible cyclic codes. Throughout the paper the length n is coprime to q. [ABSTRACT FROM AUTHOR]

Let $p$ be a prime, $s$ be a positive integer, and $\mathcal {R}$ be a finite commutative chain ring with the characteristic as a power of $p$. For a unit $\lambda \in \mathcal {R},~\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ are ideals of the quotient ring $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $. In this paper, we derive necessary and sufficient conditions under which the quotient ring $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a chain ring. When $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a chain ring, all $\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ are known. In this paper, we establish the algebraic structures of all $\lambda $ -constacyclic codes of length $p^{s}$ over $\mathcal {R}$ when $\mathcal {R}[x]/\langle x^{p^{s}}-\lambda \rangle $ is a non-chain ring. We also determine the number of codewords in each of these codes. Using their algebraic structures, we obtain symbol-pair distances, Rosenbloom–Tsfasman (RT) distances, and RT weight distributions of all constacyclic codes of length $p^{s}$ over $\mathcal {R}$. Apart from this, we derive necessary and sufficient conditions under which a constacyclic code of length $p^{s}$ over $\mathcal {R}$ is maximum-distance separable with respect to the: 1) Hamming metric; 2) symbol-pair metric; and 3) RT metric. We also provide an algorithm to decode the constacyclic codes of length $p^{s}$ over $\mathcal {R}$ using the known decoding algorithms of linear codes over finite fields with respect to the Hamming, symbol-pair, and RT metrics. [ABSTRACT FROM AUTHOR]

In addition to their applications in data communication and storage, linear codes also have nice applications in combinatorics and cryptography. Minimal linear codes, a special type of linear codes, are preferred in secret sharing. In this paper, a necessary and sufficient condition for a binary linear code to be minimal is derived. This condition enables us to obtain three infinite families of minimal binary linear codes with $w_{\min }/w_{\max } \leq 1/2$ from a generic construction, where $w_{\min }$ and $w_{\max }$ , respectively, denote the minimum and maximum nonzero weights in a code. The weight distributions of all these minimal binary linear codes are also determined. [ABSTRACT FROM AUTHOR]

Minimal linear codes have interesting applications in secret sharing schemes and secure two-party computation. This paper uses characteristic functions of some subsets of $\mathbb {F}_{q}$ to construct minimal linear codes. By properties of characteristic functions, we can obtain more minimal binary linear codes from known minimal binary linear codes, which generalizes results of Ding et al. [IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536–6545, 2018]. By characteristic functions corresponding to some subspaces of $\mathbb {F}_{q}$ , we obtain many minimal linear codes, which generalizes results of [IEEE Trans. Inf. Theory, vol. 64, no. 10, pp. 6536–6545, 2018] and [IEEE Trans. Inf. Theory, vol. 65, no. 11, pp. 7067–7078, 2019]. Finally, we use characteristic functions to present a characterization of minimal linear codes from the defining set method and present a class of minimal linear codes. [ABSTRACT FROM AUTHOR]

In this paper we prove several coordinate-ordering-free upper bounds on the insdel distances of linear codes. Our bounds are stronger than some previous known bounds. We apply these upper bounds to AGFC codes from some cyclic codes and one algebraic-geometric code with any rearrangement of coordinate positions. A strong upper bound on the insdel distances of Reed-Muller codes with the special coordinate ordering is also given. [ABSTRACT FROM AUTHOR]

Combinatorial designs are closely related to linear codes. Recently, some near MDS codes were employed to construct $t$ -designs by Ding and Tang, which settles the question as to whether there exists an infinite family of near MDS codes holding an infinite family of $t$ -designs for $t \geq 2$. This paper is devoted to the construction of infinite families of 3-designs and 2-designs from special equations over finite fields. First, we present an infinite family of almost MDS codes over ${\mathrm{ GF}}(p^{m})$ holding an infinite family of 3-designs. We then provide an infinite family of almost MDS codes over ${\mathrm{ GF}}(p^{m})$ holding an infinite family of 2-designs for any field ${\mathrm{ GF}}(q)$. In particular, some of these almost MDS codes are near MDS. Second, we present an infinite family of near MDS codes over ${\mathrm{ GF}}(2^{m})$ holding an infinite family of 3-designs by considering the number of roots of a special linearized polynomial. Compared to previous constructions of 3-designs or 2-designs from linear codes, the parameters of some of our designs are new and flexible. [ABSTRACT FROM AUTHOR]

In this paper, we study the minimum/stopping distance of array low-density parity-check (LDPC) codes. An array LDPC code is a quasi-cyclic LDPC code specified by two integers \(q\) and \(m\) , where \(q\) is an odd prime and \(m \leq q\) . In the literature, the minimum/stopping distance of these codes (denoted by \(d(q,m)\) and \(h(q,m)\) , respectively) has been thoroughly studied for \(m \leq 5\) . Both exact results, for small values of \(q\) and \(m\) , and general (i.e., independent of \(q\) ) bounds have been established. For \(m=6\) , the best known minimum distance upper bound, derived by Mittelholzer, is \(d(q,6) \leq 32\) . In this paper, we derive an improved upper bound of \(d(q,6) \leq 20\) and a new upper bound \(d(q,7) \leq 24\) by using the concept of a template support matrix of a codeword/stopping set. The bounds are tight with high probability in the sense that we have not been able to find codewords of strictly lower weight for several values of \(q\) using a minimum distance probabilistic algorithm. Finally, we provide new specific minimum/stopping distance results for \(m \leq 7\) and low-to-moderate values of \(q \leq 79\) . [ABSTRACT FROM AUTHOR]

In this paper we prove new lower bounds for the maximal size of permutation codes by connecting the theory of permutation codes with the theory of linear block codes. More specifically, using the columns of a parity check matrix of an $[{\it{ n,k,d}}]_{ {q}}$ linear block code, we are able to prove the existence of a permutation code in the symmetric group of degree n, having minimum distance at least d and large cardinality. With our technique, we obtain new lower bounds for permutation codes that enhance the ones in the literature and provide asymptotic improvements in certain regimes of length and distance of the permutation code. [ABSTRACT FROM AUTHOR]

Boolean functions, coding theory and $t$ -designs have close connections and interesting interplay. A standard approach to constructing $t$ -designs is the use of linear codes with certain regularity. The Assmus-Mattson Theorem and the automorphism groups are two ways for proving that a code has sufficient regularity for supporting $t$ -designs. However, some linear codes hold $t$ -designs, although they do not satisfy the conditions in the Assmus-Mattson Theorem and do not admit a $t$ -transitive or $t$ -homogeneous group as a subgroup of their automorphisms. The major objective of this paper is to develop a theory for explaining such codes and obtaining such new codes and hence new $t$ -designs. To this end, a general theory for punctured and shortened codes of linear codes supporting $t$ -designs is established, a generalized Assmus-Mattson theorem is developed, and a link between 2-designs and differentially $\delta $ -uniform functions and 2-designs is built. With these general results, binary codes with new parameters and explicit weight distributions are obtained, new 2-designs and Steiner system $S(2, 4, 2^{n})$ are produced in this paper. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRC) have been studied from two approaches to locally repair multiple failed nodes: 1) parallel approach, in which a coordinate $i$ of an $[n,k,d]$ linear code is said to have locality $r$ and availability $t$ if there exist $t$ disjoint repair sets each of which contains at most $r$ other coordinates that can recover the value of the $i$ -th coordinate; 2) sequential approach, in which the erased symbols (failed nodes) are repaired, one by one, and any previously repaired node can be used to repair the remaining failed nodes. In this paper, we first consider LRC aiming at joint sequential-parallel repairing multiple failed nodes, and study the $(n,k,r,t,u)$ -ELRCs (Exact locally repairable codes) which are $[n,k]$ linear codes with the property that any set of failed nodes of size at most $t$ can be simultaneously repaired in parallel mode, and each element of a set $E$ of failed nodes of size at most $u$ can be sequentially repaired by $r$ ($r< k$) other coordinates. We present a method by which with a given parity-check matrix of an $(n,k,r,t,u)$ -ELRC with minimum Hamming distance $d$ , a new ELRC with minimum Hamming distance $2d$ and availability $t+1$ is constructed that can repair each set of failed nodes $E$ of size at most $2u+1$ in sequential mode and this repair is done in at most $u-t+2$ steps. We construct a big family of LRCs by making use of orthogonal Latin rectangles and permutation cubes and some other combinatorial designs; the constructed codes contain the family of direct product codes; we also use $m$ -dimensional permutation cubes to construct LRCs with short block length for each $r$. [ABSTRACT FROM AUTHOR]

Bent functions, or equivalently, Hadamard difference sets in the elementary Abelian group (${\mathrm {GF}}(2^{2m}), $ +), have been employed to construct symmetric and quasi-symmetric designs having the symmetric difference property. The main objective of this paper is to use bent vectorial functions for a construction of a two-parameter family of binary linear codes that do not satisfy the conditions of the Assmus–Mattson theorem, but nevertheless hold 2-designs. A new coding-theoretic characterization of bent vectorial functions is presented. [ABSTRACT FROM AUTHOR]

This paper studies properties of binary runlength-limited sequences with additional constraints on their Hamming weight and/or their number of runs of identical symbols. An algebraic and a probabilistic (entropic) characterization of the exponential growth rate of the number of such sequences, i.e., their information capacity, are obtained by using the methods of multivariate analytic combinatorics, and properties of the capacity as a function of its parameters are stated. The second-order term in the asymptotic expansion of the rate of these sequences is also given, and the typical values of the relevant quantities are derived. Several applications of the results are illustrated, including bounds on codes for weight-preserving and run-preserving channels (e.g., the run-preserving insertion-deletion channel), a sphere-packing bound for channels with sparse error patterns, and the asymptotics of constant-weight sub-block constrained sequences. In addition, the asymptotics of a closely related notion— $q$ -ary sequences with fixed Manhattan weight—is briefly discussed, and an application in coding for molecular timing channels is illustrated. [ABSTRACT FROM AUTHOR]

In this paper, we revisit the combinatorial error model of Mazumdar et al. that models errors in high-density magnetic recording caused by lack of knowledge of grain boundaries in the recording medium. We present new upper bounds on the cardinality/rate of binary block codes that correct errors within this model. All our bounds, except for one, are obtained using combinatorial arguments based on hypergraph fractional coverings. The exception is a bound derived via an information-theoretic argument. Our bounds significantly improve upon existing bounds from the prior literature. [ABSTRACT FROM PUBLISHER]

A linear complementary dual (LCD) code is a linear code with complimentary dual. LCD codes have been extensively studied in literature. On the other hand, maximum distance separable (MDS) codes are an important class of linear codes that have found wide applications in both theory and practice. However, little is known about MDS codes with complimentary duals. The main purpose of this paper is to construct several classes of MDS codes with complimentary duals, i.e., LCD MDS codes, through generalized Reed-Solomon codes. [ABSTRACT FROM PUBLISHER]

Reed-Muller codes are error-correcting codes used in many areas related to coding theory, such as electrical engineering and computer science. The binary $r^{th}$ -order Reed-Muller code $RM(r,n)$ can be viewed as the set of all $n$ -variable Boolean functions of algebraic degree at most $r$. Despite the intense work on these codes, many problems are known to be hard (notably, determining their covering radius) and remain open to this day. Fourteen years ago, Carlet and Mesnager improved in [IEEE Transactions on Information Theory, “Improving the Upper Bounds on the Covering Radii of Binary Reed-Muller Codes”, 53(1), 2007] the upper bound on the covering radius of the Reed-Muller code of order 2, and they deduced improved upper bounds on the covering radii of the Reed-Muller codes of higher orders. Until 2021, these upper bounds remained the best ones in the literature. The Reed-Muller code $RM(n-3,n)$ , which corresponds to the dual of the Reed-Muller code $RM(2,n)$ , has attracted much attention. One of the main reasons is that it is precisely the code that has been considered to get the upper bounds derived by Carlet and Mesnager. Those upper bounds have been obtained thanks to the characterization of the codewords of the Reed-Muller code, whose Hamming weights are strictly less than 2.5 times the minimum distance $2^{n-r}$ due to Kasami, Tokura, and Azumi. Despite their impressive work in the seventieth, a more refined study and profound description of those codewords of ${RM}({n-3},{n})$ whose Hamming weight equals 16, and especially 18, seem necessary, as it could help us significantly in improving the covering radius of Reed-Muller codes. In this paper, we push further the known results on the Reed-Muller codes by focusing on the Reed-Muller code ${RM}({n-3},{n})$. We provide a classification of the codewords of weights 16 and 18 of the Reed-Muller code $RM(n-3,n)$. Our algebraic descriptions allow us to count the number of such codewords and to enumerate all of them explicitly. [ABSTRACT FROM AUTHOR]

Designing Boolean functions whose output can be computed with light means at high speed, and satisfying all the criteria necessary to resist all major attacks on the stream ciphers using them as nonlinear components, has been an open problem since the beginning of this century, when algebraic attacks were invented. Functions allowing a good resistance are known since 2008, but their output is a little too complex to compute. Functions with fast and easy to compute output are known which have good algebraic immunity, such as majority functions and the so-called hidden weight bit (HWB) functions, but they all have the same cryptographic weakness: their too small nonlinearity. In the present paper, we introduce a generalization of the HWB functions into a construction of $n$ -variable balanced functions $f$ from $(n-1)$ -variable Boolean functions $g$ having some property held by a large number of functions. Function $f$ is defined by its support, equal to the image set of a vectorial function depending on $g$. This makes the function complex enough for allowing good cryptographic parameters, while its output is light to compute. The HWB function is what we obtain with $f$ when the initial function $g$ equals constant 1. Other well chosen functions $g$ provide functions $f$ having good cryptographic parameters. We analyze the constructed functions $f$ , we provide a fast way to compute their output, we determine their algebraic normal forms and we show that, most often, their algebraic degree is optimal. We study their Walsh transform and their nonlinearity and algebraic immunity. We observe with computer investigations that this generalization of the HWB function allows to keep its quality of being fast to compute and having good enough algebraic immunity, while significantly improving its nonlinearity. The functions already obtained in the investigations provide a quite good (and never reached before) trade-off between speed and security. Further (probably difficult) work should allow obtaining, among such generalized HWB functions whose number is huge, still better filter functions to be used in stream ciphers. [ABSTRACT FROM AUTHOR]

Ovoids in ${\mathrm {PG}}(3, {\mathrm {GF}}(q))$ have been an interesting topic in coding theory, combinatorics, and finite geometry for a long time. So far only two families of ovoids are known. The first is the elliptic quadrics and the second is the Tits ovoids. It is known that an ovoid in ${\mathrm {PG}}(3, {\mathrm {GF}}(q))$ corresponds to a $[q^{2}+1, 4, q^{2}-q]$ code over ${\mathrm {GF}}(q)$ , which is called an ovoid code. The objectives of this paper are to develop the general theories of subfield codes and to study the subfield codes of the two families of ovoid codes. The dimensions, minimum weights, and the weight distributions of the subfield codes of the elliptic quadric codes and Tits ovoid codes are settled. The parameters of the duals of these subfield codes are also studied. Some of the codes presented in this paper are optimal, and some are distance-optimal. The parameters of the subfield codes are new. [ABSTRACT FROM AUTHOR]

In this paper, we generalize constructions in two recent works of Ding, Heng, and Zhou to any field $\mathbb {F}_{{q}}$ , ${q}$ odd, providing infinite families of minimal codes for which the Ashikhmin–Barg bound does not hold. [ABSTRACT FROM AUTHOR]

Rank weights and generalized rank weights have been proved to characterize error and erasure correction, and information leakage in linear network coding, in the same way as Hamming weights and generalized Hamming weights describe classical error and erasure correction, and information leakage in wire-tap channels of type II and code-based secret sharing. Although many similarities between both the cases have been established and proved in the literature, many other known results in the Hamming case, such as bounds or characterizations of weight-preserving maps, have not been translated to the rank case yet, or in some cases have been proved after developing a different machinery. The aim of this paper is to further relate both weights and generalized weights, show that the results and proofs in both cases are usually essentially the same, and see the significance of these similarities in network coding. Some of the new results in the rank case also have new consequences in the Hamming case. [ABSTRACT FROM PUBLISHER]

This paper considers the problem of linear Boolean classification, where the goal is to determine in which set, among two given sets of Boolean vectors, an unknown vector belongs to by making linear queries. Finding the least number of queries is equivalent to determining the minimal rank of a matrix over $GF(2)$ , whose kernel does not intersect a given set $S$ . In the case where $S$ is a Hamming ball, this reduces to finding linear codes of largest dimension. For a general set $S$ , this is an instance of the critical problem posed by Crapo and Rota in 1970, open in general. This paper focuses on the case where $S$ is an annulus. As opposed to balls, it is shown that an optimal kernel is composed not only of dense but also of sparse vectors, and the optimal mixture is identified in various cases. These findings corroborate a proposed conjecture that for an annulus of inner and outer radius $nq$ and $np$ respectively, the optimal relative rank is given by the normalized entropy $(1-q)H(p/(1-q))$ , an extension of the Gilbert–Varshamov bound. [ABSTRACT FROM AUTHOR]

In this paper, we extend two earlier works further in two directions and compute the weight distribution of these cyclic codes under more relaxed conditions. It is interesting to note that many cyclic codes in the family are optimal and have only a few non-zero weights. Besides using similar ideas, we carry out some subtle manipulation of certain exponential sums. [ABSTRACT FROM AUTHOR]

This paper revisits the ordered statistics decoding (OSD). It provides a comprehensive analysis of the OSD algorithm by characterizing the statistical properties, evolution and the distribution of the Hamming distance and weighted Hamming distance from codeword estimates to the received sequence in the reprocessing stages of the OSD algorithm. We prove that the Hamming distance and weighted Hamming distance distributions can be characterized as mixture models capturing the decoding error probability and code weight enumerator. Simulation and numerical results show that our proposed statistical approaches can accurately describe the distance distributions. Based on these distributions and with the aim to reduce the decoding complexity, several techniques, including stopping rules and discarding rules, are proposed, and their decoding error performance and complexity are accordingly analyzed. Simulation results for decoding various eBCH codes demonstrate that the proposed techniques can significantly reduce the decoding complexity with a negligible loss in the decoding error performance. [ABSTRACT FROM AUTHOR]

Let P be a partial order on [n] = 1,2, . . . , n, Fqn be the linear space of n-tuples over a finite field Fq and w be a weight on Fq. In this paper, we consider metrics on Fqn induced by chain orders P over [n] and weights w over Fq, and we determine the cardinality of all optimal anticodes and completely classify them. Moreover, we determine all diameter perfect codes for a set of relevant instances on the aforementioned metric spaces. [ABSTRACT FROM AUTHOR]

In this paper, we first study in detail the relationship between minimal linear codes and cutting blocking sets, recently introduced by Bonini and Borello, and then completely characterize minimal linear codes as cutting blocking sets. As a direct result, minimal projective codes of dimension 3 and t-fold blocking sets with t ≥ 2 in projective planes are identical objects. Some bounds on the parameters of minimal codes are derived from this characterization. Using this new link between minimal codes and blocking sets, we also present new general primary and secondary constructions of minimal linear codes. As a result, infinite families of minimal linear codes not satisfying the Aschikhmin-Barg’s condition are obtained. In addition to this, open problems on the parameters and the weight distributions of some generated linear codes are presented. [ABSTRACT FROM AUTHOR]

In this paper, we study a class of linear codes defined by characteristic functions of certain subsets of a finite field. We derive a sufficient and necessary condition for such a code to be a minimal linear code by a character-theoretical approach. We obtain new three-weight or four-weight minimal linear codes that do not satisfy the Ashikhmin-Barg condition by using partial difference sets. We show that our construction yields minimal linear codes that do not arise from cutting vectorial blocking sets, and also discuss their applications in secret sharing schemes. [ABSTRACT FROM AUTHOR]

The optical orthogonal codes (OOCs) have been widely used as spreading codes in communication systems employing the unipolar transmission. They are classified into constant-weight OOCs (CW-OOCs) and variable-weight OOCs (VW-OOCs) according to the number of distinct Hamming weights which their codewords have. In this paper, we present a new generic construction of VW-OOCs of length $(q-1)N$ from a CW-OOC of length $N$ , where $q$ is a prime power and $\gcd (q-1,N)=1$ . As a result, three new families of optimal VW-OOCs with a maximum correlation value 1 are obtained. In particular, these families can have the codewords of high weights, while most of the previously known optimal VW-OOCs have only codewords of weight less than 8. [ABSTRACT FROM PUBLISHER]

The Walsh transform \(\widehat {f}\) of a quadratic function \(f: {\mathbb F}_{p^{n}}\rightarrow {\mathbb F} _{p}\) satisfies \(|\widehat {f}| \in \{0,p^{{n+s}/{2}}\}\) for an integer \(0\le s\le n-1\) , depending on \(f\) . In this paper, quadratic functions of the form \({\mathcal {F}}_{p,n}(x) = {\rm Tr_{n}}(\sum _{i=0}^{k}a_{i}x^{p^{i}+1})\) are studied, with the restriction that \(a_{i} \in {\mathbb F} _{p},~ 0\leq i\leq k\) . Three methods for enumeration of such functions are presented when the value for \(s\) is prescribed. This paper extends earlier enumeration results significantly, for instance, the generating function for the counting function is obtained, when \(n\) is odd and relatively prime to \(p\) , or when \(n=2m\) , for odd \(m\) and \(p=2.\) The number of bent and semibent functions for various classes of \(n\) is also obtained [ABSTRACT FROM AUTHOR]

The class of \(q\) -ary list permutation invariant linear codes is introduced in this paper along with probabilistic arguments that validate their existence when certain conditions are met. The specific class of codes is characterized by an upper bound that is tighter than the generalized Shulman–Feder bound and relies on the distance of the codes’ weight distribution to the binomial (multinomial, respectively) one. The bound applies to cases where a code from the proposed class is transmitted over a \(q\) -ary output symmetric discrete memoryless channel and list decoding with fixed list size is performed at the output. In the binary case, the new upper bounding technique allows the discovery of list permutation invariant codes whose upper bound coincides with sphere-packing exponent. Furthermore, the proposed technique motivates the introduction of a new class of upper bounds for general \(q\) -ary linear codes whose members are at least as tight as the DS2 bound as well as all its variations for the discrete channels treated in this paper. [ABSTRACT FROM AUTHOR]

In 1998, Lin presented a conjecture on a class of ternary sequences with ideal two-level autocorrelation. Those sequences have a very simple structure, i.e., their trace representation has two trace monomial terms. In this paper, we present a proof for the conjecture. The mathematical tools employed are the second-order multiplexing decimation-Hadamard transform, Stickelberger’s theorem, the Teichmüller character, and combinatorial techniques for enumerating the Hamming weights of ternary numbers. As a by-product, we also prove that the ternary sequences conjectured by Lin are Hadamard equivalent to ternary \(m\) -sequences. [ABSTRACT FROM PUBLISHER]

$\epsilon $ -Minimum Storage Regenerating ($\epsilon $ -MSR) codes form a special class of Maximum Distance Separable (MDS) codes, providing mechanisms for exact regeneration of a single code block in their codewords by downloading slightly sub-optimal amount of information from the remaining code blocks. The key advantage of these codes is a significantly lower sub-packetization that grows only logarithmically with the code length, while providing optimality in storage and error-correcting capacity. However, existing constructions of $\epsilon $ -MSR codes require each remaining code block to be available for the repair of any failed code block. In this paper, we construct $\epsilon $ -MSR codes that can repair any failed code block by contacting fewer number of available code blocks. When a code block fails, our repair procedure needs to contact a few compulsory code blocks and is free to choose any subset of available code blocks for the remaining choices. Our construction requires a field size linear in code length and ensures load balancing (in terms of information downloaded) among the contacted code blocks for repairing a failed code block. [ABSTRACT FROM AUTHOR]

The notion of Generalized Hamming weights of block codes has been investigated since the nineties due to its significant role in coding theory and cryptography. In this paper we extend this concept to the context of convolutional codes. In particular, we focus on column distances and introduce the novel notion of generalized column distances (GCD). We first show that the hierarchy of GCD is strictly increasing. We then provide characterizations of such distances in terms of the truncated parity-check matrix of the code, that will allow us to determine their values. Finally, the case in which the parity-check matrix is in systematic form is treated. [ABSTRACT FROM AUTHOR]