Can I read Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases on EtoBox?

Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases by Heuberger, Clemens; Krenn, Daniel is a scholarly article available to read on EtoBox.

What is Optimality of the Width-$w$ Non-adjacent Form: General Characterisation and the Case of Imaginary Quadratic Bases about?

Efficient scalar multiplication in Abelian groups (which is an important operation in public key cryptography) can be performed using digital expansions. Apart from rational integer bases (double-and-add algorithm), imaginary quadratic integer bases are of interest for elliptic curve cryptography, because the Frobenius endomorphism fulfils a quadratic equation. One strategy for improving the efficiency is to increase the digit set (at the prize of additional precomputations). A common choice is the width\nbd-$w$ non-adjacent form (\wNAF): each block of $w$ consecutive digits contains at most one non-zero digit. Heuristically, this ensures a low weight, i.e.\ number of non-zero digits, which translates in few costly curve operations. This paper investigates the following question: Is the \wNAF{}-expansion optimal, where optimality means minimising the weight over all possible expansions with the same digit set? The main characterisation of optimality of \wNAF{}s can be formulated in the following more general setting: We consider an Abelian group together with an endomorphism (e.g., multiplication by a base element in a ring) and a finite digit set. We show that each group element h

Author

Heuberger, Clemens; Krenn, Daniel

Published

2011

Language

EN