GLV Multiplication

This note explains the scalar decomposition step on the efficient EC multiplication algorithm proposed in this article.

Some implementations of the algorithm:

• Python implementation
• Go implementation
• Rust implementation
• In-circuit implementation in halo2wrong PR

Here is a good explanation of the whole algorithm along with an implementation: bitcoin secp impl.

$$

$$

$$

$$

Scalar decomposition

The following homomorphism is defined:

$$\begin{array}{rl}f:\mathbb{Z}\times \mathbb{Z}& \to {\mathbb{F}}_n\\ (i,j)& \mapsto i+\lambda j\end{array}$$ where

$\lambda$ is the endoscalar of the curve.

The problem of decomposing a given scalar

$k\in {\mathbb{F}}_n$ consists of finding a pair

$(k_1,k_2)\in \mathbb{Z}\times \mathbb{Z}$ s.t.

$f(k_1,k_2)=k$. The key of the problem is to find the shortest vector possible that satisfies this relation.

First we precompute 2 vectors

$\gamma ,\beta$ such that

$f(\gamma )=f(\beta )=0$.
The problem now turns into finding a vector

$v$ in the lattice generated by

$[\beta ,\gamma ]$ that is close to

$(k,0)$. With such vector

$v$ we easily compute

$$(k_1,k_2):=(k,0)-v$$ which is short, (

$\le max(\Vert \beta \Vert ,\Vert \gamma \Vert )$) and satisfies our fist condition, since

$$f((k_1,k_2))=f((k,0))-f(v)=k$$

Let

$v:=t_1\cdot \beta +t_2\cdot \gamma$.
We solve the system

$$\left(\begin{array}{cc}{\beta }_1& {\gamma }_1\\ {\beta }_2& {\gamma }_2\end{array}\right)\left(\begin{array}{c}{t}_1\\ t_2\end{array}\right)=\left(\begin{array}{c}k\\ 0\end{array}\right)$$

$$\left(\begin{array}{c}{t}_1\\ t_2\end{array}\right)=\frac{1}{d}\left(\begin{array}{cc}{\gamma }_2& -{\gamma }_1\\ -{\beta }_2& {\beta }_1\end{array}\right)\left(\begin{array}{c}k\\ 0\end{array}\right)$$ where

$d$ is the determinant of the

$[\gamma ,\beta ]$ matrix.

We get

$$\begin{array}{rl}{t}_1=& \frac{1}{d}\cdot k\cdot {\gamma }_2\\ t_2=& -\frac{1}{d}\cdot k\cdot {\beta }_2\end{array}$$

Due to the determinant division, these values lie on

$\mathbb{Q}$. We round them to their closest integer value to obtain a point in the

$[\beta ,\gamma ]$-generated lattice. Now we have:

$$\left(\begin{array}{c}{k}_1\\ k_2\end{array}\right)=\left(\begin{array}{c}k\\ 0\end{array}\right)-\left(\begin{array}{cc}{\beta }_1& {\gamma }_1\\ {\beta }_2& {\gamma }_2\end{array}\right)\left(\begin{array}{c}\lfloor t_1\rceil \\ \lfloor t_2\rceil \end{array}\right)$$

We will only compute

$-k_2$:

$$-k_2={\beta }_2\cdot \lfloor t_1\rceil +{\gamma }_2\cdot \lfloor t_2\rceil$$ Then we use the original definition

$k=k_1+\lambda k_2$ to compute

$k_1$:

$$k_1=k+\lambda (-k_2)$$

Finally, instead of returning

$k_1,k_2$, this algorithm will return

$-k_i$ or

$k_i$ choosing the one with a lower absolute value. The choice is indicated with some flags. The output then is (k_1, k_1_neg, k_2, k_2_neg).