Sorina Ionica (Université de Picardie) Index Calculus Attacks on Hyperelliptic Jacobians with Effective Endomorphisms

Abstract: In curve-based cryptography, the existence of efficiently computable endomorphisms on the Jacobian of the curve results into improved scalar multiplication algorithms and fast implementations. Unfortunately, as it is often the case with extra algebraic structure in cryptography, this comes with a price to pay in terms of security. In 1999 Duursma, Gaudry, Morain showed how to use the automorphisms of the curve to speed up Pollard’s rho method on Jacobians of hyperelliptic curves. We show that similar considerations apply to the index calculus attack, which is the state-of-the-art algorithm for hyperelliptic curves defined over extension fields. 
We exploit the existence of certain endomorphisms on the Jacobian  to reduce the size of the factorization basis in this attack. This approach adds an extra cost when performing operations on the factor basis, but our benchmarks show that reducing the size of the factor basis allows to have  a gain on the total complexity of index calculus algorithm with respect to classical attacks, on several families of hyperelliptic curves of small genus.  This is joint work with Sulamithe Tsakou.