[HGI-News-de] HGI Kolloquium Do. 02.07.: "Parallel Harvesting for Index Calculus" von R. Avanzi

[Newsletter des Horst Görtz Instituts]

Hallo,

im Rahmen des HGI Kolloquiums "Aktuelle Themen der IT-Sicherheit" wird
am kommenden *Donnerstag* der folgende Vortrag angeboten:

Prof. Dr. Roberto Avanzi (MA³C):
*Parallel Harvesting for Index Calculus*

(mit Nicolas Theriault und Anoosheh Zaerin)

Termin:
Donnerstag, der 02. Juli um  11.00 Uhr (*s.t.*)
Raum: IC 4/161

Interessierte sind herzlich eingeladen!


==============================================================
Abstract:

In some cases low genus hyperelliptic curves (HEC) can offer better
performance than elliptic curves. It is thus interesting to assess their
security, which relies on the difficulty of the underlying Discrete
Logarithm Problem (DLP). The best known attacks on the DLP on HEC are of
the index calculus family. An index calculus algorithm works similarly
to the number field sieve, and in particular it calls for the solution
of a large linear algebra system. Before the linear algebra is done, it
is common to process the linear system to remove duplicate and
superfluous relations. This intermediate stage is called filtering.

For the index calculus on Jacobians of low genus curves Avanzi and
Th{\'e}riault suggested a filtering strategy called harvesting, which
can reduce the running time of the whole index calculus by 30\%\ or
more. However, this requires to redesign the whole index calculus
algorithm and in particular to collect a much larger system to begin
with, raising the question of feasibility because of the huge storage
requirements.

We thus developed a parallel version of this filtering technique. This
required a careful analysis of the original serial algorithm and
separation of the harvesting process in a control part and in processes
that carry the actual removal of the equations.

The version we introduce can be made massively parallel, making this the
index-calculus-with-harvesting approach feasible. Furthermore, its time
complexity is linear in the size of the system, making its running time
negligible with respect to the whole index calculus method.

We also present test results of serial and distributed harvesting
implementations.
==============================================================

Informationen über die nächsten geplanten Vorträge im Rahmen des
HGI Kolloquiums sind auch im Web zu finden:
http://www.hgi.rub.de/hgi/hgi-seminar/aktuelles

Gruß,
Mathias Herrmann