Multilinear Pseudorandom Functions

Abstract. We define the new notion of a multilinear pseudorandom function (PRF), and give a construction with a proof of security as-suming the hardness of the decisional Diffie-Hellman problem. A direct application of our construction yields (non-multilinear) PRFs with ag-gregate security from the same assumption, resolving an open question in [CGV15]. Additionally, multilinear PRFs give a new way of viewing existing algebraic PRF constructions: our main theorem implies they too satisfy aggregate security.