Spring 2004

Unless indicated otherwise, the CryptoSeminar is being held in the Atwater Kent building on the WPI Worcester campus. The Atwater Kent building is at the intersection of Salisbury Street and the extension of West Street (labeled "Private Way"). See directions to campus.

The talks are 30-45 minutes long and are open to everyone.

Refreshments are usually being served 15 minutes before the talk. There is no fee and no formal registration. If you are attending a Seminar for the first time, a short e-mail to Profs. Berk Sunar or Bill Martin, saying that you would like to attend, would be appreciated.

Two Aspects of the Discrete Logarithm Problem

Dr. Douglas R. Stinson, School of Computer Science, University of Waterloo, Canada
Tuesday, April 27, 2004, 4:00pm, WPI Campus Center, Hagglund Room

Abstract

The discrete logarithm problem is of fundamental importance in cryptography. The security of many widely-used cryptosystems depends on the unproved assumption that certain versions of the discrete logarithm problem are intractable.

In this talk, we discuss two aspects of the discrete logarithm problem. First we investigate and extend two algorithms of Coppersmith that pertain to the so-called "low hamming weight" discrete logarithm problem. This is the special case of the discrete log problem in which the unknown logarithm has a small number of 1's in its binary representation. Such a logarithm might be chosen in order to speed up computations in a cryptosystem; however, the algorithms we describe show that determining the discrete logarithm in this case can also be speeded up significantly. These algorithms make use of certain set systems known as "splitting systems".

The second topic we discuss is an elementary treatment of the complexity of the so-called "generic" algorithms for the discrete log problem. Informally, a generic algorithm is one that works in any group. A well-known result of Nechaev and Shoup shows that generic algorithms in a group of prime order, n, have complexity that is lower bounded by the square root of n. We describe an approach to the analysis of generic algorithms that allows an exact (rather than asymptotic) analysis to be given. This approach demionstrates a link between generic algorithms on the one hand, and sets of points in (finite) Desarguesian affine planes that generate large numbers of slopes, on the other hand.

WPI's 2004 Annual Math Awareness Lecture: Visual Cryptography, or Seeing is Believing

Dr. Douglas R. Stinson, School of Computer Science, University of Waterloo, Canada
Monday, April 26, 2004, 4:00pm, Higgins Laboratories, WPI, Room 116

This talk is intended for a general audience. No particular background in mathematics is required.

M.S. Thesis Defense: Universal Hash Functions for Ultra-Low Power Cryptographic Hardware Applications

Kaan Yüksel, CRIS Laboratory, Worcester Polytechnic Institute
Friday, April 23, 2004, 2:00pm, Atwater Kent, WPI, Room 108

Abstract

Message Authentication Codes (MACs) are valuable tools for ensuring the integrity of messages. MACs may be built around a keyed hash function. The idea of using a universal hash function (NH) was explored in the construction of UMAC. This M.S. Thesis presents three variations on NH, namely PH, PR and WH. Our main motivation was to prove that universal hash functions can be employed to provide provable security in ultra-low-power applications such as the next generation self-powered sensor networks.

The first hash function we propose, i.e. PH, produces a hash of length 2w and is shown to be 2^-w-almost universal. The other two hash functions, i.e. PR and WH, reach optimality and are proven to be universal hash functions with hash length of w only. In addition, these schemes are simple enough to allow for efficient constructions. To the best of our knowledge the proposed hash functions are the first ones specifically designed for low-power hardware implementations. We achieved drastic power savings of up to 59% and speedup of up to 7.4 times over NH. Note that the speed improvement and the power reduction are accomplished simultaneously.

Moreover, we show how the technique of multi-hashing and the Toeplitz approach can be combined to reduce the power and energy consumption even further while maintaining the same security level with a very slight increase in the amount of the key material. At low frequencies the power and energy reductions are achieved simultaneously while keeping the hashing time constant. We developed formulae for estimation of the leakage and dynamic power consumptions as well as the energy consumption based on the frequency and the Toeplitz parameter t. We introduce a powerful method for scaling WH according to specific energy and power consumption requirements. This enables us to optimize the hash function implementation for use in ultra-low-power applications such as Smart Dust motes, RFIDs, and Piconet nodes. Our implementation of WH-16 consumes only 2.95 uW at 500 kHz. It can therefore be integrated into a self-powered device. By virtue of their security and implementation features mentioned above, we believe that the proposed universal hash functions will fill an important gap in cryptographic hardware applications.

Maintained by webmaster@wpi.edu
Last modified: Monday, 10-Jan-2005 22:02:41 EST