TCS Seminar

Date: 27/05/2011, 14:15 Location: J. Liivi 2, room 317 (next to the coffee room)

Speaker: Vassil Dimitrov , Professor, Department of Electrical and Computer Engineering, University of Calgary, Canada

Title: Computer Arithmetic and Cryptography         Slides: Dimitrov_slides1

Abstract:

The field of computer arithmetic is a fascinating subject, and not at all the drudgery that most of us experienced with our first exposure to the third 'r' of the three r's' at school. The efficiency of performing computer arithmetic is of paramount importance to signal processing and cryptographic systems, and much research takes place in this area; the novelty, however, is often in the circuits and the technology, rather than in the number representations. In this talk we shall explore the latter.

We all recall tricks learned at school to improve our "mental arithmetic" prowess (for example, remebering table of multiplication and simple algorithms involved in multiplication by 11). In computer arithmetic, we also search for ways of improving the performance of the basic operations, including using tables of store precomputations. There are various flavors of number representations, other than the basic binary integer representation, that use a base of 2. Finding an efficient number representation is only part of the battle in implementing arithmetic. Many applications in cryptography involve enormous number of multiplications that can be either very time consuming or require large amount of hardware. The smart selection of a number representation can lead to very significant improvements in both speed and area complexity of various cryptographic protocols. We shall demonstrate the advantages of some nonstandard number representations in cryptographic applications including key exchange and digital signature algorithms.