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

*Shenghui Su and Tao Xie and Shuwang Lu*

**Abstract: **In this paper, to match a lightweight digital signing scheme of which the length of modulus is between 80 and 160 bits, a lightweight hash function called JUNA is proposed. It is based on the intractabilities MPP and ASPP, and regards a short message or a message digest as an input which is treated as only one block. The JUNA hash contains two algorithms: an initialization algorithm and a compression algorithm, and converts a string of n bits into another of m bits, where 80 <= m <= n <= 4096. The two algorithms are described, and their securities are analyzed from several aspects. The analysis shows that the JUNA hash is one-way, weakly collision-free, strongly collision-free along with a proof, especially resistant to birthday attack and meet-in-the-middle attack, and up to the security of O(2 ^ m) steps at present, while the time complexity of its compression algorithm is O(n) steps. Moreover, the JUNA hash with short input and small computation may be used to reform a classical hash with the output of m bits and security of O(2 ^ (m / 2)) steps into a compact hash with the output of m / 2 bits and equivalent security. Thus, it opens a door to convenience for utilization of lightweight digital signing schemes.

**Category / Keywords: **public-key cryptography / Bit long-shadow; Lightweight hash function; Compression algorithm; Birthday attack; Multivariate permutation problem; Anomalous subset product problem

**Date: **received 28 May 2013, last revised 6 Oct 2013

**Contact author: **reesse at 126 com

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

**Note: **Minor revision.

**Version: **20131007:032203 (All versions of this report)

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

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

[ Cryptology ePrint archive ]