Skip to main content
4 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 = 11$
$11^2\mod 13 = 4$
$11^3\mod 13 = 5$
$11^4\mod 13 = 3$
$11^5\mod 13 = 7$
$11^6\mod 13 = 12$
$11^7\mod 13 = 2$
$11^8\mod 13 = 9$
$11^9\mod 13 = 8$
$11^{10}\mod 13 = 10$
$11^{11}\mod 13 = 6$
$11^{12}\mod 13 = 1$
And we have :
$g^0\mod 13 = 1$
$g^q \mod 13 = 11^3 \mod 13 = 5$
$g^{2q} \mod 13 = 11^6 \mod 13 = 12$
$g^{3q} \mod 13 = 11^9 \mod 13 = 8$
$g^{4q} \mod 13 = 11^{12} \mod 13 = 1$
Therefore $<G, \times> = \{1,5,8,12\}$.
You can clearly see that $\forall g \in G, g + 1 \notin G$ with $+$ as an addition even if $a + 1 \in \mathbb{Z}/p\mathbb{Z}$.

Biv
  • 10k
  • 2
  • 42
  • 68