**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) arithmetic steps at present, while the time complexity of its compression algorithm is O(n) arithmetic steps. Moreover, the JUNA hash with short input and small computation may be used to reform a classical hash with output of n bits and security of O(2 ^ (n / 2)) into a compact hash with output of n / 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 10 Jun 2013

**Contact author: **sheenway at 126 com

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

**Note: **The some words are revised.

**Version: **20130611:014422 (All versions of this report)

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

[ Cryptology ePrint archive ]