Search

Let n be a positive integer. An NFSR of n stages is called irreducible if the family of output sequences of any NFSR of stages less than n is not included in that of the NFSR. In this paper, we prove that the density of the irreducible NFSRs of n stages is larger than 0.39. This implies that it is expected to find an irreducible NFSR of n stages among three randomly chosen NFSRs of n stages. [ABSTRACT FROM PUBLISHER]

The goal of this paper is to investigate linear approximations of random functions and permutations. Our motivation is twofold. First, before the distinguishability of a practical cipher from an ideal one can be analysed, the cryptanalyst must have an accurate understanding of the statistical behaviour of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditional models have been based on the average behaviour and simplified using other assumptions such as independence of the linear approximations. Multidimensional cryptanalysis was introduced to avoid making artificial assumptions about statistical independence of linear approximations. On the other hand, it has the drawback of including many trivial approximations that do not contribute to the attack but just cause a waste of time and memory. We show for the first time in this paper that the trivial approximations reduce the degree of freedom of the related $\chi ^{2}$ distribution. Previously, the affine linear cryptanalysis was proposed to allow removing trivial approximations and, at the same time, admitting a solid statistical model. In this paper, we identify another type of multidimensional linear approximation, called Davies-Meyer approximation, which has similar advantages, and present full statistical models for both the affine and the Davies-Meyer type of multidimensional linear approximations. The new models given in this paper are realistic, accurate and easy to use. They are backed up by standard statistical tools such as Pearson’s $\chi ^{2}$ test and finite population correction and demonstrated to work accurately using practical examples. [ABSTRACT FROM AUTHOR]

This paper studies the distinctness of primitive sequences over \bf Z/(M) modulo 2, where M is an odd integer that is composite and square-free, and \bf Z/(M) is the integer residue ring modulo M. A new sufficient condition is given for ensuring that primitive sequences generated by a primitive polynomial f\left(x\right) over \bf Z/(M) are pairwise distinct modulo 2. Such result improves a recent result obtained in our previous paper, and consequently, the set of primitive sequences over \bf Z/(M) that can be proven to be distinct modulo 2 is greatly enlarged. [ABSTRACT FROM PUBLISHER]

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]

Nowadays, the resistance against algebraic attacks and fast algebraic attacks are considered as an important cryptographic property for Boolean functions used in stream ciphers. Both attacks are very powerful analysis concepts and can be applied to symmetric cryptographic algorithms used in stream ciphers. The notion of algebraic immunity has received wide attention since it is a powerful tool to measure the resistance of a Boolean function to standard algebraic attacks. Nevertheless, an algebraic tool to handle the resistance to fast algebraic attacks is not clearly identified in the literature. In the current paper, we propose a new parameter to measure a Boolean function’s resistance to fast algebraic attack. We also introduce the notion of fast immunity profile and show that it informs both on the resistance to standard and fast algebraic attacks. Further, we evaluate our parameter for two secondary constructions of Boolean functions. Moreover, A coding-theory approach to the characterization of perfect algebraic immune functions is presented. Via this characterization, infinite families of binary linear complementary dual codes (or LCD codes for short) are obtained from perfect algebraic immune functions. Some of the binary LCD codes presented in this paper are optimal. These binary LCD codes have applications in armoring implementations against so-called side-channel attacks (SCA) and fault non-invasive attacks, in addition to their applications in communication and data storage systems. [ABSTRACT FROM AUTHOR]

The inverse function x → x−1 on F2n, is one of the most studied functions in cryptography due to its widespread use as an S-box in block ciphers like AES. In this paper, we show that, if n ≥ 5, every function that is CCZ-equivalent to the inverse function is already EA-equivalent to it. This confirms a conjecture by Budaghyan, Calderini and Villa. We also prove that every permutation that is CCZ-equivalent to the inverse function is already affine equivalent to it. The majority of the paper is devoted to proving that there is no permutation polynomial of the form L1(x−1) + L2(x) over F2n if n ≥ 5, where L1,L2 are nonzero linear functions. In the proof, we combine Kloosterman sums, quadratic forms and tools from additive combinatorics. [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 ICISC-05, and in the ePrint 2010/287, Patarin claimed a lower bound on the number of $2 q$ tuples of $n$ -bit strings $(P_{1}, \ldots, P_{2q}) \in ({\{0,1\}}^{n})^{2q}$ satisfying $P_{2i - 1} \oplus P_{2i} = \lambda _{i}$ for $1 \leq i \leq q$ such that $P_{1}, P_{2}, \ldots $ , $P_{2q}$ are distinct and $\lambda _{i} \in {\{0,1\}} ^{n} \setminus \{0^{n}\}$. This result is known as Mirror theory and widely used in cryptography. It stands as a powerful tool to provide a high-security guarantee for many block cipher-(or even ideal permutation-) based designs. In particular, Mirror theory has a direct application in the security of XOR of block ciphers. Unfortunately, the proof of Mirror theory contains some unverifiable gaps and several mistakes. This paper provides a simple and verifiable proof of Mirror theory. [ABSTRACT FROM AUTHOR]

In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest. [ABSTRACT FROM AUTHOR]

Information-theoretic security is considered in the paradigm of network coding in the presence of wiretappers, who can access one arbitrary edge subset up to a certain size, also referred to as the security level. Secure network coding is applied to prevent the leakage of the source information to the wiretappers. In this paper, we consider the problem of secure network coding when the information rate and the security level can change over time. To efficiently solve this problem, we put forward local-encoding-preserving secure network coding, where a family of secure linear network codes (SLNCs) is called local-encoding-preserving if all the SLNCs in this family share a common local encoding kernel at each intermediate node in the network. We first consider the design of a family of local-encoding-preserving SLNCs for a fixed security level and a flexible rate. A simple approach is presented for efficiently constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same security level and the rate reduced by one. By applying this approach repeatedly, we can obtain a family of local-encoding-preserving SLNCs with a fixed security level and multiple rates. We further consider the design of a family of local-encoding-preserving SLNCs for a fixed rate and a flexible security level. We present a novel and efficient approach for constructing upon an SLNC that exists a local-encoding-preserving SLNC with the same rate and the security level increased by one. Next, we consider the design of a family of local-encoding-preserving SLNCs for a fixed dimension (equal to the sum of rate and security level) and a flexible pair of rate and security level. We propose another novel approach for designing an SLNC such that the same SLNC can be applied for all the rate and security-level pairs with the fixed dimension. Also, two polynomial-time algorithms are developed for efficient implementations of the later two proposed approaches, respectively. Furthermore, we prove that all our three approaches do not incur any penalty on the required field size for the existence of SLNCs in terms of the best known lower bound by Guang and Yeung. Finally, we consider the ultimate problem of designing a family of local-encoding-preserving SLNCs that can be applied to all possible pairs of rate and security level. By combining the constructions of the three families of local-encoding-preserving SLNCs in the paper in suitable ways, we can obtain a family of local-encoding-preserving SLNCs that can be applied for all possible pairs of rate and security level. Three possible such constructions are presented. [ABSTRACT FROM AUTHOR]

The tight lower bound on the redundancy of optimal prefix-free codes in terms of a given symbol probability (not necessarily the largest or the smallest one) has been derived in the literature. The first goal of this paper is to derive the tight lower bounds in terms of $j$ ($j>1$) known symbol probabilities of the source using some properties of Kullback-Leibler distance. Since fix-free codes are special prefix-free codes (for which no codeword is a suffix of the other codewords), it is clear that all lower bounds on the redundancy of optimal prefix-free codes are also valid for fix-free ones. Accordingly, the second question of the paper is on the tightness of the derived lower bounds for optimal fix-free codes. It is proven that these lower bounds are tight for optimal fix-free codes if $j\leq 3$ , and are not tight for $j\geq 4$. Also, it is shown that the tight lower bound in terms of the probability of the most likely symbol is the same for optimal prefix-free and optimal fix-free codes. [ABSTRACT FROM AUTHOR]

This paper considers multiplexing two sequences of messages with two different decoding delays over a packet erasure channel. In each time slot, the source constructs a packet based on the current and previous messages and transmits the packet, which may be erased when the packet travels from the source to the destination. The destination must perfectly recover every source message in the first sequence subject to a decoding delay ${T}_{\mathrm{ v}}$ and every source message in the second sequence subject to a shorter decoding delay ${T}_{\mathrm{ u}}\le {T}_{\mathrm{ v}}$. We assume that the channel loss model introduces a burst erasure of a fixed length B on the discrete timeline. Under this channel loss assumption, the capacity region for the case where ${T}_{\mathrm{ v}}\le {T}_{\mathrm{ u}}+{B}$ was previously solved. In this paper, we fully characterize the capacity region for the remaining case ${T}_{\mathrm{ v}}> {T}_{\mathrm{ u}}+{B}$. The key step in the achievability proof is achieving the non-trivial corner point of the capacity region through using a multiplexed streaming code constructed by superimposing two single-stream codes. The main idea in the converse proof is obtaining a genie-aided bound when the channel is subject to a periodic erasure pattern where each period consists of a length-B burst erasure followed by a length- ${T}_{\mathrm{ u}}$ noiseless duration. [ABSTRACT FROM AUTHOR]

The paper is devoted to the problem of erasure coding in distributed storage. We consider a model of storage that assumes that nodes are organized into equally sized groups, called racks, that within each group the nodes can communicate freely without taxing the system bandwidth, and that the only information transmission that counts is the one between the racks. This assumption implies that the nodes within each of the racks can collaborate before providing information to the failed node. The main emphasis of the paper is on code construction for this storage model. We present an explicit family of maximum distance separable (MDS) array codes that support recovery of a single failed node from any number of helper racks using the minimum possible amount of inter-rack communication(such codes are said to provide optimal repair). The codes are constructed over finite fields of size comparable to the code length. We also derive a bound on the number of symbols accessed at helper nodes for the purposes of repair, and construct a code family that approaches this bound, while still maintaining the optimal repair property. Finally, we present a construction of scalar Reed-Solomon codes that support optimal repair for the rack-oriented storage model. [ABSTRACT FROM AUTHOR]

Motivated by the recent studies on $\mathbb {Z}_{2}\mathbb {Z}_{4}$ -additive cyclic codes, $\mathbb {Z}_{2}\mathbb {Z}_{2}[u]$ -cyclic codes and $\mathbb {Z}_{2}\mathbb {Z}_{2^{s}}$ -additive codes have been introduced by Aydogdu et al.. In this paper, we study $\mathbb {Z}_{q}R$ -linear cyclic codes where $R=\mathbb {Z}_{q}+u\mathbb {Z}_{q}, q$ is a prime number and $u^{2}=0$. There are two major ingredients in this paper. The first is to investigate the algebraic structure of cyclic codes and their duals over ring $\mathbb {Z}_{q}R$ , the spanning sets, the types and sizes of $\mathbb {Z}_{q}R$ -cyclic codes and their duals as well. Based on this, the second ingredient is to present an infinite family of MDSS codes and obtain some illustrative examples of $q$ -ary cyclic codes with optimal parameters derived from the $\mathbb {Z}_{q}R$ -cyclic codes. [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]

Given a binary sequence with length $n$ , determining its minimal rational fraction representation (MRFR) has important applications in the design and cryptanalysis of stream ciphers. There are many studies of this problem since Klapper and Goresky first introduced an adaptive rational approximation algorithm with a time complexity of $O(n^{2}\log n\log \log n)$. In this paper, we revisit this problem by considering both adaptive and non-adaptive efficient algorithms. Compared with the state-of-art methods, we make several contributions to the problem of finding MRFR. Firstly, we find a general and precise recursive relationship between the minimal bases for two adjacent lattices generated by successive truncation sequences. This enables us to improve the currently fastest adaptive algorithm proposed by Li et al.. Secondly, by optimizing a time-consuming step of the well-known Lagrange reduction algorithm for 2-dimensional lattices, we obtain a non-adaptive, and yet practically faster MRFR-solving algorithm named global Euclidean algorithm. Thirdly, we identify theoretical flaws on some non-adaptive methods in the literature by counter-examples and correct the problems by designing modified Euclidean algorithm named partial Euclidean algorithm. Meanwhile, we further reduce the time complexity of existing algorithm from $O(n^{2})$ to $O(n\log ^{2}n\log \log n)$ by invoking the half-gcd algorithm. We also conduct a comprehensive experimental comparative analysis on the above algorithms to validate our theoretical analysis. [ABSTRACT FROM AUTHOR]

In a recent work, Beierle, Brinkmann and Leander presented a recursive tree search for finding APN permutations with linear self-equivalences in small dimensions. In this paper, we describe how this search can be adapted to find many new instances of quadratic APN functions. In particular, we found 12,921 new quadratic APN functions in dimension eight, 35 new quadratic APN functions in dimension nine and five new quadratic APN functions in dimension ten up to CCZ-equivalence. Remarkably, two of the 35 new APN functions in dimension nine are APN permutations. Among the 8-bit APN functions, there are three extended Walsh spectra that do not correspond to any of the previously-known quadratic 8-bit APN functions and, surprisingly, there exist at least four CCZ-inequivalent 8-bit APN functions with linearity 27, i.e., the highest possible non-trivial linearity for quadratic functions in dimension eight. [ABSTRACT FROM AUTHOR]

In this paper, we aim to construct a class of complete permutations $\mathcal F$ over $\mathbb F_{q}^{n}$ from some polynomials $f_{1},f_{2},\ldots,f_{n}$ over $\mathbb F_{q}$. First of all, we determine a necessary and sufficient condition such that $\mathcal F$ is complete. Briefly, we transform the completeness of $\mathcal F$ into showing the permutation properties of two polynomials over $\mathbb F_{q}$ obtained from these $f_{i}$ ’s. Then, following the wide applications, we investigate the constructions of linear complete permutations over $\mathbb F_{2}^{n}$ based on the rotations and XORs. The following two cases are considered: the first one is to use some different circularly left shift transforms $f_{i}$ ’s and the second one is to assume $f_{i}$ ’s are of the form $b_{i}f$ with a fixed $f$ and different $b_{i}$ ’s in $\mathbb F_{q}$. In both cases, we show that the completeness of the permutation is closely related to the ranks of some matrices with particular forms, which can be determined by the cycle decomposition of the permutation over the $n$ branches. Besides, we present several explicit linear complete permutations which might be used in the design as well as the provable security of cryptographic schemes. [ABSTRACT FROM AUTHOR]

In this paper, by the Hasse-Weil bound, we determine the necessary and sufficient condition on coefficients $a_{1},a_{2},a_{3}\in {\mathbb F} _{2^{n}}$ with $n=2m$ such that $f(x) = {x}^{3\cdot 2^{m}} + a_{1}x^{2^{m+1}+1} + a_{2} x^{2^{m}+2} + a_{3}x^{3}$ is an APN function over ${\mathbb F}_{2^{n}}$. Our work together with the follow-up work by Chase and Lisoněk indicates that all such APN quadrinomials $f(x)$ are affine equivalent to two instances of Gold functions, which resolves the first half of an open problem by Carlet at the International Workshop on the Arithmetic of Finite Fields, 83-107, 2014. [ABSTRACT FROM AUTHOR]

In a prior paper (Ellingsen et al., 2020), two of us, along with P. Ellingsen, P. Felke, and A. Tkachenko, defined a new (output) multiplicative differential and the corresponding $c$ -differential uniformity, which has the potential of extending differential cryptanalysis. Here, we continue the work by looking at some APN functions through the mentioned concept and showing that their $c$ -differential uniformity increases significantly in some cases. [ABSTRACT FROM AUTHOR]

This paper investigates the construction of rank-metric codes with specified Ferrers diagram shapes. These codes play a role in the multilevel construction for subspace codes. A conjecture from 2009 provides an upper bound for the dimension of a rank-metric code with given specified Ferrers diagram shape and rank distance. While the conjecture in its generality is wide open, several cases have been established in the literature. This paper contributes further cases of Ferrers diagrams and ranks for which the conjecture holds true. In addition, the proportion of maximal Ferrers diagram codes within the space of all rank-metric codes with the same shape and dimension is investigated. Special attention is being paid to MRD codes. It is shown that for growing field size the limiting proportion depends highly on the Ferrers diagram. For instance, for $[m\times 2]$ -MRD codes with rank 2 this limiting proportion is close to $1/e$. [ABSTRACT FROM AUTHOR]

There has been much recent interest in private information retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being a simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy, and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient PIR protocols. In this paper, we are interested in designing PIR array codes. We consider the case when we have $m$ servers, with each server storing a fraction $(1/s)$ of the bits of the database; here $s$ is a fixed rational number with $s > 1$. A PIR array code with the $k$ -PIR property enables a $k$ -server PIR protocol (with $k\leq m$) to be emulated on $m$ servers, with the overall storage requirements of the protocol being reduced. The communication complexity of a PIR protocol reduces as $k$ grows, so the virtual server rate, defined to be $k/m$ , is an important parameter. We study the maximum virtual server rate of a PIR array code with the $k$ -PIR property. We present upper bounds on the achievable virtual server rate, some constructions, and ideas how to obtain the PIR array codes with the highest possible virtual server rate. In particular, we present constructions that asymptotically meet our upper bounds and the exact largest virtual server rate is obtained when $1 < s \leq 2$. A $k$ -PIR code (and similarly a $k$ -PIR array code) is also a locally repairable code with symbol availability $k-1$. Such a code ensures $k$ parallel reads for each information symbol. So the virtual server rate is very closely related to the symbol availability of the code when used as a locally repairable code. The results of this paper are discussed also in this context where subspace codes also have an important role. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem for which lengths a maximum distance separable (MDS) Euclidean self-dual code over $\mathbb {F}_{q}$ exists. This problem is completely solved for the case where $q$ is even. For $q$ is odd, some $q$ -ary MDS Euclidean self-dual codes were obtained in the literature. In this paper, we construct six new classes of $q$ -ary MDS Euclidean self-dual codes by using generalized Reed–Solomon (GRS for short) codes and extended GRS codes. [ABSTRACT FROM AUTHOR]

Motivated by systems, where the information is represented by a graph such as neural networks, associative memories, and distributed systems. In this paper, we present a new class of codes, called codes over graphs. Under this paradigm, the information is stored on the edges of undirected or directed complete graphs, and a code over graphs is a set of graphs. A node failure is the event, where all edges in the neighborhood of the erased node have been erased. We say that a code over graphs can tolerate $\rho $ node failures, if it can correct the erased edges of any $\rho $ failed nodes in the graph. While the construction of optimal codes over graphs can be easily accomplished by MDS codes, their field size has to be at least ${\mathcal{ O}}(n^{2})$ , when $n$ is the number of nodes in the graph. In this paper, we present several constructions of codes over graphs with smaller field size. To accomplish this task, we use constructions of product codes and rank metric codes. Furthermore, we present optimal codes over graphs correcting two node failures over the binary field, when the number of nodes in the graph is a prime number. Last, we also provide upper bound on the number of nodes for optimal codes. [ABSTRACT FROM AUTHOR]

BCH codes are an important class of cyclic codes which have applications in satellite communications, DVDs, disk drives, and two-dimensional bar codes. Although BCH codes have been widely studied, their parameters are known for only a few special classes. Recently, Ding et al. made some new progress in BCH codes. However, we still have very limited knowledge on the dimension of BCH codes, not to mention the weight distribution of BCH codes. In this paper, we generalize the results on BCH codes from several previous papers. 1) The dimension of narrow-sense BCH codes of length $((q^{m}-1)/{\lambda })$ with designed distance $2\leq \delta \leq (({q^{\lceil (m+1)/2 \rceil }-1})/(\lambda)+1)$ is settled, where $\lambda $ is any factor of $(q-1)$. 2) The weight distributions of two classes of narrow-sense BCH codes of length $(({q^{m}-1})/2)$ with designed distance $\delta =(({(q-1)q^{m-1}-q^{\lfloor (m-1)/2\rfloor }-1})/2)$ and $\delta =(({(q-1)q^{m-1}-q^{\lfloor (m+1)/2\rfloor }-1})/2)$ are determined. 3) The weight distribution of a class of BCH codes of length $((q^{m}-1)/({q-1}))$ is determined. In particular, a subclass of this class of BCH codes is optimal with respect to the Griesmer bound. Some optimal linear codes obtained from this class of BCH codes are characterized. [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]

We investigate the list decodability of symbol-pair codes in this paper. First, we show that the list decodability of every symbol-pair code does not exceed the Gilbert–Varshamov bound. On the other hand, we are able to prove that with high probability, a random symbol-pair code can be list decoded up to the Gilbert–Varshamov bound. Our second result of this paper is to derive the Johnson-type bound, i.e., a lower bound on list decoding radius in terms of minimum distance. Finally, we present a list decoding algorithm of Reed–Solomon codes beyond the Johnson-type bound in the pair metric. 1 A symbol-pair code is referred to a code in the pair metric. [ABSTRACT FROM AUTHOR]

In a paper by Guruswami et al., it was shown that the length $n$ of a $q$ -ary linear locally recoverable code with distance $d \geqslant 5$ is upper bounded by $O(dq^{3})$. Thus, it is a challenging problem to construct $q$ -ary locally recoverable codes with distance $d \geqslant 5$ and length approaching the upper bound. The same paper also gave an algorithmic construction of $q$ -ary locally recoverable codes with locality $r$ and length $n=\Omega _{r}(q^{2})$ for $d=5$ and 6, where $\Omega _{r}$ means that the implicit constant depends on locality $r$. In this paper, we present an explicit construction of $q$ -ary locally recoverable codes of distance $d= 5$ and 6 via binary constant weight codes. It turns out that 1) our construction is simpler and more explicit and 2) the length of our codes is greater than previously known. [ABSTRACT FROM AUTHOR]

In this paper, a new and efficient method for solving affine sub-families included in a family of nonlinear feedback shift register (NFSR) sequences is proposed. The linear case is focused on since the affine case is an analogy. Let f(x0, x1,...,xn) = x0⊕f1(x1,...,xn-1)⊕xn be a characteristic function of an n-stage NFSR, where n is a positive integer. Let deg(f) = d > 1 and f[d] be the summation of all terms in the algebraic normal form of f whose degrees attain the maximum d. First, it is proved that every linear sub-family of G(f) is a sub-family of linear feedback shift register sequences generated by a characteristic polynomial of the form Σi∈Sci xi, where ci ∈ F2 and S consists of all subscripts of variables appearing in f[d]. That is to say, every linear sub-family of G(f) is a factor of some polynomial Σi∈Sc ixi over the finite field F2. This result is a well generalization of linear recurring sequences theory since it also holds if d = 1. Based on this result, a candidate set of linear sub-families could be obtained by polynomial factorizations over F2. Second, we propose a new method to verify a linear sub-family whose memory requirement and time complexity are clearer than the previous method. For instance, all affine sub-families of the 160-bit main register used in Grain v1 could be determined within two seconds by a PC using the new method in this paper, which is unobtainable for previous algorithms. [ABSTRACT FROM AUTHOR]

Constructing locally repairable codes achieving Singleton-type bound (we call them optimal codes in this paper) is a challenging task and has attracted great attention in the last few years. Tamo and Barg first gave a breakthrough result in this topic by cleverly considering subcodes of Reed-Solomon codes. Thus, $q$ -ary optimal locally repairable codes from subcodes of Reed-Solomon codes given by Tamo and Barg have length upper bounded by $q$. Recently, it was shown through extension of construction by Tamo and Barg that length of $q$ -ary optimal locally repairable codes can be $q+1$ by Jin et al.. Surprisingly it was shown by Barg et al. that, unlike classical MDS codes, $q$ -ary optimal locally repairable codes could have length bigger than $q+1$. Thus, it becomes an interesting and challenging problem to construct $q$ -ary optimal locally repairable codes of length bigger than $q+1$. In this paper, we make use of rich algebraic structures of elliptic curves to construct a family of $q$ -ary optimal locally repairable codes of length up to $q+2\sqrt {q}$. It turns out that locality of our codes can be as big as 23 and distance can be linear in length. [ABSTRACT FROM AUTHOR]

The Demirci-Selçuk’s meet-in-the-middle attack is one of the most important methods among all the cryptanalytic vectors, which gives the best result against the round-reduced AES with respect to the rounds, and tradeoffs between data, time and memory. While we have already built provable security models against the differential cryptanalysis, linear cryptanalysis cryptanalysis, impossible differential and zero-correlation linear cryptanalysis, the provable security against the meet-in-the-middle attack is missing. In this paper, we propose the subset representation of function based on which we could give an algorithm to compute the exact number of parameters of the Demirci-Selçuk’s distinguisher given the input and output, respectively. Experiments show that this algorithm can be more efficient than the automatical tool presented by Shi et al. at Asiacrypt 2018. We further extract a formula based on this algorithm and show an upper bound for the length of the Demirci-Selçuk’s distinguisher of an iterative SPN cipher. We prove that for an SPN block cipher whose block size equals the key size, an effective Demirci-Selçuk-type meet-in-the-middle distinguisher covers at most twice the maximum of the primitive indexes of the linear layer and its inverse. As a result, we show that the known length of the Demirci-Selçuk’s distinguisher of the AES-128 cannot be improved unless the details of the S-boxes are exploited, which demonstrates that the AES has a provable security against the Demirci-Selçuk’s meet-in-the-middle attack. [ABSTRACT FROM AUTHOR]

In this paper, we propose an automatic tool to search for optimal differential and linear trails in ARX ciphers. It’s shown that a modulo addition can be divided into sequential small modulo additions with carry bit, which turns an ARX cipher into an S-box-like cipher. From this insight, we introduce the concepts of carry-bit-dependent difference distribution table (CDDT) and carry-bit-dependent linear approximation table (CLAT). Based on them, we give efficient methods to trace all possible output differences and linear masks of a big modulo addition, with returning their differential probabilities and linear correlations simultaneously. Then an adapted Matsui’s algorithm is introduced, which can find the optimal differential and linear trails in ARX ciphers. Besides, the superiority of our tool’s potency is also confirmed by experimental results for round-reduced versions of HIGHT and SPECK. More specifically, we find the optimal differential trails for up to 10 rounds of HIGHT, reported for the first time. We also find the optimal differential trails for 10, 12, 16, 8 and 8 rounds of SPECK32/48/64/96/128, and report the provably optimal differential trails for SPECK48 and SPECK64 for the first time. The optimal linear trails for up to 9 rounds of HIGHT are reported for the first time, and the optimal linear trails for 22, 13, 15, 9 and 9 rounds of SPECK32/48/64/96/128 are also found respectively. These results evaluate the security of HIGHT and SPECK against differential and linear cryptanalysis. Also, our tool is useful to estimate the security in the design of ARX ciphers. [ABSTRACT FROM AUTHOR]

Grain is one of three hardware-oriented finalists of the eSTREAM Project. A nonlinear feedback shift register (NFSR) in Grain-like structure is a cascade connection of a linear feedback shift register (LFSR) into an NFSR, in which the characteristic polynomial of the LFSR is primitive and the feedback function of the NFSR is nonsingular. In 2011 Hu and Gong pointed out that the period of the sequence generated by an NFSR in Grain-like structure is a multiple of the period of the sequence generated by its LFSR if the initial state of the LFSR is nonzero. Meanwhile, they proposed an open problem: for fixed feedback functions of an NFSR and an LFSR, determine whether the sequences generated by the NFSR in Grain-like structure can achieve the minimum period, i.e., the period of the LFSR, when the initial state of the LFSR is nonzero, and if they can achieve, provide at least one pair of the initial states of the NFSR and LFSR. Clearly, from a security point of view, it is not preferable if the sequences generated by an NFSR in Grain-like structure achieve the minimum period. This paper converts the open problem into a problem of solving an integer equation with respect to two unknown integers that uniquely correspond to the initial states of the NFSR and LFSR, by viewing the NFSR as a Boolean control network. Based on the integer equation, this paper shows that for any given initial state of an $n$ -stage NFSR and any given nonzero initial state of an $m$ -stage LFSR, the probability that the sequence generated by the NFSR in Grain-like structure achieves the minimum period $2^{m}-1$ is at most $2^{-n}$. This implies that the probability of the cascade connection used in Grain achieving the minimum period is very small. [ABSTRACT FROM AUTHOR]

A nonlinear feedback shift register (NFSR) of $n$ -stage is called irreducible if, the family of output sequences of any NFSR of stage less than $n$ is not included in that of the NFSR. Tian and Qi in this paper [IEEE-IT, 2013(6),4006–4012] gave a lower bound on the density of irreducible NFSRs. In this paper, we improve their lower bound and also give an upper bound on the density of irreducible NFSRs. Moreover, the gap between our upper and lower bounds is less than 0.04. [ABSTRACT FROM PUBLISHER]

This paper is composed of two main parts related to the nonlinearity of vectorial functions. The first part is devoted to maximally nonlinear (n,m) functions (the so-called bent vectorial functions), which contribute to an optimal resistance to both linear and differential attacks on symmetric cryptosystems. They can be used in block ciphers at the cost of additional diffusion/compression/expansion layers, or as building blocks for the construction of substitution boxes (S-boxes), and they are also useful for constructing robust codes and algebraic manipulation detection codes. A main issue on bent vectorial functions is to characterize bent monomial functions Tr_{m}^{n} (\lambda x^{d}) from \mathbb {F}_{2^{n}} to \mathbb F2^{m} (where m is a divisor of n ) leading to a classification of those bent monomials. We also treat the case of functions with multiple trace terms involving general results and explicit constructions. Furthermore, we investigate some open problems raised by Pasalic et al. and Muratović-Ribić et al. in a series of papers on vectorial functions. The second part is devoted to the nonlinearity of (n,m) -functions. No tight upper bound is known when \frac n2

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]

A Grain-like structure is a cascade connection of a primitive LFSR into an NFSR. It is well known that such structures generate sequences with periods multiples of the period of primitive LFSR sequences. In this paper, we study weak Grain-like structures, i.e., Grain-like structures generating at least one sequence with minimum period. Assume the orders of LFSR and NFSR are $n$ and $m$ respectively. We prove that weak Grain-like structures always exist when $m>n$. For $m=n$ , we give three classes of weak Grain-like structures. Then we extend the method in the second class to prove that weak Grain-like structures exist when $m\ge n-\lg n+4$. Moreover, our experimental data shows that, the ratio of weak Grain-like structures approximates a value which is a little more than 63% for small $m=n$ , and weak Grain-like structures exist with $m=3$ or 4 when $n\le 18$. [ABSTRACT FROM AUTHOR]

The paper proposes an improved difference-of-syndromes decoding algorithm for decoding quadratic residue codes up to half the minimum distance. Therein, soft-decision information is not essential, but it can be used to speed up the computations. The improvement over the prior art is demonstrated by simulations. Moreover, the proposed algorithm is also compared with the classic Berlekamp-Massey algorithm by taking two BCH codes as examples. [ABSTRACT FROM AUTHOR]

In the index coding problem a sender holds a message $x \in \{0,1\}^{n}$ and wishes to broadcast information to $n$ receivers in a way that enables the $i$ th receiver to retrieve the $i$ th bit $x_{i}$. Every receiver has prior side information comprising a subset of the bits of $x$ , and the goal is to minimize the length of the information sent via the broadcast channel. Porter and Wootters have recently introduced the model of embedded index coding, where the receivers also play the role of the sender and the goal is to minimize the total length of their broadcast information. An embedded index code is said to be task-based if every receiver retrieves its bit based only on the information provided by one of the receivers. This paper studies the effect of the task-based restriction on linear embedded index coding. It is shown that for certain side information maps there exists a linear embedded index code of length quadratically smaller than that of any task-based embedded index code. The result attains, up to a multiplicative constant, the largest possible gap between the two quantities. The proof is by an explicit construction and the analysis involves spectral techniques. [ABSTRACT FROM AUTHOR]

An $[{n}, {k}, {n}-{k}+1]$ linear code is called an MDS code. An $[{n}, {k}, {n}-{k}]$ linear code is said to be almost maximum distance separable (almost MDS or AMDS for short). A code is said to be near maximum distance separable (near MDS or NMDS for short) if the code and its dual code both are almost maximum distance separable. The first near MDS code was the [11, 6, 5] ternary Golay code discovered in 1949 by Golay. This ternary code holds 4-designs, and its extended code holds a Steiner system ${S}(5, 6, 12)$ with the largest strength known. In the past 70 years, sporadic near MDS codes holding t-designs were discovered and a lot of infinite families of near MDS codes over finite fields were constructed. However, the question as to whether there is an infinite family of near MDS codes holding an infinite family of t-designs for $ {t}\geq 2$ remains open for 70 years. This paper settles this long-standing problem by presenting an infinite family of near MDS codes over $ {GF}(3^{ {s}})$ holding an infinite family of 3-designs and an infinite family of near MDS codes over $ {GF}(2^{2 {s}})$ holding an infinite family of 2-designs. The subfield subcodes of these two families of codes are also studied, and are shown to be dimension-optimal or distance-optimal. [ABSTRACT FROM AUTHOR]

Limited magnitude asymmetric error model is well suited for flash memory. In this paper, we consider the construction of asymmetric codes correcting single error over $\mathbb {Z}_{2^{k}r}$ which is based on so called $B_{1}[{4}](2^{k}r)$ set. In fact, we reduce the construction of a maximal size $B_{1}[{4}](2^{k}r)$ set for $k\geq 3$ to the construction of a maximal size $B_{1}[{4}](2^{k-3}r)$ set. Finally, we give an explicit formula of a maximal size $B_{1}[{4}](4r)$ set and some lower bounds of a maximal size $B_{1}[{4}](2r)$ set. By computer searching up to $q\leq 106$ , we conjecture that those lower bounds are tight. [ABSTRACT FROM AUTHOR]

In this paper we define a new (output) multiplicative differential, and the corresponding c-differential uniformity. With this new concept, even for characteristic 2, there are perfect ${c}$ -nonlinear (PcN) functions. We first characterize the ${c}$ -differential uniformity of a function in terms of its Walsh transform. We further look at some of the known perfect nonlinear (PN) functions and show that only one remains a PcN function, under a different condition on the parameters. In fact, the p-ary Gold PN function increases its c-differential uniformity significantly, under some conditions on the parameters. We then precisely characterize the c-differential uniformity of the inverse function (in any dimension and characteristic), relevant for the Rijndael (and Advanced Encryption Standard) block cipher. [ABSTRACT FROM AUTHOR]

Locally repairable codes have been investigated extensively in recent years due to practical applications in distributed and cloud storage systems. However, there are few asymptotic constructions of locally repairable codes in the literature. In this paper, we provide a new explicit asymptotic construction of locally repairable codes over arbitrary finite fields from local expansions of functions at a rational place. This construction gives a Tsfasman-Vladut-Zink type bound for locally repairable codes. Its main advantage is that there are no constraints on both locality and alphabet size. Furthermore, we show that the Gilbert-Varshamov type bound of locally repairable codes over non-prime finite fields can be improved for sufficiently large alphabet sizes. [ABSTRACT FROM AUTHOR]

In this paper, locally repairable codes which have optimal minimum Hamming distance with respect to the bound presented by Prakash et al. are considered. New upper bounds on the length of such optimal codes are derived. The new bounds apply to more general cases, and have weaker requirements compared with the known ones. In this sense, they both improve and generalize previously known bounds. Further, optimal codes are constructed, whose length is order-optimal with respect to the new upper bounds. Notably, the length of the codes is super-linear in the alphabet size. [ABSTRACT FROM AUTHOR]

In a bus with $n$ wires, each wire has two states, ‘0’ or ‘1’, representing one bit of information. Whenever the state transitions from ‘0’ to ‘1’, or ‘1’ to ‘0’, joule heating causes the temperature to rise, and high temperatures have adverse effects on on-chip bus performance. Recently, the class of low-power cooling (LPC) codes was proposed to control such state transitions during each transmission. As suggested in earlier work, LPC codes may be used to control simultaneously both the peak temperature and the average power consumption of on-chip buses. Specifically, an $(n,t,w)$ -LPC code is a coding scheme over $n$ wires that (i) avoids state transitions on the $t$ hottest wires (thus preventing the peak temperature from rising); and (ii) allows at most $w$ state transitions in each transmission (thus reducing average power consumption). In this paper, for any fixed value of $w$ , several constructions are presented for large LPC codes that can be encoded and decoded in time $O\left ({n \log ^{2} (n/w)}\right)$ along with the corresponding encoding/decoding schemes. In particular, we construct LPC codes of size $(n/w)^{w-1}$ , which are asymptotically optimal. We then modify these LPC codes to also correct errors in time $O(n^{3})$. For the case where $w$ is proportional to $n$ , we further present a different construction of large LPC codes, based on a mapping from cooling codes to LPC codes. Using this construction, we obtain two families of LPC codes whose encoding and decoding complexities are $O(n^{3})$. [ABSTRACT FROM AUTHOR]

In index coding, a server broadcasts multiple messages to their respective receivers, each with some side information that can be utilized to reduce the amount of communication from the server. Distributed index coding is an extension of index coding in which the messages are broadcast from multiple servers, each storing different subsets of the messages. In this paper, the optimal tradeoff among the message rates and the server broadcast rates, which is defined formally as the capacity region, is studied for a general distributed index coding problem. Inner and outer bounds on the capacity region are established that have matching sum-rates for all 218 non-isomorphic four-message problems with equal link capacities for all the links from servers to receivers. The proposed inner bound is built on a distributed composite coding scheme that outperforms the existing schemes by incorporating more flexible decoding configurations and enhanced fractional rate allocations into two-stage composite coding, a scheme that was originally introduced for centralized index coding. The proposed outer bound is built on the polymatroidal axioms of entropy, as well as functional dependences such as the fd-separation introduced by the multi-server nature of the problem. This outer bound utilizes general groupings of servers with different levels of granularity, which allows a natural tradeoff between computational complexity and tightness of the bound, and includes and improves upon all existing outer bounds for distributed index coding. Specific features of the proposed inner and outer bounds are demonstrated through concrete examples with four or five messages. [ABSTRACT FROM AUTHOR]

The Slepian-Wolf (SW) coding system is a source coding system with two encoders and a decoder, where these encoders independently encode source sequences from two correlated sources into codewords, and the decoder reconstructs both source sequences from the codewords. In this paper, we consider the situation in which the SW coding system is asynchronous, i.e., each encoder samples a source sequence with some unknown delay. We assume that delays are unknown but maximum and minimum values of possible delays are known to encoders and the decoder. We also assume that sources are discrete stationary memoryless and the probability mass function (PMF) of the sources is unknown but the system knows that it belongs to a certain set of PMFs. For this asynchronous SW coding system, we clarify the achievable rate region which is the set of rate pairs of encoders such that the decoding error probability vanishes as the blocklength tends to infinity. We show that this region does not always coincide with that of the synchronous SW coding system in which each encoder samples a source sequence without any delay. [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 this paper we consider self-dual NRT codes, that is, self-dual codes in the metric space endowed with the Niederreiter-Rosenbloom-Tsfasman metric (NRT metric) and their shape enumerators as defined by Barg and Park. We use polynomial invariant theory to describe the shape enumerator of a binary self-dual NRT code, even self-dual NRT code, and weak doubly even self-dual NRT code in $ {M}_{ {n},2}(\mathbb {F}_{2})$. Motivated by these results, we describe the number of invariant polynomials that we must find to describe the shape enumerator of a self-dual NRT code in $ {M}_{ {n}, {s}}(\mathbb {F}_{2})$. We define the ordered flip of a matrix $ {A}\in {M}_{ {k},{ { ns}}}(\mathbb {F}_{ {q}})$ and present some constructions of self-dual NRT codes over $\mathbb {F}_{ {q}}$. We further give an application of ordered flip to the classification of self-dual NRT codes of dimension two. [ABSTRACT FROM AUTHOR]

In this paper we study array-based codes over graphs for correcting multiple node failures. These codes have applications to neural networks, associative memories, and distributed storage systems. We assume that the information is stored on the edges of a complete undirected graph and a node failure is the event where all the edges in the neighborhood of a given node have been erased. A code over graphs is called $\rho $ -node-erasure-correcting if it allows to reconstruct the erased edges upon the failure of any $\rho $ nodes or less. We present a binary optimal construction for double-node-erasure correction together with an efficient decoding algorithm, when the number of nodes is a prime number. Furthermore, we extend this construction for triple-node-erasure-correcting codes when the number of nodes is a prime number and two is a primitive element in $\mathbb {Z}_{n}$. These codes are at most a single bit away from optimality. [ABSTRACT FROM AUTHOR]