## CryptoDB

### Eiji Okamoto

#### Publications

**Year**

**Venue**

**Title**

2010

EPRINT

Compact Implementations of BLAKE-32 and BLAKE-64 on FPGA
Abstract

We propose compact architectures of the SHA-$3$ candidates BLAKE-32 and BLAKE-64 for several FPGA families. We harness the intrinsic parallelism of the algorithm to interleave the computation of four instances of the $G_i$ function. This approach allows us to design an Arithmetic and Logic Unit with four pipeline stages and to achieve high clock frequencies. With careful scheduling, we completely avoid pipeline bubbles. For the time being, the designs presented in this work are the most compact ones for any of the SHA-3 candidates. We show for instance that a fully autonomous implementation of BLAKE-32 on a Xilinx Virtex-5 device requires 56 slices and two memory blocks.

2010

EPRINT

Cryptographic Pairings Based on Elliptic Nets
Abstract

In 2007, Stange proposed a novel method of computing the Tate pairing on an elliptic curve over a finite field.
This method is based on elliptic nets,
which are maps from $\mathbb{Z}^n$ to a ring that satisfy a certain recurrence relation.
In this paper, we explicitly give formulae for computing some variants
of the Tate pairing:
Ate, Ate$_i$, R-Ate and Optimal pairings, based on elliptic nets.
We also discuss their efficiency by using some experimental results.

2010

EPRINT

A Compact FPGA Implementation of the SHA-3 Candidate ECHO
Abstract

We propose a compact architecture of the SHA-3 candidate ECHO for the Virtex-5 FPGA family. Our architecture is built around a 8-bit datapath. We show that a careful organization of the chaining variable and the message block in the register file allows one to design a compact control unit based on a 4-bit counter, an 8-bit counter, and a simple Finite State Machine.
A fully autonomous implementation of ECHO on a Xilinx Virtex-5 FPGA requires $127$ slices and a single memory block to store the internal state, and achieves a throughput of $72$Mbps.

2010

EPRINT

Pair-wise Cryptographic Models for Secure Data Exchange in P2P Database Management Systems
Abstract

A peer-to-peer database management system(P2PDBMS) is a collection of autonomous data sources, called peers. In this system each peer augments a conventional database management system with an inter-operability layer (i.e. mappings/policies) for sharing data and services. Peers exchange data in a pair-wise fashion on-the-fly in response to a query without any centralized control. Generally, the communication link between two peers is insecure and peers create a temporary session while exchanging data. When peers exchange highly confidential data between them over an insecure communication network, such as the Internet, the data might be trapped and disclosed by the intruders. In a P2PDBMS there is no centralized control for data exchange, hence we cannot assume any central third party security infrastructure (e.g. PKI) to protect confidential data. So far, there is currently no available/existing security protocol for secured data exchange in P2PDBMS. In this paper we propose three models for secure data exchange in P2PDBMSs and the corresponding security protocols. The proposed protocol allows the peers to compute their secret session keys dynamically during data exchange based on the policies between them. Our proposed protocol is robust against the man-in-the middle attack, the masquerade attack, and the reply attack.

2010

EPRINT

High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves
Abstract

This paper describes the design of a fast software library for the computation of the optimal ate pairing on a Barreto--Naehrig elliptic curve. Our library is able to compute the optimal ate pairing over a $254$-bit prime field $\mathbb{F}_{p}$, in just $2.63$ million of clock cycles on a single core of an Intel Core i7 $2.8$GHz processor, which implies that the pairing computation takes $0.942$msec. We are able to achieve this performance by a careful implementation of the base field arithmetic through the usage of the customary Montgomery multiplier for prime fields. The prime field is constructed via the Barreto--Naehrig polynomial parametrization of the prime $p$ given as, $p = 36t^4 +36t^3 +24t^2 +6t+1$, with $t = 2^{62} - 2^{54} + 2^{44}$. This selection of $t$ allows us to obtain important savings for both the Miller loop as well as the final exponentiation steps of the optimal ate pairing.

2009

CHES

2008

EPRINT

Strongly Unforgeable ID-based Signatures Without Random Oracles
Abstract

There is an open problem to construct ID-based signature schemes which satisfy strongly EUF-ID-CMA, without random oracles. It is known that strongly EUF-ID-CMA is a concept of the strongest security in ID-based signatures. In this paper, we propose a solution to the open problem, that is an ID-based signature scheme, which satisfies strongly EUF-ID-CMA, without random oracles for the first time. Security of the scheme is based on the difficulty to solve three problems related to the Diffie-Hellman problem and a one-way isomorphism.

2008

EPRINT

A Comparison Between Hardware Accelerators for the Modified Tate Pairing over $\mathbb{F}_{2^m}$ and $\mathbb{F}_{3^m}$
Abstract

In this article we propose a study of the modified Tate pairing in characteristics two and three. Starting from the $\eta_T$ pairing introduced by Barreto {\em et al.} (Des Codes Crypt, 2007), we detail various algorithmic improvements in the case of characteristic two. As far as characteristic three is concerned, we refer to the survey by Beuchat {\em et al.} (ePrint 2007-417). We then show how to get back to the modified Tate pairing at almost no extra cost. Finally, we explore the trade-offs involved in the hardware implementation of this pairing for both characteristics two and three. From our experiments, characteristic three appears to have a slight advantage over characteristic two.

2008

EPRINT

A Pipelined Karatsuba-Ofman Multiplier over GF($3^{97}$) Amenable for Pairing Computation
Abstract

We present a subquadratic ternary field multiplier based on the combination of several variants of the Karatsuba-Ofman scheme
recently published. Since one of the most relevant applications for this kind of multipliers is pairing computation,
where several field multiplications need to be computed at once, we decided to design a $k$-stage pipeline
structure for $k=1,\ldots,4$, where each stage is composed of a 49-trit polynomial multiplier unit. That
architecture can compute an average of $k$ field multiplications every three clock cycles, which implies that our
four-stage pipeline design can perform more than one field multiplication per clock cycle. When implemented in
a Xilinx Virtex V XC5VLX330 FPGA device, this multiplier can compute one field multiplication over \gf($3^{97}$)
in just $11.47$ns.

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.

2007

EPRINT

Optimised versions of the Ate and Twisted Ate Pairings
Abstract

The Ate pairing and the twisted Ate pairing for ordinary elliptic curves
which are generalizations of the $\eta_T$ pairing for supersingular curves have previously been proposed.
It is not necessarily the case that both pairings are faster than the Tate pairing.
In this paper we propose optimized versions of the Ate and twisted Ate pairings with the loop reduction method and show that both pairings are always at least as fast as the Tate pairing.
We also provide suitable families of elliptic curves that our optimized Ate and optimized twisted Ate pairings can be computed with half the loop length compared to the Tate pairing.

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

Arithmetic Operators for Pairing-Based Cryptography
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 first study an accelerator for the $\eta_T$
pairing over $\mathbb{F}_3[x]/(x^{97}+x^{12}+2)$. Our architecture is
based on a unified arithmetic operator which performs addition,
multiplication, and cubing over $\mathbb{F}_{3^{97}}$. This design
methodology allows us to design a compact coprocessor ($1888$ slices
on a Virtex-II Pro~$4$ FPGA) which compares favorably with other
solutions described in the open literature. We then describe ways to
extend our approach to any characteristic and any extension field.

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.

2007

EPRINT

Group Password-Authenticated Key Exchange from Identity-Based Cryptosystem
Abstract

Password-authenticated key exchange (PAKE) protocols are designed to be secure even when the secret key used for authentication is a human-memorable password. In this paper, we consider PAKE protocols in the group scenario, in which a group of clients, each of them shares a password with an "honest but curious" server, intend to establish a common secret key (i.e., a group key) with the help of the server. In this setting, the key established is known to the clients only and no one else, including the server. Each client needs to remember passwords only while the server keeps passwords in addition to private keys related to his identity. Towards our goal, we present the first compiler that transforms any group key exchange (KE) protocol secure against a passive eavesdropping to a group PAKE which is secure against an active adversary who controls all communication in the network. This compiler is built on any group KE protocol (e.g., the Burmester-Desmedt protocol), any identity-based encryption (IBE) scheme (e.g., Gentry's scheme), and any identity-based signature (IBS) scheme (e.g., Paterson-Schuldt scheme). It adds only two rounds and O(1) communication (per client) to the original group KE protocol. As long as a group PAKE protocol is constructed by our compiler with a group KE protocol, an IBE scheme and an IBS scheme which have provably security without random oracles, it can be proven to be secure without random oracles.

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

An Efficient ID-based Digital Signature with Message Recovery Based on Pairing
Abstract

Signature schemes with message recovery have been wildly investigated
a decade ago in the literature, but the first ID-based signature with message recovery goes out into the world until 2005. In this paper, we first point out and revise one little but important problem
which occurs in the previous ID-based signature with message recovery scheme. Then, by completely different setting, we propose a new ID-based signature scheme with message recovery. Our scheme is much more efficient than the previous scheme. In our scheme (as well as other signature schemes with message recovery), the message itself is not required to be transmitted together with the signature,
it turns out to have the least data size of communication cost comparing with generic (not short) signature schemes. Although the communication overhead is still larger than Boneh et al. 's short signature (which is not ID-based), the computational cost of our scheme is more efficient than Boneh et al. 's scheme in the verification phase. We will also prove that the proposed scheme is provably secure in the random oracle model under CDH Assumption.

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

Anonymous Secure Communication in Wireless Mobile Ad-hoc Networks
Abstract

The main characteristic of a mobile ad-hoc network is its infrastructure-less, highly dynamic topology, which is subject to malicious traffic analysis. Malicious intermediate nodes in wireless mobile ad-hoc networks are a threat concerning security as well as anonymity of exchanged information. To protect anonymity and achieve security of nodes in mobile ad-hoc networks, an anonymous on-demand routing protocol, termed RIOMO, is proposed. For this purpose, pseudo IDs of the nodes are generated considering Pairing-based Cryptography. Nodes can generate their own pseudo IDs independently. As a result RIOMO reduces pseudo IDs maintenance costs. Only trust-worthy nodes are allowed to take part in routing to discover a route. To ensure trustiness each node has to make authentication to its neighbors through an anonymous authentication process. Thus RIOMO safely communicates between nodes without disclosing node identities; it also provides different desirable anonymous properties such as identity privacy, location privacy, route anonymity, and robustness against several attacks.

2006

EPRINT

A Subject-Delegated Decryption Scheme with ``Tightly" Limited Authority
Abstract

In this paper, we present a new proxy cryptosystem named subject-delegated decryption scheme, in which the original decryptor delegates
decryption authority to multiple proxies according to different subjects. The advantage of our scheme is that the proxy authorities are tightly limited (``Tightly" Limited Authority). This means that the proxy authority can be temporarily aborted even if the validity period of the proxy key does not expire. Consequently, our protocol is
more practical than the existential protocols because the secrecy of the original decryptor can be protected efficiently from his proxy, especially when the proxy becomes corrupted. Our scheme is efficient because the encryption method in our scheme is based on a hybrid of symmetric key and public key cryptographic techniques. We give the provable security using a variant decisional Bilinear Diffie-Hellman (BDH) assumption.

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

Simple and Provable Secure Strong Designated Verifier Signature Schemes
Abstract

In this paper, we introduce
a simple strong-designated verifier signature (SDVS) scheme which is much more efficient than
previously proposed SDVS schemes. In addition, with only one more parameter
published by the signer, this scheme can provide signer's forward security. That is,
the consistency of a signature cannot
be verified by any third party even if he/she knows a signer's private key.
Thus the privacy of a signer's identity
is protected independently in each signature,
if the designated verifier's private key has
not been disclosed.
In addition, this scheme can be easily modified to a designated verifier signcryption scheme with
virtually no additional cost. We will also show that the proposed scheme is provably secure in the random oracle model.

2005

EPRINT

A Share-Correctable Protocol for the Shamir Threshold Scheme and Its Application to Participant Enrollment
Abstract

Verifiable secret sharing schemes proposed so far can only
allow participants to verify whether their shares are correct or
not. In this paper, we propose a new protocol which can
allow participants not only to verify the correctness of their
shares but also to revise the faulty shares. It is achieved
in a cooperative way by participants, but without any assistance
from the dealer.
This protocol, to the best of our
knowledge, is the first one providing such kind of ability.
Correcting shares by participants instead of the dealer is
important in many situations. In addition, this protocol is
also useful for adding new participants without the dealer's assistance.

1996

ASIACRYPT

#### Program Committees

- Crypto 2010
- Asiacrypt 2008
- Asiacrypt 2003
- PKC 2001
- PKC 2000
- PKC 1999
- Asiacrypt 1999 (Program chair)
- Asiacrypt 1996
- Asiacrypt 1991
- Crypto 1991

#### Coauthors

- Carlisle M. Adams (1)
- Jean-Luc Beuchat (13)
- Nicolas Brisebarre (5)
- Mike Burmester (1)
- Nidia Cortez-Duarte (1)
- Yvo Desmedt (1)
- Jérémie Detrey (5)
- Jorge Enrique González Díaz (1)
- Hiroshi Doi (2)
- Khalil El-Khatib (1)
- Nicolas Estibals (1)
- Kaoru Fujita (1)
- Chunxiang Gu (1)
- Goichiro Hanaoka (1)
- Florian Hess (1)
- Atsuo Inomata (2)
- Akira Kanaoka (1)
- Naoki Kanayama (2)
- Masayoshi Katouno (1)
- Yuto Kawahara (1)
- Masahiro Mambo (5)
- Mehedi Masud (1)
- Seiichi Matsuda (1)
- Ying Miao (1)
- Shigeo Mitsunari (1)
- Hussein Mouftah (1)
- K. Nakamura (1)
- Takashi Nishide (1)
- Koji Nuida (1)
- Naoki Ogura (1)
- Takeshi Okamoto (7)
- Sk. Md. Mizanur Rahman (2)
- Francisco Rodríguez-Henríquez (4)
- Kouichi Sakurai (1)
- Chifumi Sato (1)
- Takaaki Shiga (1)
- Kazumasa Shinagawa (1)
- Masaaki Shirase (6)
- Ryuji Soga (1)
- Mitsuru Tada (1)
- Tsuyoshi Takagi (7)
- Tadanori Teruya (1)
- Raylin Tso (4)
- Yukiyasu Tsunoo (1)
- Shigenori Uchiyama (1)
- Tomohiko Uyematsu (1)
- Ananda Vithanage (1)
- Lihua Wang (1)
- Hiroyasu Yamamoto (1)
- Teppei Yamazaki (2)
- Xun Yi (1)
- Yuko Yoshifuji (1)