I'm wondering if the following problem is as hard as computational or decision Diffie-Hellman problem? (Or is it actually an easy problem because $c$ is available?)

Given a cyclic group $G$ and let its order be $q$. Given $g$, $q$, $g^a$ and $g^b$ and $c \in Z_q$, decide if $c \equiv a*b \mod q$.

Another version of the problem could be: let $G$ be a group of unknown order (e.g., where RSA or strong RSA assumption could apply, thus computing roots would be hard).

  • $\begingroup$ I assume we are given $g$ and $q$. $\endgroup$
    – fgrieu
    Jul 9 at 21:27
  • $\begingroup$ This problem is obviously no harder than DDH (given an Oracle that can solve DDH, it's easy to solve your problem) $\endgroup$
    – poncho
    Jul 9 at 21:28
  • $\begingroup$ Yes, given g and q. I have rephrased question correspondingly. Thanks! $\endgroup$
    – Sean
    Jul 9 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.