Revisiting the Algorithms for the Quaternion \(\ell \) -Isogeny Path Problems

The \(\ell \) -isogeny path problems and their variations are fundamental challenges in isogeny-based cryptography, a prominent contender in post-quantum cryptography. In ANTS2014, Kohel, Lauter, Petit, and Tignol introduced the KLPT algorithm, a probabilistic polynomial algorithm addressing a mirrored version of the \(\ell \) -isogeny path problems based on quaternion algebras under the Deuring correspondence. In this study, we revisit the enhanced approach proposed by Petit and Smith in MathCrypt2018, which incorporated a solution to the Closest Vector Problem (CVP) for strong approximation in the primary step of the KLPT algorithm. This method minimizes the norm of target elements within an extremal order of the underlying quaternion algebra, making the Cornacchia’s algorithm efficient during the strong approximation step. Although Petit and Smith’s generalized KLPT algorithm should be employed in SQISign, the only isogeny-based digital signature scheme submitted to the NIST’s additional call for post-quantum cryptography standardization, their work is primarily available in the form of presentation slides, providing limited algorithmic details. We meticulously reconstruct the improvements specific to the quaternion analogue of the \(\ell \) -isogeny path problems, focusing on the strong approximation step using CVP, building upon the work of Pinto and Petit. It provides a robust theoretical foundation for our approach.