4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It is always helpful to provide additional context, e.g. a link to the paper. $\endgroup$ – mikeazo May 4 '15 at 20:10
  • $\begingroup$ Sure, here is the link of the paper cr.yp.to/papers.html#curve41417 $\endgroup$ – user110219 May 4 '15 at 20:18
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.