Multilinear Pseudorandom Functions

Aloni Cohen, Justin HolmgrenIACR ePrint 2015 · OpenReview

TL;DR

This paper introduces "multilinear pseudorandom functions" (multilinear PRFs), a new cryptographic primitive that extends the concept of PRFs to handle multiple inputs in a structured way. The authors provide a construction for these multilinear PRFs based on the hardness of the Decisional Diffie-Hellman (DDH) problem, and show how this construction can be used to build more efficient and secure versions of existing cryptographic tools, including aggregate PRFs and algebraic PRFs.

What Problem Does This Paper Address?

Traditional pseudorandom functions (PRFs) are essential building blocks in cryptography, acting as a stand-in for truly random functions. However, many applications require PRFs with additional structure beyond simple input-output mapping. Two such areas are:

  1. Aggregate PRFs: These PRFs allow for efficient computation of sums of function outputs over large, succinctly described sets of inputs. Existing constructions often rely on strong assumptions like subexponential DDH hardness, which is undesirable.
  2. Algebraic PRFs: These PRFs are designed for applications like verifiable computation and multiparty computation, but their security guarantees are limited, especially over large domains, again often requiring subexponential hardness assumptions.

The paper aims to bridge this gap by defining and constructing multilinear PRFs that offer a more structured approach, with security based on the standard (polynomial-time) DDH assumption, and demonstrating their applicability to improve existing constructions in aggregate and algebraic PRFs.

Methods

The core contribution is the definition and construction of multilinear pseudorandom functions (multilinear PRFs).

  • Definition: A multilinear PRF is a family of functions that map a product of vector spaces ($V_1 \times \dots \times V_n$) to another vector space ($Y$), such that a random function from the family is indistinguishable from a truly random multilinear function with the same domain and codomain. The paper focuses on cases where the vector spaces are over finite fields, particularly $F_2$.
  • Construction: The authors provide a concrete construction (Construction 1) for multilinear PRFs. This construction leverages the properties of DDH-hard groups and tensor products of vector spaces. The key idea is to use inner products within the tensor product space and then map the result to a DDH-hard group.
  • Proof of Security: The security of the construction is proven by reducing it to the Matrix DDH assumption, which is itself known to follow from the standard DDH assumption. The proof uses a hybrid argument and relies on two algorithms (Algorithm 1 and Algorithm 2) for statefully implementing random linear functions, which are then used to simulate oracle access to the multilinear PRF.
  • SpanSearch Algorithm: The paper utilizes a randomized algorithm for "SpanSearch" (Algorithm 3), adapted from prior work [BW04]. This algorithm efficiently solves a problem related to linear independence of simple tensors, which is crucial for the efficient implementation of the stateful oracles used in the security proof.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and proofs of security, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unifying Primitive: Multilinear PRFs offer a powerful and unified framework that can encompass and improve upon existing notions like aggregate PRFs and algebraic PRFs.
  • Standard Assumptions: The ability to achieve security for these advanced primitives based on the standard (polynomial-time) DDH assumption is a significant improvement over prior work that required subexponential hardness.
  • Truthfulness: The construction is not only pseudorandom but also "truthful," meaning it is genuinely multilinear. This property is key to its applications in aggregate PRFs, where it directly implies the correctness of aggregate computations.
  • Tensor Products as a Tool: The paper effectively uses the mathematical machinery of tensor products to define and construct multilinear functions, highlighting their importance in cryptographic constructions.
  • Algorithmic Improvements: The reliance on the SpanSearch algorithm for efficient handling of linear independence problems is a key enabler for the practical implementation of the security proof.

Key Results

  • Definition of Multilinear PRFs: A formal definition of multilinear PRFs is introduced.
  • Construction of Multilinear PRFs: A concrete construction (Construction 1) for multilinear PRFs is presented, based on DDH-hard groups.
  • Security Proof: The construction is proven secure under the Matrix DDH assumption, which implies security under the standard DDH assumption.
  • Application to Aggregate PRFs: The construction directly yields (non-multilinear) PRFs with aggregate security, resolving an open question from [CGV15]. This application relies on the "truthfulness" property of the multilinear PRF.
  • Application to Algebraic PRFs: The paper shows how existing algebraic PRF constructions can be viewed through the lens of multilinear PRFs, implying they also satisfy aggregate security.

Limitations and Future Work

  • Domain and Codomain Restrictions: The current construction is limited to specific domains (product of vector spaces over $F_p$) and codomains (DDH-hard groups). The paper notes that constructing multilinear PRFs over arbitrary finite fields or rings is an "intriguing open question."
  • Symmetric/Skew-Symmetric PRFs: The paper proposes a candidate construction for symmetric multilinear PRFs (Construction 2) but notes that its security is less clear, reducing to the n-Strong DDH assumption for $d=2$. The security of this construction for general $n$ and $d$ is left as an open problem.
  • Efficiency: While the security is based on standard assumptions, the efficiency of the construction and its applications might still be a consideration for practical deployment, especially concerning the tensor product operations and the SpanSearch algorithm.
  • Generalizations: The paper hints at further generalizations of algebraic PRFs and other applications that could be explored using the multilinear PRF framework.

Summary updated

Abstract

We define the new notion of a multilinear pseudorandom function (PRF), and give a construction with a proof of security assuming the hardness of the decisional Diffie-Hellman problem. A direct application of our construction yields (non-multilinear) PRFs with aggregate security from the same assumption, resolving an open question of Cohen, Goldwasser, and Vaikuntanathan. Additionally, multilinear PRFs give a new way of viewing existing algebraic PRF constructions: our main theorem implies they too satisfy aggregate security.
BibTeX
@article{cohen2015multilinear,
  author = {Aloni Cohen and Justin Holmgren},
  title = {{Multilinear Pseudorandom Functions}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2015},
  url = {https://openreview.net/forum?id=05I4GABgOr},
}

Loading related content...

Figure