Post-quantum cryptography and new results for rank-based cryptography

Présenté par Philippe Gaborit , Université de Limoges

6 juin 2014 à 10h00 salle E206 à TELECOM Sudparis à Evry (91)

In a first part of this talk we will introduce the notion of
post-quantum cryptography which aims at finding alternative cryptographic
algorithms to classical algorithms like RSA, EL Gamal, Elliptic curves,
in case a quantum computer with sufficiently many qbits would exist.
In a second time we will focus
on rank-based cryptography, which was introduced in 1991
with the GPT cryptosystem which adapts the McEliece scheme
with Gabidulin codes. The interest of such a scheme is that
the complexity of best known attacks to decode random rank codes,
permits to obtain small size of public keys of a few thousand bits,
which is very small compared to the classical McEliece scheme.
Meanwhile after its introduction the GPT scheme was attacked and repaired
several times, essentially because of the strong structure of Gabidulin
codes.

In this talk we present recent results which give a new light on
the potentiality of rank-based cryptography:

• the LRPC cryptosystem (an adaptation of the NTRU cryptosystem
  in a rank metric context) which has very small public keys and a poor structure,
• new efficient attacks for decoding random rank metric codes
• a proof of the hardness of decoding rank metric codes
• Ranksign: a new efficient signature algorithm based on the LRPC rank codes family,
  which leads to relatively small public key parameters of only a few thousand bits.

Philippe Gaborit :
Philippe Gaborit est professeur en Informatique à l’université de Limoges, ses domaines
principaux de recherche sont: la cryptographie, la protection de la vie privée et
les codes-correcteurs d’erreurs. Il est l’auteur de plus de 30 articles de journaux et de
4 brevets sur les applications des codes-correcteurs d’erreurs et des réseaux arithmétiques à la cryptographie.
Parcours: Ing. civil des Mines/DEA ’93, these univ. Bordeaux ’97,
post-doc univ. Illinois at Chicago 97-99, MC Limoges ’99, PR Limoges ’08.