Welcome to the resource topic for 2004/195
Title:
Signed Binary Representations Revisited
Authors: Katsuyuki Okeya, Katja Schmidt-Samoa, Christian Spahn, Tsuyoshi Takagi
Abstract:The most common method for computing exponentiation of random elements
in Abelian groups are sliding window schemes, which enhance the
efficiency of the binary method at the expense of some precomputation.
In groups where inversion is easy (e.g. elliptic curves), signed
representations of the exponent are meaningful because they decrease
the amount of required precomputation. The asymptotic best signed method is wNAF, because it minimizes the precomputation effort
whilst the non-zero density is nearly optimal. Unfortunately,
wNAF can be computed only from the least significant bit,
i.e. right-to-left. However, in connection with memory constraint devices left-to-right recoding schemes are by far more valuable.
In this paper we define the MOF (Mutual Opposite Form), a new canonical representation of signed binary strings, which can be computed in any order. Therefore we obtain the first left-to-right signed exponent-recoding scheme for general width w by applying the width w sliding window conversion on MOF left-to-right. Moreover, the analogue right-to-left conversion on MOF yields wNAF, which indicates that the new class is the natural left-to-right analogue to the useful
wNAF. Indeed, the new class inherits the outstanding properties of
wNAF, namely the required precomputation and the achieved non-zero
density are exactly the same.
ePrint: https://eprint.iacr.org/2004/195
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .