A family of fast syndrome based cryptographic hash functions. (English) Zbl 1126.94320

Dawson, Ed (ed.) et al., Progress in cryptology – Mycrypt 2005. First international conference on cryptology in Malaysia, Kuala Lumpur, Malaysia, September 28–30, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28938-0/pbk). Lecture Notes in Computer Science 3715, 64-83 (2005).
Summary: Recently, some collisions have been exposed for a variety of cryptographic hash functions [X. Wang et al., Lect. Notes Comput. Sci. 3494, 1–18, 19–35 (2005)] 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 function designs.
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 J.-S. Coron and A. Joux [Cryptology ePrint Archive (2004), http://eprint.iacr.org/2004/013/ ] based on D. Wagner’s generalized birthday algorithm [Lect. Notes Comput. Sci. 2442, 288–303 (2002; Zbl 1026.94541)] we study the asymptotical security of our functions. We demonstrate that this attack is always exponential in terms of the length of the hash value.
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.
For the entire collection see [Zbl 1089.94001].


94A60 Cryptography


Zbl 1026.94541
Full Text: DOI