Paper 2025/1604

Qlapoti: Simple and Efficient Translation of Quaternion Ideals to Isogenies

Abstract

The main building block in isogeny-based cryptography is an algorithmic version of the Deuring correspondence, called $\mathsf{IdealToIsogeny}$. This algorithm takes as input left ideals of the endomorphism ring of a supersingular elliptic curve and computes the associated isogeny. Building on ideas from $\mathsf{QFESTA}$, the $\mathsf{Clapoti}$ framework by Page and Robert reduces this problem to solving a certain norm equation. The current state of the art is however unable to efficiently solve this equation, and resorts to a relaxed version of it instead. This impacts not only the efficiency of the $\mathsf{IdealToIsogeny}$ procedure, but also its success probability. The latter issue has to be mitigated with complex and memory-heavy rerandomization procedures, but still leaves a gap between the security analysis and the actual implementation of cryptographic schemes employing $\mathsf{IdealToIsogeny}$ as a subroutine. For instance, in $\mathsf{SQIsign}$ the failure probability is still $2^{-60}$ which is not cryptographically negligible. The main contribution of this paper is a very simple and efficient algorithm called $\mathsf{Qlapoti}$ which approaches the norm equation from $\mathsf{Clapoti}$ directly, solving all the aforementioned problems at once. First, it makes the $\mathsf{IdealToIsogeny}$ subroutine between $2.2$ and $2.6$ times faster. This signigicantly improves the speed of schemes using this subroutine, including notably $\mathsf{SQIsign}$ and \prism. On top of that, $\mathsf{Qlapoti}$ has a cryptographically negligible failure probability. This eliminates the need for rerandomization, drastically reducing memory consumption, and allows for cleaner security reductions.