Cryptology ePrint Archive: Report 2015/766

Related-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. If we consider the related-key attack (RKA) against these UHF-based schemes, some of them may not be secure, especially those using the key of UHF as a part of the whole key of scheme, due to the weakness of UHF in the RKA setting. 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 RKA setting. We define related-key almost universal (RKA-AU) hash function and related-key almost XOR universal (RKA-AXU) hash function. However almost all the existing UHFs do not satisfy the new definitions. We construct one fixed-input-length universal hash functions named RH1 and two variable-input-length universal hash functions named RH2, RH3. We show that RH1 and RH2 are both RKA-AXU, and RH3 is RKA-AU for the RKD set $\Phi^\oplus$. Furthermore, RH1, RH2 and RH3 are nearly as efficient as previous similar constructions. RKA-AU (RKA-AXU) hash functions can be used as components in the related-key secure 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 for some RKD sets. More specifically, we give four concrete applications of RKA-AU and RKA-AXU in related-key secure message authentication codes and tweakable block ciphers.

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

Original Publication (with minor differences): IACR-FSE-2016

Date: received 31 Jul 2015, last revised 24 Feb 2016

Contact author: wp at is ac cn

Available format(s): PDF | BibTeX Citation

Version: 20160224:150656 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]