Batch Addition for Multi-Scalar Multiplication (MSM)

Problem

Given two sets of EC points

{P_{i}}

and

{Q_{i}}

i \in {1, . . ., n}

, calculate

{R_{i} = P_{i} + Q_{i}}

P = (x_{P}, y_{P})

Q = (x_{Q}, y_{Q})

, and

R = P + Q = (x_{R}, y_{R})

, an addition operation on an elliptic curve in short Weierstrass form

y^{2} = x^{3} + a x + b

is defined as below [1],

k = {\begin{cases} \frac{y_{Q} - y_{P}}{x_{Q} - x_{P}} & if P \neq \pm Q \\ \frac{3 x_{P}^{2} + a}{2 y_{P}} & if P = Q \end{cases} x_{R} = k^{2} - x_{P} - x_{Q} y_{R} = k (x_{P} - x_{R}) - y_{P}

We observe that each addition requires an inversion operation that is way more expensive than muliplication and addition [2].

Therefore, we want to reduce the number of inversions needed to caculate

{R_{i}}

Consider n pair of points,

P_{i} = (x_{P_{i}}, y_{P_{i}}), Q_{1} = (x_{Q_{i}}, y_{Q_{i}}), i \in {1, . . ., n}

We want to calculate

R_{i} = P_{i} + Q_{i} = (x_{R_{i}}, y_{R_{i}})

Denote

λ_{i} = x_{Q_{i}} - x_{P_{i}}

The product of all

λ

s left to

λ_{i}

yields

L_{i} = \prod_{j = 1}^{i - 1} λ_{j}

Then, the product of all

λ

s right to

λ_{i}

R_{i} = \prod_{j = i + 1}^{n} λ_{j}

With the results above, we can calculate inversion as the following

\frac{1}{x_{Q_{i}} - x_{P_{i}}} = \frac{1}{λ_{i}} = \frac{L_{i} R_{i}}{\prod_{i} λ_{i}}

Since

\prod_{i} λ_{i}

does not change with

i

and can be precomputed, the same inversion result can be shared across

R_{i} = P_{i} + Q_{i}

Therefore, we reduced the number of inversions required to calculate

$N$ additions from
$N$ to
$1$ .