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
-
2$\begingroup$ maybe this post can help you. crypto.stackexchange.com/questions/54345/… $\endgroup$– OneUserCommented May 25, 2020 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$– LinusKCommented May 26, 2020 at 11:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$– LinusKCommented Sep 17, 2020 at 17:18