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?
2 Answers
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.
-
$\begingroup$ 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? $\endgroup$– ThomasMar 16, 2022 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.