BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Learning a Zonotope and More: Cryptanalysis of NTRUSign Countermea
 sures
DTSTART:20130606T100000
DTEND:20130606T110000
DTSTAMP:20261001T181123Z
UID:47dc433935eabb60ff3f94e79517a99b2ec2d336cca2e6e540a69819
CATEGORIES:Conferences - Seminars
DESCRIPTION:Léo Ducas\, Ecole Normale Supérieure\, Paris\nLattices have 
 attracted a lot of interest in the domain of Public Key Cryptography\; and
  they are now well understood tools to build scheme which security can be 
 reduced to the hardness of lattice problems\nsuch as finding the shortest 
 vector. Yet\, the early signature scheme NTRUSign\, from 2003\, does not r
 ely on those recent tools\, and its security was an open question. Despite
  the existence of provably secure schemes\, this question remains essentia
 l in practice because its efficiency is far better than provably secure on
 es.\nA first step was done by Nguyen and Regev in 2006\, showing that a "r
 aw" version of NTRUSign was subject to a statistical attack. Precisely\, t
 hey showed that the signature belong to a parallelepiped\, which is relate
 d to the secret key\; and that it is possible to learn that parallelepiped
  given enough signatures.\nYet the full version of NTRUSign contained a pr
 eventive countermeasure against this kind of attack\, consisting of a addi
 ng a randomized perturbation\, hoping to prevent any statistical attacks. 
 In this work will first show that this perturbation results in a Zonotope\
 , and that it is still possible to learn that zonotope\; this attack was i
 mplemented and the full secret key could be recovered from about 5000 sign
 atures. We will also tackle alternative perturbation techniques\, interest
 ingly leading to the famous Graph Isomorphism problem.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR