Algorithms for the Shortest Vector Problem in $2$-dimensional Lattices, Revisited

Efficiently solving the Shortest Vector Problem (SVP) in two-dimensional lattices holds practical significance in cryptography and computational geometry. While simpler than its high-dimensional counterpart, two-dimensional SVP motivates scalable solutions for high-dimensional lattices and benefits applications like sequence cipher cryptanalysis involving large integers. In this work, we first propose a novel definition of reduced bases and develop an efficient adaptive lattice reduction algorithm $\mathbf{\text{CrossEuc}}$ that strategically applies the Euclidean algorithm across dimensions. Building on this framework, we introduce $\mathbf{\text{HVec}}$, a vectorized generalization of the Half-GCD algorithm originally defined for integers, which can efficiently halve the bit-length of two vectors and may have independent interest. By iteratively invoking $\mathbf{\text{HVec}}$, our optimized algorithm $\mathbf{\text{HVecSBP}}$ achieves a reduced basis in $O(\log nM(n))$ time for arbitrary input bases with bit-length $n$, where $M(n)$ denotes the cost of multiplying two $n$-bit integers. Compared to existing algorithms, our design is applicable to general forms of input lattices, eliminating the cost of pre-converting input bases to Hermite Normal Form (HNF). The comprehensive experimental results demonstrate that for the input lattice bases in HNF, the optimized algorithm $\mathbf{\text{HVecSBP}}$ achieves at least a $13.5\times$ efficiency improvement compared to existing methods. For general-form input lattice bases, converting them to HNF before applying $\mathbf{\text{HVecSBP}}$ offers only marginal advantages in extreme cases where the two basis vectors are nearly degenerate. However, as the linear dependency between input basis vectors decreases, directly employing $\mathbf{\text{HVecSBP}}$ yields increasingly significant efficiency gains, outperforming hybrid approaches that rely on prior $\mathbf{\text{HNF}}$ conversion.