A Family of Fast Syndrome Based Cryptographic Hash Functions
Daniel Augot, Matthieu Finiasz and Nicolas Sendrier
INRIA-projet Codes and EPFL-Lausanne (Swizerland)
Proceedings of International Conference on Cryptology
in Malaysia (Mycrypt 2005).
LNCS 3715, pp. 64-83, 2005, Springer-Verlag..
Recently, some collisions have been exposed for a variety of
cryptographic hash functions, including some of the
most widely used today. Many other hash functions using
similar constructions can however still be considered secure.
Nevertheless, this has drawn attention on the need for new hash
In this article is presented a family of secure hash functions,
whose security is directly related to the syndrome decoding problem
from the theory of error-correcting codes.
Taking into account the analysis by Coron and Joux based
on Wagner's generalized birthday algorithm, we study the
asymptotical security of our functions. We demonstrate that this
attack is always exponential in terms of the length of the hash
We also study the work-factor of this attack, along with other
attacks from coding theory, for non asymptotic range, i.e. for
practical values. Accordingly, we propose a few sets of
parameters giving a good security and either a faster hashing or a
shorter description for the function.