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: 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 ]