## CryptoDB

### Eiji Okamoto

#### Publications

Year
Venue
Title
2016
ASIACRYPT
2010
EPRINT
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
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
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
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
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
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
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
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
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
CHES
2007
EPRINT
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
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
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
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
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
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
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
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
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
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
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
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
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
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.
2000
PKC
1996
ASIACRYPT
1994
CRYPTO
1988
EUROCRYPT
1987
CRYPTO
1985
CRYPTO

#### Program Committees

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