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

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

Multi-Scalar Multiplication (MSM) is the algorithm for calculating the sum of multiple scalar multiplications. Usually, G is a cyclic group defined on the elliptic curve of y^2=x^3+ax+b on the finite field of F_p. If the group operation is conducted by the plain algorithm of fast exponentiation, the number of group operations needed for every a_i.P_i is 1.5bn times on average.
image
Sin7Y HackerNoon profile picture

Sin7Y

Sin7Y is a tech team that explores layer 2, cross-chain, ZK, and privacy computing. #WHAT IS HAPPENING IN BLOCKCHAIN#

twitter social icon

Let G be a cyclic group, P_i ∈ G is the element in the group, a_i ∈ Z is the scalar, and the Multi-Scalar Multiplication (MSM) is the algorithm for calculating ∑_{i=1}^{n} a_{i} P_{i} , 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, G is a cyclic group defined on the elliptic curve of y^2=x^3+ax+b on the finite field of F_p, with the order |G| being b ≈ 256 bits, and 0 ≤ a_i< 2^b. If the group operation is conducted by the plain algorithm of fast exponentiation, the number of group operations needed for every a_i.P_i is 1.5bn times on average, and for all a_i.P_i is 1.5b times in total. Next, we will introduce some optimization methods corresponding to larger n.

Optimization Based on the Windowing Technique

We can split the b bit scalar into c width windows: reduce the scalar to 2^c base system.

image

Here, Q_j=∑_{i=1}^{n} a_{i j} P_{i}, so we reduce the original algorithm issue of b-bit MSM into a smaller c-bit issue. We can put the same scalars from ∑_{i=1}^{n} a_{i j} P_{i} into a bucket and write them in another form:

image

For example, when c = 3, it is calculated as:

image

When calculating ∑kS_k, set the partial sum T_l=S_l+⋯+S_k, then

image

However, the operation results of T_l can be obtained through the recurrence sequence T_l=T_l+1+S_l. It means that only one group operation is needed for the operation for each T_l. Under the MSM algorithm with cc-bit scalar, all S_k requires n−2^c+1 times of group operation. All T_k requires 2^c−1 times and the sum of these T_k requires 2^c−2 times of group operation. Therefore, each window with the value of c requires n+2^c−2 times of group operations. The operation of ∑_{j=0}^{b / c-1} Q_{j} 2^{j c} only requires the normal method of fast exponentiation by (b/c−1)(c+1)=b − c + b/c−1 times of group operation.


In summary, we can conclude that the total number of group operations required by the method of the Windowing Technique of a width of c is

image

Set c = logn, then the number of group operations is 2bn/logn. When n≈10^5 , the number of group operations reduces to 1/12 of its original value.

Optimization Based on Group Endomorphism

For the cyclic group G on the elliptic curve y^2=x^3+ax+b on the finite field F_p, if the following group endomorphism of φ can be found: there exists α,β ∈ F_p, satisfying φ(x,y)=(αx,βy) holds for all the points on G, then it is easy to prove that such an endomorphism is a multiplication map, namely there is a λ making φ(P)=λP hold for all the points of P on G, 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 F_p to both the values of abscissa and ordinate. The algorithm can be further optimized based on this important property.


When λ = −1, α = 1, β = −1. 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 e_{i}.2^{i}, e_{i} ∈ {−1,0,1} and any two adjacent e_i cannot be non-zero at the same time. Compared to the b-bit scalars, the group operation number in the fast exponentiation algorithm can be reduced from the original average of 3/2⋅b times to 4/3⋅b times. This technique can also be used to optimize the Windowing Technique. After writing a_i to 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 a_i=∑_{j=0}^{b / c-1} a’_{i, j}^2^{j c} and -2^{c-1} <= a’_{i, j}^ <= 2^{c-1} 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 2^c , and the overall number of group operations required is reduced from (1) to:

image

If the parameters of the elliptic curve are special, for example, the BLS curve can be written as y^2=x^3+b, and p ≡ 1( mod3 ), take third-order element α from F_p^x, then there is a corresponding λ that holds λ(x,y)=(αx,y)


image

Algorithm 1: Signed Digits


In addition, λ3 ≡ 1(mod |G| ). Then the multiplication operation can be optimized as follows:

image

From [1], we can find a small enough scalar |m1|, |m2|<√G to make the above equation true, which gives us a way to reduce the multiplication of bb bits into the multiplication of two b/2 bits. Use it into the Windowing Technique, and the number of group operations is reduced to

image

In summary, both the above two optimization methods can reduce the number of group operations by 5.5% when n=10^5.

References

[1] Francesco Sica, Mathieu Ciet, and Jean-Jacques Quisquater. Analysis of the gallant-lambert-vanstone method based on efficient endomorphisms: Elliptic and hyperelliptic curves. In International Workshop on Selected Areas in Cryptography, pages 21–36. Springer, 2002.

react to story with heart
react to story with light
react to story with boat
react to story with money

Related Stories

L O A D I N G
. . . comments & more!