1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ @Ievgeni: Excuse me, I would like to ask whether the strength of q-SDH is related to q? Can q be 0 or 1? Just like this: input $g \in G, g' \in G',(g,(g')^a)$, output $(g^{\frac{1}{a+s}},s)$, Does it belong to q-SDH? $\endgroup$
    – pod
    Sep 10, 2023 at 9:49

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 2K, congratulations. Now your edits are free :) $\endgroup$
    – kelalaka
    Mar 16, 2022 at 16:08
  • $\begingroup$ Thanks for your answer and source! $\endgroup$
    – Thomas
    Mar 16, 2022 at 19:10
  • $\begingroup$ The link for the pdf doesn't work. Do you have an alternative link or the title/author of the papers? $\endgroup$
    – user93353
    Jan 18, 2023 at 0:13
  • $\begingroup$ @user93353 I've changed the link $\endgroup$
    – Ievgeni
    Jan 18, 2023 at 10:23
  • $\begingroup$ Thank you ..... $\endgroup$
    – user93353
    Jan 18, 2023 at 11:07
3
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ Can you give a source about your definition? $\endgroup$
    – Ievgeni
    Mar 16, 2022 at 15:04
  • $\begingroup$ Thank you for your answer! $\endgroup$
    – Thomas
    Mar 16, 2022 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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