EFFICIENT ARITHMETIC ON HYPERELLIPTIC CURVES WITH REAL REPRESENTATION

We discuss arithmetic in the Jacobian of a hyperelliptic curve C of genus g. The traditional approach is to fix a point P at infinity in C and represent divisor classes in the form E − dP . We propose a different representation which is balanced at infinity. The resulting arithmetic is more efficient than previous approaches when there are 2 points at infinity. The geometric framework presented in this analysis is then used to give a new interpretation of the infrastructure associated to a hyperelliptic curve. We prove that there is a natural injection from the set of infrastructure ideals to the class group of the corresponding curve, and use this result to give very precise results relating the difficulty of computing the distance of an arbitrary infrastructure ideal to the discrete logarithm problem in the curve. The efficient arithmetic on hyperelliptic curves afforded by our proposal is used to efficiently implement pairings. We present several optimisation ideas that allow us to conclude that pairings can be efficiently computable in real models of hyperelliptic curves. We present an attack on one of the hidden pairing schemes proposed by Dent and Galbraith. We drastically reduce the number of variables necessary to perform a multivariate attack and in some cases we can completely recover the private key. Our attack relies only on knowledge of the public system parameters. Finally, we present ideas relating the pairing inversion problem and the discrete logarithm problem on an elliptic curve. This is done using the reduction from the DLP to the Diffie-Hellman problem developed by Boneh, Lipton, Maurer and Wolf. This approach fails when only one of the pairing inversion problems can be solved. In this case we use Cheon’s algorithm to get a reduction.