A New Upper Bound for the Minimal Density of Joint Representations in Elliptic Curve Cryptosystems

Erik DAHMEN; Katsuyuki OKEYA; Tsuyoshi TAKAGI

doi:10.1093/ietfec/e90-a.5.952

A New Upper Bound for the Minimal Density of Joint Representations in Elliptic Curve Cryptosystems

Erik DAHMEN, Katsuyuki OKEYA, Tsuyoshi TAKAGI

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.5 pp.952-959

Publication Date: 2007/05/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e90-a.5.952

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Erik DAHMEN, Katsuyuki OKEYA, Tsuyoshi TAKAGI, "A New Upper Bound for the Minimal Density of Joint Representations in Elliptic Curve Cryptosystems" in IEICE TRANSACTIONS on Fundamentals, vol. E90-A, no. 5, pp. 952-959, May 2007, doi: 10.1093/ietfec/e90-a.5.952.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.5.952/_p

Copy

@ARTICLE{e90-a_5_952,
author={Erik DAHMEN, Katsuyuki OKEYA, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Upper Bound for the Minimal Density of Joint Representations in Elliptic Curve Cryptosystems},
year={2007},
volume={E90-A},
number={5},
pages={952-959},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e90-a.5.952},
ISSN={1745-1337},
month={May},}

Copy

TY - JOUR
TI - A New Upper Bound for the Minimal Density of Joint Representations in Elliptic Curve Cryptosystems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 952
EP - 959
AU - Erik DAHMEN
AU - Katsuyuki OKEYA
AU - Tsuyoshi TAKAGI
PY - 2007
DO - 10.1093/ietfec/e90-a.5.952
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2007
AB - 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.
ER -