Cryptology ePrint Archive: Report 2005/402

Some Analysis of Radix-r Representations

Dong-Guk Han and Tsuyoshi Takagi

Abstract: We deal with the radix-r representation used for the scalar multiplication of pairing-based cryptosystems with characteristic r. Our goal of this paper is to present some invariant properties about the signed radix-r representation; (1) approximation formulae for the average significant length and the average hamming weight of gNAF and wrNAF representation, (2) some classification formulae of equivalent classes called as Cutting Lemma, Collision Lemma, and Search Space Theorem. We also analyze the security of signed radix-r representations in the sense of side channel attacks, and to this end we propose a secure countermeasure.

Category / Keywords: public-key cryptography / pairing-based cryptosystems, radix-r representation, gNAF, wrNAF, side channel attacks.

Date: received 7 Nov 2005

Contact author: christa at fun ac jp

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20051114:214155 (All versions of this report)

Short URL: ia.cr/2005/402

Discussion forum: Show discussion | Start new discussion