BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Thomas Espitau (NTT Secure Platform Laboratories) and Paul Kirchne
 r (Université de Rennes 1)
DTSTART:20200704T130000Z
DTEND:20200704T133000Z
DTSTAMP:20260423T200718Z
UID:ANTS14/25
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/ANTS14/25/">
 The nearest-colattice algorithm: time-approximation tradeoff for approx-CV
 P</a>\nby Thomas Espitau (NTT Secure Platform Laboratories) and Paul Kirch
 ner (Université de Rennes 1) as part of Algorithmic Number Theory Symposi
 um (ANTS XIV)\n\n\nAbstract\nIn this paper we exhibit a hierarchy of polyn
 omial time algorithms solving approximate variants of the Closest Vector P
 roblem (\\CVP). Our first contribution is a heuristic algorithm achieving 
 the same distance as HSVP algorithms\, namely $\\approx \\beta^{\\frac{n}{
 2\\beta}}\\mathrm{covol}(\\Lambda)^{\\frac{1}{n}}$ for a random lattice $\
 \Lambda$ of dimension $n$. Compared to Kannan embedding\, our technique al
 lows using precomputations. This implies that some attacks on some lattice
 -based signatures lead to very cheap forgeries\, after a precomputation. O
 ur second contribution is a \\emph{proven} reduction from approximating th
 e closest vector with a factor $\\approx n^{\\frac32}\\beta^{\\frac{3n}{2\
 \beta}}$ to the Shortest Vector Problem (SVP) in dimension $\\beta$.\n\nCh
 airs: Claus Fieker and Elena Kirshanova\n
LOCATION:https://researchseminars.org/talk/ANTS14/25/
END:VEVENT
END:VCALENDAR