Paper 2013/327

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.

Note: Minor revision.