Abstract Nowadays, equivalence problems are widely used in cryptography, most notably to establish cryptosystems such as digital signatures, with MEDS, LESS, PERK as the most recent ones. However, in the context of matrix codes, only the code equivalence problem has been studied, while the subcode equivalence is well-defined in the Hamming metric. In this work, we introduce two new problems: the Matrix Subcode Equivalence Problem and the Inhomogeneous Matrix Subcode Problem, to which we apply the Multi-Party-Computation-in-the-Head (MPCitH) paradigm to build a signature scheme. These new problems, closely related to the Matrix Code Equivalence problem, ask to find an isometry given a code C and a subcode D . Furthermore, we prove that the Matrix Subcode Equivalence Problem reduces to the Hamming Subcode Equivalence problem, which is known to be NP-Complete, thus introducing the matrix code version of the Permuted Kernel Problem. We also adapt the combinatorial and algebraic algorithms for the Matrix Code Equivalence problem to the subcode case, and we analyze their complexities. We find with this analysis that the algorithms perform much worse than in the code equivalence case, which is the same as what happens in the Hamming metric. Finally, our analysis of the attacks allows us to take parameters much smaller than in the Matrix Code Equivalence case. Coupled with the effectiveness of Threshold-Computation-in-the-Head or VOLE-in-the-Head , we obtain a signature size of $$\approx $$ ≈ 4800 Bytes, with a public key of $$\approx $$ ≈ 275 Bytes. We thus obtain a reasonable signature size, which brings diversity in the landscape of post-quantum signature schemes, by relying on a new hard problem. In particular, this new signature scheme performs better than SPHINCS+, with a smaller size of public key + signature. Our signature compares also well with other signature schemes: compared to MEDS, the signature is smaller, and we reduced the size of the sum of signature and public key by a factor close to 5. We also obtain a signature size that is almost half the size of the CROSS signature scheme.

We present a modified version of the Bravyi-Terhal bound that applies to quantum codes defined by local parity-check constraints on aD-dimensional lattice quotient. Specifically, we consider a quotient ZD/Λ of ZDof cardinality ℓ, where Λ is someD-dimensional sublattice of ZD: we suppose that every vertex of this quotient indexesmqubits of a stabilizer codeC, which therefore has lengthn=mℓ. We prove that if all stabilizer generators act on qubits whose indices lie within a ball of radius ρ, then the minimum distancedof the code satisfiesd≤m√ γD( √D+ 4ρ)ℓD−1/D, where γDis theD-dimensional Hermite constant. We then apply this bound to derive an upper bound on the minimum distance of Abelian Two-Block Group Algebra (2BGA) codes whose parity-check matrices have the form [A|B] with each submatrix representing an element of a group algebra over a finite abelian group.

Generalized Bicycle (GB) codes offer a compelling alternative to surface codes for quantum error correction. This paper focuses on (2,2)-Generalized Bicycle codes, constructed from pairs of binary circulant matrices with two non-zero elements per row. Leveraging a lower bound on their minimum distance, we construct three novel infinite families of optimal (2,2)-GB codes with parameters [[2n2, 2,n]], [[4r2, 2, 2r]], and [[(2t+1)2+1, 2, 2t+1]]. These families match the performance of Kitaev’s toric code and the best 2D weight-4 surface codes, reaching known theoretical limits. In particular, the second family breaks a long-held belief by providing optimal even-distance GB codes, previously deemed impossible. All are CSS codes derived from Cayley graphs. Recognizing that standard equivalence relations do not preserve their CSS structure, we introduce a CSS-preserving equivalence relation for rigorous comparison of Cayley graph-based CSS codes. Under this framework, the first two families are inequivalent to all previously known optimal weight-4 2D surface codes, while the third family is equivalent to the best-known odd-distance 2D surface code. Finally, we classify all extremal, non-equivalent (2, 2)-GB codes with length below 200 and present a comparison table with existing notable 2D weight-4 surface codes.

In this paper, we revisit the Rank Quasi-Cyclic (RQC) (Melchor et al., IEEE IT, 2018) encryption scheme by proposing three possible variations for its design. Our first improvement relies on the introduction of Augmented Gabidulin codes, a new family of decodable codes exploiting the concept of support erasure for the rank metric. Following the work of Melchor et al. (PQCrypto, 2022), our second improvement uses multiple syndromes to increase the weight of the error to be decoded. As pioneered in Melchor et al. (NIST PQC, 2020), our third variation considers non-homogeneous error weights in order to decrease the parameters. These improvements can be combined together to design schemes offering various trade-offs in term of security and size. Our Multi-UR-AG (multiple syndromes, unstructured, augmented Gabidulin) scheme achieves a size of 11kB (public key + ciphertext) for 128 bits of security while featuring a conservative design as it relies on pure random instances without any ideal structure. Besides, our NH- Multi-RQC-AG (non-homogeneous error, multiple syndromes, ideal structure, augmented Gabidulin) achieves a size of 2.7 kB for 128 bits of security, namely a 50 % improvement with respect to classical RQC. Our second and third variations respectively rely on the security of the$\textsf {RSL} $and$\textsf {NHRSD} $problems (or$\textsf {NHRSL} $when considered together). In this paper, we also provide new security analysis and attacks for these problems. While these results are important for our new schemes, they are of independent interest as well. Our security analysis for the$\textsf {RSL} $problem provides an improvement on the recent algebraic attacks for some instances. In addition, we show that the$\textsf {RSL} $problem can be solved in polynomial time when$N \geq (k+1) r\frac {m}{m-r}$, this improves the best known combinatorial attack (Gaborit et al., Crypto, 2017). We also propose the first combinatorial attack against the$\textsf {NHRSD} $problem along with a precise complexity analysis of the algebraic attack described Melchor et al. (NIST PQC, 2020). At last, we combine these analysis to provide an attack against the$\textsf {NHRSL} $problem.

Let Fqbe the finite field withqelements andmbe a positive integer. The Fqm-linear low-rank parity-check (LRPC) codes have been used in many cryptographic schemes. Motivated by recent attacks on those schemes, this paper generalizes LRPC codes based on 3-tensors in Fm×m×mq. The generalized LRPC codes are mostly Fq-linear matrix codes, while a particular choice of the 3-tensor is isomorphic to the original Fqm-linear LRPC codes. We first introduce a bilinearT-product over Fmqassociated with a 3-tensorT∈ Fm×m×mq. Based on theT-product, we propose a generic method to expand Fq-linear matrix code from dimensionkto dimensionkmand then use the method to generalize LRPC codes. Finally, we propose two probabilistic polynomial-time decoding algorithms for the generalized LRPC codes under different circumstances. We provide estimates of their decoding failure rates, which, confirmed by experimental results, are almost the same as that of decoding Fqm-linear LRPC codes.

In this work we propose a family of ${\mathbb{F}_q}$-linear lowrank parity check (LRPC) codes based on a bilinear product over $\mathbb{F}_q^m$ defined by a generic 3-tensor over ${\mathbb{F}_q}$. A particular choice of this tensor corresponds to the classical ${\mathbb{F}_{{q^m}}}$-linear LRPC codes; and other tensors yield ${\mathbb{F}_q}$-linear codes, which, with some caveats, can be efficiently decoded with the same idea of decoding LRPC codes. The proposed codes contribute to the diversity of rank metric codes for cryptographic applications, particularly for the cases where attacks utilize ${\mathbb{F}_{{q^m}}}$-linearity to reduce decoding complexity.

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 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.

Designing code-based signatures is both an important and challenging problem. A standard way to tackle it consists to use the Fiat-Shamir heuristic along with an identification scheme that is required to be zero-knowledge. The authors of [1] have highlighted an issue within the zero-knowledge proof of the Veron identification scheme [2]. It turns out that the zero-knowledge proof of the AGS protocol [3] is impacted in a similar way. In this paper, we present a masking technique that solves the aforementioned issue without inducing any performance penalty. We introduce the Masked Veron and Masked AGS protocols that both leverage this masking technique and provide their zero-knowledge proofs. In addition, we present a new technique improving the performances of signatures built from code-based identification schemes subject to the attack described in [4]. The Masked Veron and Masked AGS protocols feature all the existing performance improvements from the literature.

Among the candidates for NIST's post-quantum cryptography standardization project, cryptosystems that rely on Low Rank Parity Check (LRPC) codes have interesting properties, such as a low public key size. However, the key generation phase for these cryptosystems is computationally expensive when done in constant-time, which is a security requirement on the standardization project, making it almost unusable for ephemeral key generation. We present a new constant-time algorithm for key generation on LRPC code-based cryptosystems, that divides the computational costs by four when compared to previous work over ROLLO, one of the NIST candidates. Our improvement consists in changing the way objects of a quotient ring are represented. By switching from a canonical basis to an optimal normal basis, we enable the full potential of the Itoh-Tsuiji algorithm for field inversion.

It is notably challenging to design an efficient and secure signature scheme based on error-correcting codes. An approach to build such signature schemes is to derive it from an identification protocol through the Fiat-Shamir transform. All such protocols based on codes must be run several rounds, since each run of the protocol allows a cheating probability of either 2/3 or 1/2. The resulting signature size is proportional to the number of rounds, thus making the 1/2 cheating probability version more attractive. We present a signature scheme based on double circulant codes in the rank metric, derived from an identification protocol with cheating probability of 2/3. We reduced this probability to almost 1/2 to obtain the smallest signature among code-based signature schemes based on the Fiat-Shamir paradigm, around 22 KBytes for 128 bit security level. Furthermore, among all code-based signature schemes, our proposal has the lowest value of signature plus public key size, and the smallest secret and public key sizes. We provide a security proof in the Random Oracle Model, implementation performances, and a comparison with the parameters of similar signature schemes.

We introduce a new family of rank metric codes: Low Rank Parity Check codes (LRPC), for which we propose an efficient probabilistic decoding algorithm. This family of codes can be seen as the equivalent of classical LDPC codes for the rank metric. We then use these codes to design cryptosystems à la McEliece: more precisely we propose two schemes for key encapsulation mechanism (KEM) and public key encryption (PKE). Unlike rank metric codes used in previous encryption algorithms -notably Gabidulin codes - LRPC codes have a very weak algebraic structure. Our cryptosystems can be seen as an equivalent of the NTRU cryptosystem (and also to the more recent MDPC code-based cryptosystem) in a rank metric context, due to the similar form of the public keys. The present paper is an extended version of the article introducing LRPC codes, with important new contributions. We have improved the decoder thanks to a new approach which allows for decoding of errors of higher rank weight, namely up to$\frac {2}{3}(n-k)$when the previous decoding algorithm only decodes up to$\frac {n-k}{2}$errors. Our codes therefore outperform the classical Gabidulin code decoder which deals with weights up to$\frac {n-k}{2}$. This comes at the expense of probabilistic decoding, but the decoding error probability can be made arbitrarily small. The new approach can also be used to decrease the decoding error probability of previous schemes, which is especially useful for cryptography. Finally, we introduce ideal rank codes, which generalize double-circulant rank codes and allow us to avoid known structural attacks based on folding. To conclude, we propose different parameter sizes for our schemes and we obtain a public key of 3337 bits for key exchange and 5893 bits for public key encryption, both for 128 bits of security.

Fuzzy extractors (Dodiset al., Eurocrypt 2004) turn a noisy secret into a stable, uniformly distributed key. Reusable fuzzy extractors remain secure when multiple keys are produced from a single noisy secret (Boyen, CCS 2004). Boyen showed information-theoretically secure reusable fuzzy extractors are subject to strong limitations. Simoens et al. (IEEE S&P, 2009) then showed deployed constructions suffer severe security breaks when reused. Canetti et al. (Eurocrypt 2016) used computational security to sidestep this problem, building a computationally secure reusable fuzzy extractor that corrects a sublinear fraction of errors.

This paper presents a different way to improve the resistance of digital watermarking. Using the well known Lattice QIM in the spatial domain, we analyze the interest of using a different kind of error correcting codes: rank metric codes. These codes are already used in communications for network coding but not used in the context of watermarking. In this article, we show how this metric permits to correct errors with a specific structure and is adapted to specific image attacks. We propose a first study to validate the concept of rank metric for watermarking process. For this, we use these codes to obtain invariance against luminance additive constant change.

In this paper, we propose an improvement of the attack on the Rank Syndrome Decoding (RSD) problem found in [1], usually the best attack considered for evaluating the security of rank metric based cryptosystems. For H a full-rank (n-k)×n matrix over Fqmand e ∈ Fqnm of small norm r, the RSD problem consists in recovering e from s=HeT. In our case, the norm of a vector over Fqmis defined by the dimension of the Fq-subspace generated by its coordinates. This problem is very similar to the Syndrome Decoding problem in the Hamming metric (only the metric and the field of the coefficients are different) and the security of several cryptosystems relies on its hardness, like McEliece-based PKE [2], [3] or IBE [4]. Our attack is in O((n- k)3m3qw-⌈((k+1)m)/n]⌉-m) operations in Fqwhereas the previous best attacks are in O((n-k)3m3q(w-1)min(⌈((k+1)m)/n⌉,k+1)) [1], [5]. In particular in the case m ≤ n, our attack permits to obtain an exponential gain in qm(1-R)for R=k/n the rate of the code. We give examples of broken parameters for recently proposed cryptosystems based on LRPC codes or Gabidulin codes. Our attack does not fully break these cryptosystems but implies larger parameters for the same security levels.

In this paper, we introduce a new hard problem opening up the construction for new quantum resistant cryptographic schemes. The latter is called Learning Rank with Errors (LRE) and can be seen as an adaptation of the LPN problem to the rank metric setting. In addition, we describe HBLRE, an HB-like authentication protocol that constitutes an application of the aforementioned problem. We also prove that HTLRE is secure against passive attacks and compare its parameters to those of the initial HB scheme.

The Bit Flipping algorithm is a hard decision decoding algorithm originally designed by Gallager in 1962 to decode Low Density Parity Check Codes (LDPC). It has recently proved to be much more versatile, for Moderate Parity Check Codes (MDPC) or Euclidean metric. We further demonstrate its power by proposing a noisy Euclidean version of it. This tweak allows to construct a lattice based key exchange analogous to the Ouroboros protocol for Hamming metric but with a reduction to the Short Integer Solution (SIS) problem. The very efficient decoding algorithm permits to consider smaller alphabets than for NTRU or Ring-LWE decryption algorithms. Overall we obtain a new protocol which competes with the recent NEWHOPE and Kyber proposals, and also with NTRU. The resulting scheme exploits the cyclicity of the error, and benefits from the security of the renowned SIS problem.

We propose a framework for constructing efficient code-based encryption schemes that do not hide any structure in their public matrix. The framework is in the spirit of the schemes first proposed by Alekhnovich in 2003 and based on the difficulty of decoding random linear codes from random errors of low weight. We depart somewhat from Alekhnovich's approach and propose an encryption scheme based on the difficulty of decoding random quasi-cyclic codes. We propose two new cryptosystems instantiated within our framework: the hamming quasi-cyclic cryptosystem (HQC), based on the hamming metric, and the rank quasi-cyclic cryptosystem (RQC), based on the rank metric. We give a security proof, which reduces the indistinguishability under chosen plaintext attack security of our systems to a decision version of the well-known problem of decoding random families of quasi-cyclic codes for the hamming and rank metrics (the respective QCSD and RQCSD problems). We also provide an analysis of the decryption failure probability of our scheme in the Hamming metric case: for the rank metric there is no decryption failure. Our schemes benefit from a very fast decryption algorithm together with small key sizes of only a few thousand bits. The cryptosystems are very efficient for low encryption rates and are very well suited to key exchange and authentication. Asymptotically, for λ the security parameter, the public key sizes are respectively in O(λ2) for HQC and in O(λ 4/3) for RQC. Practical parameter compares well to the systems based on ring-learning parity with noise or the recent moderate density parity check codes system.

Over the last few years, considering 3D vectors as one color information instead of three independent vector components has significantly improved the color watermarking field. There have been some research about perceptual approaches but there are few about the perception of color differences of the human vision system (HVS) for watermarking applications. This paper propose a new color watermarking algorithm able to minimize the perception of color differences. It understands color information as the HVS does. It can easily be adapted to many watermarking schemes such as quantization based schemes [1] or spread spectrum insertion techniques. This algorithm is based on a psychovisual model of the human eye studied by D. Alleysson [2]. The results showed good improvements in terms of watermark invisibility and robustness to image processings: we compared quantization methods working in grayscale and its color adaptation to show model stability or improvement.

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.

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.

We give a randomized reduction for the Rank Syndrome Decoding problem and Rank Minimum Distance problem for rank codes over extension fields. Our results are based on embedding linear codes in the Hamming space into linear codes over an extension field equipped with the rank metric. We prove that if any of the previous problems for the rank metric is in ZPP = RP∩coRP, then we would have NP = ZPP. We also give complexity results for the respective rank metric approximation problems.

Abstract This article details the conception, design, development and analysis of invisible, blind and robust color image watermarking algorithms based on the wavelet transform. Using error correcting codes, the watermarking algorithms are designed to be robust against intentional or unintentional attacks such as JPEG compression, additive white Gaussian noise, low pass filter and color attacks (hue, saturation and brightness modifications). Considering the watermarking channel characterized by these attacks, repetition, Hamming, Bose Chaudhuri Hocquenghem and Reed-Solomon codes are used in order to improve the robustness using different modes and appropriate decoding algorithms. The article compares the efficiency of different type of codes against different type of attacks. To the best of our knowledge this is the first time that the effect of error-correcting codes against different attacks are detailed in a watermarking context in such a precise way: describing and comparing the effect of different classes of codes against different type of attacks. This article clearly shows that list decoding of Reed-Solomon codes using the algorithm of Sudan exhibits good performance against hue and saturation attacks. The use of error correcting codes in a concatenation mode allows the non-binary block codes to show good performance against JPEG compression, noise and brightness attacks.

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.

We introduce a new class of rate one-half binary codes: complementary information set codes. A binary linear code of length$2n$and dimension$n$is called a complementary information set code (CIS code for short) if it has two disjoint information sets. This class of codes contains self-dual codes as a subclass. It is connected to graph correlation immune vectorial Boolean functions of use in the security of hardware implementations of cryptographic primitives. Such codes permit to improve the cost of masking cryptographic algorithms against side channel attacks. In this paper, we investigate this new class of codes: we give optimal or best known CIS codes of length$ < 132$. We derive general constructions based on cyclic codes and on double circulant codes. We derive a Varshamov–Gilbert bound for long CIS codes, and show that they can all be classified in small lengths$\leq 12$by the building up construction. Some nonlinear permutations are constructed by using${\BBZ}_{4}$-codes, based on the notion of dual distance of a possibly nonlinear code.

In this paper we classify all extremal and s-extremal binary self-dual codes of length 38. There are exactly 2744 extremal self-dual codes, two s-extremal codes, and 1730 s-extremal codes. We obtain our results from the use of a recursive algorithm used in the recent classification of all extremal self-dual codes of length 36, and from a generalization of this recursive algorithm for the shadow. The classification of -extremal codes permits to achieve the classification of all -extremal codes with .

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.

Ring signatures were introduced by Rivest, Shamir, and Tauman in 2001. These signatures allow a signer to anonymously authenticate a message on behalf of a group of his choice. This concept was then extended by Bresson, Stern, and Szydlo into$t$-out-of-$N$(threshold) ring signatures in 2002. We propose in this article a generalization of Stern's code-based identification (and signature) scheme to design a practical$t$-out-of-$N$threshold ring signature scheme. The size of the resulting signatures is in${\cal O}(N)$and does not depend on$t$, contrary to most of the existing protocols. Our scheme is existentially unforgeable under a chosen message attack in the random oracle model assuming the hardness of the minimum distance problem, is unconditionally source hiding, has a very short public key and has an overall complexity in${\cal O}(N)$. This protocol is the first efficient code-based ring signature scheme and the first code-based threshold ring signature scheme. Moreover it has a better complexity than number-theory based schemes which have a complexity in${\cal O}(Nt)$. This paper is an extended version of a paper published in the conference PQCrypto 2008, with complete proofs and definitions.

This paper presents a perception based watermarking algorithm for perceptually uniform color spaces. The image is watermarked using a blind watermarking scheme in the contourlet domain for the RGB, CIELAB, Y UV and AC1C2color spaces. The contourlet transform is used to decompose the image into directional subbands at multiple levels for all the color spaces. The contourlet transform allows to models the spatial frequency selectivity of the human visual system. The invisibility results of all the color spaces are compared with each other using CIEDE2000 and SSIM metrics. The visual distortion for each color component and its interaction with other color components is considered for all the subbands. Subjective tests are carried out to further validate the objective results. The results of the testing procedures show that the YUV color space is best suited for watermark insertion in terms of human perception.

In this paper we propose the use of list decoding of Reed Solomon codes to improve the robustness of blind frequency domain watermarking schemes in the presence of attacks, specially aimed at the colour aspect of the schemes. List decoding allows to decode errors well beyond the normally used bounded distance decoding algorithms and shows significant improvement when the code rates are low. We compare the results of different families of error correcting codes in order to improve the robustness of a blind, wavelet transform based colour image watermarking scheme. We use four families of error correcting codes to improve the robustness of the watermarking scheme (repetition, Hamming, BCH, and Reed Solomon). The experimental results show consistency with the theoretical approximations and the watermarked images with lower code rates are resistant to a variety of attacks.

Private scalar product protocols have proved to be interesting in various applications such as data mining, data integration, trust computing, etc. In 2007, Yao et al. proposed a distributed scalar product protocol with application to privacy-preserving computation of trust [1]. This protocol is split in two phases: an homorphic encryption computation; and a private multi-party summation protocol. The summation protocol has two drawbacks: first, it generates a non-negligible communication overhead; and second, it introduces a security flaw. The contribution of this present paper is two-fold. We first prove that the protocol of [1] is not secure in the semi-honest model by showing that it is not resistant to collusion attacks and we give an example of a collusion attack, with only four participants. Second, we propose to use a superposed sending round as an alternative to the multi-party summation protocol, which results in better security properties and in a reduction of the communication costs. In particular, regarding security, we show that the previous scheme was vulnerable to collusions of three users whereas in our proposal we can t isin [1..n - 1] and define a protocol resisting to collusions of up to t users.

A wireless ad-hoc network is a network which does not use any infrastructure such as access points or base station. Instead, the mobile nodes forward packets to each others, allowing communication among nodes outside wireless transmission range. In this dynamic network, each node is considered as a mobile router but in an energy-conserving manner. This fact makes node an active element in the network which is able of the best and of the worst. Actually, a malicious node can easily disrupt the proper functioning of the routing by simply refusing to forward routing message (misbehavior node), inject the wrong routing packets, modifying others, etc. In this paper, we propose a new routing protocol for wireless ad-hoc network based on multi-agent systems and particularly on ant behavior. The novelty of our protocol relies in the fact that, apparently for the first time, a protocol combines at the same time routing on one side and trust level and reputation between nodes on the other side. This combination permits to increase the security of route establishment. More generally, this protocol opens the door to the use of different agents for obtaining different mixed functionalities, routing and trust level in this paper but also other functionalities like key-distribution.

In this paper we introduce a new probabilistic lattice-based bounded homomorphic encryption scheme. For this scheme the sum of two encrypted messages is the encryption of the sum of two messages and the scheme is able to preserve a vector spave structure of the message. The size of the public key is rather large ap 3 Mb but the encryption and the decryption operations are very fast (of the same speed order than NTRU). The homomorphic operation, i.e. the addition of ciphertexts is dramatically fast compared to homomorphic schemes based on group theory like Paillier or El Gamal.

A PIR scheme is a scheme that allows a user to get an element of a database without giving any information about what part of the database he is interested in. In this paper we present a lattice-based PIR scheme, based on problems close to coding theory problems known to be NP-complete [1], in which the computational cost is a few thousand bit-operations per bit in the database. This improves the protocol computational performance by two orders of magnitude when compared to existing approaches. Our scheme has not as good communication performance as other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.

The Gilbert-Varshamov (GV) bound states that the maximum size A2(n, d) of a binary code of length n and minimum distance d satisfies A2(n, d)ges2n/V(n, d-1) where V(n, d)=Sigmai=0d(in) stands for the volume of a Hamming ball of radius d. Recently, Jiang and Vardy showed that for binary nonlinear codes this bound can be improved to A2(n, d)gescn2n/(V(n, d-1)) for c a constant and d/nges0.499. In this paper, we show that certain asymptotic families of linear binary [n, n/2] random double circulant codes satisfy the same improved GV bound.

In this correspondence, we give a new recursive method to classify extremal self-dual codes. As an application we classify all the 41 extremal binary$[36,18,8]$self-dual codes.

We revisit the code-based identification protocol proposed by Stern at Crypto'93, and give evidence that the size of public keys can be dramatically reduced while preserving a high and well-understood level of security. More precisely, the public keys can be made even shorter than RSA ones (typically 347 bits), while their size is around 150 Kbits in the original scheme. This is achieved by using matrices which are double circulant, rather than purely random. On the whole, this provides a very practical identification (and possibly signature) scheme which is mostly attractive for light-weight cryptography.

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.

Recently Bachoc and Gaborit introduced the notion of s-extremality for binary self-dual codes, generalizing Elkies' study on the highest possible minimum weight of the shadows of binary self-dual codes. In this paper, we introduce a concept of s-extremality for additive self-dual codes over F4, give a bound on the length of these codes with even distance d, classify them up to minimum distance d = 4, give possible lengths (only strongly conjectured for odd d) for which there exist s-extremal codes with 5 ≤ d ≤ 11, and give five s-extremal codes with d = 7 as well as four new s-extremal codes with d = 5. We also describe codes related to s-extremal codes.

In this paper we give an algorithm with complexity O(mu2) to solve Hermite multivariate polynomial interpolation with mu conditions on its Hasse derivatives. In the case of bivariate interpolation used to perform list-decoding on Reed-Solomon of length n and dimension k with multiplicity m on each point, it permits to obtain a complexity in O(n2m4) which does not depend on the rate k/n and better than previously known complexity in O( n2m5(n/k)(1/2)). This algorithm can also be used for recent interpolation list-decoding with three and more variables. For interpolation on polynomial with n points and M variables with prescribed multiplication order m the general complexity of the algorithm is O(n2m2M)

In this paper we describe an algorithm which permits to perform the erasure list-decoding of q-ary Reed-Muller codes with a quadratic complexity in the dimension of the code rather than with the usual cubic complexity for random linear codes with not too large length. The algorithm is based on a multivariable interpolation algorithm

The Gilbert-Varshamov bound states that the maximum size A2(n,d) of a binary code of length n and minimum distance d satisfies A2(n,d)ges2n/V(n,d-1) where V(n,d)=XiEdi=0(Eni) stands for the volume of a Hamming ball of radius d. Recently Jiang and Vardy showed that for binary non-linear codes this bound could be improved to A2(n,d)gescn2n/V(n,d -1) for c a constant and d/nles0.499. In this paper we show that certain asymptotic families of linear binary [n, n/2] double circulant codes satisfy the same improved Gilbert-Varshamov bound

In this paper, we study the algebraic immunity of Boolean functions and consider in particular the problem of constructing Boolean functions with a good algebraic immunity. We first give heuristic arguments which seem to indicate that the algebraic immunity of a random Boolean function on n variables is at least lfloorn/2rfloor with a very high probability (while the upper bound is lceiln/2rceil, the "ceiling" of n/2). We give an upper bound, under a reasonable assumption, on the algebraic immunity of Boolean functions constructed through Maiorana-MacFarland construction. At last we give examples of balanced functions with optimal algebraic immunity and a good nonlinearity and of balanced functions with a good algebraic immunity, a good nonlinearity and a good correlation immunity, which can be used for cryptographic purposes

In this correspondence, we compute the weight enumerators of various quadratic residue codes over F/sub 2/ and F/sub 3/, together with certain codes of related families like the duadic and the quadratic double circulant codes. We use a parallel algorithm to find the number of codewords of a given (not too high) weight, from which we deduce by usual classical methods for self-dual and formally self-dual codes over F/sub 2/ and F/sub 3/ their associated, previously unknown, weight enumerators. We compute weight enumerators for lengths as high as 152 for binary codes and 96 for ternary codes.

We compute the weight enumerators of various quadratic residue (QR) codes over F/sub 2/ and F/sub 3/, together with certain codes of related families like the duadic codes. We use a parallel algorithm to find the number of codewords of a given (not too high) weight, from which we deduce by usual classical methods for selfdual and isodual codes over F/sub 2/ and F/sub 3/ their associated, previously unknown, weight enumerators. We compute weight enumerators for lengths as high as 152 for binary codes (except for n=138 for which one lacks the number of codewords of weight 34) and 84 for ternary codes.

In this correspondence, we investigate the covering radius of codes over Z/sub 4/ for the Lee and Euclidean distances in relation with those of binary nonlinear codes and lattices obtained by the Gray map and Construction A/sub 4/, respectively. We give several upper and lower bounds on covering radii, including Z/sub 4/-analogs of the sphere-covering bound, the packing radius bound, the Delsarte bound, and the redundancy bound. We show that any Euclidean-optimal Type II code of length 24 has covering radius 8 with respect to the Euclidean distance. We determine the covering radius of the Klemm codes with respect to the Lee distance. We derive lower bounds on the covering radii of the Niemeier lattices.

We study Type IV self-dual codes over the commutative rings of order 4. Gleason-type theorems of Type IV codes and their shadow codes are investigated. A mass formula of Type IV codes over these rings are given. We give a classification of Type TV codes over Z/sub 4/ and F2+uF/sub 2/ for reasonable lengths. We also construct a number of optimal Type TV codes.

The alphabet F/sub 2/+uF/sub 2/ is viewed here as a quotient of the Gaussian integers by the ideal (2). Self-dual F/sub 2/+uF/sub 2/ codes with Lee weights a multiple of 4 are called Type II. They give even unimodular Gaussian lattices by Construction A, while Type I codes yield unimodular Gaussian lattices. Construction B makes it possible to realize the Leech lattice as a Gaussian lattice. There is a Gray map which maps Type II codes into Type II binary codes with a fixed point free involution in their automorphism group. Combinatorial constructions use weighing matrices and strongly regular graphs. Gleason-type theorems for the symmetrized weight enumerators of Type II codes are derived. All self-dual codes are classified for length up to 8. The shadow of the Type I codes yields bounds on the highest minimum Hamming and Lee weights.

In this correspondence we prove that any extremal doubly-even self-dual linear binary code of length 48 is not Z/sub 4/-linear. We also show that the putative extremal doubly-even self-dual linear binary codes of lengths 72 and 96 with minimum weight, respectively, 16 and 20, cannot be constructed as the Gray images of linear codes over Z/sub 4/.

We classify the self-dual Z/sub 4/ codes of all lengths from 10 through 15, extending the previous classification through length 9.

We give a mass formula for quaternary self-dual and type II codes and for self-dual codes over F/sub q/+uF/sub q/ rings. We define type II codes and compute the number of distinct type II codes. We also give formulas for the number of doubly even binary codes, necessary to compute N/sub d/(n), the number of distinct codes of length n, for any dimension n, and conclude that the classification of quaternary self-dual codes could be reasonably extended to length 14.