Published in

Springer, Lecture Notes in Computer Science, p. 285-301, 2007

DOI: 10.1007/978-3-540-74462-7_20

Springer (part of Springer Nature), Designs, Codes and Cryptography, 2(58), p. 173-202

DOI: 10.1007/s10623-010-9396-6

Links

Tools

Export citation

Search in Google Scholar

Redundant τ-adic expansions I : non-adjacent digit sets and their applications to scalar multiplication

Journal article published in 2010 by Roberto Maria Avanzi, Clemens Heuberger, Helmut Prodinger
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Red circle
Preprint: archiving forbidden
Orange circle
Postprint: archiving restricted
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

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 = Pℓ i=0 ziτ i , where τ is a quadratic integer depending on the curve, such that zi 6= 0 implies zw+i−1 = . . . = zi+1 = 0, like the sliding window binary recod- ings of integers. We show that the digit sets described by Solinas, formed by elements of minimal norm in their residue classes, are uniquely deter- mined. 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 ex- tending 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, generalis- ing an approach started by Avanzi, Ciet, and Sica at PKC 2004. 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 storing precomputations first, thus reducing mem- ory storage dependent on the base point to just one point.