# The difficulty of computing discrete logs

I understand that in Diffie-Hellman it should be hard to compute $a$ given $g$ and $g^a$.

In computational Diffie-Hellman, it appears to be hard to compute $(g^{ab})$ from $g^a$ and $g^b$.

As for the field, please consider $\mathbb F_p^*$ for this question.

Is it also difficult to compute the discrete log $w$ of more trivial things, such as $g^w\equiv (g^a+1)^b\pmod p$? It may be assumed that $a,b,g$ and $p$ are given.

-
Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Jan 18 at 22:25

I will assume for simplicity that you're talking about the full multiplicative group of $F_p$ instead of a proper subgroup, thus there are no problems with $g^a+1$ (except when $g^a=p-1$ which can be trivially ruled out by comparing to $p$).

The quantity $\log_g(g^a+1)$ is sometimes referred to as the Zech logarithm (strictly speaking, it is defined for characteristic 2, but can be defined here as well).

So let's define $Z(a)=\log_g(g^a-1)$ and note that it sets up a one-to-one correspondence between $a$ and $Z(a)$. Thus the difficulty of discrete logs is not really changed by introducing the kind of twist you ask about, in your reference to "trivial things".

I can't dig out the reference now, but there was a paper years ago by a French author, in a crypto related conference or journal, on whether precomputing Zech's logarithms on some subset of $F_p^{\ast}$ helped with discrete logarithms. The answer was, "not so much".

-
Great answer thanks – Arnold Jan 19 at 23:14

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

-
Hi. I mean the discrete log with respect to $g$. eg., find a $w$ such that $g^w=(g^{a}+1)^b$. Is this hard (assuming +1 is well-defined in the group)? – Arnold Jan 18 at 13:23
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^b \in G, a + 1 = g^{b+1}$. – Biv Jan 18 at 14:00
See clarification in OP. – Arnold Jan 18 at 15:34