## CryptoDB

### Masaaki Shirase

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Solving a 676-bit Discrete Logarithm Problem in $GF(3^{6n})$
Abstract

Pairings on elliptic curves over finite fields are crucial for constructing various cryptographic schemes. The \eta_T pairing on supersingular curves over GF(3^n) is particularly popular since it is efficiently implementable. Taking into account the Menezes-Okamoto-Vanstone (MOV) attack, the discrete logarithm problem (DLP) in GF(3^{6n}) becomes a concern for the security of cryptosystems using \eta_T pairings in this case. In 2006, Joux and Lercier proposed a new variant of the function field sieve in the medium prime case, named JL06-FFS. We have, however, not yet found any practical implementations on JL06-FFS over GF(3^{6n}). Therefore, we first fulfilled such an implementation and we successfully set a new record for solving the DLP in GF(3^{6n}), the DLP in GF(3^{6 \cdot 71}) of 676-bit size. In addition, we also compared JL06-FFS and an earlier version, named JL02-FFS, with practical experiments. Our results confirm that the former is several times faster than the latter under certain conditions.

2010

EPRINT

Barreto-Naehrig Curve With Fixed Coefficient - Efficiently Constructing Pairing-Friendly Curves -
Abstract

This paper describes a method for constructing Barreto-Naehrig (BN) curves and twists of BN curves that are pairing-friendly and have the embedding degree $12$ by using just primality tests without a complex multiplication (CM) method.
Specifically, this paper explains that the number of points of elliptic curves $y^2=x^3\pm 16$ and $y^2=x^3 \pm 2$ over $\Fp$ is given by 6 polynomials in $z$, $n_0(z),\cdots, n_5(z)$, two of which are irreducible, classified by the value of $z\bmod{12}$ for a prime $p(z)=36z^4+36z^3+24z^2+6z+1$ with $z$ an integer.
For example, elliptic curve $y^2=x^3+2$ over $\Fp$ always becomes a BN curve for any $z$ with $z \equiv 2,11\!\!\!\pmod{12}$.
Let $n_i(z)$ be irreducible.
Then, to construct a pairing-friendly elliptic curve, it is enough to find an integer $z$ of appropriate size such that $p(z)$ and $n_i(z)$ are primes.

2008

EPRINT

FPGA and ASIC Implementations of the $\eta_T$ Pairing in Characteristic Three
Abstract

Since their introduction in constructive cryptographic applications, pairings over (hyper)elliptic curves are at the heart of an ever increasing number of protocols. As they rely critically on efficient algorithms and implementations of pairing primitives, the study of hardware accelerators became an active research area.
In this paper, we propose two coprocessors for the reduced $\eta_T$ pairing introduced by Barreto {\it et al.} as an alternative means of computing the Tate pairing on supersingular elliptic curves. We prototyped our architectures on FPGAs. According to our place-and-route results, our coprocessors compare favorably with other solutions described in the open literature. We also present the first ASIC implementation of the reduced $\eta_T$ pairing.

2008

EPRINT

Analysis and Improvement of Authenticatable Ring Signcryption Scheme
Abstract

Ring signcryption is an anonymous signcryption which allows a user
to anonymously signcrypt a message on behalf of a set of users
including himself. In an ordinary ring signcryption scheme, even if
a user of the ring generates a signcryption, he also cannot prove
that the signcryption was produced by himself. In 2008, Zhang, Yang,
Zhu, and Zhang solve the problem by introducing an identity-based
authenticatable ring signcryption scheme (denoted as the ZYZZ
scheme). In the ZYZZ scheme, the actual signcrypter can prove that
the ciphertext is generated by himself, and the others cannot
authenticate it. However, in this paper, we show that the ZYZZ
scheme is not secure against chosen plaintext attacks. Furthermore,
we propose an improved scheme that remedies the weakness of the ZYZZ
scheme. The improved scheme has shorter ciphertext size than the
ZYZZ scheme. We then prove that the improved scheme satisfies
confidentiality,
unforgeability, anonymity and authenticatability.

2007

EPRINT

A Coprocessor for the Final Exponentiation of the $\eta_T$ Pairing in Characteristic Three
Abstract

Since the introduction of pairings over (hyper)elliptic curves in
constructive cryptographic applications, an ever increasing number of
protocols based on pairings have appeared in the literature. Software
implementations being rather slow, the study of hardware architectures
became an active research area. Beuchat et al. proposed for
instance a coprocessor which computes the characteristic three
$\eta_T$ pairing, from which the Tate pairing can easily be derived,
in $33$\,$\mu$s on a Cyclone II FPGA. However, a final exponentiation
is required to ensure a unique output value and the authors proposed
to supplement their $\eta_T$ pairing accelerator with a coprocessor
for exponentiation. Thus, the challenge consists in designing the
smallest possible piece of hardware able to perform this task in less
than $33$\,$\mu$s on a Cyclone~II device. In this paper, we propose a
novel arithmetic operator implementing addition, cubing, and
multiplication over $\mathbb{F}_{3^{97}}$ and show that a coprocessor
based on a single such operator meets this timing constraint.

2007

EPRINT

A Refined Algorithm for the $\eta_T$ Pairing Calculation in Characteristic Three
Abstract

We describe further improvements of the $\eta_T$ pairing algorithm in
characteristic three. Our approach combines the loop unrolling
technique introduced by Granger {\em et. al} for the Duursma-Lee
algorithm, and a novel algorithm for multiplication over
$\mathbb{F}_{3^{6m}}$ proposed by Gorla {\em et al.} at SAC 2007. For
$m=97$, the refined algorithm reduces the number of multiplications
over $\mathbb{F}_{3^m}$ from $815$ to $692$.

2007

EPRINT

Algorithms and Arithmetic Operators for Computing the $\eta_T$ Pairing in Characteristic Three
Abstract

Since their introduction in constructive cryptographic applications,
pairings over (hyper)elliptic curves are at the heart of an ever
increasing number of protocols. Software implementations being rather
slow, the study of hardware architectures became an active research
area.
In this paper, we discuss several algorithms to compute the $\eta_T$
pairing in characteristic three and suggest further improvements.
These algorithms involve addition, multiplication, cubing, inversion,
and sometimes cube root extraction over $\mathbb{F}_{3^m}$. We propose
a hardware accelerator based on a unified arithmetic operator able to
perform the operations required by a given algorithm. We describe the
implementation of a compact coprocessor for the field
$\mathbb{F}_{3^{97}}$ given by $\mathbb{F}_3[x]/(x^{97}+x^{12}+2)$,
which compares favorably with other solutions described in the open
literature.

2006

EPRINT

An Algorithm for the $\eta_T$ Pairing Calculation in Characteristic Three and its Hardware Implementation
Abstract

In this paper, we propose a modified $\eta_T$ pairing algorithm in
characteristic three which does not need any cube root extraction. We
also discuss its implementation on a low cost platform which hosts an
Altera Cyclone~II FPGA device. Our pairing accelerator is ten times
faster than previous known FPGA implementations in characteristic
three.

2006

EPRINT

Some Efficient Algorithms for the Final Exponentiation of $\eta_T$ Pairing
Abstract

Recently Tate pairing and its variations are attracted in cryptography. Their operations consist of a main iteration loop and a final exponentiation. The final exponentiation is necessary for generating a unique value of the bilinear pairing in the extension fields. The speed of the main loop has become fast by the recent improvements, e.g., the Duursma-Lee algorithm and $\eta_T$ pairing. In this paper we discuss how to enhance the speed of the final exponentiation of the $\eta_T$ pairing in the extension field ${\mathbb F}_{3^{6n}}$. Indeed, we propose some efficient algorithms using the torus $T_2({\mathbb F}_{3^{3n}})$ that can efficiently compute an inversion and a powering by $3^{n}+1$. Consequently, the total processing cost of computing the $\eta_T$ pairing can be reduced by 17% for n=97.

#### Coauthors

- Jean-Luc Beuchat (5)
- Nicolas Brisebarre (2)
- Jérémie Detrey (1)
- Hiroshi Doi (1)
- Kaoru Fujita (1)
- Takuya Hayashi (2)
- Atsuo Inomata (1)
- Akira Kanaoka (1)
- Masayoshi Katouno (1)
- Fagen Li (1)
- Masahiro Mambo (1)
- Shin'ichiro Matsuo (2)
- Takeshi Okamoto (1)
- Eiji Okamoto (6)
- Takaaki Shiga (1)
- Naoyuki Shinohara (2)
- Ryuji Soga (1)
- Tsuyoshi Takagi (9)
- Ananda Vithanage (1)
- Lihua Wang (2)
- Hiroyasu Yamamoto (1)