Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
    
Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Jan 18 at 22:25
up vote 5 down vote accepted

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

share|improve this answer
    
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}$.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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