1-7hit |
Seigo ARITA Kazuto MATSUO Koh-ichi NAGAO Mahoro SHIMURA
This paper proposes a Weil descent attack against elliptic curve cryptosystems over quartic extension fields. The scenario of the attack is as follows: First, one reduces a DLP on a Weierstrass form over the quartic extention of a finite field k to a DLP on a special form, called Scholten form, over the same field. Second, one reduces the DLP on the Scholten form to a DLP on a genus two hyperelliptic curve over the quadratic extension of k. Then, one reduces the DLP on the hyperelliptic curve to one on a Cab model over k. Finally, one obtains the discrete-log of original DLP by applying the Gaudry method to the DLP on the Cab model. In order to carry out the scenario, this paper shows that many of elliptic curve discrete-log problems over quartic extension fields of odd characteristics are reduced to genus two hyperelliptic curve discrete-log problems over quadratic extension fields, and that almost all of the genus two hyperelliptic curve discrete-log problems over quadratic extension fields of odd characteristics come under Weil descent attack. This means that many of elliptic curve cryptosystems over quartic extension fields of odd characteristics can be attacked uniformly.
This paper gives an efficient algorithm to compute addition in Jacobian of C34 curves, aiming at C34 curve cryptosystems. Using C34 curves for cryptosystems has two advantages. The first is safety and the second is the short size of the base field. In the paper, we modify the addition algorithm of for Cab curves in the specific manner to C34 curves. We classify all of the forms of the Groebner bases of ideals involved in the algorithm and eliminate the use of Buchberger algorithm from it. Our resulting algorithm computes the addition in Jacobian of C34 curves in about 3 times amount of computation of the one in elliptic curves, when the sizes of groups are set to be the same.
This paper proposes a heuristic algorithm which, given a basis of a subspace of the space of cuspforms of weight 2 for 0(N) which is invariant for the action of the Hecke operators, tests whether the subspace corresponds to a quotient A of the jacobian of the modular curve X0(N) such that A is the jacobian of a curve C. Moreover, equations for such a curve C are computed which make the quotient suitable for applications in cryptography. One advantage of using such quotients of modular jacobians is that fast methods are known for finding their number of points over finite fields.
The goal of this paper is to describe a practical and efficient algorithm for computing in the Jacobian of a large class of algebraic curves over a finite field. For elliptic and hyperelliptic curves, there exists an algorithm for performing Jacobian group arithmetic in O(g2) operations in the base field, where g is the genus of a curve. The main problem in this paper is whether there exists a method to perform the arithmetic in more general curves. Galbraith, Paulus, and Smart proposed an algorithm to complete the arithmetic in O(g2) operations in the base field for the so-called superelliptic curves. We generalize the algorithm to the class of Cab curves, which includes superelliptic curves as a special case. Furthermore, in the case of Cab curves, we show that the proposed algorithm is not just general but more efficient than the previous algorithm as a parameter a in Cab curves grows large.
Gaudry has described a new algorithm (Gaudry's variant) for the discrete logarithm problem (DLP) in hyperelliptic curves. For a hyperelliptic curve of a small genus on a finite field GF(q), Gaudry's variant solves for the DLP in time O(q2+ε). This paper shows that Cab curves can be attacked with a modified form of Gaudry's variant and presents the timing results of such attack. However, Gaudry's variant cannot be effective in all of the Cab curve cryptosystems. This paper also provides an example of a Cab curve that is unassailable by Gaudry's variant.
When we have a singular Cab curve with many rational points, we had better to construct linear codes on its normalization rather than the original curve. The only obstacle to construct linear codes on the normalization is finding a basis of L( Q) having pairwise distinct pole orders at Q, where Q is the unique place of the Cab curve at infinity. We present an algorithm finding such a basis from defining equations of the normalization of the original Cab curve.
In Adleman's Function Field Sieve algorithm solving the discrete logarithm problem in a finite field, it is assumed that a random bivariate polynomial in the certain class is absolutely irreducible with high probability. In this letter we point out that if we use Cab type random polynomials then we always get absolutely irreducible polynomials. We can also simplify the calculation of a product of many rational functions on a curve that belongs to the field of definition by the use of a Cab curve.