Definition of Multilin DDH

Question

I am on the abbreviation mutlin. DDH, which probably stands for mutliniear Decision Diffie Hellmann. I am currently looking for a definition for this term, but unfortunately cannot find a source. Can anyone here help me further?

Answer 1

The standard DDH problem is, given $g, g^a, g^b, g^c$, to decide whether $c = ab$. With a bilinear pairing (for example elliptic curve pairings), this is solvable, since $$e(g^a, g^b) = e(g, g^{ab}).$$

We therefore introduce the bilinear DDH, and it's generalisation - multilinear DDH. Suppose we have a multilinear map $$e : \mathbb{G}^\kappa \to \mathbb{G}_T$$ Where $\mathbb{G}^\kappa$ is the product of $\kappa$ copies of group $\mathbb{G}$. Suppose $g$ is a generator of $\mathbb{G}$ and $g_T$ is the corresponding generator of $\mathbb{G}_T$.

The $\kappa$-multilinear DDH problem is: given $g, g^{x_0}, \ldots, g^{x_\kappa}$ (that is, $\kappa+1$ exponentiations in $\mathbb{G}$), and an element $g_T^y$, to decide if $$y = \prod_i{x_i}.$$

With a bilinear map we can solve $\kappa = 1$, but don't know of any way to solve for higher $\kappa$. The bilinear DDH is when $\kappa = 2$, and would be solvable using a trilinear map if one existed.

Answer 2

In this paper, there is a definition:

In a $n$-linear context $(\mathbb{G}, \mathbb{G}_T)$ with a $n$ linear map which verifies:

$$e(g_1^{a_1},\dots, g_n^{a_n})=e(g_1,\dots, g_n)^{a_1\cdot a_2\dots \cdot a_n} $$

Let $g$ be a public generator of $\mathbb{G}$.

The adversary receives: $\left(g^{a_i}\right)^{n+1}_{i=1}$, and should compute $e(g,\dots, g)^{a_1\cdot a_2\dots \cdot a_n \cdot a_{n+1}} $.

I'm assuming the decisional version is only about distinguish this output from a random element of $\mathbb{G}_T$, even it's not clearly defined in this paper.