CryptoDB
Qlapoti: Simple and Efficient Translation of Quaternion Ideals to Isogenies
| Authors: |
|
|---|---|
| Download: | |
| Conference: | ASIACRYPT 2025 |
| Abstract: | The main building block in isogeny-based cryptography is an algorithmic version of the Deuring correspondence, called 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 QFESTA, the 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 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 IdealToIsogeny as a subroutine. For instance, in 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 Qlapoti which approaches the norm equation from Clapoti directly, solving all the aforementioned problems at once. First, it makes the IdealToIsogeny subroutine between 2.2 and 2.6 times faster. This signigicantly improves the speed of schemes using this subroutine, including notably SQIsign and PRISM. On top of that, Qlapoti has a cryptographically negligible failure probability. This eliminates the need for rerandomization, drastically reducing memory consumption, and allows for cleaner security reductions. |
BibTeX
@inproceedings{asiacrypt-2025-36003,
title={Qlapoti: Simple and Efficient Translation of Quaternion Ideals to Isogenies},
publisher={Springer-Verlag},
author={Giacomo Borin and Maria Corte-Real Santos and Jonathan Komada Eriksen and Riccardo Invernizzi and Marzio Mula and Sina Schaeffler and Frederik Vercauteren},
year=2025
}