[HGI-News-de] HGI Kolloquium Do, 10.6.: Strategien für effiziente Skalarmultiplikation von Thorsten Mehlich

[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:

Thorsten Mehlich (RUB)
*Strategien für effiziente Skalarmultiplikation*

Termin: Donnerstag, den 10. Juni um  11.00 Uhr (*s.t.*)
Raum: IC 4/161

Interessierte sind herzlich eingeladen!

==============================================================
Abstract:
Today the two most important algorithms for asymmetric cryptography are RSA and ECC. In the case of RSA one needs an element $x$ in a group $G$, computes the exponentiation $x^n$, where $n$ is a positive integer $n$. With elliptic curves one computes the scalar multiple $n\cdot P$, where $n$ is an integer.
Many efficient algorithms were suggested in order to compute $x^n$ or $n\cdot P$. In order to perform these computations, addition chains are used implicitly or explicitly. Such addition chains are usually obtained from redundant positional representations of the scalar (or exponent) $n$.
Now, most algorithms build ``windows'' on the initial representation of the scalar from right-to-left or left-to-right.  But there is no reason why windows should not be chosen in the middle of the representation of the scalar.  This would not be optimal for a $w$-NAF, as proved by Avanzi, but the algorithm of M\`{e}loni and Hasan actually builds the set of possible digits from an addition chain for the prefix of the input, and as such we can profit from more flexibility in trying to find the ``biggest'' digits anywhere in the representation.
In order to find and choose the window, one needs a decision rule. We have two different methods. One method is based on a cost-gain-analysis. The second decision rule uses the Balas-Algorithm from binary optimization.
After that we look at the special case of elliptic curves. In particular, our new methods prove to be better than the $w-$NAF and than the M\`{e}loni and Hasan algorithm in the case of elliptic curves.  
==============================================================


Vorankündigung: 
17. Juni 2010: Roberto Avanzi (RUB), Arithmetic of Supersingular Koblitz Curves in Characteristic Three - 24. Juni 2010: Christopher Wolf (AG Long Term Security), Äquivalente Schlüssel in Multivariaten Quadratischen Systemen - 1. Juli: Juraj Somorovsky (NDS), Streaming-based verification of XML Signatures in SOAP Messages – 5. Juli, Montag(!): Susanne Wetzel (Stevens Institute of Technology), TBA - 8. Juli: Peter Schwabe (Eindhoven University of Technology), New Software Speed Records for Cryptographic Pairings - 15. Juli: Alexander Meurer(CITS), Correcting Errors in RSA Private Keys.


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


Viele Grüße
Timo