**A Lightweight Hash Function Resisting Birthday Attack and Meet-in-the-middle Attack**

*Shenghui Su and Tao Xie and Shuwang Lv*

**Abstract: **To be paired with a lightweight digital signing scheme of which the modulus length is between 80 and 160 bits, a new non-Merkle-Damgård structure (non-MDS) hash function is proposed by the authors based on a multivariate permutation problem (MPP) and an anomalous subset product problem (ASPP) to which no subexponential time solutions are found so far. It includes an initialization algorithm and a compression algorithm, and converts a short message of n bits treated as only a block into a digest of m bits, where 80 <= m <= 232 and 80 <= m <= n <= 4096. Analysis shows that the new hash is one-way, weakly collision-free, and strongly collision-free along with a proof, and its security against existent attacks such as birthday attack and meet-in-the- middle attack gets the O(2^m) magnitude. Running time of its compression algorithm is analyzed to be O(n(m^2)) bit operations. A comparison with the Chaum-Heijst-Pfitzmann hash based on a discrete logarithm problem is made. Especially, the new hash with short input and small computation may be used to reform a classical hash with an m-bit output and an O(2^(m/2)) magnitude security into a compact hash with an m/2-bit output and the same security. Thus, it opens a door to convenience for utilization of lightweight digital signing schemes.

**Category / Keywords: **Hash function; Compression algorithm; Merkle-Damgard structure; Provable security; Birthday attack; Meet-in-the- middle attack

**Date: **received 28 May 2013, last revised 1 Nov 2014

**Contact author: **reesse at 126 com

**Available format(s): **PDF | BibTeX Citation

**Note: **The content has no essential change.

**Version: **20141101:084912 (All versions of this report)

**Short URL: **ia.cr/2013/327

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]