Cryptology ePrint Archive: Report 2013/327

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

Shenghui Su and Tao Xie and Shuwang Lu

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 27 Aug 2014

Contact author: reesse at 126 com

Available format(s): PDF | BibTeX Citation

Note: Minor revision.

Version: 20140827:143756 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]