International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Some Analysis of Radix-r Representations

Dong-Guk Han
Tsuyoshi Takagi
Search ePrint
Search Google
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.
  title={Some Analysis of Radix-r Representations},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / pairing-based cryptosystems, radix-r representation, gNAF, wrNAF, side channel attacks.},
  note={ 13095 received 7 Nov 2005},
  author={Dong-Guk Han and Tsuyoshi Takagi},