Let be a cyclic group, is the element in the group, is the scalar, and the Multi-Scalar Multiplication (MSM) is the algorithm for calculating , the sum of multiple scalar multiplications. As the group operation is more complicated than the addition and multiplication of elements in the finite field, the MSM algorithm is employed to reduce the number of times of group operation as much as possible. Usually, is a cyclic group defined on the elliptic curve of on the finite field of , with the order being bits, and . If the group operation is conducted by the plain algorithm of fast exponentiation, the number of group operations needed for every is times on average, and for all is times in total. Next, we will introduce some optimization methods corresponding to larger . G P_i ∈ G a_i ∈ Z ∑_{i=1}^{n} a_{i} P_{i} G y^2=x^3+ax+b F_p | | G b ≈ 256 0 ≤ a_i< 2^b a_i.P_i 1.5bn a_i.P_i 1.5b n Optimization Based on the Windowing Technique We can split the bit scalar into c width windows: reduce the scalar to base system. b 2^c Here, } , so we reduce the original algorithm issue of -bit MSM into a smaller -bit issue. We can put the same scalars from into a bucket and write them in another form: Q_j=∑_{i=1}^{n a_{i j} P_{i} b c ∑_{i=1}^{n} a_{i j} P_{i} For example, when , it is calculated as: c = 3 When calculating , set the partial sum T_l=S_l+⋯+S_k, then ∑kS_k However, the operation results of can be obtained through the recurrence sequence . It means that only one group operation is needed for the operation for each . Under the MSM algorithm with cc-bit scalar, all requires times of group operation. All requires times and the sum of these requires times of group operation. Therefore, each window with the value of c requires times of group operations. The operation of } only requires the normal method of fast exponentiation by times of group operation. T_l T_l=T_l+1+S_l T_l S_k n−2^c+1 T_k 2^ 1 c− T_k ^c−2 2 n+2^c−2 ∑_{j=0}^{b / c-1} Q_{j} 2^{j c (b/c−1)(c+1)=b − c + b/c−1 In summary, we can conclude that the total number of group operations required by the method of the Windowing Technique of a width of is c Set , then the number of group operations is . When , the number of group operations reduces to of its original value. c = logn 2bn/logn n≈10^5 1/12 Optimization Based on Group Endomorphism For the cyclic group on the elliptic curve on the finite field F_p, if the following group endomorphism of φ can be found: there exists , satisfying holds for all the points on , then it is easy to prove that such an endomorphism is a multiplication map, namely there is a making hold for all the points of on , which means that whenever we know the coordinates of one point, we can change it to the coordinates of another point simply by multiplying a number in to both the values of abscissa and ordinate. The algorithm can be further optimized based on this important property. G y^2=x^3+ax+b α,β ∈ F_p φ(x,y)=(αx,βy) G λ φ(P)=λP P G F_p When . The reverse value of one point can be obtained only by taking the opposite number from the ordinate. Based on this feature, in the plain fast exponentiation algorithm, the scalar can be written into the non-adjacent form (NAF), namely and any two adjacent cannot be non-zero at the same time. Compared to the -bit scalars, the group operation number in the fast exponentiation algorithm can be reduced from the original average of times to times. This technique can also be used to optimize the Windowing Technique. After writing to λ = −1, α = 1, β = −1 e_{i}.2^{i}, e_{i} ∈ {−1,0,1} ∑ e_i b 3/2⋅b 4/3⋅b a_i a_i=∑_{j=0}^{b / c-1} a_{i, j} 2^{j c}, 0 <= a_{i, j}<2^{c} conduct the following operation: The result of and - can be obtained. Since the complexity of addition and subtraction in group operation of an elliptic curve is the same, we can put these terms into a bucket according to the absolute value of scalars. Therefore, the number of groups can be reduced from the original 2c to , and the overall number of group operations required is reduced from (1) to: a_i=∑_{j=0}^{b / c-1} a’_{i, j}^2^{j c} 2^{c-1} <= a’_{i, j}^ <= 2^{c-1} 2^c If the parameters of the elliptic curve are special, for example, the BLS curve can be written as , and , take third-order element α from F_p^x, then there is a corresponding that holds y^2=x^3+b p ≡ 1( mod3 ) λ λ( )=( ) x,y αx,y Algorithm 1: Signed Digits In addition, . Then the multiplication operation can be optimized as follows: λ3 ≡ 1(mod |G| ) From [1], we can find a small enough scalar | |, | |<√ to make the above equation true, which gives us a way to reduce the multiplication of bb bits into the multiplication of two bits. Use it into the Windowing Technique, and the number of group operations is reduced to m1 m2 G b/2 In summary, both the above two optimization methods can reduce the number of group operations by when . 5.5% n=10^5 References [1] Francesco Sica, Mathieu Ciet, and Jean-Jacques Quisquater. Analysis of the gallant-lambert-vanstone method based on eﬀicient endomorphisms: Elliptic and hyperelliptic curves. In International Workshop on Selected Areas in Cryptography, pages 21–36. Springer, 2002.

Optimization of Multi-Scalar Multiplication Algorithm: Sin7Y Tech Review (21)

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

A Study on Parallel Execution: Everything You Need to Know

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

A Study on Parallel Execution: Everything You Need to Know

10 Things Everyone Should Know About Machine Learning

10 Repositories that Will Transform the Way You Approach Technical Interviews

10 (Free) Data Structure and Algorithm Courses Junior Developers Should Explore

10 Data Structure & Algorithms Books Every Programmer Should Read

The Noonification: How to Develop a DSL in Kotlin (12/12/2023)

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps