Paper 2011/252

Cryptography Secure Against Related-Key Attacks and Tampering

Mihir Bellare, David Cash, and Rachel Miller


We show how to leverage the RKA (Related-Key Attack) security of blockciphers to provide RKA security for a suite of high-level primitives. This motivates a more general theoretical question, namely, when is it possible to transfer RKA security from a primitive P1 to a primitive P2? We provide both positive and negative answers. What emerges is a broad and high level picture of the way achievability of RKA security varies across primitives, showing, in particular, that some primitives resist ``more'' RKAs than others. A technical challenge was to achieve RKA security even for the practical classes of related-key deriving (RKD) functions underlying fault injection attacks that fail to satisfy the ``claw-freeness'' assumption made in previous works. We surmount this barrier for the first time based on the construction of PRGs that are not only RKA secure but satisfy a new notion of identity-collision-resistance.

Available format(s)
Publication info
Published elsewhere. Preliminary version in Asiacrypt 2011. This is the full version.
Related-key attacktamper-resistancepseudorandom functionssignaturesidentity-based encryption
Contact author(s)
mihir @ eng ucsd edu
2011-09-06: last of 2 revisions
2011-05-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and David Cash and Rachel Miller},
      title = {Cryptography Secure Against Related-Key Attacks and Tampering},
      howpublished = {Cryptology ePrint Archive, Paper 2011/252},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.