6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Jan 18 '16 at 22:25
5
$\begingroup$

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".

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Arnold Jan 18 '16 at 13:23
  • $\begingroup$ 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}$. $\endgroup$ – Biv Jan 18 '16 at 14:00
  • $\begingroup$ See clarification in OP. $\endgroup$ – Arnold Jan 18 '16 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.