Redundant \(\tau \)-adic expansions. I: Non-adjacent digit sets and their applications to scalar multiplication
type: Item
instance of: scholarly article
title: Redundant \(\tau \)-adic expansions. I: Non-adjacent digit sets and their applications to scalar multiplication
zbMATH Open document ID: 1230.94003
author: Clemens Heuberger
author: Roberto Maria Avanzi
author: Helmut Prodinger
published in: Designs, Codes and Cryptography
publication date: 2011-03-10T00:00:00Z
review text: Koblitz curves are elliptic curves over the finite field \({\mathbb F}_{2^n}\) defined by the equation \[ y^2+xy=x^3+ax^2+1, \quad a\in\{0,1\}, \] and with Frobenius endomorphism \(\tau\). The authors investigate properties of \(\tau \)-adic expansions of scalars. Solinas introduced the width-\(w\) \(\tau \)-adic non-adjacent form for use with Koblitz curves. This is an expansion of integers \({z = \sum_{i=0}^\ell z_i \tau^i}\), where \(\tau \) is a quadratic integer depending on the curve, such that \(z_{i } \neq 0\) implies \(z_{w+i-1} = \cdots = z_{i+1} = 0\). It uses a redundant digit set. The authors show that the digit sets described by Solinas, formed by elements of minimal norm in their residue classes, are uniquely determined. Apart from this digit set of minimal norm representatives, other digit sets can be chosen such that all integers can be represented by a width-\(w\) non-adjacent form using those digits. They describe an algorithm recognizing admissible digit sets. Results by Solinas and by Blake, Murty, and Xu are generalized. In particular, they introduce two new useful families of digit sets. The first set is syntactically defined. As a consequence of its adoption they can also present improved and streamlined algorithms to perform the precomputations in \(\tau \)-adic scalar multiplication methods. The latter use an improvement of the computation of sums and differences of points on elliptic curves with mixed affine and López-Dahab coordinates. The second set is suitable for low-memory applications, generalizing an approach started by Avanzi, Ciet, and Sica. It permits to devise a scalar multiplication algorithm that dispenses with the initial precomputation stage and its associated memory space. A suitable choice of the parameters of the method leads to a scalar multiplication algorithm on Koblitz curves that achieves sublinear complexity in the number of expensive curve operations.
reviewed by: Florin Nicolae
Mathematics Subject Classification ID: 94A60
Mathematics Subject Classification ID: 11A63
Mathematics Subject Classification ID: 14H52
zbMATH DE Number: 5864187
zbMATH Keywords: Koblitz curves
zbMATH Keywords: Frobenius endomorphism
zbMATH Keywords: scalar multiplication
zbMATH Keywords: \(\tau\)-adic expansions
zbMATH Keywords: non-adjacent-forms
zbMATH Keywords: digit sets
zbMATH Keywords: point halving
zbMATH Keywords: efficient implementation
MaRDI profile type: Publication
full work available at URL: s10623-010-9396-6
OpenAlex ID: W2016027219
cites work: Delaying and Merging Operations in Scalar Multiplication: Applications to Curve-Based Cryptosystems
cites work: Public Key Cryptography – PKC 2004
cites work: Handbook of Elliptic and Hyperelliptic Curve Cryptography
cites work: Extending Scalar Multiplication Using Double Bases
cites work: Minimality of the Hamming Weight of the τ-NAF for Koblitz Curves and Improved Combination with Point Halving
cites work: Scalar multiplication on Koblitz curves using the Frobenius endomorphism and its combination with point halving: extensions and mathematical analysis
cites work: On Redundant τ-Adic Expansions and Non-adjacent Digit Sets
cites work: Scalar Multiplication on Koblitz Curves Using Double Bases
cites work: Effects of Optimizations for Software Implementations of Small Binary Field Arithmetic
cites work: Rethinking low genus hyperelliptic Jacobian arithmetic over binary fields: interplay of field arithmetic and explicit formulæ
cites work: Progress in Cryptology - INDOCRYPT 2004
cites work: A note on window \(\tau\)-NAF algorithm
cites work: On the Lambert \(w\) function
cites work: Q4736429
cites work: Radix representations of quadratic fields
cites work: Redundant \(\tau \)-adic expansions. II: Non-optimality and chaotic behaviour
cites work: Analysis of alternative digit sets for nonadjacent representations
cites work: Canonical number systems in imaginary quadratic fields
cites work: Q4050689
cites work: Q4502494
cites work: Elliptic Curve Cryptosystems
cites work: Basic digit sets for radix representation
cites work: Q4318707
cites work: Selected Areas in Cryptography
cites work: Alternative Digit Sets for Nonadjacent Representations
cites work: Information Security and Privacy
cites work: Efficient arithmetic on Koblitz curves
DOI: 10.1007/S10623-010-9396-6
description: scientific article; zbMATH DE number 5864187