Cryptology ePrint Archive: Report 2015/766

Relate-Key Almost Universal Hash Functions: Definitions, Constructions and Applications

Peng Wang and Yuling Li and Liting Zhang and Kaiyan Zheng

Abstract: Universal hash functions (UHFs) have been extensively used in the design of cryptographic schemes. But if we consider related-key attack against the schemes, some of them may not be secure, especially when the key of UHF is a part of the key of scheme. In order to solve the issue, we propose a new concept of related-key almost universal hash function, which is a natural extension to almost universal hash function in the related-key scenario. We define related-key almost universal (RK-AU) hash function and related-key almost XOR universal (RK-AXU) hash function. However almost all the existing UHFs do not satisfy the new definitions. We construct fixed-input-length universal hash functions such as RH1 and variable-input-length related-key universal hash functions such as RH2, RH3. We show that RH1 and RH2 are both RK-AXU, and RH3 is RK-AU. Furthermore, RH1, RH2 and RH3 are nearly as efficient as previous similar constructions. RK-AU (AXU) hash functions can be used as components with related-key property in the design of cryptographic schemes. If we replace the universal hash functions in the schemes with our corresponding constructions, the problems about related-key attack can be solved. More specifically, we give four concrete applications of RK-AU and RK-AXU in MACs and TBCs.

Category / Keywords: secret-key cryptography / Almost universal hash function, related-key attack, related-key almost universal hash function, message authentication code, tweakable block cipher

Date: received 31 Jul 2015

Contact author: wp at is ac cn

Available format(s): PDF | BibTeX Citation

Version: 20150731:112914 (All versions of this report)

Short URL: ia.cr/2015/766

Discussion forum: Show discussion | Start new discussion