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) 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.

Note: The some words are revised.