UC Berkeley

The Discrete Logarithm Problem (DLP) in the abelian group $E(\mathbb{F}_p)$ of $\mathbb{F}_p$-valued points on an elliptic curve $E/\mathbb{F}_p$ has been successfully used as a building block for a wide variety of both public key encryption schemes and digital signature schemes. Since the size of $E(\mathbb{F}_p)$ is roughly $p$, to have a security level of at least $80$ bits against generic collision attacks, such as Pollard rho, one must take $p$ to be at least $160$ bits.

Neil Koblitz suggested using instead the group of $\mathbb{F}_p$-valued points on the Jacobian $\operatorname{Jac}_C$ of a genus $g$ hyperelliptic curve $C/\mathbb{F}_p$. The upshot is that the size of $\operatorname{Jac}_C(\mathbb{F}_p)$ is roughly $p^g$, so to obtain a security level of $80$ bits against Pollard rho one needs to take $p$ to be at least $160/g$ bits.

When $g=2$ everything works out well. As in the case of elliptic curves, the most efficient known attack against the DLP is Pollard rho, which runs in time $\widetilde{O}(p)$. There are very efficient ways of doing arithmetic on the Jacobian of a genus $2$ curve (or rather on the Kummer surface), and with the increase in efficiency coming from using smaller fields ($p$ at least $80$ bits), such genus $2$ cryptosystems are fast enough to be competitive with elliptic curve cryptosystems.

When $g>3$ there is an efficient index calculus algorithm for breaking the DLP, which is why such curves are not considered to be useful for cryptographic purposes. Moreover, there is no efficient enough way of doing arithmetic on such high-dimensional Jacobians.

When $g=3$ the situation is much more complicated. There is an index calculus algorithm which breaks the DLP on the Jacobian of a hyperelliptic genus $3$ curve in time $\widetilde{O}(p^{4/3})$. Note for comparison that Pollard rho runs in time $\widetilde{O}(p^{3/2})$. For practical field sizes ($p$ at least $60$ bits) the difference between these complexities is quite significant. Nevertheless, this index calculus algorithm might not be fast enough to be a significant threat and the practicality of the attack is highly debatable. But genus $3$ hyperelliptic curves suffer also from another much worse security problem. Namely, it might be possible to compute an isogeny from the hyperelliptic Jacobian to another isogenous abelian variety, which has a good chance of being the Jacobian of a non-hyperelliptic genus $3$ curve over the same base field. If such an isogeny can be computed explicitly enough, the DLP can be mapped to the Jacobian of the non-hyperelliptic curve and solved using an even faster index calculus algorithm by Claus Diem, with complexity $\widetilde{O}(p)$. This sounds bad, but again the practicality of Diem's attack is debatable. The main problem turns out to be that both the hyperelliptic $\widetilde{O}(p^{4/3})$ and the non-hyperelliptic $\widetilde{O}(p)$ algorithms require vast amounts of memory. Therefore the security of genus $3$ hyperelliptic curves depends strongly on the practical performance of Diem's index calculus and the feasibility of computing isogenies explicity.

We develop and study, both in theory and in practice, a new index calculus algorithm for attacking non-hyperelliptic genus $3$ curves. Our attack is related to Diem's index calculus, but improves it in several aspects. We obtain detailed space and time complexity estimates for our algorithm, making all hidden factors in the $\widetilde{O}$-notation explicit. We discuss time-memory trade-offs and practical ways of dealing with the massive memory requirements. Finally we discuss ways of generating hyperelliptic genus $3$ curves in such a way that performing isogeny attacks becomes particularly difficult. This is done by generating input data for the genus $3$ CM method of Weng in a very careful way, allowing us to precisely control which isogenies the attacker can use to reach non-hyperelliptic Jacobians.