Secure message authentication against related-key attack

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