Efficient pseudorandom functions from the decisional linear assumption and weaker variants

Abstract

In this paper, we generalize Naor and Reingold's construction of pseudorandom functions under the DDH Assumption [22] to yield a construction of pseudorandom functions under the decisional k-Linear Assumption, for each k › 1. The decisional Linear Assumption was first introduced by Boneh, Boyen, and Shacham in [5] as an alternative assumption for settings where the DDH problem is easy, such as bilinear groups. Shacham [25] and Hofheinz and Kiltz [16] independently introduced the generalized decisional k-Linear Assumptions and showed that the decisional (k+1)-Linear problem is hard for generic groups even when the decisional k-Linear problem is easy. It is thus desirable to have constructions of cryptographic primitives based on the decisional k-Linear Assumption instead of DDH. Not surprisingly, one must pay a small price for added security: as k increases, our constructed functions become slightly less efficient to compute and the key size increases (quadratically in k).