2
$\begingroup$

Let, $g^{a}$, $g^{b}$ are known elements, where $g\in G$ and $a, b\in Z_q$. According to Computational Diffie-Hellman (CDH) assumption, it is hard to compute $g^{ab}$.

If $g^{a^2}$ is also known then is it still fall into Computational Diffie-Hellman assumption? In other words, if $g$, $g^{a}$, $g^{b}$, $g^{a^2}$ and $q$ are known, is it still hard to compute $g^{ab}$?

$\endgroup$
  • 1
    $\begingroup$ Are you asking whether, given $g, g^a$, whether computing $g^{a^2}$ is also a CDH problem? Or, are you asking whether, given $g, g^a, g^{a^2}, g^b$, is computing $g^{ab}$ still CDH? $\endgroup$ – poncho Dec 29 '17 at 18:42
  • $\begingroup$ I want to know if $g$, $g^{a}$, $g^{a^2}$, $g^{b}$ are known, is computing $g^{ab}$ still CDH? $\endgroup$ – Nazatul Dec 29 '17 at 18:46
  • $\begingroup$ To readers: Note that the prime is still unknown so computing $g^{a^2}$ cannot be performed by just anybody as it requires computation within a group of an unknown size (I hope I correctly formulated that, feel free to grind this comment to bits if I didn't.) $\endgroup$ – Maarten Bodewes Dec 29 '17 at 19:37
  • 1
    $\begingroup$ @MaartenBodewes: actually, even if we know $q$ (which we typically do), we can't easily compute $g^{a^2}$ because we're working in a ring where we can compute addition (given $g^a, g^b$ we can compute $g^{a+b}$), we can't do multiplication (given $g^a, g^b$, computing $g^{ab}$ is hard, that is the CDH assumption). In fact, if $q$ is odd and known, then computing $g^{a^2}$ is equivalent to the CDH assumption $\endgroup$ – poncho Dec 29 '17 at 20:05
  • $\begingroup$ A ring, right. It's about time to re-read some of the theoretical crypto books I suppose. $\endgroup$ – Maarten Bodewes Dec 29 '17 at 20:07
5
$\begingroup$

No, the assumption "given $g, g^a, g^b, g^{a^2}$, it is infeasible to compute $g^{ab}$" is not known to reduce to the CDH assumption. In fact, we can even prove a separation in the generic group model (meaning, it is impossible to build such a reduction by using the group operations in a black box way). Intuitively, this is because we do not know how to generate an instance of the first assumption given a CDH instance: it requires computing $g^{a^2}$ from $g^a$, which is already equivalent to breaking the CDH assumption. However, this assumption remains a plausible one: a scheme whose security would reduce to this assumption would be considered secure in the crypto community. In fact, many assumptions of this type which are variants of the CDH assumption are common in the crypto community.

$\endgroup$
  • $\begingroup$ Is computing $g^{ab}$ from the known elements $g$, $g^a$, $g^{a^2}$, $g^b$ a "Strong Diffie-Hellman" problem? $\endgroup$ – Nazatul Jan 4 '18 at 22:10
  • $\begingroup$ As I said previously, this is not directly a "strong Diffie-hellman assumption" in the usual sense, but it is implied (hence it is at least as strong as) the 1-strong Diffie-hellman assumption (which states that $g^{a^3}$ cannot be computed from $g^{a}$,$g^{a^2}$) $\endgroup$ – Geoffroy Couteau Jan 4 '18 at 23:20
  • $\begingroup$ Thank you so much once again. Wish you a happy and prosperous New Year! $\endgroup$ – Nazatul Jan 5 '18 at 15:08
0
$\begingroup$

It does not compromise DH security. Because computing $a$ from $g^a$ and $g^{a^2}$ is as hard as finding $a$ from $g^a$. So without knowledge of $a$ we cant compute $g^{ab}$ from just $g^a$ and $g^b$ and vice a verse.

$\endgroup$
  • $\begingroup$ This does not follow; there might be a way to compute $g^{ab}$ that does not involve recovering $a$. $\endgroup$ – poncho Dec 29 '17 at 20:53
  • $\begingroup$ Because of less knowledge, the only way i know to compute $g^{ab}$ is either by $g^{a^b}$ or ${g^b}^a$. Please guide to the details of method which does not require adversary to recover $a$ or $b$ for computing $g^{ab}$ $\endgroup$ – khan Dec 29 '17 at 21:03
  • 1
    $\begingroup$ 'I do not know of a way' $\ne$ 'It is provable that there is no way'. $\endgroup$ – poncho Dec 29 '17 at 22:05
  • $\begingroup$ I didnt mean that. I intentionally added the line "So without knowledge of $a$ we cant compute $g^{ab}$ from just $g^a$ and $g^b$ and vice a verse." to state my level of knowing the things so that someone can point out and correct me if i am wrong. So If there is a way, please tel me $\endgroup$ – khan Dec 30 '17 at 20:05

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.