The ongoing NIST standardization process has shown that Proof of Knowledge (PoK) based signatures have become an important type of possible post-quantum signatures. Regarding code-based cryptography, the main original approach for PoK based signatures is the Stern protocol which allows to prove the knowledge of a small weight vector solving a given instance of the Syndrome Decoding (SD) problem over ${\mathbb{F}_2}$. It features a soundness error equal to 2/3. This protocol was improved a few years later by Véron who proposed a variation of the scheme based on the General Syndrome Decoding (GSD) problem which leads to better results in terms of communication. A few years later, the AGS protocol introduced a variation of the Véron protocol based on Quasi-Cyclic (QC) matrices. The AGS protocol permits to obtain an asymptotic soundness error of 1/2 and an improvement in terms of communications.In the present paper, we introduce the Quasi-Cyclic Stern PoK which constitutes an adaptation of the AGS scheme in a SD context, as well as several new optimizations for code-based PoK. Our main optimization on the size of the signature cannot be applied to GSD based protocols such as AGS and therefore motivated the design of our new protocol. In addition, we also provide a special soundness proof that is compatible with the use of the Fiat-Shamir transform for 5-round protocols. This approach is valid for our protocol but also for the AGS protocol which was lacking such a proof. We compare our results with existing signatures including the recent code-based signatures based on PoK leveraging the MPC in the head paradigm. In practice, our new protocol is as fast as AGS while reducing its associated signature length by 20%. As a consequence, it constitutes an interesting trade-off between signature length and execution time for the design of a code-based signature relying only on the difficulty of the SD problem.

In this paper we give the first blind signature protocol for code-based cryptography. Our approach is different from the classical original RSA based blind signature scheme, it is done in the spirit of the Fischlin approach [9] which is based on proofs of knowledge. To achieve our goal we consider a new tool for zero-knowledge (ZK) proofs, the Concatenated Stern ZK protocol, which permits to obtain an authentication protocol for concatenated matrices. A signature is then obtained from the usual Fiat-Shamir heuristic. We describe our blind signature protocol for cryptography based on Hamming metric and show how it can be extended to rank based cryptography. The security of our blind protocol is based on the security of a trapdoor function for the syndrome decoding problem: the CFS signature scheme for Hamming distance and on the more recent RankSign protocol for rank metric. We give proofs in the random oracle model (ROM) for our blind signature scheme, which rely on the Syndrome Decoding problem. The parameters we obtain for our protocol are practical for rank metric (200kBytes) for the signature length and 15kBytes for public key size) and a little less practical for Hamming distance.

QC-MDPC-McEliece is a recent variant of the McEliece encryption scheme which enjoys relatively small key sizes as well as a security reduction to hard problems of coding theory. Furthermore, it remains secure against a quantum adversary and is very well suited to low cost implementations on embedded devices. Decoding MDPC codes is achieved with the (iterative) bit flipping algorithm, as for LDPC codes. Variable time decoders might leak some information on the code structure (that is on the sparse parity check equations) and must be avoided. A constant time decoder is easy to emulate, but its running time depends on the worst case rather than on the average case. So far implementations were focused on minimizing the average cost. We show that the tuning of the algorithm is not the same to reduce the maximal number of iterations as for reducing the average cost. This provides some indications on how to engineer the QC-MDPC-McEliece scheme to resist a timing side-channel attack.

We give here an efficient algorithm for recovering the permutation of an unknown turbo-code when several noisy codewords are given. The algorithm presented here uses the same information as some other algorithms given previously for this problem but in an optimal fashion. This paper also clarifies the link between this problem and the BCJR decoding algorithm.

In this work, we propose two McEliece variants: one from Moderate Density Parity-Check (MDPC) codes and another from quasi-cyclic MDPC codes. MDPC codes are LDPC codes of higher density (and worse error-correction capability) than what is usually adopted for telecommunication applications. However, in cryptography we are not necessarily interested in correcting many errors, but only a number which ensures an adequate security level. By this approach, we reduce under certain hypotheses the security of the scheme to the well studied decoding problem. Furthermore, the quasi-cyclic variant provides extremely compact-keys (for 80-bits of security, public-keys have only 4801 bits).

Code-based cryptography allows the construction of primitives with various functionalities. Those designs are in general secure and possess no undesirable features that cannot be corrected by a proper choice of parameters and a careful implementation (i.e. semantically secure conversion). Their security reduction is, for the systems who do not require a trapdoor decoder, as good as possible as we have an exact reduction to the syndrome decoding problem, the hardness of which conveys an extreme confidence. For public-key systems (encryption, signature) there exists no really threatening (non exponential) attacks but the security reduction involves other problems (indistinguishability of families of codes) which offer some confidence but which also need to be considered with more hindsight, in particular for variants with reduced key size (typically using quasi-cyclic or quasi-dyadic codes). The security reductions of code-based cryptosystems rely on well identified problems and in that sense are well founded. We hope that the problems we expose here will attract some attention and eventually help to produce even better reductions.

We propose in this paper an algorithm to recover the interleaver of an unknown turbo encoder by observing noisy codewords. Our technique is practical but is limited to rate 1/3 turbo-code using two unpunctured rate 1/2 systematic convolutional encoders.

In this work, we present an algorithm to recover the convolutional code which has produced a observed noisy binary sequence. It makes use of previously unpublished structural properties of convolutional codes that we present here. This allow us to improve on previously known techniques. The algorithm was fully implemented and runs in reasonable time for practical parameters values.

In this note we reconsider the code-based pseudorandom generator proposed by Fischer and Stern. This generator is proven as secure as the syndrome decoding problem but has two main drawbacks: it is slow (3000 bits/s) and a large size of memory is needed (88 kiloBytes). We propose a variation on the scheme which avoid them: the use of regular words speeds the system up and the use of quasi-cyclic codes allows a decrease of the memory requirements. We eventually obtain a generator as fast as AES in counter mode using only about 8000 bits of memory. We also give a more precise security reduction.

We present here a new algorithm for encoding binary information into words of prescribed length and weight. Existing solutions use a combinatorial approach and, though they are optimal in terms of information theory, they have a rather high algorithmic complexity as they require the computation of binomial coefficients. The solution we propose has linear complexity. The price to pay is variable length encoding and a small loss of (information theoretic) efficiency

Using the hull dimension spectra of linear codes, we show that linear codes with complementary dual meet the asymptotic Gilbert-Varshamov bound.

We show that it is possible to know whether the secret Goppa code of an instance of the McEliece public-key cryptosystem was chosen with a binary generator polynomial. Furthermore, whenever such a weak key is used, we present an attack which can be completed, for codes of length 1024 and dimension 524, with a large, but feasible amount of computation.

Two linear codes are permutation-equivalent if they are equal up to a fixed permutation on the codeword coordinates. We present here an algorithm able to compute this permutation. It operates by determining a set of properties invariant by permutation, one for each coordinate, called a signature. If this signature is fully discriminant-i.e., different for all coordinates-the support of the code splits into singletons, and the same signature computed for any permutation-equivalent code will allow the reconstruction of the permutation. A procedure is described to obtain a fully discriminant signature for most linear codes. The total complexity of the support splitting algorithm is polynomial in the length of the code and exponential in the dimension of its hull, i.e., the intersection of the code with its dual.

The hull [Assmus, Jr. and Key, Discrete Math., 83 (1990), pp. 161--187], [Assmus, Jr. and Key, Designs and Their Codes, Cambridge University Press, 1992, p. 43] of a linear code is defined to be its intersection with its dual. We give here the number of distinct q-ary linear codes which have a hull of given dimension. We will prove that, asymptotically, the proportion of q-ary codes whose hull has dimension l is a positive constant that depends only on l and q and consequently that the average dimension of the hull is asymptotically a positive constant depending only on q.

Using a characterization of the idempotents of a narrow-sense primitive binary BCH code, the authors are able to give classes of such codes whose minimum distance does not exceed the BCH bound. Their results are compiled in a table.>

Primitive binary cyclic codes of length n=2/sup m/ are considered. A BCH code with designed distance delta is denoted B(n, delta ). A BCH code is always a narrow-sense BCH code. A codeword is identified with its locator polynomial, whose coefficients are the symmetric functions of the locators. The definition of the code by its zeros-set involves some properties for the power sums of the locators. Moreover, the symmetric functions and the power sums of the locators are related to Newton's identities. An algebraic point of view is presented in order to prove or disprove the existence of words of a given weight in a code. The principal result is the true minimum distance of some BCH codes of length 255 and 511. which were not known. The minimum weight codewords of the codes B(n2/sup h/-1) are studied. It is proved that the set of the minimum weight codewords of the BCH code B(n,2/sup m-2/-1) equals the set of the minimum weight codewords of the punctured Reed-Muller code of length n and order 2, for any m.>