<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=windows-1252">
<META content="MSHTML 6.00.2900.3395" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT face=Arial size=2><FONT face="Times New Roman" size=3>Il Prof.
Ludovic Perret, dell'Université Pierre et Marie Curie, Paris, sarà ospite del
Dipartimento di Matematica dal 13 al 16 Settembre, e<BR>terrà un seminario
Martedì 14 settembre alle ore 16 in Sala Seminari</FONT><BR><BR><BR>
<STYLE>a:link, a:visited, a:active {
color: #C29F4C;
</STYLE>
<FONT color=#660033>
<H3>MARTEDI' 14 SETTEMBRE 2010 </H3></FONT>
<P></P>
<P><B>SEMINARIO</B><BR>16:00-17:30, Sala Seminari (Dip.
Matematica)<BR><I>Algebraic Cryptanalysis of McEliece Variants with Compact Keys
</I><BR>Prof. Ludovic Perret ('Université Pierre et Marie Curie,' Paris)<BR><A
href="http://www.dm.unipi.it/notiziario/index.php?op=view2&id=903"></A><BR><FONT
color=#660033></FONT><BR><BR><B>Abstract:</B><BR></P>
<P>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. </P>
<P>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 <BR>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) </P>
<TABLE border=0>
<TBODY></TBODY></TABLE></FONT></DIV>
<DIV> </DIV>
<DIV> <I><FONT size=2><FONT face=Arial>Liviana Paoletti <BR>
Segreteria Scientifica</FONT></FONT></I></DIV>
<DIV>
<P style="MARGIN-BOTTOM: 0cm"><FONT size=2><FONT face=Arial><I>Dipartimento di
Matematica<BR>"L. Tonelli" Universita' di Pisa<BR>tel.
0502213251<BR>e-mail </I><A
href="mailto:paoletti@dm.unipi.it"><I>paoletti@dm.unipi.it</I></A></FONT></FONT></P><PRE></PRE></DIV></BODY></HTML>