The decomposition step is a major bottleneck in the effectiveness of the index-calculus algorithm for solving the discrete logarithm problem on the Jacobian of hyperelliptic curves with low genus, as it requires solving a nonlinear system of multivariate polynomial equations. Sarkar and Singh, in the year 2016, proposed a decomposition method for the curves, defined over quadratic extensions, which avoids solving multivariate polynomial systems. In this paper, building on the Sarkar-Singh work and using the cyclic group of the underlined extension field, we identify a class of weak curves for which the decomposition is easy to handle. In the new decomposition, we completely avoid solving the system of multivariate polynomial equations, and the time complexity remains the same as that of the Sarkar-Singh decomposition. The new decomposition applies to specific curves defined over extension fields. For a given random hyperelliptic curve, it can be efficiently checked whether this decomposition attack applies to it or not, using the discrete logarithms in the cyclic group of the underlying extension field. The discrete logarithm problem (DLP) over finite fields is generally easier than the DLP over the Jacobian of hyperelliptic curves. Therefore, we can reasonably assume that discrete logarithms over the underlying finite field are accessible. This assumption aids in determining whether the given curve is susceptible to this type of attack.
Security, Privacy, and Applied Cryptography Engineering (SPACE)
2026
2026-05-01