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$
5
  • 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, 2017 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$
    – Naz
    Dec 29, 2017 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, 2017 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, 2017 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, 2017 at 20:07

2 Answers 2

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$
3
  • $\begingroup$ Is computing $g^{ab}$ from the known elements $g$, $g^a$, $g^{a^2}$, $g^b$ a "Strong Diffie-Hellman" problem? $\endgroup$
    – Naz
    Jan 4, 2018 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$ Jan 4, 2018 at 23:20
  • $\begingroup$ Thank you so much once again. Wish you a happy and prosperous New Year! $\endgroup$
    – Naz
    Jan 5, 2018 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$
4
  • $\begingroup$ This does not follow; there might be a way to compute $g^{ab}$ that does not involve recovering $a$. $\endgroup$
    – poncho
    Dec 29, 2017 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$
    – crypt
    Dec 29, 2017 at 21:03
  • 2
    $\begingroup$ 'I do not know of a way' $\ne$ 'It is provable that there is no way'. $\endgroup$
    – poncho
    Dec 29, 2017 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$
    – crypt
    Dec 30, 2017 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.