Séminaire des jeunes

Efficient Code-Based Encryption Without Trapdoors

by Mr Jean-Christophe Deneuville

XR203 (Faculté des sciences et Techniques)


Faculté des sciences et Techniques

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)