| Presentation | 2007-12-19 Efficiency Analysis of Multi-Scalar Multiplication using Direct Computation Method Hisashi YAMADA, Tsuyoshi TAKAGI, Kouichi SAKURAI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The most time consuming operation to verify a signature with the elliptic curve digital signature algorithm (ECDSA) is a multi-scalar multiplication with two scalars. The Interleave method with NAF (IL-NAF) and the Interleave method with MOF (IL-MOF) are efficient methods for the multi-scalar multiplications without any pre-computations. We have to the estimate the length of the consecutive zero digits (zero-run) for efficiency analysis of multi-scalar multiplications using the IL-NAF/MOF. In this paper, we consider the appearance probability of the zero-runs and their average zero-run length using the markov chain. We present asymptotic length of the consecutive zero digits (zero-run length) of IL-NAF/MOF for randomly chosen n bit two scalars. Indeed, the average zero-run length of the IL-NAF and IL-MOF is asymptotically 3 and 256/85, respectively. Moreover, we apply the appearance probability of zero-runs to the speed estimation of multi-scalar multiplications using the direct computation method. We prove that the IL-NAF/MOF using direct computation method can achieve 4.7～4.8% faster computation than the standard IL-NAF/MOF with iterated doubling. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | multi-scalar multiplication / interleave method / IL-NAF / IL-MOF |
| Paper # | ISEC2007-121 |
| Date of Issue |
| Conference Information | |
| Committee | ISEC |
|---|---|
| Conference Date | 2007/12/12(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) | Efficiency Analysis of Multi-Scalar Multiplication using Direct Computation Method |
| Sub Title (in English) | |
| Keyword(1) | multi-scalar multiplication |
| Keyword(2) | interleave method |
| Keyword(3) | IL-NAF |
| Keyword(4) | IL-MOF |
| 1st Author's Name | Hisashi YAMADA |
| 1st Author's Affiliation | Future University-Hakodate() |
| 2nd Author's Name | Tsuyoshi TAKAGI |
| 2nd Author's Affiliation | Future University-Hakodate |
| 3rd Author's Name | Kouichi SAKURAI |
| 3rd Author's Affiliation | Kyushu University |
| Date | 2007-12-19 |
| Paper # | ISEC2007-121 |
| Volume (vol) | vol.107 |
| Number (no) | 397 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |