[HGI-News] HGI Seminar, Montag, 20.06.05

[Newsletter des Horst Görtz Instituts]

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

                         Selcuk Baktir
           Cryptography & Information Security Laboratory
                  Worcester Polytechnic Institute (USA)
	
    "Finite Field Polynomial Multiplication in the Frequency Domain 
           with Application to Elliptic Curve Cryptography"

                   Montag, 20.06.2005, 13:15 Uhr, IC 4/39,


Abstract

The fast Fourier transform (FFT) based multiplication method originally
proposed for integer multiplication provides an extremely efficient method
with the best asymptotic complexity, i.e. O(n log_n loglog_n), for
multiplication of n-bit integers, or polynomials of degree n. Unfortunately,
the FFT based method bears significant overhead due to the conversions
between the time and frequency domains. This makes the original FFT method
impractical for multiplication of short operands as used in many
applications.

In this talk, we will introduce an efficient algorithm for computing
Montgomery products of polynomials in the frequency domain. Our algorithm
performs the entire modular multiplication (including the reduction step) in
the frequency domain, and thus eliminates costly back and forth conversions
between the frequency and time domains. We will show that in platforms where
multiplication operation is expensive, with careful selection of parameters,
frequency domain multiplication of finite field elements can be achieved
more efficiently than multiplication in the time domain for operand sizes
relevant to elliptic curve cryptography.
 

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

EMAIL-VERTEILER: Wenn Sie Vortragsankündigungen auch in Zukunft per
Email erhalten wollen, können Sie hier
http://www.hgi.ruhr-uni-bochum.de/deutsch/newsletter/
unseren Newsletter abonnieren.

ANFAHRT: Eine Wegbeschreibung zum IC Gebäude der RUB ist hier zu finden:
http://www.crypto.ruhr-uni-bochum.de/contact.html

VORTRÄGE IM SS 2005:
(Abstracts sind hier:
 http://www.crypto.ruhr-uni-bochum.de/hgi_sose05.html)

25.04 Marcel Holtmann, 13.15 hrs. IC 4/39,
"Bluetooth Security Unleashed"

02.05 Jan Pelzl, COSY - RUB, 13.15 hrs. IC 4/39,
"Hardware-based Factorization of Integers with the Elliptic Curve Method"

09.05 Michael Schmidt, University of Siegen, 13.15 hrs. IC 4/39,
"Subscriptionless Mobile Networking - A Secure, Privacy-Preserving Ad-hoc
Service Architecture"
 
23.05 Dario Carluccio, COSY - RUB, 13.15 hrs. IC 4/39,
"Electromagnetic Side Channel Analysis for Embedded Crypto Devices"

30.05 Thomas Dullien, RUB, 13.15 hrs. IC 4/39
"Structural Comparison of Executable Objects"

06.06 Stefan Strobel, cirosec GmbH, 13.15 hrs. IC 4/39,
"Sicherheit von Web-Applikation und E-Business-Systemen"

13.06 Marco Macchetti, Politecnico di Milano, 13.15 hrs. IC 4/39,
"Efficient Approaches for Hardware S-box DPA Resistance: a Proposal"

20.06 Selcuk Baktir, CRIS, WPI (USA), 13:15 hrs. IC 4/39,
"Finite Field Polynomial Multiplication in the Frequency Domain with 
Application to Elliptic Curve Cryptography"

27.06  Andrey Bogdanov, IEM, Uni Duisburg-Essen, 13:15 hrs. IC 4/39,
"ABC: A Family of Fast Stream Ciphers"

04.07  Björn Fay, Justus Liebig-Uni Giessen, 13.15 hrs. IC 4/39,
"Anwendung und Sicherheit der Random-Oracle Methode"

11.07  Kerstin Lemke, COSY - RUB, 13:15 hrs. IC 4/39
"A Stochastic Model for Differential Side Channel Cryptanalysis"

18.07  Philipp Südmeyer, COSY - RUB, 13.15 hrs. IC 4/39,
TBA

25.07  Jens-Peter Kaps, CRIS, WPI (USA), 13:15 hrs. IC 4/39,
"Cryptography for Ultra-Low Power Devices, Securing Pervasive Computing"


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

M.Tech. Sandeep Kumar
Chair for Communication Security
Dept. of Electr. Eng. & Information Sciences
Ruhr-University Bochum
44780 Bochum, Germany

URL: www.crypto.rub.de