Multilinear maps

A cryptographic multilinear map generalizes a bilinear pairing to a k-way map e: G_1 x … x G_k → G_T that is linear in each argument and on which discrete-log-type problems are conjectured hard; the known candidates are graded encodings, and they underlie the first iO candidate (GGHRSW13).

TODO: syntax and security definition.

Variations

Decision Multilinear No-Exact-Cover assumption

For a multilinear map whose levels are the subsets of $[n]$, sample $a_1,\dots ,a_n\stackrel{\$}{\leftarrow }{\mathbb{Z}}_p$. The Decision Multilinear No-Exact-Cover assumption holds if for every instance $(n,T_1,\dots ,T_{\ell })$ of Exact Cover with no exact cover, no efficient adversary given the level-$T_j$ encodings of ${\prod }_{i\in T_j}{a}_i$ for all $j$ distinguishes the level-$[n]$ encoding of ${\prod }_{i=1}^n{a}_i$ from an encoding of a uniform element, except with negligible advantage — GGSW13.

Participates in

Builds on Multilinear maps

• MMap + Leveled FHE ⇒ iO
• Multilinear No-Exact-Cover ⇒ Witness encryption (GGSW) (via Decision Multilinear No-Exact-Cover assumption)