## CryptoDB

### Mitsuru Kawazoe

#### 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

Gr\"obner Basis Based Cryptanalysis of SHA-1
Abstract

Recently, Wang proposed a new method to cryptanalyze SHA-1
and found collisions of $58$-round SHA-1.
However many details of Wang's attack are still unpublished,
especially,
1) How to find differential paths?
2) How to modify messages properly?
For the first issue, some results have already been reported. In our article, we clarify the second issue and give a sophisticated method based on Gr\"obner basis techniques. We propose two algorithm based on the basic and an improved message modification techniques respectively. The complexity of our algorithm to find a collision for 58-round SHA-1 based on the basic message modification is $2^{29}$ message modifications and its implementation is equivalent to $2^{31}$ SHA-1 computation experimentally, whereas Wang's method needs $2^{34}$ SHA-1 computation. We propose an improved message modification and apply it to construct a more sophisticated algorithm to find a collision. The complexity to find a collision for 58-round SHA-1 based on this improved message modification technique is $2^8$ message modifications, but our latest implementation is very slow, equivalent to $2^{31}$ SHA-1 computation experimentally. However we conjecture that our algorithm can be improved by techniques of error correcting code and Gr\"obner basis. By using our methods, we have found many collisions for
$58$-round SHA-1.

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

Relation between XL algorithm and Groebner Bases Algorithms
Abstract

We clarify a relation between the XL algorithm and Groebner bases algorithms. The XL algorithm was proposed to be a more efficient algorithm to solve a system of equations with a special assumption without trying to calculate a whole Groebner basis. But in our result, it is shown that the XL algorithm is also a Groebner bases algorithm which can be represented as a redundant version of a Groebner bases algorithm F4 under the assumption in XL.

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

- Gwénolé Ars (1)
- Aya Comuta (1)
- Jean-Charles Faugère (1)
- Eisaku Furukawa (1)
- Mitsuhiro Haneda (1)
- Hideki Imai (4)
- Ludovic Perret (1)
- Makoto Sugita (4)
- Tetsuya Takahashi (4)