BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:Complexity Bound on Semaev's Naive Index Calculus Method for ECDLP
DTSTART;VALUE=DATE-TIME:20191003T083000Z
DTEND;VALUE=DATE-TIME:20191003T093000Z
DTSTAMP;VALUE=DATE-TIME:20200924T212612Z
UID:indico-event-5017@indico.math.cnrs.fr
DESCRIPTION:Since Semaev introduced summation polynomials\,\na number of w
orks have been devoted to improve\nindex calculus algorithms for solving\n
the elliptic curve discrete logarithm problem (ECDLP)\, \nwith better com
plexity than generic algorithms such\nas Pollard's rho method.\nIn this ta
lk\, we give a deep analysis on Gr\\"obner\nbasis computation for a polyno
mial system appearing in\nthe point decomposition problem (PDP) in a naive
\nindex calculus method.\nOur analysis is based on linear algebra under\ns
imple statistical assumptions on summation polynomials.\nSpecifically\, we
show that the ideal derived from\nthe PDP has a special structure\, and r
egard Gr\\"obner\nbasis computation for the ideal as an extension of\nthe
extended Euclidean algorithm.\nThis allows us to obtain a precise analysis
\non a lower bound on the cost of Gr\\"obner basis computation.\nWe also p
rove that the naive index calculus\ncannot be more efficient than even the
brute\nforce method.\n\nhttps://indico.math.cnrs.fr/event/5017/
LOCATION:Bâtiment XLIM Salle XR203
URL:https://indico.math.cnrs.fr/event/5017/
END:VEVENT
END:VCALENDAR