1-19hit |
We have realized a design automation platform of hardware accelerator for pairing operation over multiple elliptic curve parameters. Pairing operation is one of the fundamental operations to realize functional encryption. However, known as a computational complexity-heavy algorithm. Also because there have been not yet identified standard parameters, we need to choose curve parameters based on the required security level and affordable hardware resources. To explore this design optimization for each curve parameter is essential. In this research, we have realized an automated design platform for pairing hardware for such purposes. Optimization results show almost equivalent to those prior-art designs by hand.
Kaoru MASADA Ryohei NAKAYAMA Makoto IKEDA
BLS signature is an elliptic curve cryptography with an attractive feature that signatures can be aggregated and shortened. We have designed two ASIC architectures for hashing to the elliptic curve and pairing to minimize the latency. Also, the designs are optimized for BLS12-381, a relatively new and safe curve.
Xianghong HU Hongmin HUANG Xin ZHENG Yuan LIU Xiaoming XIONG
Elliptic curve cryptography (ECC), one of the asymmetric cryptography, is widely used in practical security applications, especially in the Internet of Things (IoT) applications. This paper presents a low-power reconfigurable architecture for ECC, which is capable of resisting simple power analysis attacks (SPA) and can be configured to support all of point operations and modular operations on 160/192/224/256-bit field orders over GF(p). Point multiplication (PM) is the most complex and time-consuming operation of ECC, while modular multiplication (MM) and modular division (MD) have high computational complexity among modular operations. For decreasing power dissipation and increasing reconfigurable capability, a Reconfigurable Modular Multiplication Algorithm and Reconfigurable Modular Division Algorithm are proposed, and MM and MD are implemented by two adder units. Combining with the optimization of operation scheduling of PM, on 55 nm CMOS ASIC platform, the proposed architecture takes 0.96, 1.37, 1.87, 2.44 ms and consumes 8.29, 11.86, 16.20, 21.13 uJ to perform one PM on 160-bit, 192-bit, 224-bit, 256-bit field orders. It occupies 56.03 k gate area and has a power of 8.66 mW. The implementation results demonstrate that the proposed architecture outperforms the other contemporary designs reported in the literature in terms of area and configurability.
Kazuki NAGANUMA Takashi SUZUKI Hiroyuki TSUJI Tomoaki KIMURA
Gaussian integer has a potential to enhance the safety of elliptic curve cryptography (ECC) on system under the condition fixing bit length of integral and floating point types, in viewpoint of the order of a finite field. However, there seems to have been no algorithm which makes Gaussian integer ECC safer under the condition. We present the algorithm to enhance the safety of ECC under the condition. Then, we confirm our Gaussian integer ECC is safer in viewpoint of the order of finite field than rational integer ECC or Gaussian integer ECC of naive methods under the condition.
Yasuyuki NOGAMI Hiroto KAGOTANI Kengo IOKIBE Hiroyuki MIYATAKE Takashi NARITA
Pairing-based cryptography has realized a lot of innovative cryptographic applications such as attribute-based cryptography and semi homomorphic encryption. Pairing is a bilinear map constructed on a torsion group structure that is defined on a special class of elliptic curves, namely pairing-friendly curve. Pairing-friendly curves are roughly classified into supersingular and non supersingular curves. In these years, non supersingular pairing-friendly curves have been focused on from a security reason. Although non supersingular pairing-friendly curves have an ability to bridge various security levels with various parameter settings, most of software and hardware implementations tightly restrict them to achieve calculation efficiencies and avoid implementation difficulties. This paper shows an FPGA implementation that supports various parameter settings of pairings on non supersingular pairing-friendly curves for which Montgomery reduction, cyclic vector multiplication algorithm, projective coordinates, and Tate pairing have been combinatorially applied. Then, some experimental results with resource usages are shown.
Hyoung-Kee CHOI Ki-Eun SHIN Hyoungshick KIM
With the rapid merger of healthcare business and information technology, more healthcare institutions and medical practices are sharing information. Since these records often contain patients' sensitive personal information, Healthcare Information Systems (HISs) should be properly designed to manage these records in a secure manner. We propose a novel security design for the HIS complying with the security and privacy rules. The proposed system defines protocols to ensure secure delivery of medical records over insecure public networks and reliable management of medical record in the remote server without incurring excessive costs to implement services for security. We demonstrate the practicality of the proposed system through a security analysis and performance evaluation.
Parinya CHALERMSOOK Hiroshi IMAI Vorapong SUPPAKITPAISARN
In this letter, we derive two lower bounds for the number of terms in a double-base number system (DBNS), when the digit set is {1}. For a positive integer n, we show that the number of terms obtained from the greedy algorithm proposed by Dimitrov, Imbert, and Mishra [1] is $Thetaleft(rac{log n}{log log n} ight)$. Also, we show that the number of terms in the shortest double-base chain is Θ(log n).
Hiroshi IMAI Vorapong SUPPAKITPAISARN
In this paper, we improve a width-3 joint sparse form proposed by Okeya, Katoh, and Nogami. After the improvement, the representation can attain an asymtotically optimal complexity found in our previous work. Although claimed as optimal by the authors, the average computation time of multi-scalar multiplication obtained by the representation is 563/1574n+o(n)≈0.3577n+o(n). That number is larger than the optimal complexity 281/786n+o(n)≈0.3575n+o(n) found in our previous work. To optimize the width-3 joint sparse form, we add more cases to the representation. After the addition, we can show that the complexity is updated to 281/786n+o(n)≈0.3575n+o(n), which implies that the modified representation is asymptotically optimal. Compared to our optimal algorithm in the previous work, the modified width-3 joint sparse form uses less dynamic memory, but it consumes more static memory.
Field Programmable Gate Array (FPGA) implementation of Elliptic Curve Cryptography (ECC) over GF(p) is commonly not fast enough to meet the request of high-performance applications. There are three critical factors to determine the performance of ECC processor over GF(p): multiplication structure, modular multiplication algorithm, and scalar point multiplication scheduling. This work proposes a novel multiplication structure which is a two-stage pipeline on the basis of Karatsuba-Ofman algorithm. With the proposed multiplication structure, we design a 256-bit modular multiplier based on Improved Barret Modular Multiplication algorithm. Upon the modular multiplier, we finish the scalar point multiplication scheduling and implement a high-performance ECC processor on FPGA. Compared with the previous modular multipliers, our modular multiplier reduces the 256-bit modular multiplication time by 28% at least. Synthesis result on Altera Stratix II shows that our ECC processor can complete a 256-bit ECC scalar point multiplication in 0.51ms, which is at least 1.3 times faster than the currently reported FPGA ECC processors over GF(p).
This paper presents a power analysis that applies to elliptic curves over generalized Mersenne prime field Fp. This prime field enables efficient modular reductions which influence the computational performance of an elliptic curve cryptosystem. The general modular reductions stochastically calculate extra operations. Some studies showed the possibility of power analysis attacks to scalar multiplication with a unified code by using the statistical information of extra operations. In this paper, we present the statistical experiment and possibility of attacks, and propose the more sensitive attack and the countermeasure without performance impact.
Kazuyuki TANIMURA Ryuta NARA Shunitsu KOHARA Youhua SHI Nozomu TOGAWA Masao YANAGISAWA Tatsuo OHTSUKI
Modular multiplication is the most dominant arithmetic operation in elliptic curve cryptography (ECC), that is a type of public-key cryptography. Montgomery multiplier is commonly used to compute the modular multiplications and requires scalability because the bit length of operands varies depending on its security level. In addition, ECC is performed in GF(P) or GF(2n), and unified architecture for multipliers in GF(P) and GF(2n) is required. However, in previous works, changing frequency is necessary to deal with delay-time difference between GF(P) and GF(2n) multipliers because the critical path of the GF(P) multiplier is longer. This paper proposes unified dual-radix architecture for scalable Montgomery multiplications in GF(P) and GF(2n). This proposed architecture unifies four parallel radix-216 multipliers in GF(P) and a radix-264 multiplier in GF(2n) into a single unit. Applying lower radix to GF(P) multiplier shortens its critical path and makes it possible to compute the operands in the two fields using the same multiplier at the same frequency so that clock dividers to deal with the delay-time difference are not required. Moreover, parallel architecture in GF(P) reduces the clock cycles increased by dual-radix approach. Consequently, the proposed architecture achieves to compute a GF(P) 256-bit Montgomery multiplication in 0.28 µs. The implementation result shows that the area of the proposal is almost the same as that of previous works: 39 kgates.
Soonhak KWON Taekyoung KWON Young-Ho PARK
We propose a new linear array for multiplication in GF(2m) which outperforms most of the existing linear multipliers in terms of the area and time complexity. Moreover we will give a very detailed comparison of our array with other existing architectures for the five binary fields GF(2m), m=163,233,283,409,571, recommended by NIST for elliptic curve cryptography.
Cryptosystems using pairing computation on elliptic curves have various applications including ID-based encryption ([19],[29],[30] etc.). Scott [33] proposed a scaling method of security by a change of the embedding degree k. On the other hand, he also presented an efficient pairing computation method on an ordinary (non-supersingular) elliptic curve over a large prime field Fp ([34]). In this paper, we present an implementation method of the pairing computation with both of the security scaling in [33] and the efficiency in [34]. First, we will investigate the mathematical nature of the set of the paremeter r (the order of cyclic group used) so as to support many k's. Then, based on it, we will suggest some modification to the algorithm of Scott in [34] to achieve flexible scalability of security level.
The Gallant-Lambert-Vanstone method [14](GLV method for short) is a scalar multiplication method for elliptic curve cryptography (ECC). In WAP WTLS [49], SEC 2 [44], ANSI X9.62 [1] and X9.63 [2], several domain parameters for applications of the GLV method are described. Curves with those parameters have efficiently-computable endomorphisms. Recently the GLV method for Jacobians of hyperelliptic curve (HEC) has also been studied. In this paper, we discuss applications of the GLV method to curves with real multiplication (RM). It is the first time to use RM for efficient scalar multiplication as far as we know. We describe the general algorithm for using such RM, and we show that some genus 2 curves with RM have enough effciency to be used in the GLV method as in the previous CM case. Moreover, we will see that such RM curves can be obtained abundantly unlike the previously proposed CM curves of genus 2.
Shyi-Tsong WU Jung-Hui CHIU Bin-Chang CHIEU
Some cryptographic schemes based on the bilinear pairings were proposed recently. In this paper, we apply the pairings on elliptic curve and Elliptic Curve Cryptography to the key agreement of dynamic peer group. Each member performs authentication and contributes a secret data to negotiate a group common key by means of a binary key tree. The proposed protocol does not need a dedicated central server to perform the key agreement, and the overhead is distributed among the group members. To provide a secure dynamic group communication, the key renewing mechanism has to be included. While the member joins/leaves, the group session key will be renewed to provide the backward/forward privacy, respectively. The key renewing is much efficient because it is only confined to the keys of the key-path. The proposed protocol is flexible while the change of membership is frequent.
The application of Elliptic Curve Cryptosystem has gained more and more attention. ECC uses smaller key size and lower memory requirement to retain the security level and can be a crucial factor in the smart card system. In this paper, an ECC based implementation of security schemes in smart card system to access control the door of some confidential places is proposed. The confidential place, for example a coffer, a strong room in the bank is used to store treasures as well as cashes, and where the mutual vigilance could be required. For the safety consideration, the going in and out a coffer by a person is not permissive but a group of authorized people. It involves the problem of secret sharing. The adopted solution of sharing secret is threshold scheme. Every participant possesses a secret shadow, which will be saved in the smart card. After correct reconstructing the shared secrets, it is permissible to access the coffer's door. For resisting dishonest participants, cheating detection and cheater identification will be included. The user can change his password of smart card freely and need not memorize his assigned lengthy password and shadow as traditional ID-based schemes makes our implementation much more user friendly.
Katsuyuki OKEYA Kouichi SAKURAI
We develop efficient precomputation methods of multi-scalar multiplication on ECC. We should recall that multi-scalar multiplication is required in some elliptic curve cryptosystems including the signature verification of ECDSA signature scheme. One of the known fast computation methods of multi-scalar multiplication is a simultaneous method. A simultaneous method consists of two stages; precomputation stage and evaluation stage. Precomputation stage computes points of precomputation, which are used at evaluation stage. Evaluation stage computes multi-scalar multiplication using precomputed points. In the evaluation stage of simultaneous methods, we can compute the multi-scalar multiplied point quickly because the number of additions is small. However, if we take a large window width, we have to compute an enormous number of points in precomputation stage. Hence, we have to compute an abundance of inversions, which have large computational amount. As a result, precomputation stage requires much time, as well known. Our proposed method reduces from O(22w) inversions to O(w) inversions for a window width w, using Montgomery trick. In addition, our proposed method computes uP and vQ first, then compute uP+vQ, where P,Q are elliptic points. This procedure enables us to remove unused points of precomputation. Compared with the method without Montgomery trick, our proposed method is 3.6 times faster in the case of the precomputation stage for simultaneous sliding window NAF method with window width w=3 and 160-bit scalars under the assumption that I/M=30, S/M=0.8, where I,M,S respectively denote computational amounts of inversion, multiplication and squaring on a finite field.
Sangook MOON Yong Joo LEE Jae Min PARK Byung In MOON Yong Surk LEE
A new approach on designing a finite field multiplier architecture is proposed. The proposed architecture trades reduction in the number of clock cycles with resources. This architecture features high performance, simple structure, scalability and independence on the choice of the finite field, and can be used in high security cryptographic applications such as elliptic curve crypto-systems in large prime Galois Fields (GF(2m)).
Junji SHIKATA Yuliang ZHENG Joe SUZUKI Hideki IMAI
The problem we consider in this paper is whether the Menezes-Okamoto-Vanstone (MOV) reduction for attacking elliptic curve cryptosystems can be realized for genera elliptic curves. In realizing the MOV reduction, the base field Fq is extended so that the reduction to the discrete logarithm problem in a finite field is possible. Recent results by Balasubramanian and Koblitz suggest that, if l q-1, such a minimum extension degree is the minimum k such that l|qk-1, which is equivalent to the condition under which the Frey-Ruck (FR) reduction can be applied, where l is the order of the group in the elliptic curve discrete logarithm problem. Our point is that the problem of finding an l-torsion point required in evaluating the Weil pairing should be considered as well from an algorithmic point of view. In this paper, we actually propose a method which leads to a solution of the problem. In addition, our contribution allows us to draw the conclusion that the MOV reduction is indeed as powerful as the FR reduction under l q-1 not only from the viewpoint of the minimum extension degrees but also from that of the effectiveness of algorithms.