Score:1

Definition of Multilin DDH

tr flag

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?

Score:1
gb flag

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.

tr flag
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?
Score:0
cn flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.