Paper 2014/478

Related-Key Secure Pseudorandom Functions: The Case of Additive Attacks

Benny Applebaum and Eyal Widder


In a related-key attack (RKA) an adversary attempts to break a cryptographic primitive by invoking the primitive with several secret keys which satisfy some known relation. The task of constructing provably RKA secure PRFs (for non-trivial relations) under a standard assumption has turned to be challenging. Currently, the only known provably-secure construction is due to Bellare and Cash (Crypto 2010). This important feasibility result is restricted, however, to linear relations over relatively complicated groups (e.g., $\Z^*_q$ where $q$ is a large prime) that arise from the algebraic structure of the underlying cryptographic assumption (DDH/DLIN). In contrast, applications typically require RKA-security with respect to simple additive relations such as XOR or addition modulo a power-of-two. In this paper, we partially fill this gap by showing that it is possible to deal with simple additive relations at the expense of relaxing the model of the attack. We introduce several natural relaxations of RKA-security, study the relations between these notions, and describe efficient constructions either under lattice assumptions or under general assumptions. Our results enrich the landscape of RKA security and suggest useful trade-offs between the attack model and the family of possible relations.

Available format(s)
Publication info
Preprint. MINOR revision.
Related-key Attackspseudo-randomness
Contact author(s)
benny applebaum @ gmail com
2015-08-30: revised
2014-06-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Applebaum and Eyal Widder},
      title = {Related-Key Secure Pseudorandom Functions: The Case of Additive Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2014/478},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.