Reading about index calculus for discrete logarithm, I noticed that it works for $(\mathbb Z / p \mathbb Z)^*$. Is this the only situation in which it works? If not, please give examples of other situations in which index calculus works to solve discrete log.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Leonard Adleman and Jonathan DeMarrais's A Subexponential Algorithm for Discrete Logarithms over All Finite Fields (in Proceedings of Crypto 1993 and in Mathematics of Computation, 1993) states: «Our subexponential method for all finite fields actually consists of two algorithms. They both may be described as "index calculus" methods.» $\endgroup$– fgrieu ♦Commented Jul 2, 2023 at 17:11
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
There are a various situations where index calculus can be used to solve discrete logarithms. The classic index calculus of Western and Miller can be used for multiplicative subgroups of $(\mathbb Z/n\mathbb Z)^\times$, but is most often used in the prime case. In this case the factor base is small prime numbers when the problem is lifted to the integers/rationals. (The number field sieve generalises this to prime ideals of small norm when the problem is lifted to a number field).
It was noted that the same approach can work for multiplicative (sub)groups of finite fields of small characteristic, with the factor base being polynomials of small degree when the problem is lifted to the full polynomial ring of that characteristic. (Again the function field sieve of Adleman generalises this and recent work by Joux, Granger et al improves this dramatically).
Multiplicative groups in more general finite fields can be tackled by one or other generalised approach with the (extended) tower number field sieve of Barbulescu et al finding particularly good interpolations. The Menezes, Okamoto and Vanstone attack on elliptic curves with small embedding degree works by transferring the problem to such a setting.
Adleman, DeMarrais and Huang found a way to use index calculus methods to solve discrete logarithm in Jacobians of hyper elliptic curve of large genus over finite fields. The Weil descent attack of Gaudry, Hess and Smart showed that the discrete logarithm of some elliptic curves over fields of small characteristic and composite degree can be often be efficiently transferred to this setting.
The work of Gaudry and Diem proposes a different index calculus attack on fields of small characteristic.
I don't expect this list to be exhaustive. One might also consider the multi-target Pollard lambda/kangaroo attack to be an instance of index calculus with a completely arbitrary factor base for a generic cyclic group.
-
$\begingroup$ Thank you for your answer. Do any of these implementations beat the running time of the generic algorithm? $\endgroup$ Commented Jul 2, 2023 at 20:59
-
1$\begingroup$ I think that all of these are subexponential in some sense (barring the multi-target kangaroo) and so there are certainly problem instances where each one beats the "black box" attack. $\endgroup$– Daniel SCommented Jul 3, 2023 at 12:46
-
$\begingroup$ Can you confirm that none of these work in a well chosen elliptic curve over a prime field with a complexity beating the generic algorithm? $\endgroup$– kodluCommented Jul 4, 2023 at 2:27
-
1$\begingroup$ @kodlu none of the attacks will be better than the generic algorithm for an elliptic curve over a prime field with large embedding degree (such as NIST-P256, secp256k1 or Curve 25519). For some pairing-friendly curves where the embedding degree is quite small (e.g. BN-256), the MOV attack is superior to the generic algorithm in terms of computation, this is taken into account when standard pairing-friendly curves are selected. $\endgroup$– Daniel SCommented Jul 4, 2023 at 6:35
-
$\begingroup$ @DanielS yet, there s no index calculus algorithm that allow speeding a discrete logarithm computation if a range is known. So why pollard kangaroo is an instance of index calculus? $\endgroup$ Commented Aug 19 at 0:40