# Definition of Multilin DDH

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?

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.

• Thanks for your reply, I'm really amazed how fast you get replies in this forum and how good they are. Can you still give me the source for this so I can quote it? Mar 16 at 18:23

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.