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

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]