The complexity of computing discrete logarithms in a multiplicative group modulo a prime $p$ is assumed to be sub-exponential time. The complexity is determined by $q$, the biggest factor of the group order $p-1$. Is there any group $\mathbb{Z}_p^*$ such that discrete logarithms are easier than subexponential in $q$?

  • 2
    $\begingroup$ maybe this post can help you. crypto.stackexchange.com/questions/54345/… $\endgroup$ – OneUser May 25 '20 at 23:31
  • $\begingroup$ @OneUser but this discusses only weaknesses in form of small subgroups. I wondered if there is any field in which the dlog is easier than sub-exponential in the largest subgroup order. $\endgroup$ – LinusK May 26 '20 at 11:26

As far as I am aware, all the recent progress on discrete log algorithms which derived pseudopolynomial efficiencies took place for the case of small characteristic fields $GF(p^n)$ with a structured exponent $n$. So the best complexity is still exponential in $\log N$ where $N$ is the size of the subgroup under consideration. So nothing better than generic DL complexity seems to be known.

You may find the following interesting. Bernstein and Lange have shown advances for generic discrete logs for the case that preprocessing is allowed, e.g., for curves in standards.

Even there, the online phase complexity seems to be $\geq (\log N)^{1/3}.$ See this paper for a discussion. Here is a quote:

In practice, however, an adversary may have access to the description of the group $G$ long before it has to solve a discrete-log problem instance. In particular, the vast majority of real-world cryptosystems use one of a handful of groups, such as NIST P-256, Curve25519, or the DSA groups.

  • $\begingroup$ Would it be surprising if there was a polynomial time algorithm solving dlogs in very small subgroups of finite fields e.g. $C_{7}$ or $C_{11}$ ? $\endgroup$ – LinusK Sep 17 '20 at 17:18

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.