Secure message authentication against related-key attack

Rishiraj Bhattacharyya*, Arnab Roy

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)


Security against related-key attacks is an important criteria for modern cryptographic constructions. In the related-key setting, the adversary has the ability to query the underlying function on the target key as well as on some related-keys. Although provable security against related-key attack has received considerable attention in recent years, most of the results in the literature aim to achieve pseudorandomness and semantic security and often lead to inefficient constructions. In this paper, we formalize the notion of unpredictability in the related-key setting. We start with the definitions of related-key security of Message Authentication Codes and identify required properties of related-key derivation functions for provable security. We show that unlike PRFs, MACs can inherently tolerate related-key attacks against constant transformations. Next, we consider the construction of variable-input-length MACs from fixed-input-length related-key unpredictable functions. We present simple attacks against XCBC and TMAC. We present a general construction of related-key secure MACs. Our construction, instantiated with Enciphered CBC construction of Dodis, Pietrzak and Puniya (EUROCRYPT 2008), results into first provably secure domain extension of related-key secure unpredictable functions. Finally, we present two constructions of related-key secure MACs from DDH assumption. The first construction is extremely efficient and tolerates group-induced partial key transformations. The second construction achieves security against independent group-induced tranformations and is more efficient than the RK-PRFs achieved by Bellare and Cash (CRYPTO 2010).

Original languageEnglish
Title of host publicationFast Software Encryption - 20th International Workshop, FSE 2013, Revised Selected Papers
PublisherSpringer Verlag
Number of pages20
ISBN (Print)9783662439326
Publication statusPublished - 2014
Event20th International Workshop on Fast Software Encryption, FSE 2013 - Singapore, Singapore
Duration: 11 Mar 201313 Mar 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8424 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference20th International Workshop on Fast Software Encryption, FSE 2013


  • Domain extension
  • Message authentication
  • Related-key attack

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Secure message authentication against related-key attack'. Together they form a unique fingerprint.

Cite this