In this talk we propose an efficient code-based cryptosys-
tem with no hidden trapdoor in the public matrix. The system is in the
spirit of a system proposed by Alekhnovich in 2003 based on random
matrices, but still our approach is slightly different and optimized in or-
der to obtain security reduction to decoding random quasi-cyclic codes.
Beside a security proof we also provide a detailed analysis of the decryp-
tion failure probability of our scheme. Our scheme benefits from a very
fast decryption algorithm and has small sizes of public key with only a
few thousand bits. The encryption is rather low but our system can be
very efficient for key exchange and authentication. We also generalize
our approach to rank metric for which we obtain even better parameters
than for Hamming metric.
(travail commun avec Carlos Aguilar Melchor, Olivier Blazy, Philippe Gaborit, et Gilles Zémor)