Skip to main content
2 of 5
edited body
Biv
  • 10k
  • 2
  • 42
  • 68

There is 3 kind of discrete log problem as you explained :

  1. Diffie-Hellman problem (Dlog):
    Pick $a \in \{1,\ldots,q\}$. Compute $A = g^a (mod\ p)$
    Given $(p,q,g,A)$ find $a$.
    Assumed hard.

  2. Computational Diffie-Hellman problem (CDH) :
    Pick $a,b \in \{1,\ldots,q\}$. Compute $A = g^a (mod\ p)$ and $B = g^b (mod\ p)$
    Given $(p,q,g,A,B)$ find $g^{ab}$.

Note that solving the DH problem solves the CDH problem.

  1. Decisional Diffie-Hellman problem (DDH) :
    Pick $a,b,c \in \{1,\ldots,q\}$. Compute $A = g^a (mod\ p)$ and $B = g^b (mod\ p)$
    Given $(p,q,g,A,B)$ distinguish $g^{ab}$ from $g^{c}$.

In any of these problems, the goal is to find the $a$ or $b$. In your question you are giving them, therefore there is no complexity (as the generator $g$ of a sub-group of $\mathbb{Z}/p\mathbb{Z}$ is usually provided).

Biv
  • 10k
  • 2
  • 42
  • 68