Paper 2011/030
Fast Elliptic Curve Cryptography Using Optimal Double-Base Chains
Vorapong Suppakitpaisarn, Masato Edahiro, and Hiroshi Imai
Abstract
In this work, we propose an algorithm to produce the double-base chains that optimize the time used for computing an elliptic curve cryptosystem. The double-base chains is the representation that combining the binary and ternary representation. By this method, we can reduce the Hamming weight of the expansion, and reduce the time for computing the scalar point multiplication (Q = rS), that is the bottleneck operation of the elliptic curve cryptosystem. This representation is very redundant, i.e. we can present a number by many expansions. Then, we can select the way that makes the operation fastest. However, the previous works on double-bases chain have used a greedy algorithm, and their solutions are not optimized. We propose the algorithm based on the dynamic programming scheme that outputs the optimized the double-bases chain. The experiments show that we have reduced the time for computing the scalar multiplication by 3.88-3.95%, the multi-scalar multiplication by 2.55-4.37%, and the multi-scalar multiplication on the larger digit set by 3.5-12%.
Metadata
- Available format(s)
-
PDF
PS
- Category
- Implementation
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Elliptic Cruve CryptographyMinimal Weight ConversionDigit Set ExpansionDouble-Base Chains
- Contact author(s)
- mr_t_dtone @ is s u-tokyo ac jp
- History
- 2011-01-18: received
- Short URL
- https://ia.cr/2011/030
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2011/030,
author = {Vorapong Suppakitpaisarn and Masato Edahiro and Hiroshi Imai},
title = {Fast Elliptic Curve Cryptography Using Optimal Double-Base Chains},
howpublished = {Cryptology {ePrint} Archive, Paper 2011/030},
year = {2011},
url = {https://eprint.iacr.org/2011/030}
}
