International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Tsuyoshi Takagi

Affiliation: Kyushu University

Publications

Year
Venue
Title
2016
EUROCRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2014
PKC
2012
ASIACRYPT
2010
PKC
2010
EPRINT
Solving a 676-bit Discrete Logarithm Problem in $GF(3^{6n})$
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
Mingwu Zhang Tsuyoshi Takagi Bo Yang
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
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
Fagen Li Masaaki Shirase Tsuyoshi Takagi
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
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
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
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
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
ASIACRYPT
2006
EPRINT
An Algorithm for the $\eta_T$ Pairing Calculation in Characteristic Three and its Hardware Implementation
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
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
Yuto Kawahara Tsuyoshi Takagi Eiji Okamoto
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
Masaaki Shirase Tsuyoshi Takagi Eiji Okamoto
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
CHES
2005
EPRINT
One-Wayness Equivalent to General Factoring
Kaoru Kurosawa Tsuyoshi Takagi
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
Dong-Guk Han Tetsuya Izu Tsuyoshi Takagi
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
Dong-Guk Han Tsuyoshi Takagi
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
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
Keisuke Hakuta Hisayoshi Sato Tsuyoshi Takagi
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
CRYPTO
2004
PKC
2004
EPRINT
Signed Binary Representations Revisited
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
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
ASIACRYPT
2003
ASIACRYPT
2003
ASIACRYPT
2003
CHES
2003
PKC
2003
EPRINT
Some RSA-based Encryption Schemes with Tight Security Reduction
Kaoru Kurosawa Tsuyoshi Takagi
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
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.
2002
PKC
2002
PKC
2000
JOFC
1999
ASIACRYPT
1999
CHES
1998
CRYPTO
1998
EUROCRYPT
1997
CRYPTO

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