[CvGmt News] [Notiziario] [Settimanale] avviso di seminario 14-9

Liviana Paoletti paoletti at dm.unipi.it
Fri Sep 10 09:35:26 CEST 2010


Il Prof. Ludovic Perret, dell'Université Pierre et Marie Curie, Paris, sarà ospite del Dipartimento di Matematica dal 13 al 16 Settembre, e
terrà un seminario Martedì 14 settembre alle ore 16 in Sala Seminari



MARTEDI' 14 SETTEMBRE 2010 

SEMINARIO
16:00-17:30, Sala Seminari (Dip. Matematica)
Algebraic Cryptanalysis of McEliece Variants with Compact Keys 
Prof. Ludovic Perret ('Université Pierre et Marie Curie,' Paris)



Abstract:


In this talk, we will present a new approach to investigate the  security of the McEliece cryptosystem. We recall that this cryptosystem relies on the use of error-correcting codes. Since its  invention thirty years ago, no efficient attack had been devised that  managed to recover the private key. We prove that the private key of  the cryptosystem satisfies a system of bi-homogeneous polynomial  equations.This property is due to the particular class of codes  considered which are alternanting codes.We have used these highly structured algebraic equations to mount an efficient key-recovery  attack against two recent variants of the McEliece cryptosystems that  aim at reducing public key sizes. These two compact variants of  McEliece managed to propose keys with less than 20,000 bits.To do so,  they proposed to use quasi-cyclic or dyadic structures. 

An  implementation of our algebraic attack in the computer algebra system  Magma allows to find the secret-key in a negligible time (less than  one second) for almost all the proposed challenges. For instance, a  
private key designed for a 256-bit security has been found in 0.06  seconds with about 2^17.8 operations. joint work with Jean-Charles Faugère, Ayoub Otmani, and Jean-Pierre  Tillich) 



  Liviana Paoletti 
  Segreteria Scientifica
Dipartimento di Matematica
"L. Tonelli" Universita' di Pisa
tel. 0502213251
e-mail  paoletti at dm.unipi.it
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cvgmt.sns.it/pipermail/news/attachments/20100910/6a46090a/attachment.htm>
-------------- next part --------------
_______________________________________________
Settimanale mailing list
Settimanale at mail.dm.unipi.it
https://mail.dm.unipi.it/listinfo/settimanale
-------------- next part --------------
_______________________________________________
Notiziario mailing list
Notiziario at mail.dm.unipi.it
https://mail.dm.unipi.it/listinfo/notiziario


More information about the News mailing list