On redundant τ-adic expansions and non-adjacent digit sets
Date
2007
Authors
Avanzi R.M.
Heuberger C.
Prodinger H.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper studies τ-adic expansions of scalars, which are important in the design of scalar multiplication algorithms on Koblitz Curves, and are less understood than their binary counterparts. At Crypto '97 Solinas introduced the width-w τ-adic non-adjacent form for use with Koblitz curves. It is an expansion of integers z = Σi=0ℓ z iτi, where τ is a quadratic integer depending on the curve, such that zi ≠ 0 implies zw+i-1 = ... = zi+1 = 0, like the sliding window binary recodings of integers. We show that the digit sets described by Solinas, formed by elements of minimal norm in their residue classes, are uniquely determined. However, unlike for binary representations, syntactic constraints do not necessarily imply minimality of weight. Digit sets that permit recoding of all inputs are characterized, thus extending the line of research begun by Muir and Stinson at SAC 2003 to Koblitz Curves. Two new useful digit sets are introduced: one set makes precomputations easier, the second set is suitable for low-memory applications, generalising an approach started by Avanzi, Ciet, and Sica at PKC 2004 and continued by several authors since. Results by Solinas, and by Blake, Murty, and Xu are generalized. Termination, optimality, and cryptographic applications are considered. We show how to perform a "windowed" scalar multiplication on Koblitz curves without doing precomputations first, thus reducing memory storage dependent on the base point to just one point. © Springer-Verlag Berlin Heidelberg 2007.
Description
Keywords
Algorithms, Computation theory, Curve fitting, Integer programming, Scalability, Digit sets, Koblitz Curves, Cryptography
Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
4356 LNCS
4356 LNCS