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.

To design robust symmetric encryption schemes, we need to use Boolean functions with suitable properties. Among the security criteria these functions need to fulfill, we can mention algebraic immunity. A lot of papers study how to construct suitable functions, but some of them assume the validity of Tu-Deng's combinatorial conjecture [2] to estimate the algebraic immunity of the Boolean functions they design. In this paper we prove two new results about this conjecture and point out a new family of integers that satisfy it.

In this paper, we propose two new generic attacks on the rank syndrome decoding (RSD) problem. Let C be a random [n, k] rank code over GF(qm) and let y = x + e be a received word, such that x ∈ C and rank(e) = r. The first attack, the support attack, is combinatorial and permits to recover an error e of rank weight r in min(O((n - k)3m3qr1(km/n)J, O((n - k)3m3q⌈(r-1)I(((k+1)m)/n)J))⌉operations on GF(q). This new attack improves the exponent for the best generic attack for the RSD problem in the case n > m, by introducing the ratio m/n in the exponential coefficient of the previously best known attacks. The second attack, the annulator polynomial attack, is an algebraic attack based on the theory of q-polynomials introduced by Ore. We propose a new algebraic setting for the RSD problem that permits to consider equations and unknowns in the extension field GF(qm) rather than in GF(q) as it is usually the case. We consider two approaches to solve the problem in this new setting. The linearization technique shows that if n ≥ (k + 1) (r + 1) - 1 the RSD problem can be solved in polynomial time. More generally, we prove that if [(((r + 1)(k + 1)- (n + 1))/r)1 ≤ k, the RSD problem can be solved with an average complexity of O(r3k3qrΓ(((r+1)(k+1)-(n+1))/r)l)⌉operations in the base field GF(q). We also consider solving with Gröbner bases for which we discuss theoretical complexity, we also consider hybrid solving with Gröbner bases on practical parameters. As an example of application, we use our new attacks on all recent cryptosystems parameters, which repair the GPT cryptosystem, we break all examples of published proposed parameters, and some parameters are broken in less than 1 s in certain cases.

In this paper we propose a new one-time signature algorithm based on coding theory. The algorithm uses properties of automorphism group of certain codes to dramatically decrease the size of the public key of the scheme. By considering the action of cyclic shifts or the action of the group PSL2(p) we obtain public keys of less than 18 kilobits for a signature of 7 kilobits. Overall the scheme we propose is perfectly fitted to be used with Merkle tree and proposes a very good trade-off between size of key and size of signatures compared to other code-based signature schemes, with multi-time signatures of size 28kb.

In this paper we present a new 5-pass identification scheme with asymptotic cheating probability ½ based on the syndrome decoding problem. Our protocol is related to the Stern identification scheme but has a reduced communication cost compared to previous code-based zero-knowledge schemes, moreover our scheme permits to obtain a very low size of public key and secret key. The contribution of this paper is twofold, first we propose a variation on the Stern authentication scheme which permits to decrease asymptotically the cheating probability to 1/2 rather than 2/3 (and very close to 1/2 in practice) but with less communication. Our solution is based on deriving new challenges from the secret key through cyclic shifts of the initial public key syndrome; a new proof of soundness for this case is given Secondly we propose a new way to deal with hashed commitments in zero-knowledge schemes based on Stern's scheme, so that in terms of communication, on the average, only one hash value is sent rather than two or three. Overall our new scheme has the good features of having a zero-knowledge security proof based on well known hard problem of coding theory, a small size of secret and public key (a few hundred bits), a small calculation complexity, for an overall communication cost of 19kb for authentication (for a 216security) and a signature of size of 93kb (11.5kB) (for security 280), an improvement of 40% compared to previous schemes based on coding theory.