Presentation 2008-05-16
A Study on Higher Order Differnce Operation for Elliptic Curve Scalar Multiplication Using Path Table
Tomoko K. MATSUSHIMA, Yoshitaka SAGARA, Osamu ASHIHARA,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Efficient elliptic curve arithmetic is crucial for cryptosystems based on elliptic curves. Such cryptosystems often require computing a scalar multiple kP of a base point P. Recently, some papers have proposed efficient algorithms to compute λP ± μQ directly for small integers λ and μ from given points P and Q. The authors have already developed some programs to find the path with the minimum cost for each scalar multiplication kP under the condition that several operations of λP ± μQ can be used. We have also developed the minimum-cost path-table of scalar multiples kP for 1 ≦ k ≦ k_. In this paper, we present an algorithm to compute KP where k_ ≪ K. The algorithm adopts the higher order difference operation for the coefficients in b-ary representation of KP where b is the radix. We evaluate the costs due to our proposed algorithm in comparison with some conventional algorithms.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) elliptic curves / scalar multiplication / addition chains / power tree / path table / higher order difference operation
Paper # ISEC2008-11
Date of Issue

Conference Information
Committee ISEC
Conference Date 2008/5/9(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) A Study on Higher Order Differnce Operation for Elliptic Curve Scalar Multiplication Using Path Table
Sub Title (in English)
Keyword(1) elliptic curves
Keyword(2) scalar multiplication
Keyword(3) addition chains
Keyword(4) power tree
Keyword(5) path table
Keyword(6) higher order difference operation
1st Author's Name Tomoko K. MATSUSHIMA
1st Author's Affiliation Information Systems Engineering Dept., Polytechnic Univ.()
2nd Author's Name Yoshitaka SAGARA
2nd Author's Affiliation Information Systems Engineering Dept., Polytechnic Univ.
3rd Author's Name Osamu ASHIHARA
3rd Author's Affiliation Information Systems Engineering Dept., Polytechnic Univ.
Date 2008-05-16
Paper # ISEC2008-11
Volume (vol) vol.108
Number (no) 38
Page pp.pp.-
#Pages 8
Date of Issue