Index calculus attacks on hyperelliptic Jacobians with efficient endomorphisms

Abstract

For a hyperelliptic curve defined over a finite field GF(qⁿ) with n > 1, the discrete logarithm problem is subject to index calculus attacks. We exploit the endomorphism of the Jacobian to reduce the size of the factorization base and improve the complexity of the index calculus attack for certain families of ordinary elliptic curves and genus 2 hyperelliptic Jacobians defined over finite fields. This approach adds an extra cost when performing operations on the factor base, but the benchmarks show that reducing the size of the factor base allows to have a gain on the total complexity of index calculus algorithm with respect to the original attack.