International Association
for Cryptologic Research

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 efficient IBE schemes that are RKA secure for sets consisting of all affine functions and all polynomial functions of bounded degree. These results are in the standard model and hold under reasonable hardness assumptions. Applying results of Bellare, Cash and Miller to these IBE schemes, we obtain the first constructions of public-key encryption and signature schemes secure against related key attacks for sets of non-linear related key derivation functions, both in the standard model under reasonable hardness assumptions. As a corollary, we provide the first jointly secure combined signature and encryption schemes for the RKA setting. We also describe a specific and highly efficient RKA-secure CCA-PKE scheme for affine related key derivation functions based on the KEM of Boyen, Mei and Waters. Finally, we explain how to obtain RKA-secure SE-CCA from strong RKA-secure IBE and give instantiations for sets of related key derivation functions that are non-linear.