If we allow DH operations in addition to exponentiation and multiplication can we get a lower bound for discrete logarithm?

Ask Question

Asked 9 months ago

Modified 9 months ago

Viewed 69 times

In https://crypto.stackexchange.com/questions/72969/proof-dlog-is-hard-in-generic-group-model/ it is shown if we allow only exponentiation and multiplication we can get an exponential complexity lower bound on discrete logarithm computation in the generic group model.

If in addition if we allow Diffie-Hellman operations as well, would there be any sort of exponential lower bound in the generic group model?

edited Mar 20 at 8:24

asked Mar 20 at 3:35

Turbo

13.9k1 gold badge27 silver badges76 bronze badges

$\begingroup$ Could you clarify what you mean by Diffie-Hellman operations? $\endgroup$
– Daniel Weber
Commented Mar 20 at 3:49
$\begingroup$ @CommandMaster: the Diffie-Hellman operation is: with inputs $G^a, G^b$, compute the value $G^{ab}$. Quite common when talking about crypto; probably less so in general math... $\endgroup$
– poncho
Commented Mar 20 at 4:51
1

$\begingroup$ The paper "Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms" by Maurer seems to suggest that for many cases it's fairly easy (although you do need a short advice string) $\endgroup$
– Daniel Weber
Commented Mar 20 at 5:03
$\begingroup$ @CommandMaster I do not think the result is in Shoup's generic group model as you are talking about many 'cases' which means Maurer uses structure of the group and not a generic model. $\endgroup$
– Turbo
Commented Mar 20 at 8:24
1

$\begingroup$ It uses the size of the group and it being abelian, from what I could see, that's it $\endgroup$
– Daniel Weber
Commented Mar 20 at 12:13

Add a comment |

0