Provably Good Codes for Hash Function Design

Charanjit Jutla, IBM Watson

We develop a new technique to lower bound the minimum distance of quasi-cyclic codes of large dimension by reducing the problem to the minimum distance of a few significantly smaller dimensional codes. Using this technique, we prove that a linear code which is similar to the SHA-1 message expansion code has minimum distance 82, and that too in just the last 64 of the 80 expanded words. Contrast this with the minimum distance of 25 for SHA-1. We expect our technique to be helpful in designing future practical collision-resistant hash functions. In particular, a modified SHA-1 with the new code is resistant to recent differential attacks of Wang et al and their natural extensions. The talk will also address limitations of purely algebraic techniques in estimating minimum distance of such linear codes.

4 Aug (Friday) at 1630 hrs

Gates 4B (opposite 490)