Scholarlink

The main building block in isogeny-based cryptography is an algorithmic version of the Deuring correspondence, called \(\textsf{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 \(\textsf{QFESTA}\) , the \(\textsf{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 \(\textsf{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 \(\textsf{IdealToIsogeny}\) as a subroutine. For instance, in \(\textsf{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 \(\textsf{Qlapoti}\) which approaches the norm equation from \(\textsf{Clapoti}\) directly, solving all the aforementioned problems at once. First, it makes the \(\textsf{IdealToIsogeny}\) subroutine between 2.2 and 2.6 times faster. This significantly improves the speed of schemes using this subroutine, including notably \(\textsf{SQIsign}\) and \(\textsf{PRISM}\) . On top of that, \(\textsf{Qlapoti}\) has a cryptographically negligible failure probability. This eliminates the need for rerandomization, drastically reducing memory consumption, and allows for cleaner security reductions.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

\(\textsf{Qlapoti}\) : Simple and Efficient Translation of Quaternion Ideals to Isogenies

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Giacomo Borin,
  • Maria Corte-Real Santos,
  • Jonathan Komada Eriksen,
  • Riccardo Invernizzi,
  • Marzio Mula,
  • Sina Schaeffler,
  • Frederik Vercauteren

摘要

The main building block in isogeny-based cryptography is an algorithmic version of the Deuring correspondence, called \(\textsf{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 \(\textsf{QFESTA}\) , the \(\textsf{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 \(\textsf{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 \(\textsf{IdealToIsogeny}\) as a subroutine. For instance, in \(\textsf{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 \(\textsf{Qlapoti}\) which approaches the norm equation from \(\textsf{Clapoti}\) directly, solving all the aforementioned problems at once. First, it makes the \(\textsf{IdealToIsogeny}\) subroutine between 2.2 and 2.6 times faster. This significantly improves the speed of schemes using this subroutine, including notably \(\textsf{SQIsign}\) and \(\textsf{PRISM}\) . On top of that, \(\textsf{Qlapoti}\) has a cryptographically negligible failure probability. This eliminates the need for rerandomization, drastically reducing memory consumption, and allows for cleaner security reductions.