## CryptoDB

### Tetsuya Takahashi

#### Affiliation: Osaka Prefecture University

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Pairing-friendly Hyperelliptic Curves with Ordinary Jacobians of Type $y^2=x^5+ax$
Abstract

An explicit construction of pairing-friendly hyperelliptic curves with ordinary Jacobians
was firstly given by D.~Freeman. In this paper, we give other explicit constructions of pairing-friendly hyperelliptic curves with ordinary Jacobians based on the closed formulae
for the order of the Jacobian of a hyperelliptic curve of type $y^2=x^5+ax$. We present two methods in this paper. One is an analogue of the Cocks-Pinch method and the other is a cyclotomic method. By using these methods, we construct a pairing-friendly hyperelliptic curve $y^2=x^5+ax$ over a finite prime field ${¥mathbb F}_p$ whose Jacobian is ordinary and simple over ${¥mathbb F}_p$ with a prescribed embedding degree. Moreover, the analogue of the Cocks-Pinch produces curves with $¥rho¥approx 4$ and the cyclotomic method produces curves with $3¥le ¥rho¥le 4$.

2006

EPRINT

Pairing-friendly elliptic curves with small security loss by Cheon's algorithm
Abstract

Pairing based cryptography is a new public key cryptographic scheme. An elliptic curve suitable for pairing based cryptography is called a ``pairing-friendly'' elliptic curve. After Mitsunari, Sakai and Kasahara's traitor tracing scheme and Boneh and Boyen's short signature scheme, many protocols based on pairing-related problems such as the $q$-weak Diffie-Hellman problem have been proposed.
In Eurocrypt 2006, Cheon proposed a new efficient algorithm to solve pairing-related problems and recently the complexity of Cheon's algorithm has been improved by Kozaki, Kutsuma and Matsuo.
Due to these two works, an influence of Cheon's algorithm should be considered when we construct a suitable curves for the use of a protocol based on a pairing-related problem.
Among known methods for constructing pairing-friendly elliptic curves, ones using cyclotomic polynomials such as the Brezing-Weng method and the Freeman-Scott-Teske method are affected by Cheon's algorithm.
In this paper, we study how to reduce a security loss of a cyclotomic family by Cheon's algorithm. The proposed method constructs many pairing-friendly elliptic curves with small security loss by Cheon's algorithm suitable for protocols based on pairing-related problems.

2004

EPRINT

Suitable Curves for Genus-4 HCC over Prime Fields: Point Counting Formulae for Hyperelliptic Curves of type $y^2=x^{2k+1}+ax$
Abstract

Computing the order of the Jacobian group of a hyperelliptic curve
over a finite field is very important to construct
a hyperelliptic curve cryptosystem (HCC), because
to construct secure HCC, we need Jacobian groups of order in the form
$l(J\(Bcdot c$ where $l$ is a prime greater than about $2^{160}$ and
$c$ is a very small integer.
But even in the case of genus two,
known algorithms to compute the order of a Jacobian group for a general curve
need a very long running time over a large prime field.
In the case of genus three, only a few examples of suitable curves for HCC are known.
In the case of genus four, no example has been known over a large prime field.
In this article, we give explicit formulae of the order of Jacobian groups for
hyperelliptic curves over a finite prime field of type $y^2=x^{2k+1}+a x$,
which allows us to search suitable
curves for HCC. By using these formulae,
we can find many suitable curves for genus-4 HCC and show some examples.

2002

EPRINT

Counting Points for Hyperelliptic Curves of type $y^2=x^5+ax$ over Finite Prime Fields
Abstract

Counting rational points on Jacobian varieties of hyperelliptic curves
over finite fields is very important for constructing
hyperelliptic curve cryptosystems (HCC),
but known algorithms for general curves over given large prime
fields need very long running times.
In this article, we propose an extremely fast point counting algorithm for
hyperelliptic curves of type $y^2=x^5+ax$ over given large
prime fields $\Fp$, e.g. 80-bit fields.
For these curves, we also determine the necessary condition
to be suitable for HCC, that is, to satisfy that the order
of the Jacobian group is of the form $l\cdot c$ where $l$
is a prime number greater than about $2^{160}$ and
$c$ is a very small integer.
We show some examples of suitable curves for HCC obtained by
using our algorithm.
We also treat curves of type $y^2=x^5+a$ where $a$ is not
square in $\Fp$.

#### Coauthors

- Aya Comuta (1)
- Eisaku Furukawa (1)
- Mitsuhiro Haneda (1)
- Mitsuru Kawazoe (4)