52 Things: Number 26: Describe the NAF scalar multiplication algorithm.

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. In this week, we describe the NAF scalar multiplication algorithm.

The NAF scalar multiplication algorithm is an enhanced form of scalar multiplication, in which the use of Non-Adjacent Form (NAF) representation decreases the expected running time of the algorithm. In more detail:

Let k be a positive integer and P a point on an elliptic curve E over the field $\mathbb{F}_{q}$. The operation that computes the multiplication $Q = k\cdot P$ is known as the elliptic curve scalar multiplication (or point multiplication) and dominates the execution time of elliptic curve cryptographic schemes. One of the most basic methods to compute a scalar multiplication is based on a double-and-add variant of Horner's rule, known as the binary method. As the name suggests, the two most prominent building blocks of this method are the point doubling and point addition primitives. More particularly, to calculate $k\cdot P$, integer k is represented as $k=k_{n-1}2^{n-1}+k_{n-2}2^{n-2}+ \cdots +k_{1}+k_{0}$ , where $k_{i} \in \{0,1\}$, $i= 0,1,2...,n-1$ (binary representation form). The following algorithms form the additive versions of the basic repeated-square-and-multiply methods for exponentiation [1,2].

INPUT: k = (kt−1,..., k1, k0)2, P ∈ E($\mathbb{F}_{q}$). 
OUTPUT: k $\cdot$ P.
       Q←$\infty$.
       For i from 0 to t−1 do
           If ki  = 1 then Q←Q+P.
           P←2P. 
Return(Q). 

INPUT: k = (kt−1,..., k1, k0)2, P ∈ E($\mathbb{F}_{q}$). 
OUTPUT: k $\cdot$ P.
       Q←$\infty$.
       For i from t−1 down to 0 do
             Q←2Q.
             If ki = 1 then Q←Q+P.
Return(Q). 

The first algorithm processes the bits of k from right to left, while the second processes the bits from left to right. The expected number of ones in the binary representation of k for both  algorithms is t/2≈m/2, therefore the expected running time of both algorithms is approximately m/2 point additions and m point doublings [1]: 

$\frac{m}{2} \cdot A + m \cdot D$.

In 1951, Booth [3] proposed a new scalar binary representation called signed binary method and later Rietweisner [4] proved that every integer could be uniquely represented in this format [5]. More particularly, If P=(x,y)$\in$E($\mathbb{F}_{q}$) then −P=(x,x+y) if $\mathbb{F}_{q}$ is a binary field, and −P=(x,−y) if $\mathbb{F}_{q}$ has characteristic > 3. Thus subtraction of points on an elliptic curve is just as efficient as addition. This motivates us to use a signed digit representation $k=\sum_{i=0}^{l-1} k_i \cdot 2^i$, where $k_i \in \{0, \pm \}$. A particularly useful signed digit representation is the non-adjacent form (NAF). A NAF representation of a positive integer k is an expression $k=\sum_{i=0}^{l-1} k_i \cdot 2^i$ , where  $k_i \in \{0, \pm \}$ , $k_{l-1} \ne 0$ , and no two consecutive digits ki are non-zero. The length of the NAF is l [1].

Properties of NAF [1]:

1. k has a unique NAF denoted NAF(k). 
2. NAF(k) has the fewest non-zero digits of any signed digit representation of k. 
3. The length of NAF(k) is at most one more than the length of the binary representation of k. 
4. If the length of NAF(k) is l, then 2l /3 < k < 2l+1/3.
5. The average density of non-zero digits among all NAFs of length l is approximately 1/3. 

NAF(k) can be efficiently computed using the following algorithm [1]:

INPUT: A positive integer k.
OUTPUT: NAF(k).
       i←0.
       While k≥1 do
             If k is odd then: ki ←2−(k mod 4), k←k−ki;
             Else: ki ←0.
             k←k/2, i←i+1.
Return(ki−1, ki−2,..., k1, k0).

The last algorithm presents the way we can modify the left-to-right binary method for scalar multiplication by using NAF(k) instead of the binary representation of k [1]:

INPUT: Positive integer k, P ∈ E($\mathbb{F}_{q}$). 
OUTPUT: k $\cdot$ P.
       Based on previous algorithm compute NAF(k) =$\sum_{i=0}^{l-1} k_i \cdot 2^i$. 
       Q←$\infty$.
       For i from l−1 down to 0 do
             Q←2Q.
             If ki  = 1 then Q←Q+P.
             If ki  = −1 thenQ←Q−P.
Return(Q).

Based on the third and fifth properties of NAF, the expected running time of the NAF scalar multiplication algorithm is approximately [1]:

$\frac{m}{3} \cdot A + m \cdot D$.

[1] Hankerson, Darrel, Scott Vanstone, and Alfred J. Menezes. "Guide to elliptic curve cryptography". Springer Science & Business Media, 2004.
[2] Jonathan Taverne, Armando Faz-Hernández, Diego F. Aranha, Francisco Rodríguez-Henríquez, Darrel Hankerson, Julio López. "Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction", Journal of Cryptographic Engineering, Vol. 1, No 3, pp. 187-199, 2011.
[3] A.D.Booth, “A Signed binary multiplication technique”, Journal of Applied Mathematics, Vol. 4. No. 2, pp.236-240, 1951 
[4] G.W.Reitwiesner, “Binary Arithmetic”, Advances in computers, Academic Press, Vol. 1, pp.231-308, 1960
[5] Karthikeyan, E. “Survey of elliptic curve scalar multiplication algorithms.” International Journal of Advanced Networking and Applications, Vol. 4, No 2, pp. 1581-1590, 2012