Search

In general coding theory, we often assume that error is observed in transferring or storing encoded symbols, while the process of encoding itself is error-free. Motivated by recent applications of coding theory, in this paper, we consider the case where the process of encoding is distributed and prone to error. We introduce the problem of distributed encoding, comprised of a set of $K \in \mathbb {N}$ isolated source nodes and $N \in \mathbb {N}$ encoding nodes. Each source node has one symbol from a finite field, which is sent to each of the encoding nodes. Each encoding node stores an encoded symbol from the same field, as a function of the received symbols. However, some of the source nodes are controlled by the adversary and may send different symbols to different encoding nodes. Depending on the number of the adversarial nodes, denoted by $\beta \in \mathbb {N}$ , and the cardinality of the set of symbols that each one generates, denoted by $v \in \mathbb {N}$ , the process of decoding from the encoded symbols could be impossible. Assume that a decoder connects to an arbitrary subset of $t \in \mathbb {N}$ encoding nodes and wants to decode the symbols of the honest nodes correctly, without necessarily identifying the sets of honest and adversarial nodes. An important characteristic of a distributed encoding system is $t^{*} \in \mathbb {N}$ , the minimum of such $t$ , which is a function of $K$ , $N$ , $\beta $ , and $v$. In this paper, we study the distributed linear encoding system, i.e. one in which the encoding nodes use linear coding. We show that $t^{*}_{\textrm {Linear}}=K+2\beta (v-1)$ , if $N\ge K+2\beta (v-1)$ , and $t^{*}_{\textrm {Linear}}=N$ , if $N\le K+2\beta (v-1)$. In order to achieve $t^{*}_{\textrm {Linear}}$ , we use random linear coding and show that in any feasible solution that the decoder finds, the messages of the honest nodes are decoded correctly. In order to prove the converse of the fundamental limit, we show that when the adversary behaves in a particular way, it can always confuse the decoder between two feasible solutions that differ in the message of at least one honest node. [ABSTRACT FROM AUTHOR]

As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest $k$ -path problem ($k$ -VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph $G$ of order $n$ , BP algorithm converges to the unique optimal solution of $k$ -VDSP on $G$ within $O(n^{2}w_{max})$ iterations, provided that the weight $w_{e}$ is nonnegative integral for each arc $e\in E(G)$ , where $w_{max}=\max \{w_{e}: e\in E(G)\}$. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of $k$ -VDSP to the case of multiple sources or sinks. [ABSTRACT FROM AUTHOR]

In its most elementary form, compressed sensing studies the design of decoding algorithms to recover a sufficiently sparse vector or code from a lower dimensional linear measurement vector. Typically it is assumed that the decoder has access to the encoder matrix, which in the combinatorial case is sparse and binary. In this paper we consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone, that is without access to encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrices from the associated linear measurement matrix. The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation, with strong performance guarantees. Under mild assumptions on the sparse coding matrix and by deploying a novel random encoder matrix, we prove that Decoder-Expander Based Factorisation recovers both the encoder and sparse coding matrix at the optimal measurement rate with high probability and from a near optimal number of measurement vectors. In addition, our experiments demonstrate the efficacy and computational efficiency of our algorithm in practice. Beyond compressed sensing, our results may be of interest for researchers working in areas as diverse as linear sketching, coding theory, matrix compression and dictionary learning. [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]

Erasure codes are essential for providing efficient resilience against node failures in distributed storage. Typically, an $[n, k]$ erasure code encodes $k$ symbols into $n$ symbols which are then stored in different nodes. Recent work by Kadekodi et al. shows that the failure rates of storage nodes vary significantly over time, and that changing the rate of the code (via a change in $n$ and $k$) in response to such variations provides substantial storage space savings. However, the resource overhead of re-encoding the already encoded data is prohibitively high. We present a new theoretical framework formalizing code conversion—the process of converting data encoded with an $[n^{ I}, k^{ I}]$ code into data encoded with an $[{n^{ F}}, {k^{ F}}]$ code while maintaining desired decodability properties. We then introduce convertible codes, a new class of codes that allow for code conversions in a resource-efficient manner. This paper begins the study on convertible codes by focusing on linear MDS codes and the access cost of conversion. We derive a lower bound on the access cost of conversion and present an explicit optimal construction matching this bound for an important subclass of conversions. Additionally, we propose constructions with low field-size requirement for a broad subset of parameters. Our results show that it is possible to achieve code conversions with significantly less resources than the default approach of re-encoding for a wide range of parameters. [ABSTRACT FROM AUTHOR]

Linear codes generated by component functions of perfect nonlinear (PN for short) and almost perfect nonlinear (APN for short) functions and the first-order Reed-Muller codes have been an object of intensive study in coding theory. The objective of this paper is to investigate some binary shortened codes of two families of linear codes from APN functions and some $p$ -ary shortened codes associated with PN functions. The weight distributions of these shortened codes and the parameters of their duals are determined. The parameters of these binary codes and $p$ -ary codes are flexible. Many of the codes presented in this paper are optimal or almost optimal. The results of this paper show that the shortening technique is very promising for constructing good codes. [ABSTRACT FROM AUTHOR]

Linear codes with few weights have applications in consumer electronics, communications, data storage systems, secret sharing, authentication codes, and association schemes. As a special class of linear codes, minimal linear codes have important applications in secret sharing and secure computation of data between two parties. The construction of minimal linear codes with new and desirable parameters is an interesting research topic in coding theory and cryptography. Recently, Mesnager et.al. stated that “constructing linear codes with good parameters from non-weakly regular bent functions is an interesting problem.” The goal of this paper is to construct linear codes with two or three weights from non-weakly regular bent functions over finite fields and analyze the minimality of the constructed linear codes. In doing so, we draw inspiration from a paper by Mesnager in which she constructed linear codes with small weights from weakly regular bent functions based on a generic construction method. First, we recall the definitions of the subsets $B_{+}(f)$ and $B_{-}(f)$ associated with a non-weakly regular bent function $f$. Next, we construct two- or three-weight linear $p$ -ary codes on these sets using duals of the non-weakly regular bent functions that are also bent. We note that the constructed linear codes are minimal in almost all cases. Moreover, when $f$ is a non-weakly regular bent function in a certain subclass of Generalized Maiorana-McFarland bent functions, we determine the weight distributions of the corresponding linear codes. As far as we know, the construction of linear codes from non-weakly regular bent functions over finite fields is first studied in the literature by the second author in his dissertation. [ABSTRACT FROM AUTHOR]

This paper investigates the theory of sum-rank-metric codes for which the individual matrix blocks may have different sizes. Various bounds on the cardinality of a code are derived, along with their asymptotic extensions. The duality theory of sum-rank-metric codes is also explored, showing that MSRD codes (the sum-rank analogue of MDS codes) dualize to MSRD codes only if all matrix blocks have the same number of columns. In the latter case, duality considerations lead to an upper bound on the number of blocks for MSRD codes. The paper also contains various constructions of sum-rank-metric codes for variable block sizes, illustrating the possible behaviours of these objects with respect to bounds, existence, and duality properties. [ABSTRACT FROM AUTHOR]

We study an important specialization of the general problem of broadcasting on directed acyclic graphs, namely, that of broadcasting on two-dimensional (2D) regular grids. Consider an infinite directed acyclic graph with the form of a 2D regular grid, which has a single source vertex $X$ at layer 0, and $k + 1$ vertices at layer $k \geq 1$ , which are at a distance of $k$ from $X$. Every vertex of the 2D regular grid has outdegree 2, the vertices at the boundary have indegree 1, and all other non-source vertices have indegree 2. At time 0, $X$ is given a uniform random bit. At time $k \geq 1$ , each vertex in layer $k$ receives transmitted bits from its parents in layer $k-1$ , where the bits pass through independent binary symmetric channels with common crossover probability $\delta \in \left({0,\frac {1}{2}}\right)$ during the process of transmission. Then, each vertex at layer $k$ with indegree 2 combines its two input bits using a common deterministic Boolean processing function to produce a single output bit at the vertex. The objective is to recover $X$ with probability of error better than $\frac {1}{2}$ from all vertices at layer $k$ as $k \rightarrow \infty $. Besides their natural interpretation in the context of communication networks, such broadcasting processes can be construed as one-dimensional (1D) probabilistic cellular automata, or discrete-time statistical mechanical spin-flip systems on 1D lattices, with boundary conditions that limit the number of sites at each time $k$ to $k+1$. Inspired by the literature surrounding the “positive rates conjecture” for 1D probabilistic cellular automata, we conjecture that it is impossible to propagate information in a 2D regular grid regardless of the noise level $\delta $ and the choice of common Boolean processing function. In this paper, we make considerable progress towards establishing this conjecture, and prove using ideas from percolation and coding theory that recovery of $X$ is impossible for any $\delta \in \left({0,\frac {1}{2}}\right)$ provided that all vertices with indegree 2 use either AND or XOR for their processing functions. Furthermore, we propose a detailed and general martingale-based approach that establishes the impossibility of recovering $X$ for any $\delta \in \left({0,\frac {1}{2}}\right)$ when all NAND processing functions are used if certain structured supermartingales can be rigorously constructed. We also provide strong numerical evidence for the existence of these supermartingales by computing several explicit examples for different values of $\delta $ via linear programming. [ABSTRACT FROM AUTHOR]

In this paper we introduce Ouroboros, a new family of Key Exchange protocols based on coding theory. The protocols propose a middle ground between the cryptosystems based on $\mathsf {QC}$ - $\mathsf {MDPC}$ codes, which feature small parameter sizes, but have a security reduction to two problems: the syndrome decoding problem and the indistinguishability of the code, and the HQC protocol, which features bigger parameters but has a security reduction to the syndrome decoding problem only. Ouroboros features a reduction to the syndrome decoding problem with only a small overhead compared to the $\mathsf {QC}$ - $\mathsf {MDPC}$ based cryptosystems. The approach is based on an ideal structure and also works for the rank metric. This yields a simple, secure and efficient approach for key exchange, the Ouroboros family of protocols. For the Hamming metric we obtain the same type of parameters (and almost the same simple decoding) as for $\mathsf {MDPC}$ based cryptosystems, but with a security reduction to decoding random quasi-cyclic codes in the Random Oracle Model. This represents a reduction of up to 38% on the public key size compared to HQC, for the most secure parameters. For the rank metric, we obtain better parameters than for RQC, saving up to 31% on the public key for the most secure set of parameters, using non homogeneous errors in Ouroboros. In this full version, the protocol and decoding algorithm have been slightly improved, additional details are given in the security proof, and the protocol is fully described for the rank metric. [ABSTRACT FROM AUTHOR]

Minimal linear codes have significant applications in secret sharing schemes and secure two-party computation. When they are defined over finite fields, those codes have been intensively studied, especially in recent years, but they have been firstly partially characterized by Ashikhmin and Barg since 1998. Next, they were completely characterized in 2018 by Ding, Heng, and Zhou in terms of the minimum and maximum nonzero weights in the corresponding codes. Since then, many construction methods for minimal linear codes over finite fields throughout algebraic and geometric approaches have been proposed in the literature. In particular, the algebraic approach gives rise to minimal codes from (cryptographic) functions. Linear codes over finite fields have been expanded into the collection of acceptable alphabets for codes and study codes over finite commutative rings. A natural way to extend the known results available in the literature is to consider minimal linear codes over commutative rings with unity. In extending coding theory to codes over rings, several essential principles must be considered. Particularly extending the minimality property from finite fields to rings and creating such codes is not simple. Such an extension offers more flexibility in the construction of minimal codes. The present article investigates one-dimensional minimal linear codes over the rings $\mathbb {Z}_{p^{n}}$ (where $p$ is a prime) and $\mathbb {Z}_{p^{m}q^{n}}$ (where $p < q$ are distinct primes and $m\leq n$). Our ultimate objective is to characterize such codes’ minimality and design minimal linear codes over the considered rings. Given our objective, we first introduced the notion of minimal codes over (commutative) rings and succeeded in deriving simple characterization of one-dimensional minimal linear codes over the underlying rings mentioned above. Our new algebraic approach allows designing new minimal linear codes. Almost minimal codes over rings are also presented. To the best of our knowledge, the present paper offers a wide variety of minimal codes over (commutative) rings for the first time. Novel perspectives and developments in this direction are expected in the future. [ABSTRACT FROM AUTHOR]

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]

The de Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize the window property of de Bruijn sequences, on its shorter subsequences, are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be called locally-constrained de Bruijn sequences and a set of such sequences will be called a locally-constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the $\ell $ -symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size to previously known codes. [ABSTRACT FROM AUTHOR]

An $(n,r,h,a,q)$ -Local Reconstruction Code (LRC) is a linear code over $\mathbb {F}_{q}$ of length $n$ , whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies ‘ $a$ ’ local parity checks to recover from ‘ $a$ ’ erasures in that local group and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it offers the best blend of locality and global erasure resilience—namely it can correct all erasure patterns whose recovery is information-theoretically feasible given the locality structure (these are precisely patterns with up to ‘ $a$ ’ erasures in each local group and an additional $h$ erasures anywhere in the codeword). Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We give an explicit construction of $(n,r,h,a,q)$ -MR LRCs with field size $q$ bounded by $\left ({O\left ({\max \{r,n/r\}}\right)}\right)^{\min \{h,r-a\}}$. This significantly improves upon known constructions in many practically relevant parameter ranges. Moreover, it matches the lower bound from Gopi et al. (2020) in an interesting range of parameters where $r=\Theta (\sqrt {n})$ , $r-a=\Theta (\sqrt {n})$ and $h$ is a fixed constant with $h \leqslant a+2$ , achieving the optimal field size of $\Theta _{h}(n^{h/2})$. Our construction is based on the theory of skew polynomials. We believe skew polynomials should have further applications in coding and complexity theory; as a small illustration we show how to capture algebraic results underlying list decoding folded Reed-Solomon and multiplicity codes in a unified way within this theory. [ABSTRACT FROM AUTHOR]

We present two lower bounds on sub-packetization level $\alpha $ of MSR codes with parameters $(n, k, d=n-1, \alpha)$ where $n$ is the block length, $d$ is the number of helper nodes contacted during single-node repair, $\alpha $ the sub-packetization level and $k\alpha $ the scalar dimension. The first bound we present is for any MSR code and is given by $\alpha \ge e^{\frac {(k-1)(r-1)}{2r^{2}}}$. The second bound we present is for the case of optimal-access MSR codes and the bound is given by $\alpha \ge \min \left\{{ r^{\frac {n-1}{r}}, r^{k-1} }\right\}$. There exist optimal-access MSR constructions that achieve the second sub-packetization level bound with an equality making this bound tight. We also prove that for an optimal-access MSR code to have optimal sub-packetization level under the constraint that the $\beta $ scalar symbol indices we access from a given helper node is dependent only on the index of the failed node, it is necessary that the support of the parity-check matrix be the same as the support structure of the existing MSR constructions in literature such as the Clay code. [ABSTRACT FROM AUTHOR]

In this article, we propose an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code. Using these algorithms, we demonstrate—both with a heuristic analysis and in practice—a small polynomial speed-up over the Information-Set Decoding algorithm of Lee and Brickell (1988) for random binary codes. This appears to be the first such speed-up that is not based on a time-memory trade-off. The above speed-up should be read as a very preliminary example of the potential of a reduction theory for codes, for example in cryptanalysis. [ABSTRACT FROM AUTHOR]

A family of error-correcting codes is list-decodable from error fraction $p$ if, for every code in the family, the number of codewords in any Hamming ball of fractional radius $p$ is less than some integer $L$. It is said to be list-recoverable for input list size $\ell $ if for every sufficiently large subset of at least $L$ codewords, there is a coordinate where the codewords take more than $\ell $ values. In this work, we study the list size of random linear codes for both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below $q$ is the alphabet size, and $ \varepsilon > 0$ is the gap to capacity). (1) A random linear code of rate $1 - \log _{q}(\ell) - \varepsilon $ requires list size $L \ge \ell ^{\Omega (1/ \varepsilon)}$ for list-recovery from input list size $\ell $. (2) A random linear code of rate $1 - h_{q}(p) - \varepsilon $ requires list size $L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $ for list-decoding from error fraction $p$. (3) A random binary linear code of rate $1 - h_{2}(p) - \varepsilon $ is list-decodable from average error fraction $p$ with list size with $L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018). [ABSTRACT FROM AUTHOR]

Suppose that $\mathcal {P}$ is a property that may be satisfied by a random code $C \subset \Sigma ^{n}$. For example, for some $p \in (0,1)$ , $\mathcal {P}$ might be the property that there exist three elements of $C$ that lie in some Hamming ball of radius $pn$. We say that $R^{\ast}$ is the threshold rate for $\mathcal {P}$ if a random code of rate $R^{\ast} + \varepsilon $ is very likely to satisfy $\mathcal {P}$ , while a random code of rate $R^{\ast} - \varepsilon $ is very unlikely to satisfy $\mathcal {P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably “symmetric.” For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property $\mathcal {P}$ above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general. [ABSTRACT FROM AUTHOR]

Spectral bounds on the minimum distance of quasi-twisted codes over finite fields are proposed, based on eigenvalues of polynomial matrices and the corresponding eigenspaces. They generalize the Semenov-Trifonov and Zeh-Ling bounds in a way similar to how the Roos and shift bounds extend the BCH and HT bounds for cyclic codes. The eigencodes of a quasi-twisted code in the spectral theory and the outer codes in its concatenated structure are related. A comparison based on this relation verifies that the Jensen bound always outperforms the spectral bound under special conditions, which yields a similar relation between the Lally and the spectral bounds. The performances of the Lally, Jensen and spectral bounds are presented in comparison with each other. [ABSTRACT FROM AUTHOR]