HackMDGLV 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.
\(\newcommand{sF}{\mathbb{F}_n}\) \(\newcommand{zz}{\mathbb{Z}\times\mathbb{Z}}\) \(\newcommand{g}{\gamma}\) \(\newcommand{b}{\beta}\)
Scalar decomposition
The following homomorphism is defined: \[ \begin{aligned} f: \zz & \to \sF \\ (i,j) & \mapsto i + \lambda j \end{aligned} \] where \(\lambda\) is the endoscalar of the curve.
The problem of decomposing a given scalar \(k \in \sF\) consists of finding a pair \((k_1, k_2) \in \zz\) 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 \(\g, \b\) such that \(f(\g) = f(\b) = 0\).
The problem now turns into finding a vector \(v\) in the lattice generated by \([\b, \g]\) that is close to \((k, 0)\).
With such vector \(v\) we easily compute
\[
(k_1, k_2) := (k, 0) - v
\]
which is short, (\(\leq \max{(\lVert\b\rVert, \lVert\g\rVert)}\))
and satisfies our fist condition, since
\[
f((k_1, k_2)) = f((k, 0)) - f(v) = k
\]
Let \(v := t_1 \cdot \b + t_2 \cdot \g\).
We solve the system
\[
\begin{pmatrix}
\b_1 & \g_1 \\
\b_2 & \g_2
\end{pmatrix}
\begin{pmatrix}
t_1 \\
t_2
\end{pmatrix} =
\begin{pmatrix}
k \\
0
\end{pmatrix}
\]
\[ \begin{pmatrix} t_1 \\ t_2 \end{pmatrix} = \frac{1}{d} \begin{pmatrix} \g_2 & - \g_1 \\ -\b_2 & \b_1 \end{pmatrix} \begin{pmatrix} k \\ 0 \end{pmatrix} \] where \(d\) is the determinant of the \([\g, \b]\) matrix.
We get \[ \begin{align} t_1 =& \frac{1}{d} \cdot k \cdot \g_2 \\ t_2 =& -\frac{1}{d} \cdot k \cdot \b_2 \end{align} \]
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 \([\b, \g]\)-generated lattice. Now we have:
\[ \begin{pmatrix} k_1 \\ k_2 \end{pmatrix} = \begin{pmatrix} k \\ 0 \end{pmatrix} - \begin{pmatrix} \b_1 & \g_1 \\ \b_2 & \g_2 \end{pmatrix} \begin{pmatrix} \lfloor t_1 \rceil \\ \lfloor t_2 \rceil \end{pmatrix} \]
We will only compute \(-k_2\): \[ -k_2 = \b_2 \cdot \lfloor t_1 \rceil + \g_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).
