1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • $\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$
    – Thomas
    Mar 16 at 18:23
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.