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)