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.
Choisissez le fuseau horaire
Le fuseau horaire de votre profil:
