Score:1

Definition of the strong Diffie Hellman problem

tr flag

I am looking for the definition of the strong Diffie Hellmann problem. However, I can only find definitions for the $\ell$ or $q$-strong Diffie Hellmann.

Is it possible that the strong Diffie Hellman problem is also called the $\ell$ or $q$-strong Diffie Hellmann problem?

Score:2
sa flag

Yes, the $\ell$ or $q$ is related to the parametrization, since the basic idea is to give you a number of known values and ask you to compute a related quantity and consider the hardness of this problem. For example, a Eurocrypt 2006 paper by Cheon available here states:

Given $g$ and $g^{\alpha^i}$ in an abelian group $G$ for $i=1,2,\ldots,\ell$ compute $g^{\alpha^{\ell+1}}.$ Here $\alpha \in \mathbb{Z}_p.$

It was first introduced by Boneh and Boyen to construct a short signature scheme, that is provably secure in the standard model (without random oracles).

Ievgeni avatar
cn flag
Can you give a source about your definition?
tr flag
Thank you for your answer!
Score:2
cn flag

According to this paper (page 6), the $q$-Strong Diffie-Hellman problem (or just Strong Diffie-Hellman problem in short) is the following one: In a bilinear context $(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T)$.

Let $g_1$ and $g_2$ be public generators of $\mathbb{G}_1$, and $\mathbb{G}_2$.

The adversary receives: $\left(g^{x^i}_1\right)^q_{i=0}$ and $g_2, g_2^x$, with $x$ a random secret scalar, and should output a pair $\left(c, g^{\frac{1}{x+c}}\right)$ with $c$ a scalar of his choice.

et flag
The link for the pdf doesn't work. Do you have an alternative link or the title/author of the papers?
Ievgeni avatar
cn flag
@user93353 I've changed the link
et flag
Thank you .....
kelalaka avatar
in flag
2K, congratulations. Now your edits are free :)
tr flag
Thanks for your answer and source!
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.