Paper 2012/514

RKA Security beyond the Linear Barrier: IBE, Encryption and Signatures

Mihir Bellare, Kenneth G. Paterson, and Susan Thomson


We provide a framework enabling the construction of IBE schemes that are secure under related-key attacks (RKAs). Specific instantiations of the framework yield RKA-secure IBE schemes for sets of related key derivation functions that are non-linear, thus overcoming a current barrier in RKA security. In particular, we obtain IBE schemes that are RKA secure for sets consisting of all affine functions and all polynomial functions of bounded degree. Based on this we obtain the first constructions of RKA-secure schemes for the same sets for the following primitives: CCA-secure public-key encryption, CCA-secure symmetric encryption and Signatures. All our results are in the standard model and hold under reasonable hardness assumptions.

Available format(s)
Publication info
Published elsewhere. Preliminary version in Asiacrypt 2012. This is the full version.
Identity-based encryptionrelated-key attackssignatures
Contact author(s)
kenny paterson @ rhul ac uk
2013-04-09: last of 3 revisions
2012-09-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mihir Bellare and Kenneth G.  Paterson and Susan Thomson},
      title = {RKA Security beyond the Linear Barrier: IBE, Encryption and Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2012/514},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.