Search

A k-plex of order n is an ${n} \times {n}$ matrix on n symbols, where every row contains k distinct symbols, every column contains k distinct symbols, and every symbol occurs exactly k times. Yi et al. (2019) introduced 3-plex codes which are 2-erasure codes (2-erasure tolerant array codes) derived from 3-plexes. In this paper, we generalize 3-plex codes to k-plex codes. We introduce the notion of a “strong” k-plex which implies the derived k-plex code is 2-erasure tolerant. Moreover, k-plex codes derived from strong $k$ -plexes have a straightforward algorithm for reconstruction. These general k-plex codes offer greater flexibility when choosing a suitable code for a storage system, enabling the operator to better optimize the unavoidable trade-offs involved. Blackburn asked for the maximum number of entries in an ${n} \times {n}$ partial Latin square on n symbols in which if distinct cells $({i},{j})$ and $({i}',{j}')$ contain the same symbol, then the cells $({i}',{j})$ and $({i},{j}')$ are empty. A “strong” k-plex satisfies the Blackburn property (along with two other properties related to erasure coding). We investigate the necessary conditions for the existence of Blackburn k-plexes (and hence necessary conditions for the existence of strong k-plexes). We show that any Blackburn k-plex has order ${n} \geq \lceil (\sqrt {2}+1){k}-2 \rceil $. We describe how to construct strong k-plexes of order n when $k \in \{2,3,4,5\}$ for all possible orders n, and we give a simple construction of strong k-plexes of order ${k}^{2}$ for $k \geq 2$. [ABSTRACT FROM AUTHOR]

Almost perfect nonlinear (APN) functions over fields of characteristic 2 play an important role in cryptography, coding theory and, more generally, mathematics and information theory. In this paper we deduce a new method for constructing APN functions by studying the isotopic equivalence, concept defined for quadratic planar functions in fields of odd characteristic. In particular, we construct a family of quadratic APN functions which provides a new example of an APN mapping over ${\mathbb F}_{2^{9}}$ and includes an example of another APN function $x^{9}+ \mathop {\mathrm {Tr}}\nolimits (x^{3})$ over ${\mathbb F}_{2^{8}}$ , known since 2006 and not classified up to now. We conjecture that the conditions for this family are satisfied by infinitely many APN functions. [ABSTRACT FROM AUTHOR]

In Eurocrypt’18, Cid et al. proposed a new cryptanalysis tool called Boomerang Connectivity Table (BCT), to evaluate S-boxes of block ciphers. Later, Boura and Canteaut further investigated the new parameter Boomerang uniformity for cryptographic S-boxes. It is of great interest to find new S-boxes with low Boomerang uniformity for even dimensions. In this paper, we prove that a class of permutation quadrinomials over $\mathbb {F}_{2^{2m}}$ with $m$ odd has Boomerang uniformity four, which gives the fifth class of such kind of permutation polynomials. Further, the occurrences of 0 and 4 in the BCTs of the investigated permutation polynomials are also completely determined. [ABSTRACT FROM AUTHOR]

In this paper, we construct several classes of maximum distance separable (MDS) codes via generalized Reed-Solomon (GRS) codes and extended GRS codes, where we can determine the dimensions of their Euclidean hulls or Hermitian hulls. It turns out that the dimensions of Euclidean hulls or Hermitian hulls of the codes in our constructions can take all or almost all possible values. As a consequence, we can apply our results to entanglement-assisted quantum error-correcting codes (EAQECCs) and obtain several new families of MDS EAQECCs with flexible parameters. The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values. Moreover, several new classes of q-ary MDS EAQECCs of length $ {n} > {q}+1$ are also obtained. [ABSTRACT FROM AUTHOR]

Permutation and multipermutation codes in the Ulam metric have been suggested for use in non-volatile memory storage systems such as flash memory devices. In this paper we introduce a new method to calculate permutation ball sizes in the Ulam metric using Young Tableaux and prove the non-existence of non-trivial perfect permutation codes in the Ulam metric. We then extend the study to multipermutations, providing upper and lower bounds on multipermutation Ulam ball sizes and resulting upper and lower bounds on the maximal size of multipermutation codes in the Ulam metric. [ABSTRACT FROM AUTHOR]

An involution over finite fields is a permutation polynomial whose inverse is itself. Owing to this property, involutions over finite fields have been widely used in applications, such as cryptography and coding theory. Following the idea by Wang to characterize the involutory behavior of the generalized cyclotomic mappings, this paper gives a more concise criterion for $x^{r}h(x^{s})\in {\mathbb F} _{q}[x]$ being involutions over the finite field ${\mathbb F}_{q}$ , where $r\geq 1$ and $s\,|\, (q-1)$. By using this criterion, we propose a general method to construct involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ from given involutions over some subgroups of ${\mathbb F}_{q}^{*}$ by solving congruent and linear equations over finite fields. Then, many classes of explicit involutions of the form $x^{r}h(x^{s})$ over ${\mathbb F}_{q}$ are obtained. [ABSTRACT FROM AUTHOR]

This paper introduces a new combinatorial construction for q-ary constant-weight codes which yields several families of optimal codes and asymptotically optimal codes. The construction reveals intimate connection between q-ary constant-weight codes and sets of pairwise disjoint combinatorial designs of various types. [ABSTRACT FROM AUTHOR]

In this paper, an explicit construction of binary self-dual cyclic codes of length n going to infinity with a minimal distance at least half the square root of n is presented. The same idea is also used to construct more general binary cyclic codes with a large minimal distance. Finally, in the special case of self-dual cyclic codes, a simplified version of a proof by Conway and Sloane is given, showing an upper bound for the distance of binary self-dual codes. [ABSTRACT FROM AUTHOR]

The notion of tweakable block ciphers was formally introduced by Liskov--Rivest--Wagner at Crypto 2002 (the 2002 Annual International Cryptology Conference). The extension and the first construction, called CMC, of this notion to tweakable enciphering schemes which can handle variable length messages was given by Halevi--Rogaway at Crypto 2003. In this paper, we present HCH, which is a new construction of such a scheme. The construction uses two universal hash computations with a counter mode of encryption in-between. This approach was first proposed by McGrew--Viega to build a scheme called XCB and later used by Wang-Feng-Wu, to obtain a scheme called HCTR. A unique feature of HCH compared to all known tweakable enciphering schemes is that HCH uses a single key, can handle arbitrary length messages, and has a quadratic security bound. An important application of a tweakable enciphering scheme is disk encryption. HCH is well suited for this application. We also describe a variant, which can utilize precomputation and makes one less block cipher call. This compares favorably to other hash-encrypt-hash-type constructions, supports better key agility and requires less key material. [ABSTRACT FROM AUTHOR]

We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic set- ting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length. [ABSTRACT FROM AUTHOR]

The edit distance correlation attack on the well-known alternating step generator for stream cipher applications was proposed by Golić and Menicocci. The attack can be successful only if the probability of the zero edit distance, the so-called embedding probability, conditioned on a given segment of the output sequence, decreases with the segment length, and if the decrease is exponential, then the required segment length is linear in the total length of the two linear feedback shift registers involved. The exponential decrease for the maximal value of the embedding probability, regarded as a function of the output segment, was estimated experimentally by Gollć and Menicocci. In this paper, by using the connection with the interleaving and decimation operations, the embedding probability is analyzed theoretically. Exponentially small upper bounds on the maximal embedding probability are thus derived. An exact expression for the minimal embedding probability is also determined. [ABSTRACT FROM AUTHOR]

In this paper, the Golden code for a 2 × 2 multiple- input multiple-output (MIMO) system is presented. This is a full- rate 2 × 2 linear dispersion algebraic space-time code with unprecedented performance based on the Golden number 1+&radic5;/2. [ABSTRACT FROM AUTHOR]

This paper deals with the linear-programming-based decoding algorithm of Feldman and Karger for repeat-accumulate "turbo-like" codes. We present a new structural characterization that captures the event that decoding fails. Based on this structural characterization, we develop polynomial algorithms that, given an RA (2) code, compute upper and lower bounds on the word error probability Pw for the binary-symmetric and the additive white Gaussian noise (AWGN) channels. Our experiments with an implementation of these algorithms for bounding Pw demonstrate in many interesting cases an improvement in the upper bound on the word error probability by a factor of over 1000 compared to the bounds by Feldman et al.. The experiments also indicate that the improvement in upper bound increases as the codeword length increase and the channel noise decrease. The computed lower bounds on the word error probability in our experiments are roughly ten times smaller than the upper bound. [ABSTRACT FROM AUTHOR]

In 2016, Chang et al. proposed a Format Preserving Encryption (FPE) scheme over a finite field and used an MDS matrix in the diffusion layer of the scheme for optimal diffusion. Later that year, Gupta et al. defined an algebraic structure named Format Preserving Set (FPS) is the diffusion layer of an FPE scheme. In 2018, Barua et al. showed that it is not possible to construct an FPS over a finite field in the diffusion layer of an FPE scheme if the cardinality of the set is not a power of prime. They extended the search of FPS over a finite commutative ring $\mathcal {R}$ and showed that if an FPS $S \subseteq \mathcal {R}$ is closed under addition then it gets module structure over some subring of $\mathcal {R}$. Moreover, in this case, the only possible cardinalities of FPS are some power of the cardinalities of subrings when the module is free. The purpose of this article is twofold. Firstly, we show that it is possible to construct format preserving sets over a finite commutative ring which are not closed under addition. Secondly, we search for format preserving sets and MDS matrices over torsion modules. We provide examples of format preserving sets of cardinalities 26 and 52 over torsion modules and rings. These cardinalities are interesting because they correspond to the set of English alphabets, without and with capitalization. By considering a finite Abelian group as a torsion module over a PID, we show that a matrix $M$ with entries from the PID is MDS if and only if $M$ is MDS under the projection map on the same Abelian group. [ABSTRACT FROM AUTHOR]

It is shown that for any alphabet size q and any code size M, there exist proper codes for error detection on a q-ary symmetric channel for all sufficiently large lengths. The stronger condition zero-strong proper code is defined. It is shown that such codes can only exist for q dividing M, and if this is the case they are shown to exist for sufficiently large lengths. The existence proofs are constructive. [ABSTRACT FROM AUTHOR]

Permutation polynomials and their compositional inverses have wide applications in cryptography, coding theory, and combinatorial designs. Motivated by several previous results on finding compositional inverses of permutation polynomials of different forms, we propose a general method for finding these inverses of permutation polynomials constructed by the AGW criterion. As a result, we have reduced the problem of finding the compositional inverse of such a permutation polynomial over a finite field to that of finding the inverse of a bijection over a smaller set. We demonstrate our method by interpreting several recent known results, as well as by providing new explicit results on more classes of permutation polynomials in different types. In addition, we give new criteria for these permutation polynomials being involutions. Explicit constructions are also provided for all involutory criteria. [ABSTRACT FROM AUTHOR]

We study ${q}$ -ary linear codes ${C}$ obtained from Veronese surfaces over finite fields. We show how one can find the higher weight spectra of these codes, or equivalently, the weight distribution of all extension codes of ${C}$ over all field extensions of $\mathbb {F}_{q}$. Our methods will be a study of the Stanley-Reisner rings of a series of matroids associated to each code ${C}$. [ABSTRACT FROM AUTHOR]

We solve the problem of existence of perfect codes in the Doob graph. It is shown that 1-perfect codes in the Doob graph $ {D(m,n)}$ exist if and only if $6 {m}+3 {n}+1$ is a power of 2; that is, if the size of a 1-ball divides the number of vertices. [ABSTRACT FROM AUTHOR]

Quaternary ZRM (r, m) codes were defined so that their binary images, via Gray map, are Reed-Muller codes for some specific values of r. In the literature, two different definitions of such codes can be found. They will be denoted ZRM(r, m) and ZRM- (r, m) codes. In this correspondence, we show that both definitions are equivalent exactly for those values of r such that their binary images are Reed-Muller codes. Moreover, we prove that, for all r, these binary images are linear codes in the case of ZRM- (r, m), but they are not if we use the definition of ZRM- (r, m). In this last case, we compute the rank and the dimension of the kernel of these codes. [ABSTRACT FROM AUTHOR]

Two algebraic methods for systematic construction of structured regular and irregular low-density parity-check (LDPC) codes with girth of at least six and good minimum distances are presented. These two methods are based on geometry decomposition and a masking technique. Numerical results show that the codes constructed by these methods perform close to the Shannon limit and as well as random-like LDPC codes. Furthermore, they have low error floors and their iterative decoding converges very fast. The masking technique greatly simplifies the random-like construction of irregular LDPC codes designed on the basis of the degree distributions of their code graphs. [ABSTRACT FROM AUTHOR]

For a linear block code with minimum distance d, its stopping redundancy is the minimum number of check nodes in a Tanner graph representation of the code, such that all nonempty stopping sets have size d or larger. We derive new upper bounds on stopping redundancy for all linear codes in general, and for maximum distance separable (MDS) codes specifically, and show how they improve upon previous results. For MDS codes, the new bounds are found by upper-bounding the stopping redundancy by a combinatorial quantity closely related to Turán numbers. (The Turán number, T(v, k, t), is the smallest number of t-subsets of a v-set, such that every k-subset of the v-set contains at least one of the t-subsets.) Asymptotically, we show that the stopping redundancy of MDS codes with length n and minimum distance d > 1 is T(n, d - 1, d - 2)(1 + O(n-1)) for fixed d, and is at most T(n, d - 1, d - 2)(3 + O(n-1)) for fixed code dimension k = n - d + 1. For d = 3, 4, we prove that the stopping redundancy of MDS codes is equal to T(n, d - 1, d - 2), for which exact formulas are known. For d = 5, we show that the stopping redundancy of MDS codes is either T(n, 4, 3) or T(n, 4, 3) + 1. [ABSTRACT FROM AUTHOR]

In this correspondence, we compute the weight enumerators of various quadratic residue codes over F2 and F3, together with certain codes of related families like the duadic and the quadratic double circulant codes. We use a parallel algorithm to find the number of codewords of a given (not too high) weight, from which we deduce by usual classical methods for self-dual and formally self-dual codes over F2 and F3 their associated, previously unknown, weight enumerators. We compute weight enumerators for lengths as high as 152 for binary codes and 96 for ternary codes. [ABSTRACT FROM AUTHOR]

This correspondence revisits the idea of constructing a binary [m n, mk] code from an [n, k] code over F2m by concatenating the code with a suitable basis representation of F2m over F2. We construct two nonequivalent examples of doubly even self-dual binary codes of length 160 which turn out to be of minimum distance 24. This improves the lower bound for this class of codes, whereas the upper bound Is given by 28. The construction at hand seems to be of interest beyond this particular example. [ABSTRACT FROM AUTHOR]

We show that the list decoding procedure of Guruswami and Sudan may be used to decode generalized Reed-Solomon (RS) codes defined over commutative rings with identity. An algorithm for performing the first of the two phases of this decoding procedure is also given. In particular, we show that for generalized RS codes over chain rings, the probability of picking an incorrect codeword from a given list can be reduced by increasing the size of the code alphabet while keeping the length and minimum (Hamming) distance of the code constant. [ABSTRACT FROM AUTHOR]

We introduce and analyze verification-based decoding for low-density parity-check (LDPC) codes, an approach specifically designed to manipulate data in packet-sized units. Verification-based decoding requires only linear time for both encoding and decoding and succeeds with high probability under random errors. We describe how to utilize code scrambling to extend our results to channels with errors controlled by an oblivious adversary. [ABSTRACT FROM AUTHOR]