Once upon a time, the cool kids used $w$-NAF for their elliptic curve scalar multiplication. Well, the cool kids who were implementing elliptic curve cryptography anyway.
The basic idea is simple enough. You want to multiply some given point $Q$ by a scalar $n$. So you pick a window width $w$, and split $n$ into a sum of signed $w$-bit pieces \[ n = \sum_i n_i 2^i \] with $-2^{w-1} \le n_i < 2^{w-1}$ for each $i$, and with at most one nonzero $n_i$ in any group of $w$. Then you walk through these, in descending order of $i$, multiplying an accumulator by appropriate small multiples of $Q$ plucked from a table and doubling.
Then we found out that actually this was a mostly terrible idea because it broadcasts $n$ through every side-channel available. The new cool idea is to convert $n$ to a signed-digit representation, so \[ n = \sum_i n_i 2^{wi} \] again, with $-2^{w-1} \le n_i < 2^{w-1}$. Now the digits are in predictable places, and all you need to avoid leakage is to do a constant-time table lookup.
This is annoying. And a waste of time and effort. There’s a unique representation of $n$ subject to these constraints. It’s possible to do the signed-digit recoding from right to left in constant time, propagating loans (like borrows in subtraction, but in the other direction) as you go. But you want to do the scalar multiplication from left to right so that you can use your table of small multiples. And, while you can do the signed-digit recoding left-to-right, you might need to look arbitrarily far ahead before you can commit to a digit. (If you see a long sequence of $2^{w-1} - 1$ digits, then you’ll have to inspect the digit after that to tell you whether they all lend one leftwards or not.) I suppose you could do this in constantly quadratic time, but I don’t think anyone would be impressed by that.
But you can have your cake and eat it too, as long as you give up on the unique representation. Relax the condition on $n_i$ to permit $2^{w-1} \le n_i \le 2^{w-1}$ and all is marvellous.
You can calculate an acceptable recoding in one pass, left to right, with one digit lookahead, and therefore in constant time.
You can do this in the same pass as the main scalar multiplication, with no additional storage.
You can work with the same size table of small multiples of $Q$. You already had to cope with the possibility of $n_i = -2^{w-1}$, and dealing with $n_i = \pm 2^{w-1}$ is no harder.
So, suppose you have a current digit $t$, and a lookahead digit $u$. (You start out with $t = 0$ and $u$ is the leftmost digit of $n$ in its standard radix-$2^w$ representation.) If $u \ge 2^{w-1}$, then set $t \gets t + 1$ and $u \gets u - 2^w$ (a loan leftwards); otherwise $u < 2^{2-1}$ and you do nothing. You can now commit to $t$: add $t Q$ to your accumulator or whatever. And finally, move along by setting $t \gets u$ and fetching the next input digit into $u$. At this point, you have $-2^{w-1} \le t < 2^{w-1}$, but you might end up adding one to it when you look at $u$; hence the bound above.
Leave a comment