Key Exchange mechanisms (KE or KEMs) such as the Diffie-Hellman protocol have proved to be a cornerstone conciliating the efficiency of symmetric encryption and the practicality of public key primitives. Such designs however assume the non-compromission of the long term asymmetric key in use. To relax this strong security assumption, and allow for modern security features such as Perfect Forward Secrecy (PFS) or Post Compromise Security (PCS), Ratcheted-KE (RKE) have been proposed. This work proposes to turn the Hamming Quasi-Cyclic (HQC) cryptosystem into such a Ratcheted-KE, yielding the first code-based such construction. Interestingly, our design allows indifferently one party to update the key on-demand rather than the other, yielding a construction called bi-directionnal RKE, which compares favorably to generic transformations. Finally, we prove that the resulting scheme satisfies the usual correctness and key-indistinguishability properties, and suggest concrete sets of parameters, assuming different reallife use cases.

International audience

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.

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.