Fake GLV: You don't need an efficient endomorphism to implement GLV-like scalar multiplication in SNARK circuits

Very cool!

A related but under appreciated trick can be used to combine both the normal GLV trick and this “fake GLV” trick. Let E be a curve with an order r subgroup and with efficient CM endomorphism \phi : E \rightarrow E corresponding to multiplication \phi(P) = [a] P where f(a) = 0 \bmod r on the order r subgroup. Let \mathbb{K} = \mathbb{Q}[\alpha]/f(\alpha) be the associated CM number field and let (r_0, r_1) be the smallest values such that r \mid N(r_0 + \alpha r_1).

To show Q = [s] P we can first find (s_0, s_1) such that s = s_0 + a s_1 \bmod r (the ordinary GLV endomorphism trick) and then write s_0 + \alpha s_1 = (u_0 + \alpha u_1) / (v_0 + \alpha v_1) \bmod (r_0 + \alpha r_1) by applying the half gcd algorithm in more or less exactly the same way to s_0 + \alpha s_1 and r_0 + \alpha r_1 over \mathbb{K}. The values u_0, u_1, v_0, v_1 are all about r^{1/4} (up to a constant factor).

Technically this requires that the number field \mathbb{K} be a euclidean domain, which is the case for j invariant 0 (\alpha = \frac{1+ \sqrt{-3}}{2}) and 1728 (\alpha = \sqrt{-1}) curves as well as Bandersnatch since \alpha = \sqrt{-2}, but is not in general true. More generally it suffices to find a short vector (not necessarily the shortest) in the lattice

\mathcal{L} = \{ (u_0, u_1, v_0, v_1, q) : u_0 + u_1 \alpha - v_0 s - v_1 s \alpha + r q = 0 \}

which is always possible using standard lattice reduction techniques like LLL or BKZ. Then to check Q = [s] P it suffices to check [u_0] P + [u_1] \phi(P_1) - [v_0] Q - [v_1] \phi(Q) = \mathcal{O}. This would allow us to apply both tricks to e.g. Bandersnatch and enjoy even better Pippenger-like speed up as a 4-msm.

5 Likes