Paper 2007/112
Decomposed Attack for the Jacobian of a Hyperelliptic Curve over an Extension Field
Kohichi Nagao
Abstract
We study the solution of the discrete logarithm problem for the Jacobian of a curve of genus g defined over an extension field Fqn, by decomposed attack, considering a external elements B0 given by points of the curve whose xcoordinates are defined in Fq. In the decomposed attack, an element of the group which is written by a sum of some elements of external elements is called (potentially) decomposed and the set of the terms, that appear in the sum, is called decomposed factor. In order for the running of the decomposed attack, a test for the (potential) decomposeness and the computation of the decomposed factor are needed. Here, we show that the test to determine if an element of the Jacobian (i.e., reduced divisor) is written by an ng sum of the elements of the external elements and the computation of decomposed factor are reduced to the problem of solving some multivariable polynomial system of equations by using the RiemannRoch theorem. In particular, in the case of a hyperelliptic curve, we construct a concrete system of equations, which satisfies these properties and consists of (n2¡n)g quadratic equations. Moreover, in the case of (g; n) = (1; 3); (2; 2) and (3; 2), we give examples of the concrete computation of the decomposed factors by using the computer algebra system Magma.
Note: Many correction of minor errors
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Decomposed AttackHyperelliptic curveDiscrete logarithm problemWeil descent attack
 Contact author(s)
 nagao @ kantogakuin ac jp
 History
 20080210: last of 4 revisions
 20070403: received
 See all versions
 Short URL
 https://ia.cr/2007/112
 License

CC BY
BibTeX
@misc{cryptoeprint:2007/112, author = {Kohichi Nagao}, title = {Decomposed Attack for the Jacobian of a Hyperelliptic Curve over an Extension Field}, howpublished = {Cryptology ePrint Archive, Paper 2007/112}, year = {2007}, note = {\url{https://eprint.iacr.org/2007/112}}, url = {https://eprint.iacr.org/2007/112} }