Most codes with an algebraic decoding algorithm are derived from Reed-Solomon codes. They are obtained by taking equivalent codes, for example, generalized Reed-Solomon codes, or by using the so-called subfield subcode method, which leads to alternant codes over the underlying prime field, or over some intermediate subfield. The main advantage of these constructions is to preserve both the minimum distance and the decoding algorithm of the underlying Reed-Solomon code. In this paper, we explore in detail the subspace subcodes construction. This kind of codes was already studied in the particular case of cyclic Reed-Solomon codes. We extend this approach to any linear code over the extension of a finite field. We are interested in additive codes who are deeply connected to subfield subcodes. We characterize the duals of subspace subcodes. We introduce the notion of generalized subspace subcodes. We apply our results to generalized Reed-Solomon codes which leads to codes with interesting parameters, especially over a large alphabet. To conclude this paper, we discuss the security of the use of generalized subspace subcodes of Reed-Solomon codes in a cryptographic context.

While Generalized Feistel Networks (GFNs) have been widely studied in the literature as a building block of a block cipher, we recall in this paper the results of [1] where a unified vision to easily represent them through a matrix representation is proposed. We also introduce a new class of such schemes called Extended Generalized Feistel Networks well suited for cryptographic applications. We instantiate this particular construction into a lightweight block cipher called Lilliput analyzing its security and its hardware performances.

Linear finite state machines (LFSMs) are particular primitives widely used in information theory, coding theory and cryptography. Among those linear automata, a particular case of study is linear feedback shift registers (LFSRs) used in many cryptographic applications such as design of stream ciphers or pseudo-random generation. LFSRs could be seen as particular LFSMs without inputs. In this paper, we first recall the description of LFSMs using traditional matrices representation. Then, we introduce a new matrices representation with polynomial fractional coefficients. This new representation leads to sparse representations and implementations. As direct applications, we focus our work on the Windmill generators case, used for example in the E0 stream cipher and on other general applications that use this new representation. In a second part, a new design criterion called diffusion delay for LFSRs is introduced and well compared with existing related notions. This criterion represents the diffusion capacity of an LFSR. Thus, using the matrices representation, we present a new algorithm to randomly pick LFSRs with good properties (including the new one) and sparse descriptions dedicated to hardware and software designs. We present some examples of LFSRs generated using our algorithm to show the relevance of our approach.

This paper corrects some errors on a previous paper concerning the synthesis of Feedback with Carry Shift Registers using the Euclidean Algorithm.

This article describes new theoretical results concerning the general behavior of a feedback with carry shift register (FCSR) automaton. They help to better understand how the initial parameters must be chosen to use this automaton as a basic block of a filtered stream cipher. These results especially concern the structure of the transition graph of an FCSR automaton and the number of iterations of the FCSR transition function required to reach the main part of the graph. A potential linear weakness and a easy way to prevent the corresponding attack are also given.

We investigate some open problems on almost perfect nonlinear (APN) functions over a finite field of characteristic$2$. We provide new characterizations of APN functions and of APN permutations by means of their component functions. We generalize some results of Nyberg (1994) and strengthen a conjecture on the upper bound of nonlinearity of APN functions. We also focus on the case of quadratic functions. We contribute to the current works on APN quadratic functions by proving that a large class of quadratic functions cannot be APN.

We investigate some open problems on almost perfect nonlinear (APN) functions over a finite field of characteristic 2. We provide a new characterization of APN mappings and of APN permutations by means of their component functions. We also focus on the case of quadratic functions. Most notably, we prove that a class of quadratic functions cannot be APN. Our result strengthens the conjecture that all quadratic APN functions are power functions, up to equivalence

Feedback with carry shift registers (FCSR) was introduced by Goresky and Klapper in 1993. It is similar to the classical linear feedback shift registers (LFSR) used in many pseudorandom generators. The main difference is that the elementary additions are not additions modulo 2 but with propagation of carries. The main problem for the use of an FCSR automaton is the fact that the generated sequences are predictable. In order to remove this weakness of FCSR-based generators, we propose filtering the state of the FCSR with a linear function. This method is efficient since the FCSR structure is not related to a linear property. This paper presents an extensive study of FCSR automata, a security analysis of our generator (concerning linear and 2-adic cryptanalysis, algebraic attack, correlation attack, etc.), and a practical example of parameters in order to design this generator. An important point concerning this generator is the fact that it is simple and efficient, both in hardware and software implementation.

Feedback with carry shift registers (FCSR) were introduced by Klapper and Goresky (1994). They are very similar to classical linear feedback shift registers (LFSR) used in many pseudorandom generators. The main difference is the fact that the elementary additions are not additions modulo 2 but with propagation of carries. The mathematical models for LFSR are equivalently linear recurring sequences over GF(2) or rational series in the set GF(2)[[x]]. For FCSR, the "good" model is the one of rational 2-adic numbers. It is well known, that the series generated by a LFSR can be synthesized by either the Berlekamp-Massey algorithm for binary linear recurring sequences or the extended Euclidean algorithm in the set GF(2)[x] of binary polynomials. Klapper and Goresky (1997) give an algorithm for the FCSR synthesis. This algorithm is similar to those of Berlekamp-Massey and is based on De Weger and Mahler's rational approximation theory. In this correspondence, we prove that it is possible to synthesize the FCSR with the extended Euclidean algorithm in the ring /spl Zopf/ of integers. This algorithm is clearly equivalent to the previous one, however, it is simpler to understand, to implement, and to prove. Our algorithm is still valid in the case of g-adic integers where g is a positive integer. We also give a near-adaptative version of this algorithm.

The rank distance was introduced by E.M. Gabidulin (see Probl. Pered. Inform., vol.21, p.1-12, 1985). He determined an upper bound for the minimum rank distance of a code. Moreover, he constructed a class of codes which meet this bound: the so-called Gabidulin codes. We first characterize the linear and semilinear isometries for the rank distance. Then we determine the isometry group and the permutation group of Gabidulin codes of any length. We give a characterization of equivalent Gabidulin codes. Finally, we prove that the number of equivalence classes of Gabidulin codes is exactly the number of equivalence classes of vector spaces of dimension n contained in GF(p/sup m/) under some particular relations.

We characterize the full automorphism groups of homogeneous and projective Reed-Muller (HRM and PRM) codes. These groups are respectively related to general and projective linear groups.

We explain how to construct Goppa codes, expurgated or extruded Goppa codes invariant under a permutation induced by an element of the projective semilinear group P/spl Gamma/L(2, GF (p/sup m/)). This follows from the knowledge of semilinear automorphism groups of generalized Reed-Solomon codes. We obtain very good codes: some of them have parameters which reach the values given in the Brouwer table (see Handbook of Coding Theory, V.S. Pless and W.C. Huffman, Eds. Amsterdam, The Netherlands: Elsevier, vol.1, ch.4., 1998).. Moreover, it is easy to construct quasi-cyclic Goppa or related codes. Often, we obtain parameters unknown for quasi-cyclic codes.

We give a condition for a "classical" Goppa (1970) code to have a cyclic extension. This condition follows from the properties of the semilinear automorphism group of the corresponding generalized Reed-Solomon codes. Using this condition, we can construct not only all the known Goppa codes with a cyclic extension, but also new families.

The extended cyclic codes of length p/sup m/, p is a prime, which are invariant under the affine-group acting on F/sub pm/, are called affine-invariant codes. Following results of Berger (1996, 1994), we present the formal expression of the permutation group of these codes. Afterwards we give several tools in order to determine effectively the group of a given code or of some infinite class of codes. We next prove, by studying some examples, that our tools are efficient. In the end, we give our main application, the permutation group of primitive BCH codes defined on any prime field.

Using the description of primitive cyclic codes in a modular algebra, the author characterizes the permutations of the support of a cyclic code which leaves the code globally invariant. Applying this result to the binary double-error-correcting BCH codes, the author proves that the automorphism group of such a code (of length 2/sup m/-1,m>4) is the semi-linear group of GF(2/sup m/) over GF(2/sup m/), and, in the special case m=4, the semi-linear group of GP(16) over GF(4).>