Séminaire Calcul Formel

Complexity Bound on Semaev's Naive Index Calculus Method for ECDLP

by Prof. Kazuhiro Yokoyama (Rikkyo University)

Salle XR203 (Bâtiment XLIM)

Salle XR203

Bâtiment XLIM


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, we give a deep analysis on Gr\"obner
basis computation for a polynomial system appearing in
the point decomposition problem (PDP) in a naive
index calculus method.
Our analysis is based on linear algebra under
simple statistical assumptions on summation polynomials.
Specifically, we show that the ideal derived from
the PDP has a special structure, and regard Gr\"obner
basis computation for the ideal as an extension of
the extended Euclidean algorithm.
This allows us to obtain a precise analysis
on a lower bound on the cost of Gr\"obner basis computation.
We also prove that the naive index calculus
cannot be more efficient than even the brute
force method.