Paper Info
Title
Decomposed Attack for the Jacobian of a Hyperelliptic Curve over an Extension Field.
Abstract
We propose some kind of new attack which gives the solution of the discrete logarithm problem for the Jacobian of a curve defined over an extension field F-q(n), considering the set of the union of factor basis and large primes B-0 given by points of the curve whose x-coordinates lie in F-q. In this attack, an element of the divisor group which is written by a sum of some elements of factor basis and large primes is called (potentially) decomposed and the set of the factors that appear in the sum, is called decomposed factors. So, it will be called decomposition attack. In order. to analyze the running of the decomposition attack, a test for the (potential) decomposedness and the computation of the decomposed factors 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 decomposed factors and the computation of decomposed factors are reduced to the problem of solving some multivariable polynomial system of equations by using the Riemann-Roch theorem. In particular, in the case of hyperelliptic curves of genus g, we construct a concrete system of equations, which satisfies these properties and consists of (n(2) - 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.
Year
DOI
Venue
2010
10.1007/978-3-642-14518-6_23
ALGORITHMIC NUMBER THEORY
Keywords
DocType
Volume
Decomposition Attack,Hyperelliptic curve,Discrete logarithm problem,Weil descent attack
Conference
6197
ISSN
Citations 
PageRank 
0302-9743
5
0.44
References 
Authors
6
1
Name
Order
Citations
PageRank
Koh-Ichi Nagao1366.17