Cryptology ePrint Archive: Report 2014/488

Related-Key Security for Pseudorandom Functions Beyond the Linear Barrier

Michel Abdalla and Fabrice Benhamouda and Alain Passelègue and Kenneth G. Paterson

Abstract: Related-key attacks (RKAs) concern the security of cryptographic primitives in the situation where the key can be manipulated by the adversary. In the RKA setting, the adversary's power is expressed through the class of related-key deriving (\RKD) functions which the adversary is restricted to using when modifying keys. Bellare and Kohno (Eurocrypt 2003) first formalised RKAs and pin-pointed the foundational problem of constructing RKA-secure pseudorandom functions (RKA-PRFs). To date there are few constructions for RKA-PRFs under standard assumptions, and it is a major open problem to construct RKA-PRFs for larger classes of \RKD functions. We make significant progress on this problem. We first show how to repair the Bellare-Cash framework for constructing RKA-PRFs and extend it to handle the more challenging case of classes of \RKD functions that contain claws. We apply this extension to show that a variant of the Naor-Reingold function already considered by Bellare and Cash is an RKA-PRF for a class of affine \RKD functions under the DDH assumption, albeit with an exponential-time security reduction. We then develop a second extension of the Bellare-Cash framework, and use it to show that the same Naor-Reingold variant is actually an RKA-PRF for a class of degree $d$ polynomial \RKD functions under the stronger decisional $d$-Diffie-Hellman inversion assumption. As a significant technical contribution, our proof of this result avoids the exponential-time security reduction that was inherent in the work of Bellare and Cash and in our first result.

Category / Keywords: Related-Key Security, Pseudorandom Functions.

Original Publication (with major differences): IACR-CRYPTO-2014

Date: received 19 Jun 2014, last revised 1 Jul 2015

Contact author: michel abdalla at ens fr

Available format(s): PDF | BibTeX Citation

Note: 2015-07-01: improved notation

Version: 20150701:135057 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]