BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:A Heuristic Subexponential Attack on the McEliece Cryptosystem
DTSTART:20261020T120000Z
DTEND:20261020T130000Z
DTSTAMP:20261029T024900Z
UID:indico-event-17560@indico.math.cnrs.fr
DESCRIPTION:Speakers: Pierre Briaud (CNRS)\n\nWe provide a new way of perf
 orming an algebraic attack on the McEliece cryptosystem basedon binary Gop
 pa codes. It also applies in general to the case where the field over whic
 hthe Goppa code is defined is of even characteristic. It is based on a new
  algebraicmodeling for finding matrices of rank $2$ in the code of quadrat
 ic relations related tothe Goppa code that is attacked. Such matrices are 
 then used to recover the secretalgebraic structure of the code\, from whic
 h an equivalent secret key can be efficientlyderived\, leading to a full k
 ey-recovery attack. A byproduct of our approach is a newdistinguisher for 
 Goppa codes in even characteristic which is as the syzygy distinguisherof 
 \\cite{R25} subexponential in the security level of the scheme. We demonst
 rate theeffectiveness of our attack on McEliece TII challenges\, some of w
 hich having been studiedin \\cite{BLT26}\, and aimed at having 83\,89\,119
 \,166\, 210 and even 248 bit securityrespectively and CFS keys with parame
 ters $r=9$ and $m=16$\, corresponding to a security of$74.9$ bits accordin
 g to \\cite{LS12}. This CFS key was not attacked in practice in\\cite{BLT2
 6} and took us 14 hours of computation and 24GB of RAM. We make the conjec
 turethat this attack has a complexity which is of the same nature as the d
 istinguisher\, namelysubexponential in the security level. It should be no
 ted that this attack is at best ofcomplexity of order $2^{454}$ for NIST l
 evel 1 Classic McEliece parameters.\n\nhttps://indico.math.cnrs.fr/event/1
 7560/
LOCATION:XR203 (XLIM)
URL:https://indico.math.cnrs.fr/event/17560/
END:VEVENT
END:VCALENDAR