Spectral Arithmetic and its Applications in Cryptography

Date: 
Monday, November 10, 2008 - 9:16am

UCSB COMPUTER SCIENCE DEPARTMENT PRESENTS:
WEDNESDAY, NOVEMBER 12, 2008
3:30 – 4:30
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: OMER EGECIOGLU

SPEAKER: Cetin Kaya Koc
Professor, Computer Science Department at City University of Istanbul
Visiting Professor, UCSB Computer Science and College of Creative Studies

Title:

Spectral Arithmetic and its Applications in Cryptography

Abstract:

Spectral arithmetic techniques rely on the Fourier transform in order to
perform arithmetic operations. The asymptotically fastest algorithm for
multiplying long integers to date is a spectral algorithm, albeit it has
some disadvantages for cryptography. Due to relatively large overhead,
the break-even point of efficiency for spectral multiplication has been
more than several thousand bits, however, most cryptographic
applications still require only a few hundred bits. Furthermore,
cryptographic algorithms require modular multiplication (multiplication
followed by a division), while it was not clear until recently how this
can be accomplished efficiently using spectral techniques. In this
seminar, we will describe new spectral algorithms for modular
multiplication of integers, show its applications in computing the RSA,
Diffie-Hellman, and elliptic curve cryptographic functions. We have also
designed a new hash function based on spectral techniques, with distinct
efficiency advantages however, its security remains to be seen.

Bio:

Cetin Kaya Koc is a visiting professor in the Department of Computer
Science and the College of Creative Studies at UCSB, teaching courses in
hardware security and cryptography. See: http://cs.ucsb.edu/~koc