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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2011/030}},
      url = {https://eprint.iacr.org/2011/030}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.