Paper 2015/766

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

Peng Wang, Yuling Li, Liting Zhang, and Kaiyan Zheng


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.

Available format(s)
Publication info
A minor revision of an IACR publication in FSE 2016
Almost universal hash functionrelated-key attackrelated-key almost universal hash functionmessage authentication codetweakable block cipher
Contact author(s)
wp @ is ac cn
2016-02-24: last of 2 revisions
2015-07-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Peng Wang and Yuling Li and Liting Zhang and Kaiyan Zheng},
      title = {Related-Key Almost Universal Hash Functions: Definitions, Constructions and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2015/766},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.