General 4-GLV Lattice Reduction Algorithms
Bei Wang, Xianhong Xie, Songsong Li, Yi Ouyang, Honggang Hu · 2021 17th International Conference on Computational Intelligence and Security (CIS) · 2021
With two$\mathbb{Z}$-linear independence endomorphisms$\Phi$and$\Psi$satisfying$\Phi^{2}+r\Phi+s=0$and$\Psi^{2}-t_{\Psi}\Psi+n_{\Psi}=0$, we construct general 4-GLV lattice reduction algorithms with$\mathbb{Z}[\Psi\vert$principal maximal orders of imaginary quadratic fields$\mathbb{Q}(\sqrt{-d})$. The algorithms can be used to calculate short bases for 4-GLV decompositions on elliptic curves (or Jacobians of genus 2 curves). Our algorithms have a theoretic upper bound of output$Cn^{1/4}$, where \begin{align*} C=\begin{cases} {\frac{4+2\sqrt{d+1}}{3-d}} (\sqrt{1+\vert r\vert +\vert s\vert }),\ &\text{if}\ \mathbb{Z}[\Psi]=\mathbb{Z}[\frac{1+\sqrt{-d}}{2}],\\ \frac{4\sqrt{d}}{(4\sqrt{d}-(d+1)}(\sqrt{1+\vert r\vert +\vert s\vert }),\ &\text{if}\ \mathbb{Z}[\Psi]=\mathbb{Z}[\frac{1+\sqrt{-d}}{2}].\end{cases}\end{align*} Especially, our algorithms cover the case$\mathbb{Z}[\Psi]=\mathbb{Z}[\sqrt{-1}]$of Yi et al. (SAC 2017) and the case$\mathbb{Z}[\Psi]=\mathbb{Z}[\frac{1+\sqrt{-3}}{2}]$of Wang et al. (AMC 2021).