A New Algorithm for Double Scalar Multiplication over Koblitz Curves
J. Adikari V. S. Dimitrov R. J. Cintra
cs.CR cs.DS















§ INTRODUCTION


Let Koblitz curve be

    E_a : y^2 + xy = x^3 + ax + 1,

where a ∈{ 0, 1}, E(𝔽_2^m) a group of points on E_a for some extension field 𝔽_2^m and n the group order of E_a(𝔽_2^m). Any point P ≡ (x, y) ∈ E_a(𝔽_2^m) has following properties

    [τ]P = (x^2, y^2)
        and    
    -P = (x, x + y),

where τ is called the Frobenius map over E_a(𝔽_2^m). Further, there exists a point at infinity denoted by 𝒪 <cit.>. The point at infinity satisfies the properties,

    [τ]𝒪 = 𝒪    and    
    -𝒪 = 𝒪.


The Frobenius mapping of a point can be computed by squaring its coordinates. The cost of the squaring is very cheap and fast in its hardware implementation with both polynomial and normal basis representations <cit.>. In the digital signature verification of an elliptic curve cryptosystem, double scalar multiplication [k]P + [l]Q consumes most computational power, where P, Q ∈ E_a(𝔽_2^m) and k, l ∈ [1, n - 1]. The scalar k, l are represented in τ-adic expansion to obtain the advantage of Frobenius map by replacing point doublings.

Let ℤ[τ] be a ring of polynomials in the form ∑_i=0^l-1u_iτ^i, where l is the length of the polynomial, u_i ∈{0,± 1} for all 0 < i < l - 1 and u_l-1 = ±1. First, both scalars are converted or reduced in ℤ[τ] to complex numbers such that l is minimal. The reduction in ℤ[τ] is defined as ρ≡ kδ, where k is an integer in [1, n - 1] and δ = (τ^m - 1)/(τ - 1). Next τ-adic non-adjacent form ∑_i=0^l-1u_iτ^i with l/3 average Hamming weight is computed <cit.>. Then two τNAFs are used as inputs to generate τ-adic joint sparse form (τJSF) of both scalars with average Hamming weight of l/2 <cit.>.

Dimitrov et al. has introduced the two dimensional Frobenius expansion (TDFE) ∑_i=0^l - 1∑_j=0^ku_i,jτ^i(τ - 1)^j, where l is the length of the τ-adic expansion, u_i,j∈{0, ±1} and k is an integer to compute single scalar multiplication <cit.>. Note that TDFE can be reduced to a polynomial in ℤ[τ] <cit.>.

Our approach towards the double scalar representation is based on TDFE. Our algorithm delivers a joint and sparse two dimensional representation that can be reduced to ℤ[τ]. It is used with Straus idea <cit.> to compute double scalar multiplication and perform minimum number of point additions. Our new algorithm, joint two dimensional Frobenius expansion (JTDFE) is having 15% improvement in terms of speed compared to τJSF in its implementation on a field programmable gate array (FPGA).

This paper is arranged as follows: two dimensional Frobenius expansion is discussed in Section <ref>. The construction of new algorithm JTDFE is discussed in Section <ref>. Section <ref> explains the hardware implementation. We conclude the paper in Section <ref>.



§ TWO DIMENSIONAL FROBENIUS EXPANSION


The Frobenius map τ is a complex number with value (μ + √(-7))/2, where μ = (-1)^1 - a. A complex number in the form of a + τ b, where a, b ∈ℤ is called a Kleinian integer <cit.>. Next, we define the {τ, τ - 1}-Kleinian integer.

{τ, τ - 1}-Kleinian integer
A Kleinian integer ω of the form ω = ±τ^x(τ - 1)^y, where x,y ∈ℤ^* is called a {τ, τ - 1}-Kleinian integer.


The two dimensional Frobenius expansion of an integer can be represented as in the following equation:

    k = ∑_i=1^ds_iτ^a_i(τ - 1)^b_i,

where d is the length of the expansion s_i = ±1 and a_i, b_i ∈ℤ^*. We rearrange (<ref>) as follows:

    k = ∑_l = 1^max(b_i)(τ - 1)^l (∑_i=1^max(a_i,l)s_i,lτ^a_i,l ),

where max(a_i,l) is the maximum power of τ that is multiplied by (τ - 1)^l in (<ref>).

Algorithm <ref> illustrates the routine to compute the single scalar multiplication [k]P when the {τ, τ - 1}-expansion of k is given. In order to simplify, we denote the terms corresponding to (τ - 1)^l in (<ref>) with r_l(k), i.e. r_l(k) = ∑_i=1^max(a_i,l)s_i,lτ^a_i,l. The multiplication [τ - 1]P costs one Frobenius mapping and a point addition. Therefore, max(b_i) should be limited when the two dimensional Frobenius expansion is computed.



Finding an algorithm that returns a fairly short representation of k as the sum of {τ, τ - 1}-Kleinian integers is an absolute need. The greedy algorithm given in <cit.> is used to obtain such a representation. Greedy algorithm does not always return the canonical {τ, τ - 1}-expansion. Note that the complexity of the greedy algorithm depends crucially on the time spent to find the closest {τ, τ - 1}-Kleinian integer to the current Kleinian integer.

However, finding the closest Kleinian integer  in an intermediate step of  greedy algorithm is achieved by precomputing all Kleinian integers ±τ^x(τ - 1)^y for x, y ∈ℤ^* less than certain bounds and using an exhaustive search. Using divide-and-conquer principle, Dimitrov et al. have invented an effective method to generate an efficient two dimensional Frobenius expansion for computing single scalar multiplication <cit.>. Further they have conjectured following:

Length of Two Dimensional Frobenius Expansion

Every Kleinian integer ξ = a + bτ, can be represented as the sum of at most
O(logN(ξ)/loglogN(ξ))
{τ, τ - 1}-Kleinian integers, where N(ξ) = (a + bτ)(a + bτ) is the norm of ξ.


They highlighted that use of two complex bases has increased the theoretical difficulties in proving the Conjecture <ref>. Nevertheless, that lead to a more important practical blocking algorithm given in <cit.>.



§ JOINT BLOCKING ALGORITHM


In this section, we present the construction of our new algorithm to return a joint and sparse representations for a pair of Kleinian integers η_0, η_1 ∈ℤ[τ]. Algorithm <ref> illustrates the procedure to compute a joint two dimensional Frobenius expansion in ℤ[τ] for a pair of Kleinian integers.



A window size w is fixed prior to running the algorithm. Then the optimal joint two dimensional Frobenius expansions for all possible pairs of w-bit τ-adic representations are precomputed and given as another input.

First, two τ-adic expansions ∑_i=0^l-1u_iτ^i, where u_i ∈{0, 1} and l is the length of the longer expansion, in ℤ[τ] are computed. Next both τ-adic expansions are arranged as in (<ref>) to generate joint columns.

    [ η_0; η_1 ] = [ η_0,l-1       …   η_0,1   η_0,0; η_1,l-1       …   η_1,1   η_1,0 ]

The i^th joint column in (<ref>) has two elements η_0,i, η_1,i∈{0, 1} for all i satisfying 0 ≤ i < l. If one τ-adic expansion is shorter than the other, then the coefficients of higher degrees of τ of shorter expansion should be set to zero.

Two τ-adic expansions are separated into w-bit ⌈ l/w⌉ number of blocks. The least significant w bits of τ-adic expansion have the label block 0, while the most significant bits have label block ⌊ l/w⌋.

At step <ref> of Algorithm <ref>, i^th block of η_0 and η_1 representations are considered to find the i^th block of optimal joint two dimensional Frobenius expansion. This is achieved by a look-up-table approach. Once the i^th block of optimal joint two dimensional Frobenius expansion is obtained, all elements are multiplied by τ^iw and appended to the relevant lists. We repeat this step for ⌈ l/w⌉-times to obtain the complete joint two dimensional Frobenius expansion. Example 3 illustrates the execution of Algorithm <ref>.

Joint Two Dimensional Frobenius Expansion

We consider two Kleinian integers η_0 = -5 - 18τ and η_1 = -21 + 5τ with a = 1 in this example. As the first step we compute τ-adic expansions for both η_0 and η_1 (Step <ref> of Algorithm <ref>):

    [ -5 - 18τ        =        (        1        1        0        1        0        1        1        0        1        1      )_τ; -21 + 5τ        =        (                 1        1        1        0        1        1        0        0        1      )_τ ]

To construct the joint expansion we need to make both expansions in the same length. Therefore we append a zero to the beginning of the τ-adic representation of -21 + 5τ:

    [ -21 + 5τ        =        (        0        1        1        1        0        1        1        0        0        1      )_τ ]

Let w = 5. We divide both τ-adic expansions into 5-bit blocks and find the optimal joint two dimensional Frobenius expansion for each block. The pair 11011_τ and 11001_τ have -(τ - 1)^4 and -τ - (τ - 1)^4. Most significant bits pair have τ^3 + τ(τ - 1)^2 and τ^3 - τ(τ - 1)^2 (Step <ref> of Algorithm <ref>). We multiply last pair by τ^5 to obtain final results (Step <ref> of Algorithm <ref>). The optimal joint two dimensional Frobenius expansion is given by:

    [ -5 - 18τ; -21 + 5τ ] = (
    [      τ^8 + τ^6(τ - 1)^2- (τ - 1)^4; τ^8 - τ^6(τ - 1)^2 - τ - (τ - 1)^4 ])_J2DFE


The main advantage of a joint representation in double scalar multiplication in elliptic curve cryptography is that Straus' method can be applied with some precomputations to improve the efficiency <cit.>. Considering Example 3, if A = P + Q and S = P - Q are precomputed, we can compute [- 5 - 18τ]P + [- 21 + 5τ]Q with four point additions. We do not consider any additions due to (τ - 1) terms in the total cost.

    [- 5 - 18τ]P + [- 21 + 5τ]Q = [τ^8]A + [τ^6(τ - 1)^2]S
     -[τ]Q - [(τ - 1)^4]A

Then we can apply Algorithm <ref> to compute final point with (<ref>). The point negations over Koblitz curves is only a field addition and can be neglected in terms of cost compared to field multiplication. Fig. <ref> illustrates the graphical representation of joint two dimensional Frobenius expansion of η_0 = -5 - 18τ and η_1 = -21 + 5τ.



The generation of precomputed optimal joint representations for all possible combinations of pairs of Kleinian integers for a given window w is achieved by an exhaustive search. This computation needs to be done only once per curve and a given window size. 












































§ HARDWARE IMPLEMENTATION AND RESULTS


The double scalar multiplication over 𝔽_2^163 with joint two dimensional Frobenius expansion is implemented in VHDL and placed and routed to Xilinx  FPGA by executing Xilinx Integrated Software Environment (ISE™) version . The window size is set to w=5 and maximum exponent of τ - 1 is limited to four. We describe the hardware architecture of our circuit in this section. The top-level design components and architecture of the circuit are illustrated in Fig. <ref>.



The circuit is partitioned into four high-level components, namely, main controller (MC), binary arithmetic processor (BAP), integer-to-τ converter (ITC) and registers. In our implementation, databus width is set to 163 bits. Other than u_0 and u_1, inputs and outputs of main controller are handshaking signals between MC and other units.

The binary arithmetic processor performs four basic arithmetic operations needed for point multiplication, namely, addition, squaring, multiplication and inversion. All arithmetic operations are performed in the normal basis representation. Addition and squaring can be executed in a single clock cycle. Addition is an exclusive OR (XOR) operation and squaring is a cyclic shift operation in the normal basis representation <cit.>. Multiplication is a direct implementation of Massey-Omura multiplier with computing four bits in one clock cycle <cit.>. Therefore we need only forty one clock cycles for the multiplication. The inversion is performed with Itoh-Tsuji architecture <cit.>. It needs nine multiplications to calculate the inversion of an element in 𝔽_2^163. Once the multiplication or inversion is performed, binary arithmetic processor sends out a job completion signal by setting DONE of BAP to high.

The primary job of the integer-to-τ converter is to compute the joint two dimensional Frobenius expansion from a pair of integers. Our implementation comprises of two integer-to-τ converters with lazy reduction introduced in <cit.>, because it is faster and needs less area in hardware implementations. The converter is slightly modified to generate nonnegative elements for the τ-adic expansion, whereas the circuit proposed in <cit.> generates the τNAF. Then a precomputed look-up-table is used to compute joint two dimensional Frobenius expansion. The signal DONE of ITC is high when first w bits of each expansion is available for processing.

The registers are used to store point coordinates and intermediate values during point additions. Further some registers can perform cyclic shift operation to facilitate Frobenius mapping on points P, Q, P+Q, and P-Q.

The main controller is designed with a finite state machine to perform the double scalar multiplication with other three components. With the INIT of MC set to high, main controller begins loading integers k_0, k_1 and P, Q point coordinates x_P, y_P, x_Q, y_Q to registers. Then k_0 and k_1 are loaded into the integer-to-τ converter simultaneously. Once DONE of ITC is high, the joint two dimensional Frobenius expansion is read to main controller and the double scalar multiplication is started. The main controller knows that it has reached to the end of computation, when the TOP of ITC is high. Final results are stored in the registers and DONE of MC is set to high.

Affine coordinates are used in precomputations. Mixed coordinates are used for computing P and Q related calculations and needs 8 field multiplications and 5 field squarings. For other point additions, i.e. P ± Q related computations we have used López-Dahab projective coordinates in this implementation <cit.>. These point additions require 13 field multiplications and 4 field squarings.

The hardware implementations are carried out for both τ-adic joint sparse form and joint two dimensional Frobenius expansion based double scalar multiplication. A window value w = 5 and maximum τ - 1 exponent max(b_i) = 4 are selected for the joint two dimensional Frobenius expansion implementation. The y^2 + xy = x^3 + x + 1 is considered over binary field 𝔽_2^163. We have considered the curve parameters and field for implementation which are specified by NIST. We have implemented both circuits in Xilinx  FPGA and tested for 10,000 pair of integers, k, l and pair of points, P, Q. The summary of the experimental results are given in Table <ref>.



The results collected in Table <ref> are based on the synthesis goals set for speed maximization. Time is read for each algorithm when the circuit is operating at its maximum frequency.



  
Note:
Timings given for single scalar multiplication in <cit.> are very smaller than the figures for double scalar multiplication presented in this paper. That is mainly due to three reasons: Firstly, the clock speed in <cit.> is two times as fast as that of this implementation. Secondly, average number of point additions in double scalar multiplication is more than twice of that in single scalar multiplication. Thirdly, field multiplication in <cit.> needs 9 clock cycles, while in this implementation we need 41 clock cycles.




§ CONCLUSIONS


The joint two dimensional Frobenius expansion outperforms the state-of-the-art τ-adic joint sparse form in double scalar multiplication over Koblitz curves, in speed, according to the experimental results presented in Table <ref>. The area of the new architecture has increased by about 45% of that of τJSF architecture. Having greater values for window sizes and maximum τ - 1 exponents, the speed of the double scalar multiplication can be improved. When the window size is increased the size of look-up-table in integer-to-τ conversion grows exponentially. We will investigate on different combinations of w and maximum τ - 1 exponent as future work.



1


koblitz_cm_91
N. Koblitz, “CM-Curves with Good Cryptographic Properties,” in CRYPTO
  '91: Proceedings of the 11th Annual International Cryptology Conference on
  Advances in Cryptology.1em plus 0.5em minus 0.4emLondon, UK:
  Springer-Verlag, 1992, pp. 279–287.

hanmenvan04
D. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve
  Cryptography.1em plus 0.5em minus 0.4emSpringer, 2004.

solinas00
J. A. Solinas, “Efficient arithmetic on Koblitz curves,” Design Codes
  Cryptography, vol. 19, no. 2-3, pp. 195–249, 2000.

ciet_improved_2003
M. Ciet, T. Lange, F. Sica, and J. Quisquater, “Improved algorithms for
  efficient arithmetic on elliptic curves using fast endomorphisms,” in
  Advances in Cryptology, EUROCRYPT 2003, 2003, pp. 388–400.

dimitrov2008provably
V. S. Dimitrov, K. U. Järvinen, M. J. Jacobson, W. F. Chan, and Z. Huang,
  “Provably sublinear point multiplication on Koblitz curves and its
  hardware implementation,” Computers, IEEE Transactions on, vol. 57,
  pp. 1469–1481, 2008.

strauss64
E. G. Straus, “Addition chains of vectors (problem 5125),” American
  Mathematical Monthly, vol. 70, pp. 806–808, 1964.

conway_quaternions_2003
J. H. Conway and D. Smith, On Quaternions and Octonions, 1st ed.1em plus 0.5em minus 0.4emAK Peters, 2003.

brumley10
B. B. Brumley and K. U. Järvinen, “Conversion algorithms and
  implementations for Koblitz curve cryptography,” Computers, IEEE
  Transactions on, vol. 59, pp. 81–92, 2009.

agnew_arithmetic_1993
G. Agnew, T. Beth, R. Mullin, and S. Vanstone, “Arithmetic operations in
  GF(2^m),” Journal of Cryptology, vol. 6, no. 1, pp. 3–13, Mar.
  1993.

patent_4587627
J. K. Omura and J. L. Massey, “Computational method and apparatus for finite
  field arithmetic,” no. 4587627, May 1986, (US Patent 4587627).

Itoh_fast_1988
T. Itoh and S. Tsujii, “A fast algorithm for computing multiplicative inverses
  in GF(2^m) using normal bases,” Information and Computation,
  vol. 78, no. 3, pp. 171–177, Sept. 1988.

lopez_fast_1999
J. López and R. Dahab, “Fast Multiplication on elliptic curves Over
  GF(2^m) without precomputation,” in Cryptographic Hardware and
  Embedded Systems, ser. Lecture Notes in Computer Science.1em plus
  0.5em minus 0.4emSpringer Berlin / Heidelberg, 1999, vol. 1717, pp.
  316–327.


























