A new upper bound for the minimal density of joint representations in Elliptic Curve cryptosystems

Erik Dahmen, Katsuyuki Okeya, Tsuyoshi Takagi

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


The most time consuming operation to verify a signature with the Elliptic Curve Digital Signature Algorithm is a multi-scalar multiplication with two scalars. Efficient methods for its computation are the Shamir method and the Interleave method, whereas the performance of those methods can be improved by using general base-2 representations of the scalars. In exchange for the speed-up, those representations require the precomputation of several points that must be stored. In the case of two precomputed points, the Interleave method and the Shamir method provide the same, optimal efficiency. In the case of more precomputed points, only the Interleave method can be sped-up in an optimal way and is currently more efficient than the Shamir method. This paper proposes a new general base-2 representation of the scalars that can be used to speed up the Shamir method. It requires the precomputation of ten points and is more efficient than any other representation that also requires ten precomputed points. Therefore, the proposed method is the first to improve the Shamir method such that it is faster than the Interleave method.

Original languageEnglish
Pages (from-to)952-959
Number of pages8
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number5
Publication statusPublished - May 2007
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'A new upper bound for the minimal density of joint representations in Elliptic Curve cryptosystems'. Together they form a unique fingerprint.

Cite this