Skip to main content
3 of 5
added 714 characters in 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).


The group used here is $<G,\times>$ where $G=\{1,g,g^2,g^3,...,g^{q−1}\}\subset \mathbb{Z}/p\mathbb{Z}$ with $q<p$ and $g^q = 1$. The $+1$ is either not defined (if you assume addition) or means : $\forall a \in G, a + 1 = a \times g$ which could be simplified as : $\forall a=g^x \in G, a + 1 = g^{x+1}$.

We are using as a basis $<\mathbb{Z}/p\mathbb{Z}, +, \times>$ where $+$ is define. If $a \in G$ why $a + 1$ may not be in $G$. Here is an example : $p = 13, q = 3, g = 11$.
$11^0\mod 13 = 1\\ 11^1\mod 13 = 1\\ 11^2\mod 13 = 1\\ 11^3\mod 13 = 1\\ 11^4\mod 13 = 1\\ 11^4\mod 13 = 1\\ 11^4\mod 13 = 1\\ 11^4\mod 13 = 1\\ 11^4\mod 13 = 1\\ 11^4\mod 13 = 1\\\\$

Biv
  • 10k
  • 2
  • 42
  • 68