Search

Multiplicity code decoders are based on Hermite polynomial interpolation with error correction. In order to have a unique Hermite interpolant one assumes that the field of scalars has characteristic 0 or ≥ 𝓁 +1, where 𝓁 is the maximum order of the derivatives in the list of values of the polynomial and its derivatives which are interpolated. For scalar fields of characteristic 𝓁+1, the minimum number of values for interpolating a polynomial of degree ≤ D is D+1+2E(𝓁+1) when ≤ E of the values are erroneous. Here we give an error-correcting Hermite interpolation algorithm that requires fewer values, that is, that can tolerate more errors, assuming that the characteristic of the scalar field is either 0 or ≥ D+1. Our algorithm requires (𝓁+1)D + 1 - (𝓁+1)𝓁/2 + 2E values. As an example, we consider 𝓁 = 2. If the error ratio (number of errors)/(number of evaluations) ≤ 0.16, our new algorithm requires (4+7/17),D - (1+8 /17) values, while multiplicity decoding requires 25D+25 values. If the error ratio is ≤ 0.2, our algorithm requires 5D-2 evaluations over fields of characteristic 0 or ≥ D+1, while multiplicity decoding for an error ratio 0.2 over fields of characteristic 3 is not possible for D ≥ 3. Our algorithm is based on Reed-Solomon interpolation without multiplicities, which becomes possible for Hermite interpolation because of the high redundancy necessary for error-correction.

Successive-cancellation list (SCL) decoding is a widely used and studied decoding algorithm for polar codes. For short blocklengths, empirical evidence shows that SCL decoding with moderate list sizes (say, $L \leq 32$ ) closely matches the performance of maximum-likelihood (ML) decoding. Hashemi et al. proved that on the binary erasure channel (BEC), SCL decoding actually coincides with ML decoding for list sizes $L \geq 2^{\gamma}$ , where $\gamma$ is a new parameter we call the mixing factor. Loosely speaking, the mixing factor counts the number of information bits mixed-in among the frozen bits; more precisely $\gamma=\vert\{i\in \mathcal{F}^{c}:i\leq \max\{\mathcal{F}\}\}\vert$ , where $\mathcal{F}\subset [n]$ denotes the set of frozen indices. Herein, we extend the aforementioned result of Hashemi et al. from the BEC to arbitrary binary-input memoryless symmetric channels. Our proof is based on capturing all $2^{\gamma}$ decoding paths that correspond to the $\gamma$ information bits appearing before the last frozen bit, and then finding the most-likely extension for each of these paths efficiently using a nearest coset decoding algorithm introduced herein. Furthermore, we present a hybrid successive-cancellation list (H -SCL) decoding algorithm, which is a hybrid between conventional SCL decoding and nearest coset decoding. We believe that the hybrid algorithm can outperform the conventional SCL decoder with lower decoding complexity.

The reconstruction model, first proposed by Levenshtein in 2001, assumes that a word is transmitted over multiple identical noisy channels that output distinct words. Given the channels' outputs, the transmitted word is guaranteed to be decoded uniquely only if the number of the channels is greater than some value. Otherwise, there could be several transmitted words leading to the same channels' outputs. Hence, these words should be found following the list decoding approach. Motivated by DNA storage systems, the present work takes the first steps towards studying list decoding for insertions and deletions under the reconstruction model. More specifically, it will be assumed that an arbitrary binary word is transmitted over $m$ t-insertions (or $t$ deletions) identical channels. For specific values of $m$ , bounds on the largest list decoder size are provided. These bounds are mainly derived by investigating the largest intersection of $m$ t- insertion (or t-deletion) balls surrounding arbitrary binary words in the space. Furthermore, all pairs of binary words achieving the largest intersection of their t-insertion balls are characterized.

Due to the introduction of 5G, the Polar codes have attracted researchers in the communication field. It is one of a linear block error-correcting codes. This is a kind of Information channel coding techniques with low-complexity in nature wherein the encoding and decoding operation will be performed. Moreover, when it is considered in theoretical prospective, this is considered as one of the capacitive achieving algorithm for a wide range of channel. Polar codes are shown to be instances of concatenated codes. It is proved that the effect of a polar code can be increased by showing the multistage decoding algorithm with log likelihood based Successive List decoding (SCL). As for as Frame error rate is concerned the SCL decoding is not an optimal solution. In this paper the performance of polar codes concatenated with CRC codes is presented and it is proved that it outperforms turbo or LDPC codes. The simulation result shows that with the sufficient amount of training this method can provide a lower frame-error rate for different code lengths.

The Gilbert–Varshamov bound non-constructively establishes the existence of binary codes of distance 1/2−є/2 and rate Ω(є2). In a breakthrough result, Ta-Shma [STOC 2017] constructed the first explicit family of nearly optimal binary codes with distance 1/2−є/2 and rate Ω(є2+α), where α → 0 as є → 0. Moreover, the codes in Ta-Shma’s construction are є-balanced, where the distance between distinct codewords is not only bounded from below by 1/2−є/2, but also from above by 1/2+є/2. Polynomial time decoding algorithms for (a slight modification of) Ta-Shma’s codes appeared in [FOCS 2020], and were based on the Sum-of-Squares (SoS) semidefinite programming hierarchy. The running times for these algorithms were of the form NOα(1) for unique decoding, and NOє,α(1) for the setting of “gentle list decoding”, with large exponents of N even when α is a fixed constant. We derive new algorithms for both these tasks, running in time Oє(N). Our algorithms also apply to the general setting of decoding direct-sum codes. Our algorithms follow from new structural and algorithmic results for collections of k-tuples (ordered hypergraphs) possessing a “structured expansion” property, which we call splittability. This property was previously identified and used in the analysis of SoS-based decoding and constraint satisfaction algorithms, and is also known to be satisfied by Ta-Shma’s code construction. We obtain a new weak regularity decomposition for (possibly sparse) splittable collections W ⊆ [n]k, similar to the regularity decomposition for dense structures by Frieze and Kannan [FOCS 1996]. These decompositions are also computable in near-linear time O(|W |), and form a key component of our algorithmic results.

We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in one pass, and modifies at most a p fraction of the bits of the codeword. (1) Explicit uniquely decodable codes for space bounded channels: Our main result is that for every 0 ≤ p 0 and a uniquely decodable code with rate 1−H(p) for channels with space nδ. This code is explicit (meaning that encoding and decoding are in poly-time). This improves upon previous explicit codes by Guruswami and Smith, and Kopparty, Shaltiel and Silbak (FOCS 2019). Specifically, we obtain the same space and rate as earlier works, even though prior work gave only list-decodable codes (rather than uniquely decodable codes). (2) Complete characterization of the capacity of space bounded channels: Together with a result by Guruswami and Smith showing the impossibility of unique decoding for p ≥ 1/4, our techniques also give a complete characterization of the capacity R(p) of space n1−o(1) channels, specifically: For 0≤pp R(·) is not continuous at p=1/4. Our results are incomparable to recent work on casual channels (these are stronger channels that read the codeword in one pass, but there is no space restriction). The best known codes for casual channels, due to Chen, Jaggi and Langberg (STOC 2015), are shown to exist by the probabilistic method, and no explicit codes are known. A key new ingredient in our construction is a new notion of “evasiveness” of codes, which is concerned with whether a decoding algorithm rejects a word that is obtained when a channel induces few errors to a uniformly chosen (or pseudorandom) string. We use evasiveness (as well as several additional new ideas related to coding theory and pseudorandomness) to identify the “correct” message in the list obtained by previous list-decoding algorithms.

Recently, Long Range (LoRa) has developed itself as one of the dominant technologies for Low Power Wide Area Networks (LP-WAN). LoRa is primarily based on its patented chirp spread spectrum (CSS) modulation. The patented LoRa physical layer supports Forward Error Correction (FEC) codes that are basically derived from simple Hamming codes. Such Hamming codes are restricted to either mere error detection or single error correction. However, burst errors actually exceed the correction capability of standard FEC. Accordingly in this paper, we propose a list decoding technique that helps in resolving the burst errors that could be encountered due to noise as well as interference effects. The proposed list decoding technique depends on widening the search in a list of candidate symbols that are considered based on a pre-defined list size. In order to easily evaluate the performance of the proposed list decoding technique, this paper also introduces an analytical model for the resultant block error rate (BLER) under additive white Gaussian noise (AWGN) channel. The proposed technique is evaluated at different coding rates, different Signal to Noise Ratio (SNR) and different Signal to Interference Ratio (SIR) scenarios. Results demonstrate that the proposed list decoding technique significantly enhances the BLER performance compared to the nominal LoRa case. In case of spreading factor sf =7, coding rate 4/7 and SIR γ = 0.25 dB, the SNR gain of the proposed technique reaches 15 dB compared to the nominal LoRa performance at BLER 10−4. In addition, results verify the accuracy of the derived BLER analytical expression compared to the simulations.

In this work, we propose an interleaved cyclic redundancy check (CRC) code for the partitioned successive cancellation list (PSCL) decoder of polar codes. Since the CRC bits are interleaved into each partition of the PSCL decoder, the CRC bit can be used to eliminate the unreliable codewords. We examine that the performances of the PSCL decoder are influenced by the first-row weight of the parity-check matrix of interleaved CRC code. Therefore, the parity-check matrix of interleaved CRC code must be constructed by minimizing the first-row weight. The simulation results show that the interleaved CRC with a smaller weight can provide better error-correcting performance than the interleaved CRC with a larger weight.

In this paper, we study the decoding error probability of linear codes over the erasure channel under the list decoding. The notion of the $q^\ell $ -incorrigible sets of linear codes is introduced to characterize its decoding error probability under the list decoding or the maximum likelihood decoding. By calculating the $q^\ell $ -incorrigible set distributions, the decoding error probability of a linear code over the erasure channel under the list decoding or the maximum likelihood decoding is expressed by its support weight distributions. For the ensemble of all $[n,k]$ linear codes, the average decoding error probability under the maximum likelihood decoding and the average unsuccessful decoding probability under unambiguous decoding are determined. Furthermore, the error exponent of the average unsuccessful decoding probability under the unambiguous decoding is determined for the ensemble of all $[n,nR]$ linear codes.

Noise can help weak information bearing signal to be detected in nonlinear systems by the use of stochastic perturbation. In this letter, we propose a novel belief propagation list (BPL) decoder that relies on artificial noise. The proposed decoder is constructed by using parallel independent BP decoders. Noise with different powers are added to different BP decoders that runs in parallel, and the output of the decoder that pass the early detection and termination criteria check is considered as the recovered data. Adding small amount of noise enables the decoder to handle un-converged errors. The obtained results show that the performance of noise-aided BPL decoder is much better than the performances of BP, successive cancelation (SC), and successive cancelation list (SCL) decoders, and it is a bit behind of cyclic redundancy check aided SCL in terms of bit-error rate performance.

This paper discusses the possibility of list decoding of wavelet codes and states that wavelet codes over the field $GF(q)$ of an odd characteristic with the length of the code and information words $n=q-1$ and ${n}/{2} $, respectively, as well as over the field of an even characteristic with the length of the code and information words $n=q-1$ and ${n-1}/{2}$, respectively, allow list decoding if among the coefficients of the spectral representation of the polynomials generating them there are $d + 1$ consecutive zeros, $0$ < $d$ < $n/2$ for fields of the odd characteristic and $0$ < $d$ < $(n-3)/2$ for fields of the even characteristic. Also, a description is given of an algorithm that allows one to perform list decoding of wavelet codes subject to the listed conditions. As a demonstration of the operation of this algorithm, step-by-step solutions for model problems of list decoding of noisy wavelet code words over fields of even and odd characteristics are given. In addition, a wavelet version of Golay's quasi-perfect ternary code is constructed. The lengths of its code and information words are 8 and 4, respectively, the code distance is 4, the minimum radius of balls with centers in code words covering the space of words of length 8 is 3.

The problem of list decoding algebraic subspace codes and rank-metric codes is considered. We develop two separate methods, via two different approaches, for list decoding subspace codes and rank-metric codes. These methods provide, for certain code parameters, improved tradeoffs between rate and error-correction capability than that of the Koetter-Kschischang codes, in the domain of subspace codes, and than that of the Gabidulin codes, in the domain of rank-metric codes, and several other extensions thereof. In the first approach, we introduce the notion of root multiplicities for a certain sub-ring of the ring of linearized polynomials. In the list-decoding algorithm, multiple roots are enforced for the interpolation polynomial in order to achieve an improved error-correction radius for an extended family of Koetter–Kschischang subspace codes. The normalized error-correction radius for this approach is \begin{equation*}\tau _{A} = \frac {2(L+1)}{({r+1})} -1- \frac {L(L+1)(L+n)}{r(r+1)}R,\end{equation*} where $L$ is the maximum list size, $n$ is the subspace code dimension, $R$ is the rate of the code, and $r$ is the multiplicity parameter. In the second approach, we construct a folded version of Koetter-Kschischang codes. A linear-algebraic list-decoding algorithm is proposed for these codes that achieves the error-correction radius \begin{equation*}\tau _{B} = s(1-sR),\end{equation*} where $s$ is the folding parameter. As opposed to the first approach, the size of output list in the second approach depends on the underlying field size and is at most $q^{m(s-1)}$ , where $q^{m}$ is the size of the field that message symbols are chosen from. It is also shown that the output list size is 1, with high probability, in a probabilistic setting. We utilize the techniques of the second approach in the domain of rank-metric codes to construct folded Gabidulin codes to enable a linear-algebraic list-decoding algorithm for such codes. Our algorithm makes it possible to recover the message provided that the normalized rank of error is at most $1-R-\epsilon $ , for any $\epsilon > 0$ . Notably, this achieves the Singleton bound on the error-correction radius of a rank-metric code.

We consider a communication scenario in which the channel undergoes two different classes of attacks at the same time: a passive eavesdropper and an active jammer. This scenario is modelled by the concept of arbitrarily varying wiretap channels (AVWCs). In this paper, we derive a full characterization of the list secrecy capacity of the AVWC, showing that the list secrecy capacity is equivalent to the correlated random secrecy capacity if the list size L is greater than the order of symmetrizability of the AVC between the transmitter and the legitimate receiver. Otherwise, it is zero. Our result indicates that for a sufficiently large list size L, list codes can overcome the drawbacks of correlated and uncorrelated codes and provide a stable secrecy capacity for AVWCs. Furthermore, we investigate the effect of relaxing the reliability and secrecy constraints by allowing a non-vanishing error probability and information leakage on the list size L. We found that we can construct a list code whose rate is close to the correlated secrecy capacity using a finite list size L that only depends on the average error probability requested. Finally, we point out that our capacity characterization is an important step in investigating the analytical properties of the capacity function such as: the continuity behavior, Turing computability and super-activation of parallel AVWCs.

This paper introduces the simultaneous partial-inverse problem (SPI) for polynomials and develops its application to decoding interleaved Reed–Solomon codes beyond half the minimum distance. While closely related both to standard key equations and to well-known Pade approximation problems, the SPI problem stands out in several respects. First, the SPI problem has a unique solution (up to a scale factor), which satisfies a natural degree bound. Second, the SPI problem can be transformed (monomialized) into an equivalent SPI problem where all moduli are monomials. Third, the SPI problem can be solved by an efficient algorithm of the Berlekamp–Massey type. Fourth, decoding interleaved Reed–Solomon codes (or subfield-evaluation codes) beyond half the minimum distance can be analyzed in terms of a partial-inverse condition for the error pattern: if that condition is satisfied, then the (true) error locator polynomial is the unique solution of a standard key equation and can be computed in many different ways, including the well-known multi-sequence Berlekamp–Massey algorithm and the SPI algorithm of this paper. Two of the best performance bounds from the literature (the Schmidt–Sidorenko–Bossert bound and the Roth–Vontobel bound) are generalized to hold for the partial-inverse condition and thus to apply to several different decoding algorithms.

We prove that a known general approach to improve Shamir’s celebrated secret sharing scheme; i.e., adding an information-theoretic authentication tag to the secret, can make it robust for n parties against any collusion of size $$\delta n$$ , for any constant $$\delta \in (0, 1/2)$$ . Shamir’s original scheme is robust for all $$\delta \in (0,1/3)$$ . Beyond that, we employ the best known list decoding algorithms for Reed-Solomon codes and show that, with high probability, only the correct secret maintains the correct information-theoretic tag if an algebraic manipulation detection (AMD) code is used to tag secrets. This result holds in the so-called “non-rushing” model in which the n shares are submitted simultaneously for reconstruction. We thus obtain a fully explicit and robust secret sharing scheme in this model that is essentially optimal in all parameters including the share size which is $$k(1+o(1)) + O(\kappa )$$ , where k is the secret length and $$\kappa $$ is the security parameter. Like Shamir’s scheme, in this modified scheme any set of more than $$\delta n$$ honest parties can efficiently recover the secret. Using algebraic geometry codes instead of Reed-Solomon codes, the share length can be decreased to a constant (only depending on $$\delta $$ ) while the number of shares n can grow independently. In this case, when n is large enough, the scheme satisfies the “threshold” requirement in an approximate sense; i.e., any set of $$\delta n(1+\rho )$$ honest parties, for arbitrarily small $$\rho > 0$$ , can efficiently reconstruct the secret. From a practical perspective, the main importance of our result is in showing that existing systems employing Shamir-type secret sharing schemes can be made much more robust than previously thought with minimal change, essentially only involving the addition of a short and simple checksum to the original data.

Guruswami and Resch proved that a random F q -linear rank-metric code is list decodable with list decoding radius attaining the Gilbert–Varshamov bound [8] . Furthermore, in Hamming metric, random linear self-orthogonal codes can be list decoded up to the Gilbert–Varshamov bound with polynomial list size [11] . Motivated by these two results and the potential applications of self-orthogonal rank-metric codes in network coding and cryptography [20] , [18] and [5] , we focus on investigating their list decodability. In this paper, we prove that with high probability, a random F q -linear self-orthogonal rank-metric code over F q n × m can be list decoded up to the Gilbert–Varshamov bound with polynomial list size. In addition, we show that an F q m -linear self-orthogonal rank-metric code of rate up to the Gilbert–Varshamov bound with exponential list size.

Polar code is adapted as the channel coding scheme for control channel in 5G NR. The basic algorithm of polar code is the successive cancelation (SC) decoding but its performance is not good enough and decoding latency is relatively high. So the simplified successive cancelation list(SSCL) decoding is generally used. When the SSCL is operated, path metric calculator generates children candidates and the number of children candidates influenced on the H/W complexity. The reliability of children candidates is affected by that of their parent candidates. The number of children candidates is adaptively selected according to the reliability of their parent candidate and the total number of children candidates could be reduced. Our proposed algorithm reduces H/W complexity of polar decoder while preserving decoding performance.

We propose a new family of polar coding which realizes high coding gain, low complexity, and high throughput by introducing a protograph-based design. The proposed technique called as quasi-cyclic (QC) polar codes can be highly parallelized without sacrificing decoding complexity. We analyze short cycles in the protograph polar codes and develop a design method to increase the girth. Our approach can resolve the long-standing unsolved problem that belief propagation (BP) decoding does not work well for polar codes due to the inherently short cycles. We demonstrate that a high lifting factor of QC polar codes can improve the performance and that QC polar codes with BP decoding can outperform conventional polar codes with state-of-the-art list decoding. Moreover, we show that a greedy pruning method can improve the performance-complexity trade-off., 6 pages, 8 figures, under review in ISIT

In this paper we deal with polar code automorphisms that are beneficial under low-latency automorphism ensemble (AE) decoding, and we propose polar code designs that have such automorphisms. Successive-cancellation (SC) decoding and thus SC-based AE decoding are invariant with respect to the only known polar code automorphisms, namely those of the lower-triangular affine (LTA) group. To overcome this problem, we provide methods to determine whether a given polar code has non-LTA automorphisms and to identify such automorphisms. Building on this, we design specific polar codes that admit automorphisms in the upper-diagonal linear (UTL) group, and thus render SC-based AE decoding effective. Demonstrated by examples, these new polar codes under AE decoding outperform conventional polar codes under SC list decoding in terms of error rate, while keeping the latency comparable to SC decoding. Moreover, state-of-the-art BP-based permutation decoding for polar codes is beaten by BP-based AE thanks to this design., 6 pages, 4 figures, final version of conference paper accepted to IEEE ITW 2021

In this paper we address the problem of list decoding of linear codes over an integer residue ring Zq, where qis a power of a prime p. The proposed procedure exploits a particular matrix representation of the linear code over Zpr, called the standard form, and the p-adic expansion of the to-be-decoded vector. In particular, we focus on the erasure channel in which the location of the errors is known. This problem then boils down to solving a system of linear equations with coefficients in Zpr. From the parity-check matrix representations of the code we recursively select certain equations that a codeword must satisfy and have coefficients only in the field pr−1Zpr. This yields a step by step procedure obtaining a list of the closest codewords to a given received vector with some of its coordinates erased. We show that such an algorithm actually computes all possible erased coordinates, that is, the provided list is minimal. This work of the second and forth authors is supported by the Center for Research and Development in Mathematics and Applications (CIDMA) through the Portuguese Foundation for Science and Technology (FCT-Fundação para a Ciência e a Tecnologia), references UIDB/04106/2020 and UIDP/04106/2020. The first author partially supported by Ministerio de Ciencia e Innovación via the grant with ref. PID2019-108668GB-I00. The third author is supported by the Swiss Confederation through the Swiss Government Excellence Scholarship no: 2019.0413 and by the Swiss National Science Foundation grant n. 188430.

Linearized Reed-Solomon (LRS) codes are sum-rank metric codes that fulfill the Singleton bound with equality. In the two extreme cases of the sum-rank metric, they coincide with Reed-Solomon codes (Hamming metric) and Gabidulin codes (rank metric). List decoding in these extreme cases is well-studied, and the two code classes behave very differently in terms of list size, but nothing is known for the general case. In this paper, we derive a lower bound on the list size for LRS codes, which is, for a large class of LRS codes, exponential directly above the Johnson radius. Furthermore, we show that some families of linearized Reed-Solomon codes with constant numbers of blocks cannot be list decoded beyond the unique decoding radius.

In successive cancellation list (SCL) decoding, the tree pruning operation retains the $L$ best paths with respect to a metric at every decoding step. However, the correct path might be among the $L$ worst paths due to imposed penalties. In this case, the correct path is pruned and the decoding process fails. Shifted-pruning (SP) scheme can recover the correct path by additional decoding attempts when decoding fails, in which the pruning window is shifted by $L$ over the bits with high likelihood of the elimination of the correct path, one at a time. In this work, we generalize the scheme by more freedom in shifting the pruning window, aiming to improve the error correction performance in the constrained number of decoding attempts. We also propose a metric for prioritizing the shifting positions.

The quantization of intermediate log-likelihood ratios (LLRs) is a concern in the hardware implementation of the LLR-based tree search algorithms such as successive cancellation list (SCL) and sequential (SCS) decoding for polar codes (particularly for large block-lengths), where comparability of tree paths requires precision for path metrics that the uniform quantization demands a large memory space due to the wide dynamic range. As the consequence of low accuracy in uniform quantization (with large step size) for small LLR values, the error correction performance degrades. In this work, we present a logarithmic non-uniform quantization (based on lookup table, logarithm functions, and piecewise linear functions) which can provide an error correction performance close to floating-point precision for a wide range of code-lengths.

This paper introduces algorithms for the successive-cancellation decoding and the successive-cancellation list decoding of binary polar source/channel codes. By using the symmetric parametrization of conditional probability, we reduce both space and time complexity compared to the original algorithm introduced by Tal and Vardy., 14 pages, this is the extended version of the paper submitted to 2021 IEEE International Symposium on Information Theory

Recently, codes in the sum-rank metric attracted attention due to several applications in e.g. multishot network coding, distributed storage and quantum-resistant cryptography. The sum-rank analogs of Reed-Solomon and Gabidulin codes are linearized Reed-Solomon codes. We show how to construct $h$-folded linearized Reed-Solomon (FLRS) codes and derive an interpolation-based decoding scheme that is capable of correcting sum-rank errors beyond the unique decoding radius. The presented decoder can be used for either list or probabilistic unique decoding and requires at most $\mathcal{O}(sn^2)$ operations in $\mathbb{F}_{q^m}$, where $s \leq h$ is an interpolation parameter and $n$ denotes the length of the unfolded code. We derive a heuristic upper bound on the failure probability of the probabilistic unique decoder and verify the results via Monte Carlo simulations., Comment: 10 pages, 1 figure, presented at WCC 2022

We propose the new rank-metric code-based cryptosystem LIGA which is based on the hardness of list decoding and interleaved decoding of Gabidulin codes. LIGA is an improved variant of the Faure-Loidreau (FL) system, which was broken in a structural attack by Gaborit, Otmani, and Tal\'e Kalachi (GOT, 2018). We keep the FL encryption and decryption algorithms, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleaved Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail---hence LIGA resists the GOT attack. We also prove that the public-key encryption version of LIGA is IND-CPA secure in the standard model and the KEM version is IND-CCA2 secure in the random oracle model, both under hardness assumptions of formally defined problems related to list decoding and interleaved decoding of Gabidulin codes. We propose and analyze various exponential-time attacks on these problems, calculate their work factors, and compare the resulting parameters to NIST proposals. The strengths of LIGA are short ciphertext sizes and (relatively) small key sizes. Further, LIGA guarantees correct decryption and has no decryption failure rate. It is not based on hiding the structure of a code. Since there are efficient and constant-time algorithms for encoding and decoding Gabidulin codes, timing attacks on the encryption and decryption algorithms can be easily prevented., Comment: Extended version of arXiv:1801.03688

Wachter-Zeh (IEEE Trans Inf Theory 59(11):7268–7276, 2013), and later together with Raviv (IEEE Trans Inf Theory 62(4):1605–1615, 2016), proved that Gabidulin codes cannot be efficiently list decoded for any radius τ, providing that τ is large enough. Also, they proved that there are infinitely many choices of the parameters for which Gabidulin codes cannot be efficiently list decoded at all. Subsequently, in Trombetti and Zullo (IEEE Trans Inf Theory 66(9):5379–5386, 2020) these results have been extended to the family of generalized Gabidulin codes and to further family of MRD-codes. In this paper, we provide bounds on the list size of rank-metric codes containing generalized Gabidulin codes in order to determine whether or not a polynomial-time list decoding algorithm exists. We detect several families of rank-metric codes containing a generalized Gabidulin code as subcode which cannot be efficiently list decoded for any radius large enough and families of rank-metric codes which cannot be efficiently list decoded. These results suggest that rank-metric codes which are Fqm-linear or that contains a (power of) generalized Gabidulin code cannot be efficiently list decoded for large values of the radius.

Permutation decoding is a technique which involves finding a subset S, called PD-set, of the permutation automorphism group of a code C. Constructions of small PD-sets for partial decoding for two families of Z 4 -linear codes (Hadamard and Kerdock) are given. Moreover, different decoding methods for Z4-linear codes are compared by showing their performance applied to these two families.

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes. Info-communications Media Development Authority (IMDA) National Research Foundation (NRF) Submitted/Accepted version The work of Shu Liu was supported in part by the National Natural Science Foundation of China under Grant 11901077, Grant 2019YFB1803102, and Grant 2020YFB1806805; in part by the National Key Research and Development Program of China under Contract IFN2020203; and in part by the Fundamental Research Funds for the Central Universities of China under Grant ZYGX2018KYQD216. The work of Ivan Tjuawinata was supported by the National Research Foundation, Singapore, under its Strategic Capability Research Centres Funding Initiative. The work of Chaoping Xing was supported in part by the National Natural Science Foundation of China under Grant 12031011 and in part by the National Key Research and Development Project under Grant 2020YFA0712300.