Revisiting Orthogonal Lattice Algorithms: Enhanced AIOL-σ Algorithm for General Approximate Common Divisor Problem

We revisit orthogonal lattice (OL) attacks and rounding techniques (RT) for solving the Approximate Common Divisor (ACD) problem. First, we systematically organize all existing OL algorithms within a novel logical framework proposed in this work. Specifically, we restate four existing OL algorithms, construct two OL algorithms using existing conclusions, refine the AIOL algorithm by adjusting the number of samples, and propose a new OL method (Algorithm 1: AIOL-σ). Second, by introducing the Log-Hermite-factor σ as a novel lattice quality metric, we theoretically re-analyze OL algorithms associated with σ. To establish a quantitative link between ACD parameters and σ, derive a new upper bound for short vector norms in the target lattice, and obtain a new lower bound for the required number of samples, our proposed algorithm identifies the optimal value of parameter α (a lattice parameter introduced in Xu et al.’s work) as 1. Consequently, our new algorithm remains invariant under the RT technique. Finally, experimental results demonstrate that the proposed algorithm achieves state-of-the-art performance in both attack efficiency and sample complexity. Finally, the great potential of the ACD problem in IoT applications is verified through a simple lightweight authentication protocol. In conclusion, the great potential of the ACD problem in IoT applications is verified through a simple lightweight authentication protocol.