I am studying (sliding) window method in Elliptic Curve Cryptography (ECC) but I am confused by the term, signed fixed window method. By the way term is used in a research paper and not in the book that I am reading.
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ It is always helpful to provide additional context, e.g. a link to the paper. $\endgroup$– mikeazoMay 4, 2015 at 20:10
-
$\begingroup$ Sure, here is the link of the paper cr.yp.to/papers.html#curve41417 $\endgroup$– user110219May 4, 2015 at 20:18
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In the basic fixed window method of performing point multiplication, we compute the value $nP$ (where $n$ is the integer we're multiplying by, and $P$ is the basis point) by finding the base $b$ representation $n = d_k b^k + d_{k-1} b^{k-1} + ... + d_1 b^1 + d_0 b^0$ (where $0 \le d_i < b$), and then computing first $1P, 2P, ..., (b-1)P$ and then $nP = d_0 P + b ( d_1 P + b ( d_2 P + ... + b(d_kP))) ...)$ (where the computation of $d_iP$ is done by a lookup of the precomputed values).
There are a number of tweaks we can do to that basic method, but most of those are irrelevant for this discussion.
One is, not, though. It turns out that Elliptic Curves has one cheap operation that the group $Z_p^*$ does not; it is cheap to compute the inverse. So, one improvement to this basic method we can do is represent $n$ in balanced notation, where we allow negative digits; $-b/2 \le d_i \le b/2$. We then compute the values $1P, 2P, ..., (b/2)P$, and then when we need to do a lookup of a value $d_iP$, and $d_i < 0$, we just use the value $-(-d_i)P$, which is a lookup and an inverse.
What this allows us to do is double the size of $b$ at essentially no cost; the table we need to precompute is the same, and the number of additions we need to do is reduced.
