Title :
Left-to-right Generalized Non-adjacent Form Recoding for Elliptic Curve Cryptosystems
Author :
Kong, Fanyu ; Yu, Jia ; Cai, Zhun ; Li, Daxing
Author_Institution :
Inst. of Network Security, Shandong Univ., Jinan
Abstract :
Various signed digit representations have been used to speed up point multiplication in elliptic curve cryptosystems. In this paper, we present an analysis of the left-to-right radix-r (rges2) generalized non-adjacent form (GNAF) recoding algorithm. A probability model is established to analyze the on-line efficiency of the algorithm. It is proved that the average number of scanned digits required for obtaining one GNAF recoding digit is E(L)= 1 + 1/r-1, with the standard variance sigma(L) = radicr/r-1, and satisfying Pr[L>k] = 1/r(k-1) when k is any positive integer. This algorithm can be used to implement point multiplication in pairing-based cryptosystems and reduce the storage space compared to the right-to-left radix-r (rges2) generalized non-adjacent form (GNAF) recoding algorithm
Keywords :
cryptography; elliptic equations; probability; elliptic curve cryptosystems; left-to-right generalized nonadjacent form recoding; point multiplication; probability model; signed digit representations; Algorithm design and analysis; Digital arithmetic; Educational institutions; Elliptic curve cryptography; Elliptic curves; Information security; Information technology;
Conference_Titel :
Hybrid Information Technology, 2006. ICHIT '06. International Conference on
Conference_Location :
Cheju Island
Print_ISBN :
0-7695-2674-8
DOI :
10.1109/ICHIT.2006.253503
