Referent: Kazuhiro Yokoyama: Complexity Bound on Semaev's Naive Index Calculus Method for ECDLP
Donnerstag, 09.01.2020, 14:00 h
Abstract: Since Semaev introduced summation polynomials, a number of works have been devoted to improve index calculus algorithms for solving the elliptic curve discrete logarithm problem (ECDLP), with better complexity than generic algorithms such as Pollard's rho method. In this talk, I give a deep analysis on Groebner basis computation for a polynomial system appearing in the point decomposition problem (PDP) in a naive index calculus method. The analysis is based on linear algebra under simple statistical assumptions on summation polynomials. Specifically, I show that the ideal derived from the PDP has a special structure, and regard Groebner basis computation for the ideal as an extension of the extended Euclidean algorithm with help of the notion of signature. This allows us to obtain a precise analysis on a lower bound on the cost of Groebner basis computation.