In this talk, we describe a technique to give a lower bound on the minimum distance of certain types of quasi-cyclic codes. The key idea is to reduce this problem to prove a lower bound on the minimum distance of a few significantly smaller codes. Using this technique, we show that a code which is similar to SHA-1 (Secure Hash Algorithm) message expansion code, has a minimum distance of 82. The technique is further applied to prove that the minimum weight of the SHA-1 message expansion code is small. The low minimum distance of SHA-1 message expansion code has earlier been exploited to cause an effective collision attack on SHA-1. Estimating the minimum distance of a code given by its parity check matrix is well known to be a hard problem. This technique is expected to be helpful in estimating the minimum distance of similar quasi-cyclic codes as well as in designing future practical cryptographic hash functions.
Anindya C. Patthak presently works for Intel Corporation in the Computational Lithography Group. Earlier he was a post doctoral researcher at the University of California, Riverside. He received his Ph.D. from the University of Texas at Austin in 2007, under the guidance of Prof. David Zuckerman, and a B.Tech. from IIT Kharagpur. His research focuses on error correcting codes and their applications to theoretical computer science. He is also interested in algebraic property testing, algebraic-combinatorial constructions and pseudo-randomness etc.