## CryptoDB

### Tsuyoshi Takagi

#### Affiliation: Kyushu University

#### Publications

**Year**

**Venue**

**Title**

2016

EUROCRYPT

2014

PKC

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

On the Public Key Replacement and Universal Forgery Attacks of Short Certificateless Signature
Abstract

Certificateless cryptography eliminates the need of certificates in the PKI and solves the inherent key escrow problem in the ID-based cryptography. Recently, Du and Wen proposed a short certi¯cateless signature scheme without MapToPoint hash function, and the signature size is short enough with only half of the DSA signature. In this paper, after the detailing the formal of certificateless signature scheme, we show that the Du and Wen's short certificateless signature scheme is insecure which is broken by a type-I adversary who has the ability in replacing users' public keys and accessing to the signing oracles, and it also cannot resist on the universal forgery attack
for any third user.

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

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

Efficient Implementation of the Pairing on Mobilephones using BREW
Abstract

Pairing based cryptosystems can accomplish novel security applications such as ID-based cryptosystems, which have not been constructed efficiently without the pairing. The processing speed of the pairing based cryptosystems is relatively slow compared with the other conventional public key cryptosystems. However, several efficient algorithms for computing the pairing have been proposed, namely Duursma-Lee algorithm and its variant $\eta_T$ pairing.
In this paper, we present an efficient implementation of the pairing over some mobilephones. The processing speed of our implementation in ARM9 processors on BREW achieves under 100 milliseconds using the supersingular curve over $\mathbb F_{3^{97}}$. It has become efficient enough to implement security applications, such as ID-based cryptosystems and broadcast encryption, using the pairing on BREW mobilephones.

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

Side Channel Attacks and Countermeasures on Pairing Based Cryptosystems over Binary Fields
Abstract

Pairings on elliptic curves have been used as cryptographic
primitives for the development of new applications such as
identity based schemes. For the practical applications, it is
crucial to provide efficient and secure implementations of the
pairings. There have been several works on efficient
implementations of the pairings. However, the research for secure
implementations of the pairings has not been thoroughly
investigated. In this paper, we investigate vulnerability of the
pairing used in some pairing based protocols against side channel
attacks. We propose an efficient algorithm secure against such
side channel attacks of the eta pairing using randomized
projective coordinate systems for the pairing computation.

2006

EPRINT

Efficient Implementation of Tate Pairing on a Mobile Phone using Java
Abstract

Pairing-based cryptosystems (PBC) have been attracted by researchers in cryptography. Some implementations show that PBC are relatively slower than the standard public key cryptosystems. We present an efficient implementation for computing Tate pairing on a mobile phone using Java.
We implemented the $\eta_T$ pairing (a recent efficient variation of
Duursma-Lee algorithm) over some finite fields of characteristic 3 with extension degree $m= \{ 97, 167, 193, 239 \}$. Our optimized implementation for $m=97$ achieved about 0.5 seconds for computing Tate pairing over FOMA SH901iS, NTT DoCoMo. Then our implementation of Tate pairing is compared in the same platform with other Java program of the standard cryptosystems, i.e., RSA cryptosystem and elliptic curve cryptosystem (ECC). The computation speed of Tate pairing is comparable to that of RSA or ECC on the same mobile device.

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.

2005

EPRINT

One-Wayness Equivalent to General Factoring
Abstract

This paper shows the first practical semantically secure public-key encryption scheme such that its one-wayness is equivalent to
{\it general} factoring in the {\it standard} model (in the sense of IND-CPA).
Next our proof technique is applied to Rabin-Paillier encryption scheme and a variant of RSA-Paillier encryption scheme to prove their exactly tight one-wayness.

2005

EPRINT

Some Explicit Formulae of NAF and its Left-to-Right Analogue
Abstract

Non-Adjacent Form (NAF) is a canonical form of signed binary representation of integers. We present some explicit formulae of NAF and its left-to-right analogue (FAN) for randomly chosen n-bit integers. Interestingly, we prove that the zero-run length appeared in FAN is asymptotically 16/7, which is longer than that of the standard NAF. We also apply the proposed formulae to the speed estimation of elliptic curve cryptosystems.

2005

EPRINT

Some Analysis of Radix-r Representations
Abstract

We deal with the radix-r representation used for the scalar
multiplication of pairing-based cryptosystems with characteristic
r. Our goal of this paper is to present some invariant
properties about the signed radix-r representation; (1)
approximation formulae for the average significant length and the
average hamming weight of gNAF and wrNAF representation, (2)
some classification formulae of equivalent classes called as
Cutting Lemma, Collision Lemma, and Search Space Theorem. We also
analyze the security of signed radix-r representations in the
sense of side channel attacks, and to this end we propose a secure
countermeasure.

2005

EPRINT

Collision Attack on XTR and a Countermeasure with a Fixed Pattern
Abstract

Public-key cryptosystem (PKC) is one of inevitable key
technologies in order to accomplish fruitful security applications
in ubiquitous computing systems. The ubiquitous computer only has
scarce computational resources (like Smart cards, RFID, Sensor
Network), however, so that the light weight PKC is necessary for
those miniaturized low-power devices. Recently, XTR is considered
as one of good candidates for more energy efficient cryptosystems.
Among XTR exponentiation algorithms, the most efficient one is the
Improved XTR Single Exponentiation (XTR-ISE) proposed by
Stam-Lenstra. Thus among the family of XTR algorithms, XTR-ISE is
the most efficient one suitable for ubiquitous computer. Even
though the security of such devices against side channel attacks
is very dangerous, there are few works on side channel attacks
against XTR-ISE. In this paper we propose a new collision attack
on XTR-ISE, derived from the structural properties of XTR-ISE. The
analysis complexity of the proposed one is about 2^{40} where
the key size is 160-bit, which is 55% improvement from the
previously best known analysis of Page-Stam. We also propose a
novel countermeasure using a fixed pattern which is secure against
SPA. We deploy a variant of Euclidean algorithm whose one of the
registers is a monotone decreasing function with odd value. From
our estimation of the efficiency of the proposed method, XTR
exponentiation, computing Tr(g^n) with Tr(g) and n, takes
11.2log_2n multiplications in F_{p^2}. In the sense
of both efficiency and security the proposed countermeasure is the
best one among the previous countermeasures- it is about 30%
faster.

2005

EPRINT

Efficient Arithmetic on Subfield Elliptic Curves over Small Odd Characteristics
Abstract

In elliptic curve cryptosystems, scalar multiplications performed on the curves have much effect on the efficiency of the schemes, and many efficient methods have been proposed. In particular, recoding methods of the scalars play an important role in the performance of the algorithm used. For integer radices, non-adjacent form (NAF) and its generalizations (e.g., generalized non-adjacent form (GNAF) and radix-$r$ non-adjacent form ($r$NAF) \cite{CL73,TYW04}) are proposed for minimizing the non-zero densities in the representations of the scalars. On the other hand, for subfield elliptic curves, Frobenius-adic expansions of the scalars can be used for improving efficiency (\cite{Sma99+}). Unfortunately, there are only a few methods apply the techniques of NAF or its analogue to Frobenius-adic expansion, namely $\tau$-adic NAF techniques (\cite{Kob98,Sol00,BMX04} and \cite{GLS01}) for Koblitz curves and hyperelliptic Koblitz curves. In this paper, we try to combine these techniques, namely recoding methods for reducing non-zero density and Frobenius-adic expansion, and propose two new efficient recoding methods of scalars for more general family of subfield elliptic curves over odd characteristics. We also prove that the non-zero densities for the new methods are same as those for original GNAF and $r$NAF. As a result, the speed of the proposed schemes improve between 12.5{\%} and 79{\%} over that for previously known schemes.

2004

EPRINT

Signed Binary Representations Revisited
Abstract

The most common method for computing exponentiation of random elements
in Abelian groups are sliding window schemes, which enhance the
efficiency of the binary method at the expense of some precomputation.
In groups where inversion is easy (e.g. elliptic curves), signed
representations of the exponent are meaningful because they decrease
the amount of required precomputation. The asymptotic best signed method is wNAF, because it minimizes the precomputation effort
whilst the non-zero density is nearly optimal. Unfortunately,
wNAF can be computed only from the least significant bit,
i.e. right-to-left. However, in connection with memory constraint devices left-to-right recoding schemes are by far more valuable.
In this paper we define the MOF (Mutual Opposite Form), a new canonical representation of signed binary strings, which can be computed in any order. Therefore we obtain the first left-to-right signed exponent-recoding scheme for general width w by applying the width w sliding window conversion on MOF left-to-right. Moreover, the analogue right-to-left conversion on MOF yields wNAF, which indicates that the new class is the natural left-to-right analogue to the useful
wNAF. Indeed, the new class inherits the outstanding properties of
wNAF, namely the required precomputation and the achieved non-zero
density are exactly the same.

2004

EPRINT

A Complete Divisor Class Halving Algorithm for Hyperelliptic Curve Cryptosystems of Genus Two
Abstract

We deal with a divisor class halving algorithm on hyperelliptic curve cryptosystems (HECC), which can be used for scalar multiplication, instead of a doubling algorithm. It is not obvious how to construct a halving algorithm, due to the complicated addition formula of hyperelliptic curves. In this paper, we propose the first halving algorithm used for HECC of genus 2, which is as efficient as the previously known doubling algorithm. From the explicit formula of the doubling algorithm, we can generate some equations whose common solutions contain the halved value. From these equations we derive four specific equations and show an algorithm that selects the proper halved value using two trace computations in the worst case. If a base point is fixed, we can reduce these extra field operations by using a pre-computed table which shows the correct halving divisor class ?the improvement over the previously known fastest doubling algorithm is up to about 10%. This halving algorithm is applicable to DSA and DH scheme based on HECC. Finally, we present the divisor class halving algorithms for not only the most frequent case but also other exceptional cases.

2003

EPRINT

Some RSA-based Encryption Schemes with Tight Security Reduction
Abstract

In this paper, we study some RSA-based semantically secure encryption schemes (IND-CPA) in the standard model.
We first derive the exactly tight one-wayness
of Rabin-Paillier encryption scheme
which assumes that factoring Blum integers is hard.
We next propose the first IND-CPA scheme
whose one-wayness is equivalent to factoring {\it general} $n=pq$
(not factoring Blum integers).
Our reductions of one-wayness are very tight
because they require only one decryption-oracle query.

2003

EPRINT

Novel Efficient Implementations of Hyperelliptic Curve Cryptosystems using Degenerate Divisors
Abstract

It has recently been reported that the performance of hyperelliptic curve cryptosystems (HECC) is competitive to that of elliptic curve cryptosystems (ECC).
However, it is expected that HECC still can be improved due to their mathematically rich structure. We consider here the application of degenerate divisors of HECC to scalar multiplication. We investigate the operations of the degenerate divisors in the Harley algorithm and the Cantor algorithm of genus 2. The timings of these operations
are reported. We then present a novel efficient scalar multiplication method using the degenerate divisors. This method is applicable to cryptosystems with fixed base point, e.g., ElGamal-type encryption, sender of Diffie-Hellman, and DSA. Using a Xeon
processor, we found that the double-and-add-always method using the degenerate base point can achieve about a 20% increase in speed for a 160-bit HECC. However, we mounted an timing attack using the time difference to designate the degenerate divisors. The attack assumes that the secret key is fixed and the base point can be
freely chosen by the attacker. Therefore, the attack is applicable to ElGamal-type decryption and single-pass Diffie-Hellman ? SSL using a hyperelliptic curve could be vulnerable to the proposed attack. Our experimental results show that one bit of the secret key for a 160-bit HECC can be recovered by calling the decryption oracle 500 times.

1999

ASIACRYPT

#### Program Committees

- Asiacrypt 2017
- Asiacrypt 2016
- Asiacrypt 2015
- PKC 2013
- Asiacrypt 2013
- Crypto 2012
- CHES 2011
- CHES 2010
- PKC 2008
- CHES 2007
- Asiacrypt 2007
- CHES 2005
- CHES 2004
- CHES 2003

#### Coauthors

- Toru Akishita (2)
- Yoshinori Aono (1)
- Jean-Luc Beuchat (5)
- Nicolas Brisebarre (2)
- Kyo Il Chung (1)
- Xavier Dahan (1)
- Jérémie Detrey (1)
- Hiroshi Doi (1)
- Kaoru Fujita (1)
- Keisuke Hakuta (1)
- Dong-Guk Han (4)
- Michael Hartmann (1)
- Takuya Hayashi (4)
- Yun-Ju Huang (2)
- Detlef Hühnlein (2)
- Atsuo Inomata (1)
- Tsukasa Ishiguro (1)
- Tetsuya Izu (3)
- Michael J. Jacobson Jr. (1)
- Akira Kanaoka (1)
- Masanobu Katagi (2)
- Masayoshi Katouno (1)
- Yuto Kawahara (1)
- Tae Hyun Kim (2)
- Ho Won Kim (2)
- Izuru Kitamura (2)
- Shinsaku Kiyomoto (2)
- Kaoru Kurosawa (5)
- Fagen Li (1)
- Jongin Lim (1)
- Masahiro Mambo (1)
- Shin'ichiro Matsuo (2)
- Yutaka Miyake (1)
- Takeshi Okamoto (1)
- Eiji Okamoto (7)
- Katsuyuki Okeya (4)
- Shinya Okumura (1)
- Sachar Paulus (3)
- Christophe Petit (1)
- Kouichi Sakurai (2)
- Hisayoshi Sato (2)
- Katja Schmidt-Samoa (3)
- Takaaki Shiga (1)
- Takeshi Shimoyama (1)
- Naoyuki Shinohara (4)
- Masaaki Shirase (9)
- Ryuji Soga (1)
- Christian Spahn (2)
- Shingo Sugiyama (1)
- Kazuo Takaragi (1)
- Toshiaki Tanaka (1)
- Satoru Tezuka (1)
- Ananda Vithanage (1)
- Camille Vuillaume (1)
- Yuntao Wang (1)
- Lihua Wang (2)
- Hiroyasu Yamamoto (1)
- Bo Yang (1)
- Masaya Yasuda (1)
- Takanori Yasuda (1)
- Motoi Yoshitomi (1)
- Mingwu Zhang (1)