Paper 2011/030

Fast Elliptic Curve Cryptography Using Optimal Double-Base Chains

Vorapong Suppakitpaisarn, Masato Edahiro, and Hiroshi Imai


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%.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Elliptic Cruve CryptographyMinimal Weight ConversionDigit Set ExpansionDouble-Base Chains
Contact author(s)
mr_t_dtone @ is s u-tokyo ac jp
2011-01-18: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.