[HGI-News] HGI Seminar am Donnerstag, 18.9.

[hgi-news at lists.ruhr-uni-bochum.de]

Liebe Krypto-Interessierte, übermorgen trägt einer unsere Gäste über
schnelle ECC-Implementierungen vor. Das Seminar ist wie immer für
alle offen.  Gruß, Christof Paar
========================================================================

                       Selcuk Baktir

            Worcester Polytechnic Institute, USA

          Donerstag, 18.9.2003, 11:00 st, IC 4/39

    OPTIMAL TOWER FIELDS FOR ELLIPTIC CURVE CRYPTOGRAPHY


Elliptic curve cryptography relies heavily on the existence of efficient
algorithms for finite field arithmetic. Optimal Extension Fields (OEFs)
have been found to be especially successful in embedded software
implementations of elliptic curve schemes. In the elliptic curve
scalar-point multiplication, a large number of field multiplications and
inversions are computed. This poses a significant problem in embedded
systems where computational power is quite limited. Despite recent
improvements, inversion is still the slowest operation in elliptic curve
implementations. In this talk, this issue will be addressed by introducing
a specialized tower field representation, named Optimal Tower Fields
(OTFs), which facilitates efficient finite field arithmetic.

The recursive direct inversion method developed for OTFs will be
presented. It will be shown that the asymptotic complexity of OTF
inversion algorithm is phenomenally as low as  O(m^2), which is same as
the asymptotic complexity of multiplication and a significant improvement
over the O(m^2 log_2 m) asymptotic complexity of Itoh-Tsujii method. We
will see that this complexity is further improved to O(m^(log_2 3)) by
utilizing the Karatsuba-Ofman algorithm. We will also see that OTFs are in
fact a special class of OEFs, and an OTF element may be converted to OEF
representation via a simple permutation of the coefficients. Hence, OTF
operations are available to OEFs whenever a corresponding OTF exists.

The implementation results of OTF inversion algorithm on the ARM family of
processors will be presented for a medium and a large sized field whose
elements can be represented with 192 and 320 bits, respectively. Finally,
we will comment on the remarkable speed-up advantage of using OTF
inversion in performing elliptic curve point multiplication operation.

========================================================================

EMAIL-VERTEILER: Wenn Sie Vortragsankündigungen auch in Zukunft per
Email erhalten wollen, schicken Sie bitte eine kurze Nachricht an:
             cpaar at crypto.rub.de


ANFAHRT: Eine Wegbeschreibung zur RUB ist hier zu finden:
http://www.ruhr-uni-bochum.de/pressestelle/anreise.htm



============================================
Prof. Christof Paar
Chair for Communication Security
Dept. of Electr. Eng. & Information Sciences
Ruhr-Universitaet Bochum
44780 Bochum, Germany

URL: www.crypto.rub.de