Giacomo Borin
IBM Research Zurich and University of Zurich, Switzerland

Maria Corte-Real Santos
ENS de Lyon, CNRS, UMPA, France

Jonathan Komada Eriksen
COSIC, KU Leuven, Belgium

Riccardo Invernizzi
COSIC, KU Leuven, Belgium

Marzio Mula
University of the Bundeswehr Munich, Germany

Sina Schaeffler
IBM Research Zurich and ETH Zurich, Switzerland

Frederik Vercauteren
COSIC, KU Leuven, Belgium

Keywords: Isogeny-based cryptography, quaternion algebras, ideal to isogeny translation, SQIsign, PRISM

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 IdealToIsogenyas 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 significantly 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.