Return to Answer

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.

3. 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}$.

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.

3. 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}$.

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.

3. 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\\\\$

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.

3. 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}$.

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.

3. 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).

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.

3. 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\\\\$