<figure><img src="image_1.png" /></figure>

HAL
open science

SQIsign2D-West The Fast, the Small, and the Safer

Andrea Basso, Luca de Feo, Pierrick Dartois, Antonin Leroux, Luciano Maino,
Giacomo Pope, Damien Robert, Benjamin Wesolowski

<figure><img src="image_2.png" /></figure>

To cite this version:

Andrea Basso, Luca de Feo, Pierrick Dartois, Antonin Leroux, Luciano Maino, et al., SQIsign2D-West The Fast, the Small, and the Safer. 2024. hal-04603556

HAL Id: hal-04603556

https://hal.science/hal-04603556

Preprint submitted on 6 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
SQIsign2D-West

The Fast, the Small, and the Safer

Andrea Basso¹,², Luca De Feo², Pierrick Dartois³,⁴, Antonin Leroux⁵,⁶, Luciano Maino¹, Giacomo Pope¹,⁷, Damien Robert³,⁴, and Benjamin Wesolowski⁸

¹ University of Bristol, Bristol, United Kingdom

² IBM Research Europe, Zürich, Switzerland

³ Univ. Bordeaux, CNRS, INRIA, IMB, UMR 5251, F-33400 Talence, France

⁴ INRIA, IMB, UMR 5251, F-33400, Talence, France

⁵ DGA-MI, Bruz, France

⁶ IRMAR - UMR 6625, Université de Rennes, France

⁷ NCC Group, Cheltenham, United Kingdom

⁸ ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France

**Abstract.** We introduce SQIsign2D-West, a variant of SQIsign using two-dimensional isogeny representations.

SQIsignHD was the first variant of SQIsign to use higher dimensional isogeny representations. Its eight-dimensional variant is geared towards provable security but is deemed impractical. Its four-dimensional variant is geared towards efficiency and has significantly faster signing times than SQIsign, but slower verification owing to the complexity of the four-dimensional representation. Its authors commented on the apparent difficulty of getting any improvement over SQIsign by using two-dimensional representations.

In this work, we introduce new algorithmic tools that make two-dimensional representations a viable alternative. These lead to a signature scheme with sizes comparable to SQIsignHD, slightly slower signing than SQIsignHD but still much faster than SQIsign, and the fastest verification of any known variant of SQISign. We achieve this without compromising on the security proof: the assumptions behind SQIsign2D-West are similar to those of the eight-dimensional variant of SQISignHD. Additionally, like SQISignHD, SQISign2D-West favourably scales to high levels of security. Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic based on intrinsics available to the Ice Lake architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.

**Keywords:** Isogenies · Post-quantum · Signatures.

# 1 Introduction

SQIsign [14,8] is a signature scheme based on the conjectured hardness of computing endomorphism rings of supersingular curves. A candidate in the NIST post-quantum cryptography standardisation process, it features the smallest
SQIsign2D-West

The Fast, the Small, and the Safer

Andrea Basso¹,², Luca De Feo², Pierrick Dartois³,⁴, Antonin Leroux⁵,⁶, Luciano Maino¹, Giacomo Pope¹,⁷, Damien Robert³,⁴, and Benjamin Wesolowski⁸

¹ University of Bristol, Bristol, United Kingdom

² IBM Research Europe, Zürich, Switzerland

³ Univ. Bordeaux, CNRS, INRIA, IMB, UMR 5251, F-33400 Talence, France

⁴ INRIA, IMB, UMR 5251, F-33400, Talence, France

⁵ DGA-MI, Bruz, France

⁶ IRMAR - UMR 6625, Université de Rennes, France

⁷ NCC Group, Cheltenham, United Kingdom

⁸ ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France

**Abstract.** We introduce SQIsign2D-West, a variant of SQIsign using two-dimensional isogeny representations.

SQIsignHD was the first variant of SQIsign to use higher dimensional isogeny representations. Its eight-dimensional variant is geared towards provable security but is deemed impractical. Its four-dimensional variant is geared towards efficiency and has significantly faster signing times than SQIsign, but slower verification owing to the complexity of the four-dimensional representation. Its authors commented on the apparent difficulty of getting any improvement over SQIsign by using two-dimensional representations.

In this work, we introduce new algorithmic tools that make two-dimensional representations a viable alternative. These lead to a signature scheme with sizes comparable to SQIsignHD, slightly slower signing than SQIsignHD but still much faster than SQISign, and the fastest verification of any known variant of SQISign. We achieve this without compromising on the security proof: the assumptions behind SQIsign2D-West are similar to those of the eight-dimensional variant of SQIsignHD. Additionally, like SQISignHD, SQISign2D-West favourably scales to high levels of security. Concretely, for NIST level I we achieve signing times of 80 ms and verifying times of 4.5 ms, using optimised arithmetic based on intrinsics available to the Ice Lake architecture. For NIST level V, we achieve 470 ms for signing and 31 ms for verifying.

**Keywords:** Isogenies · Post-quantum · Signatures.

# 1 Introduction

SQIsign [14,8] is a signature scheme based on the conjectured hardness of computing endomorphism rings of supersingular curves. A candidate in the NIST post-quantum cryptography standardisation process, it features the smallest
combined size of public key and signature, but it also exhibits one the slowest performances among all candidates.

The SIDH attacks [7,32,41] shook the foundations of isogeny-based cryp-
tography by showing that any isogeny can be efficiently recovered from its
evaluation on a sufficiently large torsion subgroup. Although they marked the end
of SIDH/SIKE [26,25] and related schemes, it was not long before the same tech-
nique was put to constructive use, notably in the encryption schemes FESTA [4]
and QFESTA [33], and in the SQIsignHD [11] variant of SQIsign. The key to
all these applications is to embed an isogeny of elliptic curves into an isogeny
between higher-dimensional abelian varieties. The number of dimensions used
for the embedding is a key parameter for efficiency: Robert [40] shows that
eight dimensions are always enough, however the cost of representing the higher-
dimensional objects grows exponentially with the dimension, thus all practical
constructions strive to limit the embedding dimension. For example, FESTA and
QFESTA manage to restrict themselves to two-dimensional isogenies.

In the same vein, SQIsignHD consists of two sub-variants. The first, Rigorous-SQIsignHD, uses eight-dimensional isogenies and strives for the best possible provable security but is deemed unpractical. The second, FastSQIsignHD, uses four-dimensional isogenies and compromises on the security proof to achieve the best possible efficiency: the result is a signature scheme with smaller signatures than SQIsign, similarly sized public keys, and significantly faster signing times, but, realistically, slower verification owing to the complexity of the four-dimensional representation.

**Our contributions.** The question of whether it is possible to obtain an improvement over SQIsign by using only two-dimensional isogenies was left open in [11], where a short paragraph commented on the apparent difficulty of this task. We answer this question in the affirmative by introducing SQIsign2D-West.

To achieve this we introduce new tools for computing higher-dimensional
isogeny representations in the context of supersingular elliptic curves:

- An algorithm, a simple extension of [33, Algorithm 2], to evaluate a random elliptic isogeny of given degree by embedding it in a two-dimensional isogeny;

- An algorithm, inspired by [36], to translate a quaternion ideal into a two-dimensional representation of the corresponding elliptic isogeny. Combined with an algorithm to sample uniformly random quaternion ideals of given norm, it lets the signer uniformly generate isogenies to be transmitted to the verifier.

We give concrete parameterisations of SQIsign2D-West for NIST security
levels I, III and V, and implement them, using both generic and optimised
modular arithmetic. With key and signature sizes as reported in Table 1, it is
comparable to SQIsignHD in terms of bandwidth. Our benchmarks highlight a
consistent improvement over SQIsign across the whole spectrum, slightly slower
signing performance to FastSQIsignHD but much faster than SQIsign, and *the
fastest verification* among all variants of SQIsign. Because prime characteristics in
combined size of public key and signature, but it also exhibits one the slowest
performances among all candidates.

The SIDH attacks [7,32,41] shook the foundations of isogeny-based cryp-
tography by showing that any isogeny can be efficiently recovered from its
evaluation on a sufficiently large torsion subgroup. Although they marked the end
of SIDH/SIKE [26,25] and related schemes, it was not long before the same tech-
nique was put to constructive use, notably in the encryption schemes FESTA [4]
and QFESTA [33], and in the SQIsignHD [11] variant of SQIsign. The key to
all these applications is to embed an isogeny of elliptic curves into an isogeny
between higher-dimensional abelian varieties. The number of dimensions used
for the embedding is a key parameter for efficiency: Robert [40] shows that
eight dimensions are always enough, however the cost of representing the higher-
dimensional objects grows exponentially with the dimension, thus all practical
constructions strive to limit the embedding dimension. For example, FESTA and
QFESTA manage to restrict themselves to two-dimensional isogenies.

In the same vein, SQIsignHD consists of two sub-variants. The first, Rigorous-SQIsignHD, uses eight-dimensional isogenies and strives for the best possible provable security but is deemed unpractical. The second, FastSQIsignHD, uses four-dimensional isogenies and compromises on the security proof to achieve the best possible efficiency: the result is a signature scheme with smaller signatures than SQIsign, similarly sized public keys, and significantly faster signing times, but, realistically, slower verification owing to the complexity of the four-dimensional representation.

**Our contributions.** The question of whether it is possible to obtain an improvement over SQIsign by using only two-dimensional isogenies was left open in [11], where a short paragraph commented on the apparent difficulty of this task. We answer this question in the affirmative by introducing SQIsign2D-West.

To achieve this we introduce new tools for computing higher-dimensional
isogeny representations in the context of supersingular elliptic curves:

- An algorithm, a simple extension of [33, Algorithm 2], to evaluate a random elliptic isogeny of given degree by embedding it in a two-dimensional isogeny;

- An algorithm, inspired by [36], to translate a quaternion ideal into a two-dimensional representation of the corresponding elliptic isogeny. Combined with an algorithm to sample uniformly random quaternion ideals of given norm, it lets the signer uniformly generate isogenies to be transmitted to the verifier.

We give concrete parameterisations of SQIsign2D-West for NIST security
levels I, III and V, and implement them, using both generic and optimised
modular arithmetic. With key and signature sizes as reported in Table 1, it is
comparable to SQIsignHD in terms of bandwidth. Our benchmarks highlight a
consistent improvement over SQIsign across the whole spectrum, slightly slower
signing performance to FastSQIsignHD but much faster than SQIsign, and *the
fastest verification* among all variants of SQIsign. Because prime characteristics in
<table><caption>**Table 1.** Parameter sizes and performance of SQIsign2D-West. Average running times computed using an Intel Xeon Gold 6338 (Ice Lake, 2GHz) using finite field arithmetic optimised for the x64 architecture, turbo boost disabled. See Section 7 for details.</caption><thead><tr><th rowspan="2"></th><th colspan="2">Sizes (bytes)</th><th colspan="3">Timings (ms)</th></tr><tr><th>Public key</th><th>Signature</th><th>Keygen</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>NIST I</td><td>66</td><td>148</td><td>30</td><td>80</td><td>4.5</td></tr><tr><td>NIST III</td><td>98</td><td>222</td><td>85</td><td>230</td><td>14.5</td></tr><tr><td>NIST V</td><td>130</td><td>294</td><td>180</td><td>470</td><td>31.0</td></tr></tbody></table>

the shape required by SQIsign2D-West are abundant, our variant, unlike SQIsign, does not need a costly search for a “SQIsign-friendly” prime and thus scales seamlessly to high security levels.

Our security proof shows that the security of SQIsign2D-West reduces to the problem of computing the endomorphism ring of a random supersingular curve, in a security model where the attacker is given (classical) access to an oracle computing (higher-dimensional representations of) uniformly random isogenies from a given curve. Hence, compared to SQIsignHD, SQIsign2D-West manages to blend the efficiency gains of FastSQIsignHD with security guarantees similar to RigorousSQIsignHD.

The algorithmic tools we introduce are very flexible, and we considered several variants with different trade offs between provable security and speed. In the main text, we focus on the most secure variant: our security proof follows the blueprint of RigorousSQIsignHD and achieve a reduction to the endomorphism ring problem, provided an isogeny-sampling oracle. By contrast the proof of unforgeability for SQIsign essentially assumes that the signing oracle does not leak information on the secrets. Nevertheless, if one is ready to accept heuristic security, it is possible to modify SQIsign2D-West to obtain even faster signing. We describe this variant in Appendix A.

**Related Work.** Besides SQISignHD, there is a growing interest in finding more efficient variants of SQISign. The recent work AprèsSQI [9] achieves promising savings in verification, while keeping the general structure of SQISign the same (in particular, AprèsSQI does not use higher dimensional isogenies). The key idea is to use larger extensions of the base field to access more small-order points of the curves, and thus more easy-to-compute isogenies. Nevertheless, because it does not change the overall structure, AprèsSQI suffers from the same problems as SQISign when it comes to scaling: suitable primes are difficult to find and negatively impact the performance of high security levels.

While preparing this work, we were informed of three concurrent projects with similar objectives. What they have in common is the use of two-dimensional isogeny representations and prime characteristics of similar shape. In particular, they all scale to higher security levels more favourably than SQISign. We briefly discuss the differences with our work below.
<table><caption>**Table 1.** Parameter sizes and performance of SQIsign2D-West. Average running times computed using an Intel Xeon Gold 6338 (Ice Lake, 2GHz) using finite field arithmetic optimised for the x64 architecture, turbo boost disabled. See Section 7 for details.</caption><thead><tr><th rowspan="2"></th><th colspan="2">Sizes (bytes)</th><th colspan="3">Timings (ms)</th></tr><tr><th>Public key</th><th>Signature</th><th>Keygen</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>NIST I</td><td>66</td><td>148</td><td>30</td><td>80</td><td>4.5</td></tr><tr><td>NIST III</td><td>98</td><td>222</td><td>85</td><td>230</td><td>14.5</td></tr><tr><td>NIST V</td><td>130</td><td>294</td><td>180</td><td>470</td><td>31.0</td></tr></tbody></table>

the shape required by SQIsign2D-West are abundant, our variant, unlike SQIsign, does not need a costly search for a “SQIsign-friendly” prime and thus scales seamlessly to high security levels.

Our security proof shows that the security of SQIsign2D-West reduces to the problem of computing the endomorphism ring of a random supersingular curve, in a security model where the attacker is given (classical) access to an oracle computing (higher-dimensional representations of) uniformly random isogenies from a given curve. Hence, compared to SQIsignHD, SQIsign2D-West manages to blend the efficiency gains of FastSQIsignHD with security guarantees similar to RigorousSQIsignHD.

The algorithmic tools we introduce are very flexible, and we considered several variants with different trade offs between provable security and speed. In the main text, we focus on the most secure variant: our security proof follows the blueprint of RigorousSQIsignHD and achieve a reduction to the endomorphism ring problem, provided an isogeny-sampling oracle. By contrast the proof of unforgeability for SQIsign essentially assumes that the signing oracle does not leak information on the secrets. Nevertheless, if one is ready to accept heuristic security, it is possible to modify SQIsign2D-West to obtain even faster signing. We describe this variant in Appendix A.

**Related Work.** Besides SQISignHD, there is a growing interest in finding more efficient variants of SQISign. The recent work AprèsSQI [9] achieves promising savings in verification, while keeping the general structure of SQISign the same (in particular, AprèsSQI does not use higher dimensional isogenies). The key idea is to use larger extensions of the base field to access more small-order points of the curves, and thus more easy-to-compute isogenies. Nevertheless, because it does not change the overall structure, AprèsSQI suffers from the same problems as SQISign when it comes to scaling: suitable primes are difficult to find and negatively impact the performance of high security levels.

While preparing this work, we were informed of three concurrent projects with similar objectives. What they have in common is the use of two-dimensional isogeny representations and prime characteristics of similar shape. In particular, they all scale to higher security levels more favourably than SQISign. We briefly discuss the differences with our work below.
1. In [34], Nakagawa and Onuki first introduce an algorithm to translate ideals to isogenies relying on the computation of two-dimensional isogenies. This algorithm is reminiscent of the techniques used in [20]; in particular, it is significantly different from the one we introduce in Section 4.2. Then, they apply the algorithm to SQIsign. Their proof-of concept implementation in Julia suggests an improvement over SQIsign for key generation and signing, especially at higher security levels. The proof of security, however, remains heuristic.

2. In [35], Nakagawa and Onuki design SQIsign2D-East, a version of SQIsign where verification requires a computation of a two-dimensional isogeny. This idea shares many similarities with the heuristic version we describe in Appendix A. At the time of writing, we were not provided an implementation, but we expect SQIsign2D-East to have performance similar to our heuristic version. The main difference between this work and ours is the rigorous proof of security of SQIsign2D-West, which appears difficult to emulate with SQIsign2D-East.

3. In [19], Duparc and Fouotsa introduce another version of SQIsign, called SQIprime. SQIprime is the closest to SQIsignHD of all the variants, the main difference being the type of challenge used in the identification protocol. The authors describe two versions, one using two-dimensional isogeny representations and another using four-dimensional ones. The security of either is close to FastSQIsignHD, and thus less rigorous than ours. No implementation of SQIPrime is available at the time, but we expect the four-dimensional variant to perform similarly to SQIsignHD, and the two-dimensional variant to perform similarly to SQIsign2D-East/West, albeit with larger keys and signatures.

For conciseness, from now on we will use SQIsign2D to refer to our protocol, only using SQIsign2D-West when it is needed to distinguish it from other variants.

**Plan.** We start by reviewing some mathematical background in Section 2 and the fundamentals of SQIsign and its variants in Section 3. In Section 4 we introduce our new algorithms to compute two-dimensional representations of isogenies. Building on these we give in Section 5 a detailed description of the SQIsign2D identification protocol, and provide a formal proof of its security in Section 6. Finally in Section 7 we describe our implementation of SQISign2D-West and of its heuristic variant, and report on their performance. Additionally in Appendix A we describe the aforementioned heuristic variant.

## 2 Preliminaries

In this section, we recall some background knowledge about the Deuring correspondence and isogenies between products of two elliptic curves. We assume some familiarity with elliptic curves and their isogenies and refer to [43,13] for more information.
1. In [34], Nakagawa and Onuki first introduce an algorithm to translate ideals to isogenies relying on the computation of two-dimensional isogenies. This algorithm is reminiscent of the techniques used in [20]; in particular, it is significantly different from the one we introduce in Section 4.2. Then, they apply the algorithm to SQIsign. Their proof-of concept implementation in Julia suggests an improvement over SQIsign for key generation and signing, especially at higher security levels. The proof of security, however, remains heuristic.

2. In [35], Nakagawa and Onuki design SQIsign2D-East, a version of SQIsign where verification requires a computation of a two-dimensional isogeny. This idea shares many similarities with the heuristic version we describe in Appendix A. At the time of writing, we were not provided an implementation, but we expect SQIsign2D-East to have performance similar to our heuristic version. The main difference between this work and ours is the rigorous proof of security of SQIsign2D-West, which appears difficult to emulate with SQIsign2D-East.

3. In [19], Duparc and Fouotsa introduce another version of SQIsign, called SQIprime. SQIprime is the closest to SQIsignHD of all the variants, the main difference being the type of challenge used in the identification protocol. The authors describe two versions, one using two-dimensional isogeny representations and another using four-dimensional ones. The security of either is close to FastSQIsignHD, and thus less rigorous than ours. No implementation of SQIPrime is available at the time, but we expect the four-dimensional variant to perform similarly to SQIsignHD, and the two-dimensional variant to perform similarly to SQIsign2D-East/West, albeit with larger keys and signatures.

For conciseness, from now on we will use SQIsign2D to refer to our protocol, only using SQIsign2D-West when it is needed to distinguish it from other variants.

**Plan.** We start by reviewing some mathematical background in Section 2 and the fundamentals of SQIsign and its variants in Section 3. In Section 4 we introduce our new algorithms to compute two-dimensional representations of isogenies. Building on these we give in Section 5 a detailed description of the SQIsign2D identification protocol, and provide a formal proof of its security in Section 6. Finally in Section 7 we describe our implementation of SQISign2D-West and of its heuristic variant, and report on their performance. Additionally in Appendix A we describe the aforementioned heuristic variant.

## 2 Preliminaries

In this section, we recall some background knowledge about the Deuring correspondence and isogenies between products of two elliptic curves. We assume some familiarity with elliptic curves and their isogenies and refer to [43,13] for more information.
## 2.1 The Deuring correspondence

We now give a brief summary of the theory of the Deuring correspondence, following the approach in [30, Chapter 2]. Let $p > 3$ be a prime $\equiv 3 \pmod 4$ and let $\mathcal{B}_{p,\infty}$ be the unique quaternion algebra ramified at $p$ and $\infty$, i.e. $\mathcal{B}_{p,\infty} = \mathbb{Q}\langle i, j\rangle$, where $i^2 = -1$ and $j^2 = -p$. Given a fractional ideal $I$, we define its left order as $\mathcal{O}_L(I) = \{\alpha \in \mathcal{B}_{p,\infty} \mid \alpha I \subset I\}$; similarity, one can define its right order $\mathcal{O}_R(I)$.

In [17], Deuring showed a categorical equivalence between maximal orders in $\mathcal{B}_{p,\infty}$ and supersingular elliptic curves defined over $\mathbb{F}_{p^2}$. From now on, we will refer to this equivalence as the *Deuring Correspondence*. Under this correspondence, an isogeny $\varphi: E_1 \to E_2$ corresponds to a fractional ideal $I_\varphi$, where $\mathcal{O}_L(I_\varphi) \cong \text{End}(E_1)$ and $\mathcal{O}_R(I_\varphi) \cong \text{End}(E_2)$. Moreover, $\text{deg}(\varphi) = n(I_\varphi)$.

Given two isogenies $\varphi_1: E \to E_1$ and $\varphi_2: E \to E_2$ of coprime degrees, we denote by $[\varphi_1]_*\varphi_2: E_1 \to E'$ the pushforward isogeny of $\varphi_2$ under $\varphi_1$, i.e. $\ker([\varphi_1]_*\varphi_2) = \varphi_1(\ker(\varphi_2))$. Equivalently, we define the pushforward of $I_{\varphi_2}$ under $I_{\varphi_1}$ as the ideal corresponding to the isogeny $[\varphi_1]_*\varphi_2$. We give a succinct summary of the Deuring correspondence in the following table.

<table><thead><tr><th>Supersingular elliptic curves</th><th>Quaternions</th></tr></thead><tbody><tr><td>$j(E)$ or $j(E)^p$ supersingular</td><td>$\mathcal{O} \cong \text{End}(E)$ maximal order in $\mathcal{B}_{p,\infty}$</td></tr><tr><td>$\varphi: E \to E'$</td><td>left $\mathcal{O}$-ideal and right $\mathcal{O}'$-ideal $I_\varphi$</td></tr><tr><td>$\varphi, \psi: E \to E'$</td><td>$I_\varphi \sim I_\psi$ ($I_\psi = I_\varphi \alpha$)</td></tr><tr><td>$\hat{\varphi}: E' \to E$</td><td>$\overline{I_\varphi}$</td></tr><tr><td>$\varphi \circ \psi$</td><td>$I_\psi \cdot I_\varphi$</td></tr><tr><td>$\theta \in \text{End}(E)$</td><td>Principal ideal $\mathcal{O}\theta$</td></tr><tr><td>$\text{deg}(\varphi)$</td><td>$\text{nrd}(I_\varphi)$</td></tr></tbody></table>

A problem we will face in the following sections is to compute the ideal associated to a given kernel generator. To be more precise, we are given an isogeny $\varphi: E_0 \to E$, where we know $\mathcal{O}_0 \cong \text{End}(E_0)$ and its associated ideal $I_\varphi$. We also have a point $K \in E$ of smooth order $D$ coprime to $\text{deg}(\varphi)$, which described the kernel of an isogeny $\psi: E \to E'$. Our goal is to compute $I_\psi$, the ideal corresponding to $\psi$.

We can accomplish this goal using the algorithm [11, Alg. 9]. In particular, we first push $\mathcal{O}_0$ under $\varphi$ via [11, Alg. 8] and then use [11, Alg. 9] to retrieve $I_\psi$. In our use case, we want to avoid running [11, Alg. 8] and [11, Alg. 9] on the fly but rather allow some precomputations. Let $(P, Q)$ be a basis $E[D]$ and write $K$ as $[a]P + [b]Q$. In [11, Alg. 9, Line 1], we have to evaluate a basis $(\beta_1, \beta_2, \beta_3, \beta_4)$ of the right order of $I_\varphi$ at $K$. This is equivalent to evaluating $(\beta_1, \beta_2, \beta_3, \beta_4)$ at the basis $(P, Q)$ and then retrieving $\beta_i(K)$ as $[a]\beta_i(P) + [b]\beta_i(Q)$.

In what follows, we use the notation $\{\beta_i(P), \beta_i(Q)\}_{i=1,...,4}$ to mean that we have evaluated a basis $(\beta_1, \beta_2, \beta_3, \beta_4)$ of the right order of $I_\varphi$ at $(P, Q)$ via [11, Alg. 9]. Additionally, we say that we use the datum $\{\beta_i(P), \beta_i(Q)\}_{i=1,...,4}$ to
## 2.1 The Deuring correspondence

We now give a brief summary of the theory of the Deuring correspondence, following the approach in [30, Chapter 2]. Let $p > 3$ be a prime $\equiv 3 \pmod 4$ and let $\mathcal{B}_{p,\infty}$ be the unique quaternion algebra ramified at $p$ and $\infty$, i.e. $\mathcal{B}_{p,\infty} = \mathbb{Q}\langle i, j\rangle$, where $i^2 = -1$ and $j^2 = -p$. Given a fractional ideal $I$, we define its left order as $O_L(I) = \{\alpha \in \mathcal{B}_{p,\infty} | \alpha I \subset I\}$; similarity, one can define its right order $O_R(I)$.

In [17], Deuring showed a categorical equivalence between maximal orders in $\mathcal{B}_{p,\infty}$ and supersingular elliptic curves defined over $\mathbb{F}_{p^2}$. From now on, we will refer to this equivalence as the *Deuring Correspondence*. Under this correspondence, an isogeny $\varphi: E_1 \to E_2$ corresponds to a fractional ideal $I_\varphi$, where $O_L(I_\varphi) \cong \text{End}(E_1)$ and $O_R(I_\varphi) \cong \text{End}(E_2)$. Moreover, $\deg(\varphi) = n(I_\varphi)$.

Given two isogenies $\varphi_1: E \to E_1$ and $\varphi_2: E \to E_2$ of coprime degrees, we denote by $[\varphi_1]_*\varphi_2: E_1 \to E'$ the pushforward isogeny of $\varphi_2$ under $\varphi_1$, i.e. $\ker([\varphi_1]_*\varphi_2) = \varphi_1(\ker(\varphi_2))$. Equivalently, we define the pushforward of $I_{\varphi_2}$ under $I_{\varphi_1}$ as the ideal corresponding to the isogeny $[\varphi_1]_*\varphi_2$. We give a succinct summary of the Deuring correspondence in the following table.

<table><thead><tr><th>Supersingular elliptic curves</th><th>Quaternions</th></tr></thead><tbody><tr><td>$j(E)$ or $j(E)^p$ supersingular</td><td>$O \cong \text{End}(E)$ maximal order in $\mathcal{B}_{p,\infty}$</td></tr><tr><td>$\varphi: E \to E'$</td><td>left $O$-ideal and right $O'$-ideal $I_\varphi$</td></tr><tr><td>$\varphi, \psi: E \to E'$</td><td>$I_\varphi \sim I_\psi$ ($I_\psi = I_\varphi \alpha$)</td></tr><tr><td>$\hat{\varphi}: E' \to E$</td><td>$\overline{I_\varphi}$</td></tr><tr><td>$\varphi \circ \psi$</td><td>$I_\psi \cdot I_\varphi$</td></tr><tr><td>$\theta \in \text{End}(E)$</td><td>Principal ideal $O\theta$</td></tr><tr><td>$\deg(\varphi)$</td><td>$\text{nrd}(I_\varphi)$</td></tr></tbody></table>

A problem we will face in the following sections is to compute the ideal associated to a given kernel generator. To be more precise, we are given an isogeny $\varphi: E_0 \to E$, where we know $O_0 \cong \text{End}(E_0)$ and its associated ideal $I_\varphi$. We also have a point $K \in E$ of smooth order $D$ coprime to $\deg(\varphi)$, which described the kernel of an isogeny $\psi: E \to E'$. Our goal is to compute $I_\psi$, the ideal corresponding to $\psi$.

We can accomplish this goal using the algorithm [11, Alg. 9]. In particular, we first push $O_0$ under $\varphi$ via [11, Alg. 8] and then use [11, Alg. 9] to retrieve $I_\psi$. In our use case, we want to avoid running [11, Alg. 8] and [11, Alg. 9] on the fly but rather allow some precomputations. Let $(P, Q)$ be a basis $E[D]$ and write $K$ as $[a]P + [b]Q$. In [11, Alg. 9, Line 1], we have to evaluate a basis $(\beta_1, \beta_2, \beta_3, \beta_4)$ of the right order of $I_\varphi$ at $K$. This is equivalent to evaluating $(\beta_1, \beta_2, \beta_3, \beta_4)$ at the basis $(P, Q)$ and then retrieving $\beta_i(K)$ as $[a]\beta_i(P) + [b]\beta_i(Q)$.

In what follows, we use the notation $\{\beta_i(P), \beta_i(Q)\}_{i=1,...,4}$ to mean that we have evaluated a basis $(\beta_1, \beta_2, \beta_3, \beta_4)$ of the right order of $I_\varphi$ at $(P, Q)$ via [11, Alg. 9]. Additionally, we say that we use the datum $\{\beta_i(P), \beta_i(Q)\}_{i=1,...,4}$ to
compute $I_ψ$ when we evaluate $(\beta_1, \beta_2, \beta_3, \beta_4)$ at $K$ as $([a]\beta_i(P) + [b]\beta_i(Q))_{i=1,...,4}$ and then run the rest of [11, Alg. 9] to obtain $I_ψ$.

## 2.2 Kani's Lemma

One of the fundamental ingredients for SQIsign2D is the notion of *efficient representation* of isogenies between elliptic curves.

**Definition 1.** Let $\mathcal{E}$ and $\mathcal{V}$ be two Turing machines. Let $\varphi : E \to E'$ be an isogeny of degree $d$ defined over a finite field $\mathbb{F}_q$. An efficient representation of $\varphi$ (with respect to $\mathcal{E}$ and $\mathcal{V}$) is some data $D \in \{0,1\}^*$ of polynomial size in $\log(d)$ and $\log(q)$ such that:

- on input $(E, E', d, D)$, $\mathcal{V}$ returns, in polynomial time in $\log q$ and $\log d$, $\top$ if $D$ is a valid encoding of an isogeny of degree $d$ between $E$ and $E'$, and $\bot$ otherwise;

- on input $(E, E', d, D)$ and $P \in E(\mathbb{F}_{q^k})$, $\mathcal{E}$ returns $\varphi(P)$ in polynomial time in $k \log(q)$ and $\log(d)$.

In [40], Robert shows that any isogeny can be efficiently represented as the datum of its evaluation on a suitably chosen set of points, then gives an efficient algorithm, akin to an *interpolation-evaluation* algorithm, which, on input an arbitrary point $x$ and the evaluation datum, outputs the value of the isogeny at $x$.

In this manuscript, we will only need a special case of this construction, i.e. the representation of isogeny between elliptic curves via two-dimensional isogenies. This can be achieved using *Kani's lemma*, which is implicitly contained in [27, § 2, Proof of Th. 2.3]. Kani's result relies on the concept of $(d_1, d_2)$-isogeny diamond.

**Definition 2.** A $(d_1, d_2)$-isogeny diamond is a commutative diagram of isogenies:

$$ \begin{array}{ccc} E_0 & \xrightarrow{\varphi_1} & E_1 \\ \Big\downarrow_{\varphi_2} & & \Big\downarrow_{\varphi'_2} \\ E_2 & \xrightarrow{\varphi'_1} & E_{12} \end{array} $$

where $\varphi_1 : E_0 \to E_1$ and $\varphi'_1 : E_1 \to E_{12}$ are $d_1$-isogenies, $\varphi_2 : E_0 \to E_2$ and $\varphi'_2 : E_1 \to E_{12}$ are $d_2$-isogenies.

*Remark 3.* If $d_1$ is coprime to $d_2$, then an isogeny diamond as above is the same thing as a pushforward square from $\varphi_1, \varphi_2$ (or a pullback square from $\varphi'_1, \varphi'_2$); equivalently, the notion of SIDH square.

**Theorem 4 (Kani's lemma).** Given a $(d_1, d_2)$-isogeny diamond, the isogeny $\Phi : E_0 \times E_{12} \to E_1 \times E_2$ given matricially by

$$ \Phi = \begin{pmatrix} \varphi_1 & \tilde{\varphi}'_1 \\ -\varphi_2 & \varphi'_2 \end{pmatrix} $$
compute $I_ψ$ when we evaluate $(\beta_1, \beta_2, \beta_3, \beta_4)$ at $K$ as $([a]\beta_i(P) + [b]\beta_i(Q))_{i=1,...,4}$ and then run the rest of [11, Alg. 9] to obtain $I_ψ$.

## 2.2 Kani's Lemma

One of the fundamental ingredients for SQIsign2D is the notion of *efficient representation* of isogenies between elliptic curves.

**Definition 1.** Let $\mathcal{E}$ and $\mathcal{V}$ be two Turing machines. Let $\varphi: E \to E'$ be an isogeny of degree $d$ defined over a finite field $\mathbb{F}_q$. An efficient representation of $\varphi$ (with respect to $\mathcal{E}$ and $\mathcal{V}$) is some data $D \in \{0,1\}^*$ of polynomial size in $\log(d)$ and $\log(q)$ such that:

- on input $(E, E', d, D)$, $\mathcal{V}$ returns, in polynomial time in $\log q$ and $\log d$, $\top$ if $D$ is a valid encoding of an isogeny of degree $d$ between $E$ and $E'$, and $\bot$ otherwise;

- on input $(E, E', d, D)$ and $P \in E(\mathbb{F}_{q^k})$, $\mathcal{E}$ returns $\varphi(P)$ in polynomial time in $k \log(q)$ and $\log(d)$.

In [40], Robert shows that any isogeny can be efficiently represented as the datum of its evaluation on a suitably chosen set of points, then gives an efficient algorithm, akin to an *interpolation-evaluation* algorithm, which, on input an arbitrary point $x$ and the evaluation datum, outputs the value of the isogeny at $x$.

In this manuscript, we will only need a special case of this construction, i.e. the representation of isogeny between elliptic curves via two-dimensional isogenies. This can be achieved using *Kani's lemma*, which is implicitly contained in [27, § 2, Proof of Th. 2.3]. Kani's result relies on the concept of $(d_1, d_2)$-isogeny diamond.

**Definition 2.** A $(d_1, d_2)$-isogeny diamond is a commutative diagram of isogenies:

$$ \begin{array}{ccc} E_0 & \xrightarrow{\varphi_1} & E_1 \\ \Big\downarrow_{\varphi_2} & & \Big\downarrow_{\varphi'_2} \\ E_2 & \xrightarrow{\varphi'_1} & E_{12} \end{array} $$

where $\varphi_1: E_0 \to E_1$ and $\varphi'_1: E_1 \to E_{12}$ are $d_1$-isogenies, $\varphi_2: E_0 \to E_2$ and $\varphi'_2: E_1 \to E_{12}$ are $d_2$-isogenies.

*Remark 3.* If $d_1$ is coprime to $d_2$, then an isogeny diamond as above is the same thing as a pushforward square from $\varphi_1, \varphi_2$ (or a pullback square from $\varphi'_1, \varphi'_2$); equivalently, the notion of SIDH square.

**Theorem 4 (Kani's lemma).** Given a $(d_1, d_2)$-isogeny diamond, the isogeny $\Phi: E_0 \times E_{12} \to E_1 \times E_2$ given matricially by

$$ \Phi = \begin{pmatrix} \varphi_1 & \tilde{\varphi}'_1 \\ -\varphi_2 & \varphi'_2 \end{pmatrix} $$
is a $(d_1 + d_2)$-isogeny between these product of elliptic curves with their principal product polarisation.

If $d_1$ is coprime to $d_2$, the kernel of $\Phi$ is given by $\text{Ker} \Phi = \{(\tilde{\varphi}_1(P), \varphi'_2(P)) \mid P \in E_1[d_1+d_2]\} = \{(-\tilde{\varphi}_2(P), \varphi'_1(P)) \mid P \in E_2[d_1+d_2]\} = \{(d_1P, \varphi'_1 \circ \varphi_1(P)) \mid P \in E_0[d_1+d_2]\}$.

*Proof.* See, for instance, [32, Theorem 1]. □

Let $\varphi_1 : E_0 \to E_1$ be an isogeny of odd degree $d$. Given an isogeny $\varphi'_2 : E_1 \to E_{12}$ of degree $2^e - d$, we can apply **Theorem 4** to construct a $2^e$-isogeny $\Phi : E_0 \times E_{12} \to E_1 \times E_2$, where $\varphi_2 : E_0 \to E_2$ is given by the pullback of $\varphi'_2$ by $\varphi_1$ and $\text{Ker} \Phi = \{(dP, \varphi'_2 \circ \varphi_1(P)) \mid P \in E_0[2^e]\}$.

The isogeny $\Phi$ can be efficiently evaluated at any point on $E_0 \times E_{12}$ using the formulae in [12]. Thus $\Phi$, or more precisely, given a basis $(P_2, Q_2)$ of $E_2[2^e]$, the two generators ($[d]P_2, \varphi'_2 \circ \varphi_1(P_2)$) and ($[d]P_2, \varphi'_2 \circ \varphi_1(P_2)$) of its kernel, encodes an efficient representation of $\varphi_1$.

If $\varphi_1$ has even degree, we can factor it as a product of an isogeny of degree $2^t$, which can be efficiently evaluated given its kernel, followed by an isogeny of odd degree $d$, to which we can apply the strategy above.

*Remark 5.* Kani's lemma extends to abelian varieties [41, § 3.2], this is the version used in SQIsignHD to build a response embedded into a dimension four isogeny.

# 3 The SQIsign family

## 3.1 SQIsign and SQIsignHD

SQIsign is a digital signature scheme obtained via the Fiat-Shamir transform [22] of an identification protocol. This protocol is built on the Deuring correspondence between quaternion ideals and isogenies. SQIsign and SQISignHD mainly differ in the way of making the Deuring correspondence effective. While SQIsign only works with smooth degree isogenies between supersingular elliptic curves, SQISignHD uses four-dimensional isogenies in the verification process. In the following, we present the main building blocks of SQISign (and SQISignHD) identification protocol which will be used in SQIsign2D.

**Public set-up.** We choose a prime $p$ and a supersingular elliptic curve $E_0/\mathbb{F}_{p^2}$ of known endomorphism ring $\mathcal{O}_0 \cong \text{End}(E_0)$ such that $E_0$ has smooth torsion defined over a small extension of $\mathbb{F}_{p^2}$ (of degree 1 or 2). In practice, one may use the curve $E_0 : y^2 = x^3 + x$ (and $p \equiv 3 \mod 4$).

**Key generation.** The prover generates a random secret isogeny $\varphi_{sk} : E_0 \to E_{pk}$ and publishes $E_{pk}$ as its public key.
is a $(d_1 + d_2)$-isogeny between these product of elliptic curves with their principal product polarisation.

If $d_1$ is coprime to $d_2$, the kernel of $\Phi$ is given by $\text{Ker} \Phi = \{(\tilde{\varphi}_1(P), \varphi'_2(P)) \mid P \in E_1[d_1+d_2]\} = \{(-\tilde{\varphi}_2(P), \varphi'_1(P)) \mid P \in E_2[d_1+d_2]\} = \{(d_1P, \varphi'_1 \circ \varphi_1(P)) \mid P \in E_0[d_1+d_2]\}$.

*Proof.* See, for instance, [32, Theorem 1]. □

Let $\varphi_1 : E_0 \to E_1$ be an isogeny of odd degree $d$. Given an isogeny $\varphi'_2 : E_1 \to E_{12}$ of degree $2^e - d$, we can apply **Theorem 4** to construct a $2^e$-isogeny $\Phi : E_0 \times E_{12} \to E_1 \times E_2$, where $\varphi_2 : E_0 \to E_2$ is given by the pullback of $\varphi'_2$ by $\varphi_1$ and $\text{Ker} \Phi = \{(dP, \varphi'_2 \circ \varphi_1(P)) \mid P \in E_0[2^e]\}$.

The isogeny $\Phi$ can be efficiently evaluated at any point on $E_0 \times E_{12}$ using the formulae in [12]. Thus $\Phi$, or more precisely, given a basis $(P_2, Q_2)$ of $E_2[2^e]$, the two generators ($[d]P_2, \varphi'_2 \circ \varphi_1(P_2)$) and ($[d]P_2, \varphi'_2 \circ \varphi_1(P_2)$) of its kernel, encodes an efficient representation of $\varphi_1$.

If $\varphi_1$ has even degree, we can factor it as a product of an isogeny of degree $2^t$, which can be efficiently evaluated given its kernel, followed by an isogeny of odd degree $d$, to which we can apply the strategy above.

*Remark 5.* Kani's lemma extends to abelian varieties [41, § 3.2], this is the version used in SQIsignHD to build a response embedded into a dimension four isogeny.

# 3 The SQIsign family

## 3.1 SQIsign and SQIsignHD

SQIsign is a digital signature scheme obtained via the Fiat-Shamir transform [22] of an identification protocol. This protocol is built on the Deuring correspondence between quaternion ideals and isogenies. SQIsign and SQIsignHD mainly differ in the way of making the Deuring correspondence effective. While SQIsign only works with smooth degree isogenies between supersingular elliptic curves, SQISignHD uses four-dimensional isogenies in the verification process. In the following, we present the main building blocks of SQIsign (and SQISignHD) identification protocol which will be used in SQIsign2D.

**Public set-up.** We choose a prime $p$ and a supersingular elliptic curve $E_0/\mathbb{F}_{p^2}$ of known endomorphism ring $\mathcal{O}_0 \cong \text{End}(E_0)$ such that $E_0$ has smooth torsion defined over a small extension of $\mathbb{F}_{p^2}$ (of degree 1 or 2). In practice, one may use the curve $E_0 : y^2 = x^3 + x$ (and $p \equiv 3 \mod 4$).

**Key generation.** The prover generates a random secret isogeny $\varphi_{sk} : E_0 \to E_{pk}$ and publishes $E_{pk}$ as its public key.
**Commitment.** The prover generates a random secret isogeny $\varphi_{com} : E_0 \to E_{com}$ and sends $E_{com}$ to the verifier as its commitment. For the identification protocol to be zero-knowledge (and the derived signature scheme to be secure), $E_{com}$ has to be computationally undistinguishable from a uniformly random elliptic curve in the supersingular isogeny graph.

**Challenge.** The verifier generates and sends to the prover a random isogeny $\varphi_{chl} : E_{pk} \to E_{chl}$ of smooth degree sufficiently large for $\varphi$ to have high entropy. The challenge space should have size $\Omega(2^{\lambda})$ to ensure $\lambda$ bits of (soundness) security.

**Response.** The prover generates and transmits to the verifier an *efficient representation* (as defined in **Definition 1**) of an isogeny $\varphi_{rsp} : E_{com} \to E_{chl}$ which does not backtrack through $\varphi_{chl}$ ($\hat{\varphi}_{rsp} \circ \varphi_{chl}$ is cyclic).

**Verification.** The verifier checks that the response returned by the prover correctly represents an isogeny $\varphi_{rsp} : E_{com} \to E_{chl}$ and checks that this isogeny does not backtrack through $\varphi_{chl}$.

<figure><img src="image_1.png" /><figcaption>**Fig. 1.** The SQIsign/SQIsignHD identification protocol.</figcaption></figure>

To compute such an efficient representation of $\varphi_{rsp}$ (that will be called $\varphi_{rsp}$ by abuse of notations), the prover uses the Deuring correspondence. Returning $\varphi_{rsp} = \varphi_{chl} \circ \varphi_{sk} \circ \hat{\varphi}_{com} : E_{com} \to E_{chl}$ would make the scheme insecure. However, the prover can translate $\varphi_{chl} \circ \varphi_{sk} \circ \hat{\varphi}_{com}$ into an ideal $I$ connecting $\text{End}(E_{com})$ and $\text{End}(E_{chl})$, find a random equivalent ideal $I_{rsp} \sim I$ and translate $I_{rsp}$ into $\varphi_{rsp}$.

The ideal $I_{rsp} \sim I$ is sampled to be relatively easy to translate into an isogeny and with a distribution that ensures one can simulate the response without secret knowledge (zero knowledge property). Those two objectives are contradictory and lead to a trade-off between efficiency and rigorous security proofs. In SQIsign, $\text{nrd}(I_{rsp})$ had to be smooth to make the ideal to isogeny translation possible. The KLPT algorithm [29] was used to find $I_{rsp}$, resulting in big norms $\text{nrd}(I_{rsp}) \approx p^{15/4}$, slow ideal to isogeny translation and a very heuristic security proof.

In SQIsignHD [11], the smoothness condition on $I_{rsp}$ is relaxed, allowing for smaller norms, a stronger security proof and a faster response at the expense of the verification time. The idea is to use the higher-dimensional SIDH attack
**Commitment.** The prover generates a random secret isogeny $\varphi_{com} : E_0 \to E_{com}$ and sends $E_{com}$ to the verifier as its commitment. For the identification protocol to be zero-knowledge (and the derived signature scheme to be secure), $E_{com}$ has to be computationally undistinguishable from a uniformly random elliptic curve in the supersingular isogeny graph.

**Challenge.** The verifier generates and sends to the prover a random isogeny $\varphi_{chl} : E_{pk} \to E_{chl}$ of smooth degree sufficiently large for $\varphi$ to have high entropy. The challenge space should have size $\Omega(2^{\lambda})$ to ensure $\lambda$ bits of (soundness) security.

**Response.** The prover generates and transmits to the verifier an *efficient representation* (as defined in **Definition 1**) of an isogeny $\varphi_{rsp} : E_{com} \to E_{chl}$ which does not backtrack through $\varphi_{chl}$ ($\hat{\varphi}_{rsp} \circ \varphi_{chl}$ is cyclic).

**Verification.** The verifier checks that the response returned by the prover correctly represents an isogeny $\varphi_{rsp} : E_{com} \to E_{chl}$ and checks that this isogeny does not backtrack through $\varphi_{chl}$.

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** The SQIsign/SQIsignHD identification protocol.</figcaption></figure>

To compute such an efficient representation of $\varphi_{rsp}$ (that will be called $\varphi_{rsp}$ by abuse of notations), the prover uses the Deuring correspondence. Returning $\varphi_{rsp} = \varphi_{chl} \circ \varphi_{sk} \circ \hat{\varphi}_{com} : E_{com} \to E_{chl}$ would make the scheme insecure. However, the prover can translate $\varphi_{chl} \circ \varphi_{sk} \circ \hat{\varphi}_{com}$ into an ideal $I$ connecting $\text{End}(E_{com})$ and $\text{End}(E_{chl})$, find a random equivalent ideal $I_{rsp} \sim I$ and translate $I_{rsp}$ into $\varphi_{rsp}$.

The ideal $I_{rsp} \sim I$ is sampled to be relatively easy to translate into an isogeny and with a distribution that ensures one can simulate the response without secret knowledge (zero knowledge property). Those two objectives are contradictory and lead to a trade-off between efficiency and rigorous security proofs. In SQIsign, $\text{nrd}(I_{rsp})$ had to be smooth to make the ideal to isogeny translation possible. The KLPT algorithm [29] was used to find $I_{rsp}$, resulting in big norms $\text{nrd}(I_{rsp}) \approx p^{15/4}$, slow ideal to isogeny translation and a very heuristic security proof.

In SQIsignHD [11], the smoothness condition on $I_{rsp}$ is relaxed, allowing for smaller norms, a stronger security proof and a faster response at the expense of the verification time. The idea is to use the higher-dimensional SIDH attack
techniques [7,32,41] to represent $\varphi_{rsp}$. The prover uses the secret knowledge of
$\varphi_{chl} \circ \varphi_{sk} \circ \hat{\varphi}_{com}$ to evaluate $\varphi_{rsp}$ on some torsion points. This torsion evaluation
(along with $\deg(\varphi_{rsp})$) is an efficient representation of $\varphi_{rsp}$ that can be sent to
the verifier. To verify the validity of this representation, the verifier computes
a four-dimensional isogeny that “embeds” $\varphi_{rsp}$ by Kani’s lemma. The efficiency
four-dimensional isogeny computation is still an open research question. How-
ever, SQIsignHD verification is expected to be slower than SQIsign verification,
especially after the latest improvements of AprèsSQI [9]. This was the main
motivation for our contribution: accelerate the verification while maintaining a
fast signing procedure and strong security proofs (with two-dimensional isogeny
computations).

## 3.2 What makes SQIsign2D different from SQIsign and SQIsignHD

As a derivative of SQIsign, SQIsign2D follows the same construction presented above but uses different techniques involving two-dimensional isogeny computations. To perform the verification, we “embed” the response $\varphi_{rsp} : E_{com} \to E_{chl}$ into a two-dimensional ($2^r, 2^r$)-isogeny. The bottleneck is to find an auxiliary isogeny $\varphi_{aux} : E_{chl} \to E_{aux}$ of degree $2^r - \deg(\varphi_{rsp})$ to complete the isogeny diamond and apply Kani’s lemma. Additionally, the distribution of $\varphi_{aux}$ needs to be uniform in order to simplify the proof of the zero knowledge property.

We overcome these issues with an algorithm to sample quaternion ideals of fixed norm with a uniform distribution (called **RandomFixedNormIdeal**) and another algorithm (called **IdealTolsogeny**) to translate any left-ideal of the special extremal order $O_0 \cong \text{End}(E_0)$ (with $j(E_0) = 1728$) into an isogeny. **IdealTolsogeny** uses two-dimensional isogenies and is inspired from the Clapoti algorithm introduced in [36] and **RandIsogImages** introduced in QFESTA [33, Algorithm 2]. Both **RandomFixedNormIdeal** and **IdealTolsogeny** are also used in the key generation and commitment steps to obtain statistically uniform distributions of $E_{pk}$ and $E_{com}$, with a clear security benefit.

# 4 Algorithmic building blocks

In this section, we present the main algorithmic building blocks of SQIsign-
2D to make the Deuring correspondence effective. We assume we are given a
cryptographic size prime $p = c \cdot 2^e - 1$ with $e \in \mathbb{N}$ and $c \in \mathbb{N}$ as small as possible. We
can find such $p$ with $c = O(\log(p))$ by Dirichlet’s arithmetic progression theorem
[18]. We denote by $E_0$ the supersingular elliptic curve given by $y^2 = x^3 + x$ over
$\mathbb{F}_p$ and by $O_0$ a maximal quaternion order isomorphic to $\text{End}(E_0)$.

First, we shall present FixedDegreelsogeny, an algorithm to compute the kernel ideal and torsion point images of an isogeny of fixed odd degree defined over $E_0$, which is almost identical to RandIsogImages introduced in QFESTA [33, Algorithm 2]. Then, we present an algorithm IdealTolsogeny to translate any left-ideal of $O_0$ into (torsion point images of) an isogeny defined over $E_0$. We finally present an algorithm RandomFixedNormIdeal to sample left ideals of a given maximal order $O \subseteq B_{p,\infty}$ of fixed norm with a uniform distribution.
techniques [7,32,41] to represent $\varphi_{rsp}$. The prover uses the secret knowledge of
$\varphi_{chl} \circ \varphi_{sk} \circ \hat{\varphi}_{com}$ to evaluate $\varphi_{rsp}$ on some torsion points. This torsion evaluation
(along with $\deg(\varphi_{rsp})$) is an efficient representation of $\varphi_{rsp}$ that can be sent to
the verifier. To verify the validity of this representation, the verifier computes
a four-dimensional isogeny that “embeds” $\varphi_{rsp}$ by Kani’s lemma. The efficiency
four-dimensional isogeny computation is still an open research question. How-
ever, SQIsignHD verification is expected to be slower than SQIsign verification,
especially after the latest improvements of AprèsSQI [9]. This was the main
motivation for our contribution: accelerate the verification while maintaining a
fast signing procedure and strong security proofs (with two-dimensional isogeny
computations).

## 3.2 What makes SQIsign2D different from SQIsign and SQIsignHD

As a derivative of SQIsign, SQIsign2D follows the same construction presented above but uses different techniques involving two-dimensional isogeny computations. To perform the verification, we “embed” the response $\varphi_{rsp} : E_{com} \to E_{chl}$ into a two-dimensional ($2^r, 2^r$)-isogeny. The bottleneck is to find an auxiliary isogeny $\varphi_{aux} : E_{chl} \to E_{aux}$ of degree $2^r - \deg(\varphi_{rsp})$ to complete the isogeny diamond and apply Kani’s lemma. Additionally, the distribution of $\varphi_{aux}$ needs to be uniform in order to simplify the proof of the zero knowledge property.

We overcome these issues with an algorithm to sample quaternion ideals of fixed norm with a uniform distribution (called **RandomFixedNormIdeal**) and another algorithm (called **IdealTolsogeny**) to translate any left-ideal of the special extremal order $O_0 \cong \text{End}(E_0)$ (with $j(E_0) = 1728$) into an isogeny. **IdealTolsogeny** uses two-dimensional isogenies and is inspired from the Clapoti algorithm introduced in [36] and **RandIsogImages** introduced in QFESTA [33, Algorithm 2]. Both **RandomFixedNormIdeal** and **IdealTolsogeny** are also used in the key generation and commitment steps to obtain statistically uniform distributions of $E_{pk}$ and $E_{com}$, with a clear security benefit.

# 4 Algorithmic building blocks

In this section, we present the main algorithmic building blocks of SQIsign-
2D to make the Deuring correspondence effective. We assume we are given a
cryptographic size prime $p = c \cdot 2^e - 1$ with $e \in \mathbb{N}$ and $c \in \mathbb{N}$ as small as possible. We
can find such $p$ with $c = O(\log(p))$ by Dirichlet’s arithmetic progression theorem
[18]. We denote by $E_0$ the supersingular elliptic curve given by $y^2 = x^3 + x$ over
$\mathbb{F}_p$ and by $O_0$ a maximal quaternion order isomorphic to $\text{End}(E_0)$.

First, we shall present FixedDegreelsogeny, an algorithm to compute the kernel ideal and torsion point images of an isogeny of fixed odd degree defined over $E_0$, which is almost identical to RandIsogImages introduced in QFESTA [33, Algorithm 2]. Then, we present an algorithm IdealTolsogeny to translate any left-ideal of $O_0$ into (torsion point images of) an isogeny defined over $E_0$. We finally present an algorithm RandomFixedNormIdeal to sample left ideals of a given maximal order $O \subseteq B_{p,\infty}$ of fixed norm with a uniform distribution.
## 4.1 Evaluating an arbitrary fixed odd degree isogeny from $E_0$

In QFESTA [33], Nakagawa and Onuki introduce an algorithm Randlsoglmages to compute non-smooth isogenies originating from $E_0$. In this section, we recall their idea and tweak Randlsoglmages to additionally output an $O_0$-left ideal corresponding to such an isogeny. We denote this algorithm by FixedDegree-Isogeny and describe it in Algorithm 1.

Let $u < 2^e$ be an odd integer. The goal of FixedDegreeIsogeny is to compute an isogeny $\varphi: E_0 \to E$ of degree $u$ and its kernel ideal $I \subseteq O_0$. First, let us sample an endomorphism $\theta \in \text{End}(E_0)$ of degree $u(2^e - u)$ via FullRepresentInteger [15, Algorithm 1]. The endomorphism $\theta$ can be written as $\theta = \psi \circ \varphi: E_0 \to E_0$, where $\varphi: E_0 \to E$ is an isogeny of degree $u$ and $\psi: E \to E_0$ is an isogeny of degree $2^e - u$. Now, consider the $(u, 2^e - u)$-isogeny diamond in Fig. 2.

<figure><img src="image_2.png" /><figcaption>Fig. 2. $(u, 2^e - u)$-isogeny diamond.</figcaption></figure>

Applying Kani's lemma (Theorem 4), we have that the two-dimensional isogeny $\Phi$ with kernel $\{([u]P, \theta(P)) | P \in E_0[2^e]\}$ can be written as

$$ \Phi = \begin{pmatrix} \varphi & \hat{\psi} \\ -\psi' & \hat{\varphi}' \end{pmatrix} : E_0 \times E_0 \to E \times E'. $$

In particular, we can evaluate $\varphi: E_0 \to E$ at any point $P$ as $(\varphi(P), -\psi'(P)) = \Phi(P, 0)$. In the rest of the paper, we will use the notation $\varphi|_N$ to refer to the action of $\varphi$ on $E_0[N]$. In practice, when we write $\varphi|_N$, we mean $\varphi(P)$ and $\varphi(Q)$, for some basis $\langle P, Q \rangle = E_0[N]$.

As we mentioned above, we also need to compute the ideal corresponding to $\varphi$. The following Lemma addresses this task.

**Lemma 6.** $I = O_0\theta + uO_0$.

*Proof.* We have $E_0[O_0\theta + uO_0] = \ker(\theta) \cap E_0[u]$. First, observe that $\ker(\varphi) \subseteq \ker(\theta) \cap E_0[u]$ since $\theta$ factors through $\varphi$, which has degree $u$.

Conversely, if $P \in \ker(\theta) \cap E_0[u]$, then $\psi(\varphi(P)) = 0$. As a result, $\varphi(P) \in E[u] \cap \ker(\psi)$ and $E[u] \cap \ker(\psi) \subseteq E[u] \cap E[2^e - u] = \{0\}$, since $u$ and $2^e - u$ are coprime. Thus, $P \in \ker(\varphi)$, proving $E_0[O_0\theta + uO_0] = \ker(\varphi)$.

The claim $I = O_0\theta + uO_0$ follows from the Deuring correspondence. $\square$
## 4.1 Evaluating an arbitrary fixed odd degree isogeny from $E_0$

In QFESTA [33], Nakagawa and Onuki introduce an algorithm Randlsoglmages to compute non-smooth isogenies originating from $E_0$. In this section, we recall their idea and tweak Randlsoglmages to additionally output an $O_0$-left ideal corresponding to such an isogeny. We denote this algorithm by FixedDegree-Isogeny and describe it in Algorithm 1.

Let $u < 2^e$ be an odd integer. The goal of FixedDegreeIsogeny is to compute an isogeny $\varphi: E_0 \to E$ of degree $u$ and its kernel ideal $I \subseteq O_0$. First, let us sample an endomorphism $\theta \in \text{End}(E_0)$ of degree $u(2^e - u)$ via FullRepresentInteger [15, Algorithm 1]. The endomorphism $\theta$ can be written as $\theta = \psi \circ \varphi: E_0 \to E_0$, where $\varphi: E_0 \to E$ is an isogeny of degree $u$ and $\psi: E \to E_0$ is an isogeny of degree $2^e - u$. Now, consider the $(u, 2^e - u)$-isogeny diamond in Fig. 2.

<figure><img src="image_4.png" /><figcaption>Fig. 2. $(u, 2^e - u)$-isogeny diamond.</figcaption></figure>

Applying Kani's lemma (Theorem 4), we have that the two-dimensional isogeny $\Phi$ with kernel $\{([u]P, \theta(P)) \mid P \in E_0[2^e]\}$ can be written as

$$ \Phi = \begin{pmatrix} \varphi & \hat{\psi} \\ -\psi' & \hat{\varphi}' \end{pmatrix} : E_0 \times E_0 \to E \times E'. $$

In particular, we can evaluate $\varphi: E_0 \to E$ at any point $P$ as $(\varphi(P), -\psi'(P)) = \Phi(P, 0)$. In the rest of the paper, we will use the notation $\varphi|_N$ to refer to the action of $\varphi$ on $E_0[N]$. In practice, when we write $\varphi|_N$, we mean $\varphi(P)$ and $\varphi(Q)$, for some basis $\langle P, Q \rangle = E_0[N]$.

As we mentioned above, we also need to compute the ideal corresponding to $\varphi$. The following Lemma addresses this task.

**Lemma 6.** $I = O_0\theta + uO_0$.

*Proof.* We have $E_0[O_0\theta + uO_0] = \ker(\theta) \cap E_0[u]$. First, observe that $\ker(\varphi) \subseteq \ker(\theta) \cap E_0[u]$ since $\theta$ factors through $\varphi$, which has degree $u$.

Conversely, if $P \in \ker(\theta) \cap E_0[u]$, then $\psi(\varphi(P)) = 0$. As a result, $\varphi(P) \in E[u] \cap \ker(\psi)$ and $E[u] \cap \ker(\psi) \subseteq E[u] \cap E[2^e - u] = \{0\}$, since $u$ and $2^e - u$ are coprime. Thus, $P \in \ker(\varphi)$, proving $E_0[O_0\theta + uO_0] = \ker(\varphi)$.

The claim $I = O_0\theta + uO_0$ follows from the Deuring correspondence. $\square$
We summarise everything in Algorithm 1. The cost of Algorithm 1 is essentially
dominated by the computation of the two-dimensional isogeny in Line 2 and its
evaluation on the 2$^e$-torsion.

**Algorithm 1 FixedDegreelsogeny**

**Input:** An odd positive integer $u < 2^e$ and a basis $(P_0, Q_0)$ of $E_0[2^e]$.

**Output:** The curve $E$, $\varphi|_{2^e}$, where $\varphi: E_0 \to E$ is a $u$-isogeny, and its corresponding ideal $I$.

1: Sample $\theta \in \text{End}(E_0)$ of degree $u(2^e - u)$. (▷) Call [15, Algorithm 1]

2: Evaluate $\Phi : E_0 \times E_0 \to E \times E'$ of kernel $\langle ([u]P_0, \theta(P_0)), ([u]Q_0, \theta(Q_0)) \rangle$ on the points $(P_0, 0)$ and $(Q_0, 0)$

3: Parse $\Phi(P_0, 0) = (\varphi(P_0), \*)$ and $\Phi(Q_0, 0) = (\varphi(Q_0), \*)$ to obtain $\varphi|_{2^e} = (\varphi(P_0), \varphi(Q_0))$

4: Set $I \leftarrow \mathcal{O}_0\theta + u\mathcal{O}_0$

5: Return $E$, $\varphi|_{2^e}$, $I$

*Remark 7.* The use of FullRepresentInteger [15, Algorithm 1] is the reason why we can only return isogenies starting from $E_0$. Indeed, FullRepresentInteger can only find solutions in the special extremal order $\mathcal{O}_0$.

We can tweak Algorithm 1 to compute a (2, 2)-isogeny chain of length $f < e$ in Line 2. In Line 1, we sample an endomorphism of degree $(2^f - u)u$ such that FullRepresentInteger succeeds with overwhelming probability (requiring $u(2^f - u) = O(p \log^2 p)$ should be enough for that, see [30, Lemma 3.1.4] for instance). The kernel of the isogeny $\Phi$ in Line 2 becomes $\langle ([2^{e-f}u]P, [2^{e-f}]\theta(P)), ([2^{e-f}u]Q, [2^{e-f}]\theta(Q)) \rangle$.

**4.2 Translating any left $\mathcal{O}_0$-ideal into (torsion point images of) the corresponding isogeny from $E_0$**

The state of the art techniques to translate ideals into isogenies impose conditions on the input norm. In SQIsign, the norm had to be smooth and in SQIsignHD, the norm nrd($I$) had to be such that $2^e - \text{nrd}(I)$ can be easily decomposed into a sum of two squares. We now propose an algorithm **IdealTolsogeny** to translate a left $\mathcal{O}_0$-ideal $I$ of any norm into an isogeny starting from $E_0$. It is inspired by Page and Robert's work in the context of the Clapoti group action [36]. In Clapoti, the ideal considered is an ideal of quadratic imaginary order but we can adapt their ideas to the quaternion special extremal order $\mathcal{O}_0$.

Let $I$ be a left $\mathcal{O}_0$-ideal. We want to compute the torsion image $\varphi_I|_{2^e}$. The general outline is as follows:

1. Find $I_1, I_2 \sim I$ of coprime norms $d_1, d_2 \approx \sqrt{p}$, and $u, v \in \mathbb{N}^*$ such that $d_1 u + d_2 v = 2^f$ with $f \le e$ and $d_1 u$ is prime to $d_2 v$.

2. Evaluate isogenies $\varphi_u, \varphi_v : E_0 \to E_u, E_v$ of degrees $u$ and $v$ on $E_0[2^e]$.
We summarise everything in Algorithm 1. The cost of Algorithm 1 is essentially
dominated by the computation of the two-dimensional isogeny in Line 2 and its
evaluation on the 2$^e$-torsion.

**Algorithm 1 FixedDegreelsogeny**

**Input:** An odd positive integer $u < 2^e$ and a basis $(P_0, Q_0)$ of $E_0[2^e]$.

**Output:** The curve $E$, $\varphi|_{2^e}$, where $\varphi: E_0 \to E$ is a $u$-isogeny, and its corresponding ideal $I$.

1: Sample $\theta \in \text{End}(E_0)$ of degree $u(2^e - u)$. (▷) Call [15, Algorithm 1]

2: Evaluate $\Phi: E_0 \times E_0 \to E \times E'$ of kernel $\langle([u]P_0, \theta(P_0)), ([u]Q_0, \theta(Q_0))\rangle$ on the points $(P_0, 0)$ and $(Q_0, 0)$

3: Parse $\Phi(P_0, 0) = (\varphi(P_0), \*)$ and $\Phi(Q_0, 0) = (\varphi(Q_0), \*)$ to obtain $\varphi|_{2^e} = (\varphi(P_0), \varphi(Q_0))$

4: Set $I \leftarrow \mathcal{O}_0\theta + u\mathcal{O}_0$

5: Return $E$, $\varphi|_{2^e}$, $I$

*Remark 7.* The use of FullRepresentInteger [15, Algorithm 1] is the reason why we can only return isogenies starting from $E_0$. Indeed, FullRepresentInteger can only find solutions in the special extremal order $\mathcal{O}_0$.

We can tweak Algorithm 1 to compute a (2, 2)-isogeny chain of length $f < e$ in Line 2. In Line 1, we sample an endomorphism of degree $(2^f - u)u$ such that FullRepresentInteger succeeds with overwhelming probability (requiring $u(2^f - u) = O(p \log^2 p)$ should be enough for that, see [30, Lemma 3.1.4] for instance). The kernel of the isogeny $\Phi$ in Line 2 becomes $\langle([2^{e-f}u]P, [2^{e-f}]\theta(P)), ([2^{e-f}u]Q, [2^{e-f}]\theta(Q))\rangle$.

**4.2 Translating any left $\mathcal{O}_0$-ideal into (torsion point images of) the corresponding isogeny from $E_0$**

The state of the art techniques to translate ideals into isogenies impose conditions on the input norm. In SQIsign, the norm had to be smooth and in SQIsignHD, the norm nrd($I$) had to be such that $2^e - \text{nrd}(I)$ can be easily decomposed into a sum of two squares. We now propose an algorithm **IdealTolsogeny** to translate a left $\mathcal{O}_0$-ideal $I$ of any norm into an isogeny starting from $E_0$. It is inspired by Page and Robert's work in the context of the Clapoti group action [36]. In Clapoti, the ideal considered is an ideal of quadratic imaginary order but we can adapt their ideas to the quaternion special extremal order $\mathcal{O}_0$.

Let $I$ be a left $\mathcal{O}_0$-ideal. We want to compute the torsion image $\varphi_I|_{2^e}$. The general outline is as follows:

1. Find $I_1, I_2 \sim I$ of coprime norms $d_1, d_2 \approx \sqrt{p}$, and $u, v \in \mathbb{N}^*$ such that $d_1u + d_2v = 2^f$ with $f \le e$ and $d_1u$ is prime to $d_2v$.

2. Evaluate isogenies $\varphi_u, \varphi_v: E_0 \to E_u, E_v$ of degrees $u$ and $v$ on $E_0[2^e]$.
3. Use Kani's lemma on $\varphi_u \circ \hat{\varphi}_1 : E_I \to E_u$ and $\varphi_v \circ \hat{\varphi}_2 : E_I \to E_v$ where $\varphi_1, \varphi_2 : E_0 \to E_I$ are the isogenies corresponding to $I_1$ and $I_2$ respectively to compute $\Phi : E_u \times E_v \to E_I \times E'$ that embeds the isogenies $\varphi_1 \circ \hat{\varphi}_u$ and $\varphi_2 \circ \hat{\varphi}_v$.

4. Use $\Phi$ to compute $\varphi_1 \circ \hat{\varphi}_u|_{2^e}$ and then $\varphi_u|_{2^e}$ to obtain $\varphi_1|_{2^e}$ and finally obtain $\varphi_I|_{2^e}$.

**Step 1.** We sample ideals $I_1, I_2 \sim I$ of odd coprime norms $d_1$ and $d_2$ until we find positive integers $u, v$ such that $d_1u + d_2v = 2^e$. A sufficient (but not necessary) condition for a solution $(u, v)$ to exist is $d_1d_2 < 2^e$. Hence, the norms $d_1$ and $d_2$ should be as small as possible. To find equivalent ideals of such norms, we sample $\beta_i \in I$ with sufficiently small reduced norm and choose $I_i := I\beta_i/\text{nrd}(I)$, so that $\text{nrd}(I_i) = \text{nrd}(\beta_i)/\text{nrd}(I)$. Minkowski's theorem and [29, Section 3.1] (see also [11, Lemma 12]) ensure that the shortest vector in $I$ has norm $O(\text{nrd}(I)\sqrt{p})$ so we should expect to find $d_1, d_2 \approx \sqrt{p}$ so that $d_1d_2 \approx p \approx 2^e$ in general. This is not enough to rigorously ensure the existence of $u$ and $v$.

However, we can provide heuristic arguments to justify that we expect to find $I_1, I_2, u, v$ after $O(\log(p)^2)$ attempts. Given coprime positive integers $d_1, d_2 \le 2^{e-1}$, we can find $u, v \in \mathbb{N}^*$ as follows. We select an integer $1 \le u < 2^e/d_1 - 1$ until $d_2|2^e - ud_1$, so that we can define $v := (2^e - ud_1)/d_2$. Heuristically, conditional to $d_1$ and $d_2$, the probability that $d_2|2^e - ud_1$ is $\approx 1/d_2$ when $u$ is random so the probability to find such an integer $u$ is $\approx 2^e/d_1 \cdot 1/d_2 = 2^e/(d_1d_2)$. Hence, we can make the following heuristic assumption: for any $1 \le d \le 2^{e-1}$, the probability that a couple $(d_1, d_2)$ selected uniformly at random among couples of coprime integers such that $d_1, d_2 \le d$ satisfies $ud_1 + vd_2 = 2^e$ with $u, v \in \mathbb{N}^*$ is larger than $2^e/d^2$.

This heuristic assumption is still not sufficient because $q_I(\beta) := \text{nrd}(\beta)/\text{nrd}(I)$ has not the same distribution as a uniformly random integer when we sample $\beta \in I$ such that $q_I(\beta) \le d$. We now give more detail on how we sample $\beta \in I$. First, we find a Minkowski reduced basis $\mathcal{B} := (\alpha_1, \dots, \alpha_4)$ of $I$. Then we sample $x_j \in [-B_j; B_j]$ uniformly at random with $B_j := \lfloor 1/4\sqrt{d/q_I(\alpha_j)} \rfloor$ for all $j \in \lfloor 1; 4 \rfloor$ and we set $\beta := \sum_{j=1}^4 x_j\alpha_j$. By triangular inequality (which is valid since $q_I$ is a positive definite quadratic form), we have,

$$q_I(\beta) \le \left( \sum_{j=1}^{4} |x_j| \sqrt{q_I(\alpha_j)} \right)^2 \le d.$$

Hence, we want that $q_I(\beta_1)$ and $q_I(\beta_2)$ satisfy the above integer heuristic assumption when $\beta_1$ and $\beta_2$ are sampled uniformly at random in the set:

$$P_d(\mathcal{B}) := \left\{ \sum_{j=1}^{4} x_j \alpha_j \mid \forall j \in \lfloor 1; 4 \rfloor, \ x_j \in [-B_j; B_j] \right\}.$$

Namely, we make the following assumption:
3. Use Kani's lemma on $\varphi_u \circ \hat{\varphi}_1 : E_I \to E_u$ and $\varphi_v \circ \hat{\varphi}_2 : E_I \to E_v$ where $\varphi_1, \varphi_2 : E_0 \to E_I$ are the isogenies corresponding to $I_1$ and $I_2$ respectively to compute $\Phi : E_u \times E_v \to E_I \times E'$ that embeds the isogenies $\varphi_1 \circ \hat{\varphi}_u$ and $\varphi_2 \circ \hat{\varphi}_v$.

4. Use $\Phi$ to compute $\varphi_1 \circ \hat{\varphi}_u|_{2^e}$ and then $\varphi_u|_{2^e}$ to obtain $\varphi_1|_{2^e}$ and finally obtain $\varphi_I|_{2^e}$.

**Step 1.** We sample ideals $I_1, I_2 \sim I$ of odd coprime norms $d_1$ and $d_2$ until we find positive integers $u, v$ such that $d_1u + d_2v = 2^e$. A sufficient (but not necessary) condition for a solution $(u, v)$ to exist is $d_1d_2 < 2^e$. Hence, the norms $d_1$ and $d_2$ should be as small as possible. To find equivalent ideals of such norms, we sample $\beta_i \in I$ with sufficiently small reduced norm and choose $I_i := I\beta_i/\text{nrd}(I)$, so that $\text{nrd}(I_i) = \text{nrd}(\beta_i)/\text{nrd}(I)$. Minkowski's theorem and [29, Section 3.1] (see also [11, Lemma 12]) ensure that the shortest vector in $I$ has norm $O(\text{nrd}(I)\sqrt{p})$ so we should expect to find $d_1, d_2 \approx \sqrt{p}$ so that $d_1d_2 \approx p \approx 2^e$ in general. This is not enough to rigorously ensure the existence of $u$ and $v$.

However, we can provide heuristic arguments to justify that we expect to find $I_1, I_2, u, v$ after $O(\log(p)^2)$ attempts. Given coprime positive integers $d_1, d_2 \le 2^{e-1}$, we can find $u, v \in \mathbb{N}^*$ as follows. We select an integer $1 \le u < 2^e/d_1 - 1$ until $d_2|2^e - ud_1$, so that we can define $v := (2^e - ud_1)/d_2$. Heuristically, conditional to $d_1$ and $d_2$, the probability that $d_2|2^e - ud_1$ is $\approx 1/d_2$ when $u$ is random so the probability to find such an integer $u$ is $\approx 2^e/d_1 \cdot 1/d_2 = 2^e/(d_1d_2)$. Hence, we can make the following heuristic assumption: for any $1 \le d \le 2^{e-1}$, the probability that a couple $(d_1, d_2)$ selected uniformly at random among couples of coprime integers such that $d_1, d_2 \le d$ satisfies $ud_1 + vd_2 = 2^e$ with $u, v \in \mathbb{N}^*$ is larger than $2^e/d^2$.

This heuristic assumption is still not sufficient because $q_I(\beta) := \text{nrd}(\beta)/\text{nrd}(I)$ has not the same distribution as a uniformly random integer when we sample $\beta \in I$ such that $q_I(\beta) \le d$. We now give more detail on how we sample $\beta \in I$. First, we find a Minkowski reduced basis $\mathcal{B} := (\alpha_1, \dots, \alpha_4)$ of $I$. Then we sample $x_j \in [-B_j; B_j]$ uniformly at random with $B_j := \lfloor 1/4\sqrt{d/q_I(\alpha_j)} \rfloor$ for all $j \in \lfloor 1; 4 \rfloor$ and we set $\beta := \sum_{j=1}^4 x_j\alpha_j$. By triangular inequality (which is valid since $q_I$ is a positive definite quadratic form), we have,

$$q_I(\beta) \le \left( \sum_{j=1}^{4} |x_j| \sqrt{q_I(\alpha_j)} \right)^2 \le d.$$

Hence, we want that $q_I(\beta_1)$ and $q_I(\beta_2)$ satisfy the above integer heuristic assumption when $\beta_1$ and $\beta_2$ are sampled uniformly at random in the set:

$$P_d(\mathcal{B}) := \left\{ \sum_{j=1}^{4} x_j \alpha_j \mid \forall j \in \lfloor 1; 4 \rfloor, \ x_j \in [-B_j; B_j] \right\}.$$

Namely, we make the following assumption:
**Heuristic 1** For $1 \le d \le 2^{e-1}$, consider:

$$S_{d,e}(\mathcal{B}) := \{(\beta_1, \beta_2) \in P_d(\mathcal{B})^2 \mid \gcd(q_I(\beta_1), q_I(\beta_2)) = 1 \text{ and} \\ \exists u, v \in \mathbb{N}^*, uq_I(\beta_1) + vq_I(\beta_2) = 2^e\}.$$

Then, there exists constants $C', C > 0$ independent from $I, \mathcal{B}$ and the parameters $p$ and $e$ such that for all $1 \le d \le 2^{e-1}$,

1. $\#S_{d,e}(\mathcal{B}) \ge C \#P_d(\mathcal{B})^{2e}/d^2 - 1$.

2. When $\beta_1, \beta_2$ are independent and uniformly distributed in $P_d(\mathcal{B})$,

$$\mathbb{P}((\beta_1, \beta_2) \in S_{d,e}(\mathcal{B})) \ge C' \frac{\#S_{d,e}(\mathcal{B})}{\#P_d(\mathcal{B})^2}.$$

Note that we need $d_1u$ and $d_2v$ to be coprime. Since $d_1u + d_2v = 2^e$ and $d_1$ and $d_2$ are odd and coprime, this condition is not satisfied only when $u$ and $v$ are even. Hence, we may divide $u$ and $v$ by $2^{e'}$ and replace $e$ by $f := e - e'$ with $e' = \min(v_2(u), v_2(v))$, so that $d_1u + d_2v = 2^f$ and $d_1u$ and $d_2v$ are coprime. We summarise step 1 in Algorithm 2.

**Algorithm 2** Step 1: Finding suitable ideals $I_1, I_2 \sim I$.

**Input:** An ideal $I \subseteq \mathcal{O}_0 \cong \text{End}(E_0)$, a bound $d = \Theta(\sqrt{p})$.

**Output:** $\beta_1, \beta_2 \in I$ and $u, v \in \mathbb{N}^*$ and $f \le e$ such that $\gcd(uq_I(\beta_1), vq_I(\beta_2)) = 1$ and $uq_I(\beta_1) + vq_I(\beta_2) = 2^f$.

1: Compute a Minkowski reduced basis $(\alpha_1, \dots, \alpha_4)$ of $I$

2: $B_j \leftarrow [1/4\sqrt{d/q_I(\alpha_j)}]$ for $j \in [1; 4]$

3: Sample $x_j \in [-B_j; B_j]^4$ for $j \in [1; 4]$ and initialise $L \leftarrow [(x_1, \dots, x_4)]$

4: **for** $(y_1, \dots, y_4) \in [-B_1; B_1]^4 \times \dots \times [-B_4; B_4]^4$ **do**

5: **for** $(x_1, \dots, x_4) \in L$ **do**

6: $\beta_1 \leftarrow \sum_{j=1}^4 x_j \alpha_j$ and $\beta_2 \leftarrow \sum_{j=1}^4 y_j \alpha_j$

7: $d_1 \leftarrow q_I(\beta_1)$, $d_2 \leftarrow q_I(\beta_2)$

8: **if** $d_1 \equiv 1 \mod 2$ and $d_2 \equiv 1 \mod 2$ and $\gcd(d_1, d_2) = 1$ **then**

9: $u \leftarrow 2^e d_1^{-1} \mod d_2$

10: $v \leftarrow (2^e - ud_1)/d_2$

11: **if** $v > 0$ **then**

12: $e' \leftarrow \min(v_2(u), v_2(v))$, $u \leftarrow u/2^{e'}$, $v \leftarrow v/2^{e'}$ and $f \leftarrow e - e'$

13: **return** $\beta_1, \beta_2, u, v, f$

14: **else**

15: Append $(y_1, \dots, y_4)$ to $L$

**Proposition 8.** Assuming Heuristic 1, there exists a bound $d = \tilde{\Theta}(\sqrt{p})$ such that Algorithm 2 terminates after $O(\log(p)^2)$ iterations on average.

*Proof.* Let $1 \le d \le 2^{e-1}$. Then we have:

$$\#P_d(\mathcal{B}) = \prod_{j=1}^{4} (2B_j + 1) \ge \prod_{j=1}^{4} \frac{1}{2} \sqrt{\frac{d}{q_I(\alpha_j)}} = \frac{d^2}{16 \sqrt{\prod_{j=1}^{4} q_I(\alpha_j)}}.$$
**Heuristic 1** For $1 \le d \le 2^{e-1}$, consider:

$$S_{d,e}(\mathcal{B}) := \{(\beta_1, \beta_2) \in P_d(\mathcal{B})^2 \mid \gcd(q_I(\beta_1), q_I(\beta_2)) = 1 \text{ and} \\ \exists u, v \in \mathbb{N}^*, uq_I(\beta_1) + vq_I(\beta_2) = 2^e\}.$$

Then, there exists constants $C', C > 0$ independent from $I, \mathcal{B}$ and the parameters $p$ and $e$ such that for all $1 \le d \le 2^{e-1}$,

1. $\#S_{d,e}(\mathcal{B}) \ge C \#P_d(\mathcal{B})^{2e}/d^2 - 1$.

2. When $\beta_1, \beta_2$ are independent and uniformly distributed in $P_d(\mathcal{B})$,

$$\mathbb{P}((\beta_1, \beta_2) \in S_{d,e}(\mathcal{B})) \ge C' \frac{\#S_{d,e}(\mathcal{B})}{\#P_d(\mathcal{B})^2}.$$

Note that we need $d_1u$ and $d_2v$ to be coprime. Since $d_1u + d_2v = 2^e$ and $d_1$ and $d_2$ are odd and coprime, this condition is not satisfied only when $u$ and $v$ are even. Hence, we may divide $u$ and $v$ by $2^{e'}$ and replace $e$ by $f := e - e'$ with $e' = \min(v_2(u), v_2(v))$, so that $d_1u + d_2v = 2^f$ and $d_1u$ and $d_2v$ are coprime. We summarise step 1 in Algorithm 2.

**Algorithm 2** Step 1: Finding suitable ideals $I_1, I_2 \sim I$.

**Input:** An ideal $I \subseteq \mathcal{O}_0 \cong \text{End}(E_0)$, a bound $d = \Theta(\sqrt{p})$.

**Output:** $\beta_1, \beta_2 \in I$ and $u, v \in \mathbb{N}^*$ and $f \le e$ such that $\gcd(uq_I(\beta_1), vq_I(\beta_2)) = 1$ and $uq_I(\beta_1) + vq_I(\beta_2) = 2^f$.

1. Compute a Minkowski reduced basis $(\alpha_1, \dots, \alpha_4)$ of $I$

2. $B_j \leftarrow [1/4\sqrt{d/q_I(\alpha_j)}]$ for $j \in [1; 4]$

3. Sample $x_j \in [-B_j; B_j]^4$ for $j \in [1; 4]$ and initialise $L \leftarrow [(x_1, \dots, x_4)]$

4. **for** $(y_1, \dots, y_4) \in [-B_1; B_1]^4 \times \dots \times [-B_4; B_4]^4$ **do**

5. **for** $(x_1, \dots, x_4) \in L$ **do**

6. $\beta_1 \leftarrow \sum_{j=1}^4 x_j \alpha_j$ and $\beta_2 \leftarrow \sum_{j=1}^4 y_j \alpha_j$

7. $d_1 \leftarrow q_I(\beta_1)$, $d_2 \leftarrow q_I(\beta_2)$

8. **if** $d_1 \equiv 1 \mod 2$ and $d_2 \equiv 1 \mod 2$ and $\gcd(d_1, d_2) = 1$ **then**

9. $u \leftarrow 2^e d_1^{-1} \mod d_2$

10. $v \leftarrow (2^e - ud_1)/d_2$

11. **if** $v > 0$ **then**

12. $e' \leftarrow \min(v_2(u), v_2(v))$, $u \leftarrow u/2^{e'}$, $v \leftarrow v/2^{e'}$ and $f \leftarrow e - e'$

13. **return** $\beta_1, \beta_2, u, v, f$

14. **else**

15. Append $(y_1, \dots, y_4)$ to $L$

**Proposition 8.** Assuming Heuristic 1, there exists a bound $d = \tilde{\Theta}(\sqrt{p})$ such that Algorithm 2 terminates after $O(\log(p)^2)$ iterations on average.

*Proof.* Let $1 \le d \le 2^{e-1}$. Then we have:

$$\#P_d(\mathcal{B}) = \prod_{j=1}^{4} (2B_j + 1) \ge \prod_{j=1}^{4} \frac{1}{2} \sqrt{\frac{d}{q_I(\alpha_j)}} = \frac{d^2}{16 \sqrt{\prod_{j=1}^{4} q_I(\alpha_j)}}.$$
Besides, $\mathcal{B} = (\alpha_1, \dots, \alpha_4)$ being Minkowski reduced, $q_I(\alpha_1), \dots, q_I(\alpha_4)$ are the successive minima of the lattice $I$ and we obtain by Minkowski's second theorem (see the proof of [11, Lemma 48]) that $\prod_{j=1}^4 q_I(\alpha_j) \le 64p^2/\pi^4$, so that:

$$ \#P_d(\mathcal{B}) \ge \frac{Dd^2}{p}, $$

with $D := \pi^2/128$. By **Heuristic 1**, there exists $C, C' > 0$ such that:

$$ \mathbb{P}((\beta_1, \beta_2) \in S_{d,e}(\mathcal{B})) \ge C' \left( \frac{C2^e}{d^2} - \frac{1}{\#P_d(\mathcal{B})^2} \right) \ge C' \left( \frac{C2^e}{d^2} - \frac{p^2}{D^2d^4} \right), $$

where $\beta_1, \beta_2$ are independent and uniformly distributed in $P_d(\mathcal{B})$. The lower bound on the right is maximised by the value $d := p/(D\sqrt{C2^{e-1}})$ and for this value of $d$, we obtain:

$$ \mathbb{P}((\beta_1, \beta_2) \in S_{d,e}(\mathcal{B})) \ge \frac{C' C^2 D^2 2^{2(e-1)}}{p^2} = \Omega(1/\log(p)^2), \quad (1) $$

since $p = O(\log(p)2^e)$ by Dirichlet's arithmetic progression theorem [18]. Algorithm 2 enumerates $\beta_1, \beta_2$ independent and uniformly distributed in $P_d(\mathcal{B})$ and terminates when $(\beta_1, \beta_2) \in S_{d,e}(\mathcal{B})$. Hence Eq. (1) completes the proof. $\square$

**Remark 9.** In most cases, the successive minima $q_I(\alpha_j)$ are close to each other and close to $\sqrt{p}$ so the $B_j$ are very close. For that reason, in the implemented version of Algorithm 2 we fix a bound $B \in \mathbb{N}^*$ and sample all of the $x_j$ and $y_j$ in $[-B; B]$.

**Step 2.** We can use FixedDegreeIsogeny (Algorithm 1) to evaluate isogenies $\phi_u, \phi_v : E_0 \to E_u, E_v$ of degrees $u$ and $v$ on $E_0[2^e]$. Since $u, v \approx \sqrt{p}$, we do not need to compute (2,2)-isogeny chains of full length $e$ in this step, but of half length $e/2$ instead (see Remark 7).

**Remark 10.** Alternatively, we may save some time on step 2 at the expense of step 1. Assuming $u = a^2 + b^2$, with $a, b \in \mathbb{Z}$, then we can choose $\phi_u := [a] + [b]\iota \in \mathrm{End}(E_0)$, with $\iota : (x, y) \in E_0 \to (-x, \sqrt{-1}y) \in E_0$ and similarly for $v$. Finding $u, v$ in step 1 that can be written easily as a sum of to squares is more costly. There is also a hybrid approach where we only require $u$ (or $v$) to be a sum of two squares. Experimentally, both of these approach were on the whole more costly than the proposed method as soon as the ideal given in input is a bit unbalanced (and the smallest possible $d_2$ is a bit bigger than the expected $\approx \sqrt{p}$). However, we believe that there is room for improvement in our implementation of this search for $d_1, d_2, u$ and $v$, and this could lead to a different conclusion regarding which variant is the most efficient. Answering this interrogation is left as an interesting open question for future work.
Besides, $\mathcal{B} = (\alpha_1, \dots, \alpha_4)$ being Minkowski reduced, $q_I(\alpha_1), \dots, q_I(\alpha_4)$ are the successive minima of the lattice $I$ and we obtain by Minkowski's second theorem (see the proof of [11, Lemma 48]) that $\prod_{j=1}^4 q_I(\alpha_j) \le 64p^2/\pi^4$, so that:

$$ \#P_d(\mathcal{B}) \ge \frac{Dd^2}{p}, $$

with $D := \pi^2/128$. By Heuristic 1, there exists $C, C' > 0$ such that:

$$ \mathbb{P}((\beta_1, \beta_2) \in S_{d,e}(\mathcal{B})) \ge C' \left( \frac{C2^e}{d^2} - \frac{1}{\#P_d(\mathcal{B})^2} \right) \ge C' \left( \frac{C2^e}{d^2} - \frac{p^2}{D^2d^4} \right), $$

where $\beta_1, \beta_2$ are independent and uniformly distributed in $P_d(\mathcal{B})$. The lower bound on the right is maximised by the value $d := p/(D\sqrt{C2^{e-1}})$ and for this value of $d$, we obtain:

$$ \mathbb{P}((\beta_1, \beta_2) \in S_{d,e}(\mathcal{B})) \ge \frac{C' C^2 D^2 2^{2(e-1)}}{p^2} = \Omega(1/\log(p)^2), \quad (1) $$

since $p = O(\log(p)2^e)$ by Dirichlet's arithmetic progression theorem [18]. Algorithm 2 enumerates $\beta_1, \beta_2$ independent and uniformly distributed in $P_d(\mathcal{B})$ and terminates when $(\beta_1, \beta_2) \in S_{d,e}(\mathcal{B})$. Hence Eq. (1) completes the proof. $\square$

**Remark 9.** In most cases, the successive minima $q_I(\alpha_j)$ are close to each other and close to $\sqrt{p}$ so the $B_j$ are very close. For that reason, in the implemented version of Algorithm 2 we fix a bound $B \in \mathbb{N}^*$ and sample all of the $x_j$ and $y_j$ in $[-B; B]$.

**Step 2.** We can use FixedDegreeIsogeny (Algorithm 1) to evaluate isogenies $\phi_u, \phi_v : E_0 \to E_u, E_v$ of degrees $u$ and $v$ on $E_0[2^e]$. Since $u, v \approx \sqrt{p}$, we do not need to compute (2,2)-isogeny chains of full length $e$ in this step, but of half length $e/2$ instead (see Remark 7).

**Remark 10.** Alternatively, we may save some time on step 2 at the expense of step 1. Assuming $u = a^2 + b^2$, with $a, b \in \mathbb{Z}$, then we can choose $\phi_u := [a] + [b]\iota \in \mathrm{End}(E_0)$, with $\iota : (x, y) \in E_0 \to (-x, \sqrt{-1}y) \in E_0$ and similarly for $v$. Finding $u, v$ in step 1 that can be written easily as a sum of to squares is more costly. There is also a hybrid approach where we only require $u$ (or $v$) to be a sum of two squares. Experimentally, both of these approach were on the whole more costly than the proposed method as soon as the ideal given in input is a bit unbalanced (and the smallest possible $d_2$ is a bit bigger than the expected $\approx \sqrt{p}$). However, we believe that there is room for improvement in our implementation of this search for $d_1, d_2, u$ and $v$, and this could lead to a different conclusion regarding which variant is the most efficient. Answering this interrogation is left as an interesting open question for future work.
<figure><img src="image_3.png" /></figure>

**Step 3.** We now give more details on steps 3 and 4 inspired by [36]. Consider the following $(d_1u, d_2v)$-isogeny diamond:

where $\varphi'_u := [\varphi_u \circ \varphi_1]_*(\varphi_v \circ \varphi_2)$ and $\varphi'_v := [\varphi_v \circ \varphi_2]_*(\varphi_u \circ \varphi_1)$ (pushforward isogenies). By Kani's lemma, we have a $(2^f, 2^f)$-isogeny:

$$ \Phi := \begin{pmatrix} \varphi_1 \circ \hat{\varphi}_u & \varphi_2 \circ \hat{\varphi}_v \\ -\varphi'_u & \varphi'_v \end{pmatrix} : E_u \times E_v \to E_I \times E', $$

with kernel:

$$ \ker(\Phi) = \{([d_1]\varphi_u(P), \varphi_v \circ \hat{\varphi}_2 \circ \varphi_1(P)) \mid P \in E_u[2^f]\}. $$

Let $\theta := \hat{\varphi}_2 \circ \varphi_1 \in \mathrm{End}(E_0)$. By Lemma 11, given $I_1$ and $I_2$, if we write $I_1 := I\overline{\beta_1}/\mathrm{nrd}(I)$ and $I_2 := I\overline{\beta_2}/\mathrm{nrd}(I)$ with $\beta_1, \beta_2 \in I$, then we can compute $\theta = \beta_2\overline{\beta_1}/\mathrm{nrd}(I)$ so we can evaluate it easily. By step 2, we also know $\varphi_v|_{2^e}$ and $\varphi_u|_{2^e}$. Hence, we can compute $\ker(\Phi)$ (and evaluate $\Phi$) efficiently. This completes step 3.

**Step 4.** We first notice that we can evaluate $\varphi_1 \circ \hat{\varphi}_u$ from the two-dimensional isogeny $\Phi$. This implies we can evaluate $\varphi_1$ on $E_0[2^e]$ as follows: $\Phi(\varphi_u(P), 0) = ([u]\varphi_1(P), \*)$ and $\Phi(\varphi_u(Q), 0) = ([u]\varphi_1(Q), \*)$ and we can invert $u$ modulo $2^e$ since $u$ is odd to get $\varphi_1|_{2^e} = (\varphi_1(P), \varphi_1(Q))$. To obtain $\varphi_I|_{2^e}$, we rely on the following lemma.

**Lemma 11.** For $i \in \{1, 2\}$, if we write $I_i := I\overline{\beta_i}/\mathrm{nrd}(I)$ with $\beta_i \in I$, then $\hat{\varphi}_i \circ \varphi_I = \beta_i$.

*Proof.* Let $i \in \{1, 2\}$. We have $O_L(\overline{I_i}) = O_R(I_i) = \overline{\beta_i}^{-1}O_R(I)\overline{\beta_i}$. It follows that $O_L(\overline{\beta_i} \cdot \overline{I_i} \cdot \overline{\beta_i}^{-1}) = O_R(I)$ and the ideal corresponding to the isogeny $\hat{\varphi}_i \circ \varphi_I$ via the Deuring correspondence is:

$$ I\overline{\beta_i} \cdot \overline{I_i} \cdot \overline{\beta_i}^{-1} = I \frac{\overline{\beta_i}\overline{\beta_i}}{\mathrm{nrd}(I)} \overline{I} \cdot \overline{\beta_i}^{-1} = I\overline{I} \frac{\mathrm{nrd}(\overline{\beta_i})}{\mathrm{nrd}(I)} \frac{\overline{\beta_i}}{\mathrm{nrd}(\overline{\beta_i})} = O_0\overline{\beta_i}. $$

The result follows.

□

Following Lemma 6, we have that $[d_1]\varphi_I = \varphi_1 \circ \beta_1$. Since we can evaluate $\beta_1$ and $\varphi_1$ on $E_0[2^e]$ and $d_1$ can be inverted modulo $2^e$, we can evaluate $\varphi_I$ on $E_0[2^e]$, completing step 4. Algorithm 3 summarises all these steps.
<figure><img src="image_5.png" /></figure>

**Step 3.** We now give more details on steps 3 and 4 inspired by [36]. Consider the following $(d_1u, d_2v)$-isogeny diamond:

where $\varphi'_u := [\varphi_u \circ \varphi_1]_*(\varphi_v \circ \varphi_2)$ and $\varphi'_v := [\varphi_v \circ \varphi_2]_*(\varphi_u \circ \varphi_1)$ (pushforward isogenies). By Kani's lemma, we have a $(2^f, 2^f)$-isogeny:

$$ \Phi := \begin{pmatrix} \varphi_1 \circ \hat{\varphi}_u & \varphi_2 \circ \hat{\varphi}_v \\ -\varphi'_u & \varphi'_v \end{pmatrix} : E_u \times E_v \to E_I \times E', $$

with kernel:

$$ \ker(\Phi) = \{([d_1]\varphi_u(P), \varphi_v \circ \hat{\varphi}_2 \circ \varphi_1(P)) \mid P \in E_u[2^f]\}. $$

Let $\theta := \hat{\varphi}_2 \circ \varphi_1 \in \mathrm{End}(E_0)$. By Lemma 11, given $I_1$ and $I_2$, if we write $I_1 := I\overline{\beta_1}/\mathrm{nrd}(I)$ and $I_2 := I\overline{\beta_2}/\mathrm{nrd}(I)$ with $\beta_1, \beta_2 \in I$, then we can compute $\theta = \beta_2\overline{\beta_1}/\mathrm{nrd}(I)$ so we can evaluate it easily. By step 2, we also know $\varphi_v|_{2^e}$ and $\varphi_u|_{2^e}$. Hence, we can compute $\ker(\Phi)$ (and evaluate $\Phi$) efficiently. This completes step 3.

**Step 4.** We first notice that we can evaluate $\varphi_1 \circ \hat{\varphi}_u$ from the two-dimensional isogeny $\Phi$. This implies we can evaluate $\varphi_1$ on $E_0[2^e]$ as follows: $\Phi(\varphi_u(P), 0) = ([u]\varphi_1(P), \*)$ and $\Phi(\varphi_u(Q), 0) = ([u]\varphi_1(Q), \*)$ and we can invert $u$ modulo $2^e$ since $u$ is odd to get $\varphi_1|_{2^e} = (\varphi_1(P), \varphi_1(Q))$. To obtain $\varphi_I|_{2^e}$, we rely on the following lemma.

**Lemma 11.** For $i \in \{1, 2\}$, if we write $I_i := I\overline{\beta_i}/\mathrm{nrd}(I)$ with $\beta_i \in I$, then $\hat{\varphi}_i \circ \varphi_I = \beta_i$.

*Proof.* Let $i \in \{1, 2\}$. We have $O_L(\overline{I_i}) = O_R(I_i) = \overline{\beta_i}^{-1}O_R(I)\overline{\beta_i}$. It follows that $O_L(\overline{\beta_i} \cdot \overline{I_i} \cdot \overline{\beta_i}^{-1}) = O_R(I)$ and the ideal corresponding to the isogeny $\hat{\varphi}_i \circ \varphi_I$ via the Deuring correspondence is:

$$ I\overline{\beta_i} \cdot \overline{I_i} \cdot \overline{\beta_i}^{-1} = I \frac{\overline{\beta_i}\beta_i}{\mathrm{nrd}(I)} \overline{I} \cdot \overline{\beta_i}^{-1} = I\overline{I} \frac{\mathrm{nrd}(\beta_i)}{\mathrm{nrd}(I)} \frac{\beta_i}{\mathrm{nrd}(\beta_i)} = O_0\beta_i. $$

The result follows.

□

Following Lemma 6, we have that $[d_1]\varphi_I = \varphi_1 \circ \beta_1$. Since we can evaluate $\beta_1$ and $\varphi_1$ on $E_0[2^e]$ and $d_1$ can be inverted modulo $2^e$, we can evaluate $\varphi_I$ on $E_0[2^e]$, completing step 4. Algorithm 3 summarises all these steps.
**Algorithm 3 Ideal Tolsogeny**

**Input:** An ideal $I \subseteq \mathcal{O}_0 \cong \text{End}(E_0)$ and a basis $(P_0, Q_0)$ of $E_0[2^e]$.

**Output:** The image $\varphi_I|_{2^e} = (\varphi_I(P_0), \varphi_I(Q_0))$ of the isogeny $\varphi_I : E_0 \to E_I$ associated to $I$.

1. Use Algorithm 2 to obtain $\beta_1, \beta_2 \in I$ and $u, v \in \mathbb{N}^*$ and $f \le e$ such that $\text{gcd}(uq_I(\beta_1), vq_I(\beta_2)) = 1$ and $uq_I(\beta_1) + vq_I(\beta_2) = 2^f$

2. $I_i \leftarrow I \beta_i / \text{nrd}(I)$ for $i \in \{1, 2\}$

3. $\theta \leftarrow \beta_2 \beta_1 / \text{nrd}(I) \in \text{End}(E_0)$ (▷) $\theta := \hat{\varphi}_2 \circ \varphi_1$

4. Compute $\varphi_u|_{2^e}$ for a $u$-isogeny $\varphi_u : E_0 \to E_u$ (▷) FixedDegreelsogeny($u, P_0, Q_0$)

5. Compute $\varphi_v|_{2^e}$ for a $v$-isogeny $\varphi_v : E_0 \to E_v$ (▷) FixedDegreelsogeny($v, P_0, Q_0$)

6. Set $K_P \leftarrow [2^{e-f}]/([d_1]\varphi_u(P_0), \varphi_v \circ \theta(P_0))$

7. Set $K_Q \leftarrow [2^{e-f}]/([d_1]\varphi_u(Q_0), \varphi_v \circ \theta(Q_0))$

8. Compute $\Phi : E_v \times E_v \to E_I \times E'$ of kernel $\langle K_P, K_Q \rangle$

9. Evaluate $\Phi(\varphi_u(P_0), 0) = ([u]\varphi_1(P_0), *)$ and $\Phi(\varphi_u(Q_0), 0) = ([u]\varphi_1(Q_0), *)$ to obtain $\varphi_1|_{2^e}$

10. Use $\varphi_1|_{2^e}$ to evaluate $\varphi_I = [1/d_1]\varphi_1 \circ \beta_1$ on $(P_0, Q_0)$ and obtain $\varphi_I|_{2^e}$

11. **return** $\varphi_I|_{2^e}$

## 4.3 Sampling uniformly at random an ideal of fixed norm

In the protocol, we shall need to uniformly sample at random cyclic isogenies $\varphi : E \to E'$ of fixed degree $N$ several times. When $\mathcal{O} \cong \text{End}(E)$ is known, by the Deuring correspondence this reduces to sampling a left ideal $I \subseteq \mathcal{O}$ of norm $N$ uniformly at random. $I$ is then translated into an isogeny $\varphi$ (e.g. using Algorithm 3 if $\mathcal{O} = \mathcal{O}_0$). For $\varphi$ to be cyclic, $I$ has to be primitive, that is to say that $I \not\subseteq n\mathcal{O}$ for any integer $n > 1$.

Given a maximal quaternion order $\mathcal{O} \subseteq \mathcal{B}_{p,\infty}$ and an integer $N$ coprime with $p$, we explain how to sample primitive left ideals $I \subseteq \mathcal{O}$ of norm $N$. It has been proved that such ideals are in bijection with primitive left-ideals of $\mathcal{O}/N\mathcal{O}$ via the reduction modulo $N$ which are themselves in bijection with:

$$ \mathbb{P}^1(\mathbb{Z}/N\mathbb{Z}) = \{(x, y) \in (\mathbb{Z}/N\mathbb{Z})^2 \mid \text{gcd}(x, y, N) = 1\}/(\mathbb{Z}/N\mathbb{Z})^*. $$

$N$ being coprime with $p$, $\mathcal{B}_{p,\infty}$ splits at $N$ and we have an isomorphism $\mathcal{O} \otimes \mathbb{Z}_N \cong M_2(\mathbb{Z}_N)$, where $\mathbb{Z}_N$ is the completion of the localisation of $\mathbb{Z}$ at $N$. Via the reduction modulo $N$, we obtain an isomorphism $\varphi_N : \mathcal{O}/N\mathcal{O} \xrightarrow{\sim} M_2(\mathbb{Z}/N\mathbb{Z})$.

**Lemma 12 ([28, Lemma 7.2]).** All primitive left-ideals of $M_2(\mathbb{Z}/N\mathbb{Z})$ are principal and generated by a matrix

$$ M_{x,y} = \begin{pmatrix} x & y \\ 0 & 0 \end{pmatrix} $$

with $(x : y) \in \mathbb{P}^1(\mathbb{Z}/N\mathbb{Z})$. Hence, we have the following bijection:

$$ \begin{gathered} \mathbb{P}^1(\mathbb{Z}/N\mathbb{Z}) \to \{\text{primitive left ideals } I \subseteq \mathcal{O} \text{ of norm } N\} \\ (x : y) \mapsto \mathcal{O}\varphi_N^{-1}(M_{x,y}) + N\mathcal{O} \end{gathered} $$
**Algorithm 3 Ideal Tolsogeny**

**Input:** An ideal $I \subseteq \mathcal{O}_0 \cong \text{End}(E_0)$ and a basis $(P_0, Q_0)$ of $E_0[2^e]$.

**Output:** The image $\varphi_I|_{2^e} = (\varphi_I(P_0), \varphi_I(Q_0))$ of the isogeny $\varphi_I : E_0 \to E_I$ associated to $I$.

1. Use Algorithm 2 to obtain $\beta_1, \beta_2 \in I$ and $u, v \in \mathbb{N}^*$ and $f \le e$ such that $\text{gcd}(uq_I(\beta_1), vq_I(\beta_2)) = 1$ and $uq_I(\beta_1) + vq_I(\beta_2) = 2^f$

2. $I_i \leftarrow I \beta_i / \text{nrd}(I)$ for $i \in \{1, 2\}$

3. $\theta \leftarrow \beta_2 \beta_1 / \text{nrd}(I) \in \text{End}(E_0)$ (▷) $\theta := \hat{\varphi}_2 \circ \varphi_1$

4. Compute $\varphi_u|_{2^e}$ for a $u$-isogeny $\varphi_u : E_0 \to E_u$ (▷) FixedDegreelsogeny($u, P_0, Q_0$)

5. Compute $\varphi_v|_{2^e}$ for a $v$-isogeny $\varphi_v : E_0 \to E_v$ (▷) FixedDegreelsogeny($v, P_0, Q_0$)

6. Set $K_P \leftarrow [2^{e-f}]/([d_1]\varphi_u(P_0), \varphi_v \circ \theta(P_0))$

7. Set $K_Q \leftarrow [2^{e-f}]/([d_1]\varphi_u(Q_0), \varphi_v \circ \theta(Q_0))$

8. Compute $\Phi : E_v \times E_v \to E_I \times E'$ of kernel $\langle K_P, K_Q \rangle$

9. Evaluate $\Phi(\varphi_u(P_0), 0) = ([u]\varphi_1(P_0), *)$ and $\Phi(\varphi_u(Q_0), 0) = ([u]\varphi_1(Q_0), *)$ to obtain $\varphi_1|_{2^e}$

10. Use $\varphi_1|_{2^e}$ to evaluate $\varphi_I = [1/d_1]\varphi_1 \circ \beta_1$ on $(P_0, Q_0)$ and obtain $\varphi_I|_{2^e}$

11. **return** $\varphi_I|_{2^e}$

## 4.3 Sampling uniformly at random an ideal of fixed norm

In the protocol, we shall need to uniformly sample at random cyclic isogenies $\varphi : E \to E'$ of fixed degree $N$ several times. When $\mathcal{O} \cong \text{End}(E)$ is known, by the Deuring correspondence this reduces to sampling a left ideal $I \subseteq \mathcal{O}$ of norm $N$ uniformly at random. $I$ is then translated into an isogeny $\varphi$ (e.g. using Algorithm 3 if $\mathcal{O} = \mathcal{O}_0$). For $\varphi$ to be cyclic, $I$ has to be primitive, that is to say that $I \not\subseteq n\mathcal{O}$ for any integer $n > 1$.

Given a maximal quaternion order $\mathcal{O} \subseteq \mathcal{B}_{p,\infty}$ and an integer $N$ coprime with $p$, we explain how to sample primitive left ideals $I \subseteq \mathcal{O}$ of norm $N$. It has been proved that such ideals are in bijection with primitive left-ideals of $\mathcal{O}/N\mathcal{O}$ via the reduction modulo $N$ which are themselves in bijection with:

$$ \mathbb{P}^1(\mathbb{Z}/N\mathbb{Z}) = \{(x, y) \in (\mathbb{Z}/N\mathbb{Z})^2 \mid \text{gcd}(x, y, N) = 1\}/(\mathbb{Z}/N\mathbb{Z})^*. $$

$N$ being coprime with $p$, $\mathcal{B}_{p,\infty}$ splits at $N$ and we have an isomorphism $\mathcal{O} \otimes \mathbb{Z}_N \cong M_2(\mathbb{Z}_N)$, where $\mathbb{Z}_N$ is the completion of the localisation of $\mathbb{Z}$ at $N$. Via the reduction modulo $N$, we obtain an isomorphism $\varphi_N : \mathcal{O}/N\mathcal{O} \xrightarrow{\sim} M_2(\mathbb{Z}/N\mathbb{Z})$.

**Lemma 12 ([28, Lemma 7.2]).** All primitive left-ideals of $M_2(\mathbb{Z}/N\mathbb{Z})$ are principal and generated by a matrix

$$ M_{x,y} = \begin{pmatrix} x & y \\ 0 & 0 \end{pmatrix} $$

with $(x : y) \in \mathbb{P}^1(\mathbb{Z}/N\mathbb{Z})$. Hence, we have the following bijection:

$$ \begin{gathered} \mathbb{P}^1(\mathbb{Z}/N\mathbb{Z}) \to \{\text{primitive left ideals } I \subseteq \mathcal{O} \text{ of norm } N\} \\ (x : y) \mapsto \mathcal{O}\varphi_N^{-1}(M_{x,y}) + N\mathcal{O} \end{gathered} $$
As a direct consequence of the above lemma, we obtain:

**Lemma 13.** The set of elements $\alpha \in \mathcal{O}$ invertible modulo $N$ acts transitively (by multiplication on the right) on the set of primitive left $\mathcal{O}$-ideals of norm $N$.

*Proof.* Let $I$ be a primitive left $\mathcal{O}$-ideal of norm $N$. Then, the ideal $I$ corresponds to $(x : y) \in \mathbb{P}^1(\mathbb{Z}/NZ)$ via the bijection of Lemma 12 and is isomorphic to $M_2(\mathbb{Z}/NZ) \cdot M_{x,y}$ via the composition of the reduction modulo $N$ and $\varphi_N$. For any representative $(x, y) \in \mathbb{Z}^2$ of $(x : y) \in \mathbb{P}^1(\mathbb{Z}/NZ)$, we have $\gcd(x, y, N) = 1$ so we may find $u, v \in \mathbb{Z}$ such that $xu + yv \equiv 1 \mod N$, so that:

$$M_{x,y} \begin{pmatrix} u & -y \\ v & x \end{pmatrix} \equiv M_{1,0} \mod N \quad \text{and} \quad \det \begin{pmatrix} u & -y \\ v & x \end{pmatrix} \equiv 1 \mod N$$

Hence, the ideal $M_2(\mathbb{Z}/NZ) \cdot M_{x,y}$ is in the orbit of $M_2(\mathbb{Z}/NZ) \cdot M_{1,0}$ under the right action of $GL_2(\mathbb{Z}/NZ)$, and as a consequence, $I/NO$ is in the orbit of the ideal $I_0/NO := \mathcal{O}\varphi_N^{-1}(M_{1,0})/NO$ under the right action of $(\mathcal{O}/NO)^*$.

To conclude, it suffices to prove that the invertible elements of $\mathcal{O}$ modulo $N$ are those of norm coprime with $N$. If $\alpha \in \mathcal{O}$ is invertible modulo $N$, there exists $\beta, \gamma \in \mathcal{O}$ such that $\alpha\beta = 1 + N\gamma$, so that

$$\mathrm{nrd}(\alpha) \mathrm{nrd}(\beta) = \mathrm{nrd}(1 + N\gamma) = 1 + N \mathrm{Tr}(\gamma) + N^2 \mathrm{nrd}(\gamma) \equiv 1 \mod N,$$

so $\mathrm{nrd}(\alpha)$ is invertible modulo $N$. Conversely, if $\mathrm{nrd}(\alpha)$ is prime to $N$, there exists $\lambda \in \mathbb{Z}$ such that $\mathrm{nrd}(\alpha)\lambda \equiv 1 \mod N$. Then, it follows that $\alpha\bar{\alpha}\lambda \equiv 1 \mod N$, so $\alpha$ is invertible modulo $N$. This completes the proof. $\square$

**Lemma 13** ensures that that $(\mathcal{O}/NO)^*$ acts transitively on primitive left ideals of norm $N$ by multiplication on the right. Hence, given a primitive left $\mathcal{O}$-ideal $I_0$ of norm $N$, if we sample $[\alpha] \in (\mathcal{O}/NO)^*$ uniformly at random, then $I_0\alpha$ is uniformly random among primitive left $\mathcal{O}$-ideals of norm $N$.

To obtain such an ideal $I_0$, we compute $\gamma \in \mathcal{O}$ of norm $NM$ with $\gcd(N, M) = 1$ and without integral factor. This can be done with the algorithms of [30, § 3.3]. We then consider $I_0 := \mathcal{O}\gamma + \mathcal{O}N$ and sample $[\alpha] \in \mathcal{O}/NO$ uniformly at random until it is invertible modulo $N$ (which can be checked by computing $\mathrm{nrd}(\alpha)$). The probability of finding such an $\alpha$ is (by the Chinese remainder theorem):

$$\frac{|GL_2(\mathbb{Z}/NZ)|}{|M_2(\mathbb{Z}/NZ)|} = \prod_{\ell^e \mid \mid N} \frac{|GL_2(\mathbb{Z}/\ell^e \mathbb{Z})|}{|M_2(\mathbb{Z}/\ell^e \mathbb{Z})|} = \prod_{\ell \mid N} \left(1 - \frac{1}{\ell}\right) \left(1 - \frac{1}{\ell^2}\right).$$

This quantity is an $\Omega(1/\log \log(N))$ by [24, Theorem 328] so we can find $\alpha$ after $\log \log(N)$ tries on average. These operations are summarised in Algorithm 4.

# 5 Detailed description of SQIsign2D

We now present a full description of the SQIsign2D protocol. We start by describing the $\Sigma$ protocol underlying SQIsign2D, and then we present the variant
As a direct consequence of the above lemma, we obtain:

**Lemma 13.** The set of elements $\alpha \in \mathcal{O}$ invertible modulo $N$ acts transitively (by multiplication on the right) on the set of primitive left $\mathcal{O}$-ideals of norm $N$.

*Proof.* Let $I$ be a primitive left $\mathcal{O}$-ideal of norm $N$. Then, the ideal $I$ corresponds to $(x : y) \in \mathbb{P}^1(\mathbb{Z}/NZ)$ via the bijection of Lemma 12 and is isomorphic to $M_2(\mathbb{Z}/NZ) \cdot M_{x,y}$ via the composition of the reduction modulo $N$ and $\varphi_N$. For any representative $(x, y) \in \mathbb{Z}^2$ of $(x : y) \in \mathbb{P}^1(\mathbb{Z}/NZ)$, we have $\gcd(x, y, N) = 1$ so we may find $u, v \in \mathbb{Z}$ such that $xu + yv \equiv 1 \mod N$, so that:

$$M_{x,y} \begin{pmatrix} u & -y \\ v & x \end{pmatrix} \equiv M_{1,0} \mod N \quad \text{and} \quad \det \begin{pmatrix} u & -y \\ v & x \end{pmatrix} \equiv 1 \mod N$$

Hence, the ideal $M_2(\mathbb{Z}/NZ) \cdot M_{x,y}$ is in the orbit of $M_2(\mathbb{Z}/NZ) \cdot M_{1,0}$ under the right action of $GL_2(\mathbb{Z}/NZ)$, and as a consequence, $I/NO$ is in the orbit of the ideal $I_0/NO := \mathcal{O}\varphi_N^{-1}(M_{1,0})/NO$ under the right action of $(\mathcal{O}/NO)^*$.

To conclude, it suffices to prove that the invertible elements of $\mathcal{O}$ modulo $N$ are those of norm coprime with $N$. If $\alpha \in \mathcal{O}$ is invertible modulo $N$, there exists $\beta, \gamma \in \mathcal{O}$ such that $\alpha\beta = 1 + N\gamma$, so that

$$\text{nrd}(\alpha) \text{nrd}(\beta) = \text{nrd}(1 + N\gamma) = 1 + N \text{Tr}(\gamma) + N^2 \text{nrd}(\gamma) \equiv 1 \mod N,$$

so $\text{nrd}(\alpha)$ is invertible modulo $N$. Conversely, if $\text{nrd}(\alpha)$ is prime to $N$, there exists $\lambda \in \mathbb{Z}$ such that $\text{nrd}(\alpha)\lambda \equiv 1 \mod N$. Then, it follows that $\alpha\bar{\alpha}\lambda \equiv 1 \mod N$, so $\alpha$ is invertible modulo $N$. This completes the proof. $\square$

**Lemma 13** ensures that that $(\mathcal{O}/NO)^*$ acts transitively on primitive left ideals of norm $N$ by multiplication on the right. Hence, given a primitive left $\mathcal{O}$-ideal $I_0$ of norm $N$, if we sample $[\alpha] \in (\mathcal{O}/NO)^*$ uniformly at random, then $I_0\alpha$ is uniformly random among primitive left $\mathcal{O}$-ideals of norm $N$.

To obtain such an ideal $I_0$, we compute $\gamma \in \mathcal{O}$ of norm $NM$ with $\gcd(N, M) = 1$ and without integral factor. This can be done with the algorithms of [30, § 3.3]. We then consider $I_0 := \mathcal{O}\gamma + \mathcal{O}N$ and sample $[\alpha] \in \mathcal{O}/NO$ uniformly at random until it is invertible modulo $N$ (which can be checked by computing $\text{nrd}(\alpha)$). The probability of finding such an $\alpha$ is (by the Chinese remainder theorem):

$$\frac{|GL_2(\mathbb{Z}/NZ)|}{|M_2(\mathbb{Z}/NZ)|} = \prod_{\ell^e \mid \mid N} \frac{|GL_2(\mathbb{Z}/\ell^e \mathbb{Z})|}{|M_2(\mathbb{Z}/\ell^e \mathbb{Z})|} = \prod_{\ell \mid N} \left(1 - \frac{1}{\ell}\right) \left(1 - \frac{1}{\ell^2}\right).$$

This quantity is an $\Omega(1/\log \log(N))$ by [24, Theorem 328] so we can find $\alpha$ after $\log \log(N)$ tries on average. These operations are summarised in Algorithm 4.

# 5 Detailed description of SQIsign2D

We now present a full description of the SQIsign2D protocol. We start by describing the $\Sigma$ protocol underlying SQIsign2D, and then we present the variant
**Algorithm 4 RandomFixedNormIdeal**

**Input:** A maximal order $O \subseteq B_{p,\infty}$ and an integer $N$ such that $p \nmid N$.

**Output:** A primitive left $O$-ideal $I$ of norm $N$ sampled uniformly at random.

1: Find $\gamma \in O$ primitive of norm $NM$ with $\gcd(N, M) = 1$

(▷) Using [30, § 3.3]

2: **repeat**

3: Sample $u_1, \dots, u_4 \in [0; N-1]$ uniformly at random

4: $\alpha \leftarrow \sum_{i=1}^{4} u_i \alpha_i$, where $(\alpha_1, \dots, \alpha_4)$ is a basis of $O$

5: **until** $\gcd(nrd(\alpha), N) = 1$

6: Return $I := O\gamma\alpha + NO$

of the Fiat-Shamir transform [22] that we rely on to obtain a digital signature protocol.

The protocol uses a prime characteristic of the form $p = c \cdot 2^e - 1$, where $c$ is a small cofactor and $\log p \approx 2\lambda$. This is already an improvement over existing SQIsign protocols: since such primes are abundant, it is significantly easier to find parameters, especially at higher security levels, for SQIsign2D than for SQIsign. Compared to SQIsignHD, which uses Montgomery-friendly primes $p = c \cdot 2^e \cdot 3^f - 1$, SQIsign2D primes offer even better opportunities for low-level optimisations, as discussed in Section 7.

## 5.1 The $\Sigma$ protocol

**Key generation.** During key generation, we sample a random left ideal $I_{sk}$ of $O_0$ of norm $N_{sk}$ via RandomFixedNormIdeal (Algorithm 4), where $N_{sk}$ is an odd integer of size $4\lambda$. The ideal $I_{sk}$ corresponds to the isogeny $\varphi_{sk}: E_0 \to E_{pk}$ connecting $E_0$ to the public key $E_{pk}$. To be more precise, we compute $E_{pk}$ via IdealTolsogeny.

From a mathematical perspective, the ideal $I_{sk}$ provides enough information to describe the secret isogeny $\varphi_{sk}$. However, in order to speed up the response algorithm, we perform additional computations that are stored as internal optimisations – we colour these lines to describe such computations. These internal optimisations are required to obtain a faster translation from the challenge to its corresponding ideal; we will formalise what we mean with “its corresponding ideal” in the paragraph “Response” below.

The gist of these optimisations is to evaluate a basis $\{\beta_1, \beta_2, \beta_3, \beta_4\}$ of the right order $O_{pk}$ of $I_{sk}$ at the $2^e$-torsion of $E_{pk}$. This is achieved via [11, Alg. 9]. The key-generation procedure is formalised in Algorithm 5.

**Commitment.** The commitment phase is similar to the key-generation computations: as explained above, we first sample a random left ideal $I_{com}$ of $O_0$ of norm $N_{com} = \ell_{com}^n$, for some $n > 0$. In particular, we require $\ell_{com} > 2^{e_{rsp}}$, where $2^{e_{rsp}}$ denotes the largest possible degree of the response isogeny. This condition implies that we can compute the pushforward of any left ideal $I$ of $O_0$ of norm $< 2^{e_{rsp}}$ under $I_{com}$, which is a necessary step in the response computation (see Algorithm 7, Line 9).
**Algorithm 4 RandomFixedNormIdeal**

**Input:** A maximal order $\mathcal{O} \subseteq \mathcal{B}_{p,\infty}$ and an integer $N$ such that $p \nmid N$.

**Output:** A primitive left $\mathcal{O}$-ideal $I$ of norm $N$ sampled uniformly at random.

1: Find $\gamma \in \mathcal{O}$ primitive of norm $NM$ with $\gcd(N, M) = 1$

(▷) Using [30, § 3.3]

2: **repeat**

3: Sample $u_1, \dots, u_4 \in [0; N-1]$ uniformly at random

4: $\alpha \leftarrow \sum_{i=1}^{4} u_i \alpha_i$, where $(\alpha_1, \dots, \alpha_4)$ is a basis of $\mathcal{O}$

5: **until** $\gcd(\text{nrd}(\alpha), N) = 1$

6: Return $I := \mathcal{O}\gamma\alpha + N\mathcal{O}$

of the Fiat-Shamir transform [22] that we rely on to obtain a digital signature protocol.

The protocol uses a prime characteristic of the form $p = c \cdot 2^e - 1$, where $c$ is a small cofactor and $\log p \approx 2\lambda$. This is already an improvement over existing SQIsign protocols: since such primes are abundant, it is significantly easier to find parameters, especially at higher security levels, for SQIsign2D than for SQIsign. Compared to SQIsignHD, which uses Montgomery-friendly primes $p = c \cdot 2^e \cdot 3^f - 1$, SQIsign2D primes offer even better opportunities for low-level optimisations, as discussed in Section 7.

## 5.1 The $\Sigma$ protocol

**Key generation.** During key generation, we sample a random left ideal $I_{sk}$ of $\mathcal{O}_0$ of norm $N_{sk}$ via RandomFixedNormIdeal (Algorithm 4), where $N_{sk}$ is an odd integer of size $4\lambda$. The ideal $I_{sk}$ corresponds to the isogeny $\varphi_{sk}: E_0 \to E_{pk}$ connecting $E_0$ to the public key $E_{pk}$. To be more precise, we compute $E_{pk}$ via IdealTolsogeny.

From a mathematical perspective, the ideal $I_{sk}$ provides enough information to describe the secret isogeny $\varphi_{sk}$. However, in order to speed up the response algorithm, we perform additional computations that are stored as internal optimisations – we colour these lines to describe such computations. These internal optimisations are required to obtain a faster translation from the challenge to its corresponding ideal; we will formalise what we mean with “its corresponding ideal” in the paragraph “Response” below.

The gist of these optimisations is to evaluate a basis $\{\beta_1, \beta_2, \beta_3, \beta_4\}$ of the right order $\mathcal{O}_{pk}$ of $I_{sk}$ at the $2^e$-torsion of $E_{pk}$. This is achieved via [11, Alg. 9]. The key-generation procedure is formalised in Algorithm 5.

**Commitment.** The commitment phase is similar to the key-generation computations: as explained above, we first sample a random left ideal $I_{com}$ of $\mathcal{O}_0$ of norm $N_{com} = \ell_{com}^n$, for some $n > 0$. In particular, we require $\ell_{com} > 2^{e_{rsp}}$, where $2^{e_{rsp}}$ denotes the largest possible degree of the response isogeny. This condition implies that we can compute the pushforward of any left ideal $I$ of $\mathcal{O}_0$ of norm $< 2^{e_{rsp}}$ under $I_{com}$, which is a necessary step in the response computation (see Algorithm 7, Line 9).
**Algorithm 5 Key Generation**

**Output:** The public key $pk = E_{pk}$ and the secret key $sk = I_{sk}$.

1: $I_{sk} \leftarrow \text{RandomFixedNormIdeal}(N_{sk})$

2: $\varphi_{sk}|_{2^e}, E_{pk} \leftarrow \text{IdealTolsogeny}(I_{sk}, P_0, Q_0)$.

3: Compute a deterministic basis $(P_{pk}, Q_{pk})$ of $E_{pk}[2^e]$.

4: Compute a basis $B = (\beta_1, \beta_2, \beta_3, \beta_4)$ of the right order $O_{pk}$ of $I_{pk}$.

5: Compute the basis $(\tilde{\beta}_1, \tilde{\beta}_2, \tilde{\beta}_3, \tilde{\beta}_4)$ of End$(E_{pk})$ corresponding to $B$. (▷) [11, Alg. 9]

6: Compute $\mathcal{B} = \{\tilde{\beta}_i(P_{pk}), \beta_i(Q_{pk})\}_{i=1,...,4}$

7: **return** pk := $E_{pk}$ and sk := $(I_{sk}, \mathcal{B})$

One of the outputs of the Commitment algorithm is the curve $E_{com}$ obtained applying IdealTolsogeny on $I_{com}$. Additionally, the algorithm outputs the internal state $I_{com}$. Similarly to what has been said above, the ideal $I_{com}$ provides enough information to compute the corresponding isogeny $\varphi_{com}: E_0 \to E_{com}$. However, as an internal optimisation, we also extract and store the isogeny representation $\varphi_{com}|_{2^e}$. We summarise everything in Algorithm 6.

**Algorithm 6 Commitment**

**Output:** The commitment curve $E_{com}$, the integer com and the corresponding state $I_{com}$

1: $I_{com} \leftarrow \text{RandomFixedNormIdeal}(N_{com})$.

2: $\varphi_{com}|_{2^e}, E_{com} \leftarrow \text{IdealTolsogeny}(I_{com}, P_0, Q_0)$.

3: **return** com := $E_{com}$ and st := $(I_{com}, \varphi_{com}|_{2^e})$.

**Challenge.** The challenge consists of a positive integer chl < $2^{e_{chl}}$, where $e_{chl}$ is a parameter denoting the size of the challenge space. This integer describes the kernel of the challenge isogeny $\varphi_{chl}: E_{pk} \to E_{chl}$; i.e. $\ker(\varphi_{chl}) = \langle P_{pk} + [chl]Q_{pk} \rangle$.

It is worth noting that, although $\deg(\varphi_{chl}) = 2^e$, the challenge space contains only $2^{e_{chl}} \ll 2^e$ possible challenges, i.e. we only allow $2^{e_{chl}}$ possible kernels. Intuitively, the extra length of $\varphi_{chl}$ is needed to deal with the fact that response isogenies may backtrack with $\varphi_{chl}$. This concept is formalised in Theorem 19.

**Response.** The diagram to keep in mind as we explain the response algorithm is the following one (see Fig. 3), where

- $\varphi_{chl}: E_{pk} \to E_{chl}$ is the isogeny described by the challenge chl;

- $\varphi'_{chl}: E_{pk} \to E_{chl}^0$ is the portion of $\varphi_{chl}$ that does not backtrack with the response isogeny;

- $\varphi_{rsp}^{(1)}: E_{com} \to E'_{chl}$ is the odd part of the response isogeny;

- $\varphi_{rsp}^{(0)}: E'_{chl} \to E_{chl}^0$ is the even, non-backtracking part of the response isogeny;

- $\varphi_{aux}: E_{com} \to E_{aux}$ is the auxiliary isogeny needed to embed the isogeny $\varphi_{rsp}^{(1)}$ into a two-dimensional isogeny;
**Algorithm 5 Key Generation**

**Output:** The public key $pk = E_{pk}$ and the secret key $sk = I_{sk}$.

1: $I_{sk} \leftarrow \text{RandomFixedNormIdeal}(N_{sk})$

2: $\varphi_{sk}|_{2^e}, E_{pk} \leftarrow \text{IdealTolsogeny}(I_{sk}, P_0, Q_0)$.

3: Compute a deterministic basis $(P_{pk}, Q_{pk})$ of $E_{pk}[2^e]$.

4: Compute a basis $B = (\beta_1, \beta_2, \beta_3, \beta_4)$ of the right order $O_{pk}$ of $I_{pk}$.

5: Compute the basis $(\tilde{\beta}_1, \tilde{\beta}_2, \tilde{\beta}_3, \tilde{\beta}_4)$ of $\text{End}(E_{pk})$ corresponding to $B$. (▷) [11, Alg. 9]

6: Compute $\mathcal{B} = \{\tilde{\beta}_i(P_{pk}), \beta_i(Q_{pk})\}_{i=1,...,4}$

7: **return** pk := $E_{pk}$ and sk := $(I_{sk}, \mathcal{B})$

One of the outputs of the Commitment algorithm is the curve $E_{com}$ obtained applying IdealTolsogeny on $I_{com}$. Additionally, the algorithm outputs the internal state $I_{com}$. Similarly to what has been said above, the ideal $I_{com}$ provides enough information to compute the corresponding isogeny $\varphi_{com}: E_0 \to E_{com}$. However, as an internal optimisation, we also extract and store the isogeny representation $\varphi_{com}|_{2^e}$. We summarise everything in Algorithm 6.

**Algorithm 6 Commitment**

**Output:** The commitment curve $E_{com}$, the integer com and the corresponding state $I_{com}$

1: $I_{com} \leftarrow \text{RandomFixedNormIdeal}(N_{com})$.

2: $\varphi_{com}|_{2^e}, E_{com} \leftarrow \text{IdealTolsogeny}(I_{com}, P_0, Q_0)$.

3: **return** com := $E_{com}$ and st := $(I_{com}, \varphi_{com}|_{2^e})$.

**Challenge.** The challenge consists of a positive integer chl < $2^{e_{chl}}$, where $e_{chl}$ is a parameter denoting the size of the challenge space. This integer describes the kernel of the challenge isogeny $\varphi_{chl}: E_{pk} \to E_{chl}$; i.e. $\ker(\varphi_{chl}) = \langle P_{pk} + [chl]Q_{pk} \rangle$.

It is worth noting that, although $\deg(\varphi_{chl}) = 2^e$, the challenge space contains only $2^{e_{chl}} \ll 2^e$ possible challenges, i.e. we only allow $2^{e_{chl}}$ possible kernels. Intuitively, the extra length of $\varphi_{chl}$ is needed to deal with the fact that response isogenies may backtrack with $\varphi_{chl}$. This concept is formalised in Theorem 19.

**Response.** The diagram to keep in mind as we explain the response algorithm is the following one (see Fig. 3), where

- $\varphi_{chl}: E_{pk} \to E_{chl}$ is the isogeny described by the challenge chl;

- $\varphi'_{chl}: E_{pk} \to E_{chl}^0$ is the portion of $\varphi_{chl}$ that does not backtrack with the response isogeny;

- $\varphi_{rsp}^{(1)}: E_{com} \to E'_{chl}$ is the odd part of the response isogeny;

- $\varphi_{rsp}^{(0)}: E'_{chl} \to E_{chl}^0$ is the even, non-backtracking part of the response isogeny;

- $\varphi_{aux}: E_{com} \to E_{aux}$ is the auxiliary isogeny needed to embed the isogeny $\varphi_{rsp}^{(1)}$ into a two-dimensional isogeny;
<figure><img src="image_4.png" /><figcaption>Fig. 3. Response diagram.</figcaption></figure>

- $\varphi'_{\text{aux}}: E'_{\text{chl}} \to E'_{\text{aux}}$ is the pushforward of $\varphi_{\text{aux}}$ under $\varphi^{(1)}_{\text{rsp}}$.

The first step is to compute the ideal $I_{\text{chl}}$ corresponding to the isogeny $\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$ with kernel $\langle P_{\text{pk}} + [\text{chl}]Q_{\text{pk}} \rangle$. This is done via [11, Alg. 9] using the datum $\mathcal{B} = \{\tilde{\beta}_i(P_{\text{pk}}), \tilde{\beta}_i(Q_{\text{pk}})\}_{i=1,\dots,4}$ computed during Key Generation (see Algorithm 5).

The ideal $I_{\text{chl}}$ is then employed to compute an isogeny $\varphi_{\text{rsp}}: E_{\text{com}} \to E_{\text{chl}}$. To be more precise, the prover first computes an ideal $I_{\text{rsp}}$, equivalent to $\overline{I_{\text{com}} \cdot I_{\text{sk}} \cdot I_{\text{chl}}}$, which is uniformly distributed among the equivalent ideals of norm $< 2^{e_{\text{rsp}}}$, The protocol parameter $e_{\text{rsp}}$ is chosen such that the existence of $I_{\text{rsp}}$ (or equivalently a connecting isogeny of degree $< 2^{e_{\text{rsp}}}$ between $E_{\text{com}}$ and $E_{\text{chl}}$) is guaranteed, which means that $2^{e_{\text{rsp}}}$ must be larger than $2\sqrt{2p}/\pi$. The norm of $I_{\text{rsp}}$ must be bounded by $2^{e_{\text{rsp}}}$ so that we can represent $\varphi_{\text{rsp}}: E_{\text{com}} \to E_{\text{chl}}$ via a $(2^{e_{\text{rsp}}}, 2^{e_{\text{rsp}}})$-isogeny. In particular, following Kani's Lemma (Theorem 4), the degree of the one-dimensional isogenies represented by such a two-dimensional isogeny must be odd, but this might not be the case for $\varphi_{\text{rsp}}$. We now explain how to deal with the case of even-degree.

Let us write the norm of $I_{\text{rsp}}$ as $n(I_{\text{rsp}}) = q = 2^n q' < 2^{e_{\text{rsp}}}$ for an odd $q'$. We can think of $\varphi_{\text{rsp}}$ as $\varphi_{\text{rsp}} = \psi \circ \varphi_{\text{rsp}}^{(1)}: E_{\text{com}} \to E'_{\text{chl}} \to E_{\text{chl}}$, where $\deg(\varphi_{\text{rsp}}^{(1)}) = q'$ and $\deg(\psi) = 2^n$. It may happen that $\ker(\tilde{\psi}) \cap \ker(\tilde{\varphi}_{\text{chl}})$ is not trivial. Let $n_{\text{bt}}$ be the positive integer such that $2^{n_{\text{bt}}} = \# \ker(\tilde{\psi}) \cap \ker(\tilde{\varphi}_{\text{chl}})$. Equivalently, $n_{\text{bt}}$ is the largest integer such that $I_{\text{chl}} \cdot \overline{I_{\text{rsp}}} \in 2^{n_{\text{bt}}} \mathcal{O}_{\text{chl}}$, where $\mathcal{O}_{\text{chl}}$ is the right order of $I_{\text{chl}}$.

Let $r' := n - n_{\text{bt}}$ and define $\varphi_{\text{rsp}}^{(0)}: E'_{\text{chl}} \to E_{\text{chl}}^{0}$ to be the isogeny with kernel $\ker(\psi)[2^{r'}] - \text{the isogeny } \varphi_{\text{rsp}}^{(0)} \text{ coincides with the non-backtrack portion of } \varphi_{\text{rsp}}$. Now, let us factor $I_{\text{rsp}}$ as $I_{\text{rsp}}^{1} \cdot I_{\text{rsp}}^{0} \cdot I'$, where $n(I_{\text{rsp}}^{(1)}) = q'$ and $n(I_{\text{rsp}}^{(0)}) = 2^{r'}$. The isogenies $\varphi_{\text{rsp}}^{(1)}$ and $\varphi_{\text{rsp}}^{(0)}$ correspond to $I_{\text{rsp}}^{(1)}$ and $I_{\text{rsp}}^{(0)}$, respectively.

Since $\varphi_{\text{rsp}}^{(1)}$ has odd degree, it can be represented via a $(2^{e_{\text{rsp}}-n}, 2^{e_{\text{rsp}}-n})$-isogeny via Kani's Lemma. This requires computing an auxiliary isogeny $\varphi'_{\text{aux}}: E'_{\text{chl}} \to E'_{\text{aux}}$ of degree $2^{e_{\text{rsp}}-n} - q'$.
<figure><img src="image_6.png" /><figcaption>Fig. 3. Response diagram.</figcaption></figure>

$\varphi'_{\text{aux}}: E'_{\text{chl}} \to E'_{\text{aux}}$ is the pushforward of $\varphi_{\text{aux}}$ under $\varphi^{(1)}_{\text{rsp}}$.

The first step is to compute the ideal $I_{\text{chl}}$ corresponding to the isogeny $\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$ with kernel $\langle P_{\text{pk}} + [\text{chl}]Q_{\text{pk}} \rangle$. This is done via [11, Alg. 9] using the datum $\mathcal{B} = \{\tilde{\beta}_i(P_{\text{pk}}), \tilde{\beta}_i(Q_{\text{pk}})\}_{i=1,\dots,4}$ computed during Key Generation (see Algorithm 5).

The ideal $I_{\text{chl}}$ is then employed to compute an isogeny $\varphi_{\text{rsp}}: E_{\text{com}} \to E_{\text{chl}}$. To be more precise, the prover first computes an ideal $I_{\text{rsp}}$, equivalent to $\overline{I_{\text{com}} \cdot I_{\text{sk}} \cdot I_{\text{chl}}}$, which is uniformly distributed among the equivalent ideals of norm $< 2^{e_{\text{rsp}}}$.
The protocol parameter $e_{\text{rsp}}$ is chosen such that the existence of $I_{\text{rsp}}$ (or equivalently a connecting isogeny of degree $< 2^{e_{\text{rsp}}}$ between $E_{\text{com}}$ and $E_{\text{chl}}$) is guaranteed, which means that $2^{e_{\text{rsp}}}$ must be larger than $2\sqrt{2p}/\pi$. The norm of $I_{\text{rsp}}$ must be bounded by $2^{e_{\text{rsp}}}$ so that we can represent $\varphi_{\text{rsp}}: E_{\text{com}} \to E_{\text{chl}}$ via a $(2^{e_{\text{rsp}}}, 2^{e_{\text{rsp}}})$-isogeny. In particular, following Kani's Lemma (Theorem 4), the degree of the one-dimensional isogenies represented by such a two-dimensional isogeny must be odd, but this might not be the case for $\varphi_{\text{rsp}}$. We now explain how to deal with the case of even-degree.

Let us write the norm of $I_{\text{rsp}}$ as $n(I_{\text{rsp}}) = q = 2^n q' < 2^{e_{\text{rsp}}}$ for an odd $q'$. We can think of $\varphi_{\text{rsp}}$ as $\varphi_{\text{rsp}} = \psi \circ \varphi_{\text{rsp}}^{(1)}: E_{\text{com}} \to E'_{\text{chl}} \to E_{\text{chl}}$, where $\deg(\varphi_{\text{rsp}}^{(1)}) = q'$ and $\deg(\psi) = 2^n$. It may happen that $\ker(\tilde{\psi}) \cap \ker(\tilde{\varphi}_{\text{chl}})$ is not trivial. Let $n_{\text{bt}}$ be the positive integer such that $2^{n_{\text{bt}}} = \# \ker(\tilde{\psi}) \cap \ker(\tilde{\varphi}_{\text{chl}})$. Equivalently, $n_{\text{bt}}$ is the largest integer such that $I_{\text{chl}} \cdot \overline{I_{\text{rsp}}} \in 2^{n_{\text{bt}}} \mathcal{O}_{\text{chl}}$, where $\mathcal{O}_{\text{chl}}$ is the right order of $I_{\text{chl}}$.

Let $r' := n - n_{\text{bt}}$ and define $\varphi_{\text{rsp}}^{(0)}: E'_{\text{chl}} \to E_{\text{chl}}^{0}$ to be the isogeny with kernel $\ker(\psi)[2^{r'}] - \text{the isogeny } \varphi_{\text{rsp}}^{(0)} \text{ coincides with the non-backtrack portion of } \varphi_{\text{rsp}}$. Now, let us factor $I_{\text{rsp}}$ as $I_{\text{rsp}}^{1} \cdot I_{\text{rsp}}^{0} \cdot I'$, where $n(I_{\text{rsp}}^{(1)}) = q'$ and $n(I_{\text{rsp}}^{(0)}) = 2^{r'}$. The isogenies $\varphi_{\text{rsp}}^{(1)}$ and $\varphi_{\text{rsp}}^{(0)}$ correspond to $I_{\text{rsp}}^{(1)}$ and $I_{\text{rsp}}^{(0)}$, respectively.

Since $\varphi_{\text{rsp}}^{(1)}$ has odd degree, it can be represented via a $(2^{e_{\text{rsp}}-n}, 2^{e_{\text{rsp}}-n})$-isogeny via Kani's Lemma. This requires computing an auxiliary isogeny $\varphi'_{\text{aux}}: E'_{\text{chl}} \to E'_{\text{aux}}$ of degree $2^{e_{\text{rsp}}-n} - q'$.
As required in Theorem 24, we need the isogeny $\varphi'_{aux} : E'_{chl} \to E'_{aux}$ to be uniformly sampled among all the isogenies of degree $2^{e_{rsp}-n} - q'$. Hence, the prover samples a random left ideal $I''_{aux}$ of $\mathcal{O}_0$ of norm $2^{e_{rsp}-n} - q'$ and then computes $I'_{aux}$ as the pushforward $I'_{aux}$ of $I''_{aux}$ through $I_{com} \cdot I_{rsp}^{(1)}$. The prover can then evaluate $\varphi'_{aux} \circ \varphi_{rsp}^{(1)} \circ \varphi_{com}$ at the $2^e$-torsion running IdealTolsogeny on input $I_{com} \cdot I_{rsp}^{(1)} \cdot I'_{aux}$.

Using the datum $\varphi_{com}|_{2^e}$, the prover has actually access to $\varphi'_{aux} \circ \varphi_{rsp}^{(1)}|_{2^e}$.

While a representation of $\varphi'_{aux} \circ \varphi_{rsp}^{(1)}$ could act as a valid response, we want the $\Sigma$ protocol to be commitment recoverable, i.e. it is possible to recompute the commitment curve from a challenge and corresponding response. This eventually leads to a more compact signature. To achieve such a property, we want the isogeny connecting $E_{aux}$ and $E'_{chl}$, passing through $E_{com}$. Thus, the prover has to compute the isogeny $\varphi_{aux} : E_0 \to E_{aux}$ of degree $2^{e_{rsp}-n} - q'$ fitting in the following commutative diagram:

<figure><img src="image_5.png" /></figure>

Such an isogeny can be obtained as one of the components of the $(2^{e_{rsp}-n}, 2^{e_{rsp}-n})$-isogeny $\Phi$ with kernel $\{([q']'P, \varphi'_{aux} \circ \varphi_{rsp}^{(1)}(P)) \mid P \in E_{com}[2^{e_{rsp}-n}]\}$:

$$ \Phi = \left( \begin{array}{cc} \varphi_{rsp}^{(1)} & -\varphi'_{aux} \\ \varphi_{aux} & \varphi \end{array} \right) : E_{com} \times E'_{aux} \to E'_{chl} \times E_{aux}. $$

To complete the response algorithm, we still need to compute the non-backtracking part of the response isogeny. Let $\varphi_{rsp}^{(0)} : E'_{chl} \to E_{chl}^0$ be such an isogeny, which indeed corresponds to the ideal $I_{rsp}^0$.

Let $\varphi'_{chl} : E_{pk} \to E_{chl}^0$ be the isogeny with kernel $\langle [2^{n_{bt}}](P_{pk} + [chl]Q_{pk}) \rangle$. In other words, $\varphi'_{chl}$ is the portion of $\varphi_{chl}$ that does not backtrack with the response isogeny. Even though $\varphi'_{chl}$ and $\varphi_{rsp}^{(0)}$ map onto the same elliptic curve, the curves obtained after an explicit computation of the two isogenies will only be equal up to isomorphism. Thus, the prover additionally has to compute an explicit isomorphism to let the two curves agree.

The explicit computation of the isomorphism between the codomains of $\varphi'_{chl}$ and $\varphi_{rsp}^{(0)}$ is required to facilitate the verification. During the verification, the verifier will not compute $\varphi_{chl}$ but rather compute its non-backtrack portion, i.e. the verifier will only compute the isogeny with kernel $\langle [2^{n_{bt}}](P_{pk} + [chl]Q_{pk}) \rangle$.

Let $\{P_{aux}, Q_{aux}\}$ be a deterministic basis of $E_{aux}[2^{e_{rsp}-n_{bt}}]$ and define

$$ P_{chl} := [2^{e_{rsp}-n} - q']^{-1} \varphi_{rsp}^{(0)} \circ \varphi_{rsp}^{(1)}(P_{aux}), \quad Q_{chl} := [2^{e_{rsp}-n} - q']^{-1} \varphi_{rsp}^{(0)} \circ \varphi_{rsp}^{(1)}(Q_{aux}). $$
As required in Theorem 24, we need the isogeny $\varphi'_{aux}: E'_{chl} \to E'_{aux}$ to be uniformly sampled among all the isogenies of degree $2^{e_{rsp}-n} - q'$. Hence, the prover samples a random left ideal $I''_{aux}$ of $\mathcal{O}_0$ of norm $2^{e_{rsp}-n} - q'$ and then computes $I'_{aux}$ as the pushforward $I'_{aux}$ of $I''_{aux}$ through $I_{com} \cdot I_{rsp}^{(1)}$. The prover can then evaluate $\varphi'_{aux} \circ \varphi_{rsp}^{(1)} \circ \varphi_{com}$ at the $2^e$-torsion running IdealTolsogeny on input $I_{com} \cdot I_{rsp}^{(1)} \cdot I'_{aux}$.

Using the datum $\varphi_{com}|_{2^e}$, the prover has actually access to $\varphi'_{aux} \circ \varphi_{rsp}^{(1)}|_{2^e}$.

While a representation of $\varphi'_{aux} \circ \varphi_{rsp}^{(1)}$ could act as a valid response, we want the $\Sigma$ protocol to be commitment recoverable, i.e. it is possible to recompute the commitment curve from a challenge and corresponding response. This eventually leads to a more compact signature. To achieve such a property, we want the isogeny connecting $E_{aux}$ and $E'_{chl}$, passing through $E_{com}$. Thus, the prover has to compute the isogeny $\varphi_{aux}: E_0 \to E_{aux}$ of degree $2^{e_{rsp}-n} - q'$ fitting in the following commutative diagram:

<figure><img src="image_7.png" /></figure>

Such an isogeny can be obtained as one of the components of the $(2^{e_{rsp}-n}, 2^{e_{rsp}-n})$-isogeny $\Phi$ with kernel $\{([q']'P, \varphi'_{aux} \circ \varphi_{rsp}^{(1)}(P)) | P \in E_{com}[2^{e_{rsp}-n}]\}$:

$$ \Phi = \left( \begin{array}{cc} \varphi_{rsp}^{(1)} & -\varphi'_{aux} \\ \varphi_{aux} & \varphi \end{array} \right) : E_{com} \times E'_{aux} \to E'_{chl} \times E_{aux}. $$

To complete the response algorithm, we still need to compute the non-backtracking part of the response isogeny. Let $\varphi_{rsp}^{(0)}: E'_{chl} \to E_0^{(0)}$ be such an isogeny, which indeed corresponds to the ideal $I_{rsp}^{(0)}$.

Let $\varphi'_{chl}: E_{pk} \to E_0^{(0)}$ be the isogeny with kernel $\langle [2^{n_{bt}}](P_{pk} + [chl]Q_{pk}) \rangle$. In other words, $\varphi'_{chl}$ is the portion of $\varphi_{chl}$ that does not backtrack with the response isogeny. Even though $\varphi'_{chl}$ and $\varphi_{rsp}^{(0)}$ map onto the same elliptic curve, the curves obtained after an explicit computation of the two isogenies will only be equal up to isomorphism. Thus, the prover additionally has to compute an explicit isomorphism to let the two curves agree.

The explicit computation of the isomorphism between the codomains of $\varphi'_{chl}$ and $\varphi_{rsp}^{(0)}$ is required to facilitate the verification. During the verification, the verifier will not compute $\varphi_{chl}$ but rather compute its non-backtrack portion, i.e. the verifier will only compute the isogeny with kernel $\langle [2^{n_{bt}}](P_{pk} + [chl]Q_{pk}) \rangle$.

Let $\{P_{aux}, Q_{aux}\}$ be a deterministic basis of $E_{aux}[2^{e_{rsp}-n_{bt}}]$ and define

$$ P_{chl} := [2^{e_{rsp}-n} - q']^{-1} \varphi_{rsp}^{(0)} \circ \varphi_{rsp}^{(1)}(P_{aux}), \quad Q_{chl} := [2^{e_{rsp}-n} - q']^{-1} \varphi_{rsp}^{(0)} \circ \varphi_{rsp}^{(1)}(Q_{aux}). $$
The output of the response algorithm consists in $(E_{\text{aux}}, P_{\text{chl}}, Q_{\text{chl}}, r', n_{\text{bt}})$. We collect what has been explained in this paragraph in Algorithm 7.

**Algorithm 7 Response**

**Input:** The public key $E_{\text{pk}}$, the secret key $I_{\text{sk}}$, $\mathcal{B}$, the commitment $(E_{\text{com}}, \text{com})$, the commitment state $I_{\text{com}}$, $\varphi_{\text{com}}(P_0)$, $\varphi_{\text{com}}(Q_0)$, and the challenge $\text{chl} < 2^{e_{\text{chl}}}$.

**Output:** $E_{\text{aux}}$, $P_{\text{aux}}$, $Q_{\text{aux}}$, $r'$, $n_{\text{bt}}$

1: Compute a deterministic basis $(P_{\text{pk}}, Q_{\text{pk}})$ of $E_{\text{pk}}[2^e]$.

2: Compute the ideal $I_{\text{chl}}$ from $\text{chl}$ and using $\mathcal{B}$. (▷) [11, Alg. 9]
$\varphi_{\text{chl}}: E_{\text{pk}} \rightarrow E_{\text{chl}}$ is the isogeny with kernel $\langle P_{\text{pk}} + [\text{chl}]Q_{\text{pk}} \rangle$.

3: Set $J = \overline{I_{\text{com}}} \cdot I_{\text{sk}} \cdot I_{\text{chl}}$.

4: Compute a uniformly distributed ideal $I_{\text{rsp}}$ to $J$ of norm $q < 2^{e_{\text{rsp}}}$.

5: Compute $n$ such that $q = q' \cdot 2^n$, where $q'$ is odd and $n_{\text{bt}} < n$ as the largest integer such that $I_{\text{chl}} \cdot \overline{I_{\text{rsp}}} \in 2^{n_{\text{bt}}} \mathcal{O}_{\text{chl}}$.

// $n_{\text{bt}}$ is the length of the part of the response that backtracks along the challenge isogeny

6: $r' \leftarrow n - n_{\text{bt}}$.

7: Factor $I_{\text{rsp}}$ as $I_{\text{rsp}}^{1} \cdot I_{\text{rsp}}^{0} \cdot I'$ where $n(I_{\text{rsp}}^{(1)}) = q'$ and $n(I_{\text{rsp}}^{(0)}) = 2^{r'}$.

// $I_{\text{rsp}}^{(1)}$ is the ideal corresponding to the odd part of the response isogeny $\varphi_{\text{rsp}}^{(1)}: E_{\text{com}} \rightarrow E'_{\text{chl}}$ and $I_{\text{rsp}}^{(0)}$ is the ideal corresponding to the even part of the response isogeny $\varphi_{\text{rsp}}^{(0)}: E'_{\text{chl}} \rightarrow E_{\text{chl}}$.

8: $I''_{\text{aux}} \leftarrow \text{RandomFixedNormIdeal}(2^{e_{\text{rsp}}-n} - q')$.

9: Compute $I'_{\text{aux}}$ as the pushforward of $I''_{\text{aux}}$ through $I_{\text{com}} \cdot I_{\text{rsp}}^{(1)}$.

// $I'_{\text{aux}}$ is the ideal corresponding to an auxiliary isogeny $\varphi'_{\text{aux}}: E'_{\text{chl}} \rightarrow E_{\text{aux}}$.

10: $\varphi'_{\text{aux}} \circ \varphi_{\text{rsp}}^{(1)} \circ \varphi_{\text{com}} \mid_{2^e}, E'_{\text{aux}} \leftarrow \text{IdealTolsogeny}(I_{\text{com}} \cdot I_{\text{rsp}}^{(1)} \cdot I'_{\text{aux}})$.

11: $P_{\text{com}}^{0}, Q_{\text{com}}^{0} \leftarrow [2^{e-(e_{\text{rsp}}-n)}]\varphi_{\text{com}}(P_0), [2^{e-(e_{\text{rsp}}-n)}]\varphi_{\text{com}}(Q_0)$.

12: $P_{\text{aux}}^{0}, Q_{\text{aux}}^{0} \leftarrow [2^{e-(e_{\text{rsp}}-n)}]\varphi'_{\text{aux}} \circ \varphi_{\text{rsp}}^{(1)} \circ \varphi_{\text{com}}(P_0), [2^{e-(e_{\text{rsp}}-n)}]\varphi'_{\text{aux}} \circ \varphi_{\text{rsp}}^{(1)} \circ \varphi_{\text{com}}(Q_0)$.

13: Compute $\Phi' : E_{\text{com}} \times E'_{\text{aux}} \rightarrow E'_{\text{chl}} \times E_{\text{aux}}$ with kernel $\langle ([q']P_{\text{com}}^{0}, P_{\text{aux}}^{0}), ([q']Q_{\text{com}}^{0}, Q_{\text{aux}}^{0}) \rangle$

14: $(\tilde{P}_{\text{chl}}, \tilde{P}_{\text{aux}}) \leftarrow \Phi'(\varphi_{\text{com}}(P_0), 0)$.

15: $(\tilde{Q}_{\text{chl}}, \tilde{Q}_{\text{aux}}) \leftarrow \Phi'(\varphi_{\text{com}}(Q_0), 0)$.

16: $E_{\text{chl}}^{0} \leftarrow E'_{\text{chl}}$.

17: **if** $r' > 0$ **then**

18: Compute the isogeny $\varphi_{\text{rsp}}^{0} : E'_{\text{chl}} \rightarrow E_{\text{chl}}^{0}$ corresponding to $I_{\text{rsp}}^{0}$.

19: $\tilde{P}_{\text{chl}}, \tilde{Q}_{\text{chl}} \leftarrow \varphi_{\text{rsp}}^{0}(\tilde{P}_{\text{chl}}), \varphi_{\text{rsp}}^{0}(\tilde{Q}_{\text{chl}})$.

20: Compute $\varphi'_{\text{chl}} : E_{\text{pk}} \rightarrow (E_{\text{chl}}^{0})'$ of kernel $\langle [2^{n_{\text{bt}}}] (P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}) \rangle$.

21: Compute the isomorphism $\iota_{\text{chl}} : E_{\text{chl}}^{0} \rightarrow (E_{\text{chl}}^{0})'$.

22: $\tilde{P}_{\text{chl}}, \tilde{Q}_{\text{chl}} \leftarrow \iota_{\text{chl}}(\tilde{P}_{\text{chl}}, \iota_{\text{chl}}(\tilde{Q}_{\text{chl}}))$.

23: Compute a deterministic basis $(P_{\text{aux}}, Q_{\text{aux}})$ of $E_{\text{aux}}[2^{e_{\text{rsp}}-n_{\text{bt}}}]$.

24: Compute $a, b, c, d \in \mathbb{Z}/2^{e_{\text{rsp}}-n_{\text{bt}}}/\mathbb{Z}$ such that
$$P_{\text{aux}} = [2^{e-e_{\text{rsp}}+n_{\text{bt}}} \mid [a]\tilde{P}_{\text{aux}} + [b]\tilde{Q}_{\text{aux}} \mid [c]\tilde{P}_{\text{aux}} + [d]\tilde{Q}_{\text{aux}}) \text{ and } Q_{\text{aux}} = [2^{e-e_{\text{rsp}}+n_{\text{bt}}} \mid [c]\tilde{P}_{\text{aux}} + [d]\tilde{Q}_{\text{aux}})$$

25: $P_{\text{chl}}, Q_{\text{chl}} \leftarrow [2^{e-e_{\text{rsp}}+n_{\text{bt}}} \mid [a]\tilde{P}_{\text{chl}} + [b]\tilde{Q}_{\text{chl}}), [2^{e-e_{\text{rsp}}+n_{\text{bt}}} \mid [c]\tilde{P}_{\text{chl}} + [d]\tilde{Q}_{\text{chl}})$

26: **return** $E_{\text{aux}}$, $P_{\text{chl}}$, $Q_{\text{chl}}$, $r'$, $n_{\text{bt}}$.

**Verification.** On input $(E_{\text{aux}}, P_{\text{chl}}, Q_{\text{chl}}, r', n_{\text{bt}})$, the verifier first computes the isogeny $\varphi_{\text{chl}}: E_0 \rightarrow E_{\text{chl}}$ with kernel $\langle [2^{n_{\text{bt}}}] (P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}) \rangle$ – this corresponds to
The output of the response algorithm consists in $(E_{\text{aux}}, P_{\text{chl}}, Q_{\text{chl}}, r', n_{\text{bt}})$. We collect what has been explained in this paragraph in Algorithm 7.

**Algorithm 7 Response**

**Input:** The public key $E_{\text{pk}}$, the secret key $I_{\text{sk}}$, $\mathcal{B}$, the commitment $(E_{\text{com}}, \text{com})$, the commitment state $I_{\text{com}}, \varphi_{\text{com}}(P_0), \varphi_{\text{com}}(Q_0)$, and the challenge $\text{chl} < 2^{e_{\text{chl}}}$.

**Output:** $E_{\text{aux}}, P_{\text{aux}}, Q_{\text{aux}}, r', n_{\text{bt}}$

1: Compute a deterministic basis $(P_{\text{pk}}, Q_{\text{pk}})$ of $E_{\text{pk}}[2^e]$.

2: Compute the ideal $I_{\text{chl}}$ from $\text{chl}$ and using $\mathcal{B}$. (▷) [11, Alg. 9]

$\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$ is the isogeny with kernel $\langle P_{\text{pk}} + [\text{chl}]Q_{\text{pk}} \rangle$.

3: Set $J = \overline{I_{\text{com}}} \cdot I_{\text{sk}} \cdot I_{\text{chl}}$.

4: Compute a uniformly distributed ideal $I_{\text{rsp}}$ to $J$ of norm $q < 2^{e_{\text{rsp}}}$.

5: Compute $n$ such that $q = q' \cdot 2^n$, where $q'$ is odd and $n_{\text{bt}} < n$ as the largest integer such that $I_{\text{chl}} \cdot \overline{I_{\text{rsp}}} \in 2^{n_{\text{bt}}} \mathcal{O}_{\text{chl}}$.

// $n_{\text{bt}}$ is the length of the part of the response that backtracks along the challenge isogeny

6: $r' \leftarrow n - n_{\text{bt}}$.

7: Factor $I_{\text{rsp}}$ as $I_{\text{rsp}}^{1} \cdot I_{\text{rsp}}^{0} \cdot I'$ where $n(I_{\text{rsp}}^{(1)}) = q'$ and $n(I_{\text{rsp}}^{(0)}) = 2^{r'}$.

// $I_{\text{rsp}}^{(1)}$ is the ideal corresponding to the odd part of the response isogeny $\varphi_{\text{rsp}}^{(1)}: E_{\text{com}} \to E'_{\text{chl}}$ and $I_{\text{rsp}}^{(0)}$ is the ideal corresponding to the even part of the response isogeny $\varphi_{\text{rsp}}^{(0)}: E'_{\text{chl}} \to E_{\text{chl}}$.

8: $I''_{\text{aux}} \leftarrow \text{RandomFixedNormIdeal}(2^{e_{\text{rsp}}-n} - q')$.

9: Compute $I'_{\text{aux}}$ as the pushforward of $I''_{\text{aux}}$ through $I_{\text{com}} \cdot I_{\text{rsp}}^{(1)}$.

// $I'_{\text{aux}}$ is the ideal corresponding to an auxiliary isogeny $\varphi'_{\text{aux}}: E'_{\text{chl}} \to E_{\text{aux}}$.

10: $\varphi'_{\text{aux}} \circ \varphi_{\text{rsp}}^{(1)} \circ \varphi_{\text{com}} \mid_{2^e} : E'_{\text{aux}} \leftarrow \text{IdealTolsogeny}(I_{\text{com}} \cdot I_{\text{rsp}}^{(1)} \cdot I'_{\text{aux}})$.

11: $P_{\text{com}}^{0}, Q_{\text{com}}^{0} \leftarrow [2^{e-(e_{\text{rsp}}-n)}]\varphi_{\text{com}}(P_0), [2^{e-(e_{\text{rsp}}-n)}]\varphi_{\text{com}}(Q_0)$.

12: $P_{\text{aux}}^{0}, Q_{\text{aux}}^{0} \leftarrow [2^{e-(e_{\text{rsp}}-n)}]\varphi'_{\text{aux}} \circ \varphi_{\text{rsp}}^{(1)} \circ \varphi_{\text{com}}(P_0), [2^{e-(e_{\text{rsp}}-n)}]\varphi'_{\text{aux}} \circ \varphi_{\text{rsp}}^{(1)} \circ \varphi_{\text{com}}(Q_0)$.

13: Compute $\Phi' : E_{\text{com}} \times E'_{\text{aux}} \to E'_{\text{chl}} \times E_{\text{aux}}$ with kernel $\langle ([q']P_{\text{com}}^{0}, P_{\text{aux}}^{0}), ([q']Q_{\text{com}}^{0}, Q_{\text{aux}}^{0}) \rangle$

14: $(\tilde{P}_{\text{chl}}, \tilde{P}_{\text{aux}}) \leftarrow \Phi'(\varphi_{\text{com}}(P_0), 0)$.

15: $(\tilde{Q}_{\text{chl}}, \tilde{Q}_{\text{aux}}) \leftarrow \Phi'(\varphi_{\text{com}}(Q_0), 0)$.

16: $E_{\text{chl}}^{0} \leftarrow E'_{\text{chl}}$.

17: **if** $r' > 0$ **then**

18: Compute the isogeny $\varphi_{\text{rsp}}^{0} : E'_{\text{chl}} \to E_{\text{chl}}^{0}$ corresponding to $I_{\text{rsp}}^{0}$.

19: $\tilde{P}_{\text{chl}}, \tilde{Q}_{\text{chl}} \leftarrow \varphi_{\text{rsp}}^{0}(\tilde{P}_{\text{chl}}), \varphi_{\text{rsp}}^{0}(\tilde{Q}_{\text{chl}})$.

20: Compute $\varphi'_{\text{chl}} : E_{\text{pk}} \to (E_{\text{chl}}^{0})'$ of kernel $\langle [2^{n_{\text{bt}}}] (P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}) \rangle$.

21: Compute the isomorphism $\iota_{\text{chl}} : E_{\text{chl}}^{0} \to (E_{\text{chl}}^{0})'$.

22: $\tilde{P}_{\text{chl}}, \tilde{Q}_{\text{chl}} \leftarrow \iota_{\text{chl}}(\tilde{P}_{\text{chl}}, \iota_{\text{chl}}(\tilde{Q}_{\text{chl}}))$.

23: Compute a deterministic basis $(P_{\text{aux}}, Q_{\text{aux}})$ of $E_{\text{aux}}[2^{e_{\text{rsp}}-n_{\text{bt}}}]$.

24: Compute $a, b, c, d \in \mathbb{Z}/2^{e_{\text{rsp}}-n_{\text{bt}}}\mathbb{Z}$ such that

$$P_{\text{aux}} = [2^{e-e_{\text{rsp}}+n_{\text{bt}}} \mid [a]\tilde{P}_{\text{aux}} + [b]\tilde{Q}_{\text{aux}} \mid \text{ and } Q_{\text{aux}} = [2^{e-e_{\text{rsp}}+n_{\text{bt}}} \mid [c]\tilde{P}_{\text{aux}} + [d]\tilde{Q}_{\text{aux}}]$$

25: $P_{\text{chl}}, Q_{\text{chl}} \leftarrow [2^{e-e_{\text{rsp}}+n_{\text{bt}}} \mid [a]\tilde{P}_{\text{chl}} + [b]\tilde{Q}_{\text{chl}}], [2^{e-e_{\text{rsp}}+n_{\text{bt}}} \mid [c]\tilde{P}_{\text{chl}} + [d]\tilde{Q}_{\text{chl}}]$

26: **return** $E_{\text{aux}}, P_{\text{chl}}, Q_{\text{chl}}, r', n_{\text{bt}}$.

**Verification.** On input $(E_{\text{aux}}, P_{\text{chl}}, Q_{\text{chl}}, r', n_{\text{bt}})$, the verifier first computes the isogeny $\varphi_{\text{chl}}: E_0 \to E_{\text{chl}}$ with kernel $\langle [2^{n_{\text{bt}}}] (P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}) \rangle$ – this corresponds to
the non-backtrack portion of the challenge isogeny as in the previous paragraph. Additionally, they compute ($P_{aux}$, $Q_{aux}$), a deterministic basis of $E_{aux}$ [$2^{e_{rsp}-n_{bt}}$]

If $r' > 0$, it means that the prover has chosen a response isogeny having an even, non-backtrack component. In this case, [$2^{e_{rsp}-r'-n_{bt}}$] $P_{chl}$ and [$2^{e_{rsp}-r'-n_{bt}}$] $Q_{chl}$ are linearly dependent, and [$2^{e_{rsp}-r'-n_{bt}}$] $P_{chl}$, [$2^{e_{rsp}-r'-n_{bt}}$] $Q_{chl}$ is the kernel of the dual of the isogeny $\varphi_{rsp}^{(0)}$ (Cfr. Fig. 3). The verifier then computes the isogeny $\varphi: E_{chl} \to E'_{chl}$ with kernel [$2^{e_{rsp}-r'-n_{bt}}$] $P_{chl}$, [$2^{e_{rsp}-r'-n_{bt}}$] $Q_{chl}$ and updates $E_{chl} \leftarrow E'_{chl}$, $P_{chl} \leftarrow \varphi(P_{chl})$ and $Q_{chl} \leftarrow \varphi(Q_{chl})$.

From Kani's Lemma, it follows that the isogeny $\Phi$ with kernel

$$ \langle (P_{chl}, [2^{r'}]P_{aux}), (Q_{chl}, [2^{r'}]Q_{aux}) \rangle $$

maps $E'_{chl} \times E_{aux}$ onto $E_{aux} \times E_{com}$. This proves the existence of an isogeny connecting $E_{com}$ and $E'_{chl}$. We summarise these steps in Algorithm 8.

Remark 14 (Technical Remark). In the concrete instantiation, when computing the isogeny $\Phi$ with kernel $\mathcal{K} = \langle (P_{chl}, [2^{r'}]P_{aux}), (Q_{chl}, [2^{r'}]Q_{aux}) \rangle$, we use the formulae in [12]. In particular, in order to avoid the computation of extra square roots in the codomain computation, we use the four torsion above $\mathcal{K}$. As explained in [11, Theorem 56], this also fixes a symplectic four-torsion basis on the codomain, which in turns defines a theta structure.

In the implementation, we always pick the four-torsion above $\mathcal{K}$ such that the codomain is of the form $E'_{aux} \times E_{com}$. Therefore, in Algorithm 8, Line 15, we can restrict ourselves to checking that $F_2$ is isomorphic to $E_{com}$.

**Algorithm 8 Verify**

**Input:** The public key $E_{pk}$, the commitment $E_{com}$, the challenge $chl$, the response $E_{aux}$, $P_{chl}$, $Q_{chl}$, $r'$, $n_{bt}$.

**Output:** true or false.

1: Compute a deterministic basis ($P_{pk}$, $Q_{pk}$) of $E_{pk}$ [$2^e$].

2: Compute $\varphi_{chl}: E_0 \to E_{chl}$ with kernel [$2^{n_{bt}}$]($P_{pk}$ + [chl] $Q_{pk}$).

3: Compute a deterministic basis ($P_{aux}$, $Q_{aux}$) of $E_{aux}$ [$2^{e_{rsp}-n_{bt}}$].

4: **if** $r' > 0$ **then**

5: **if** [$2^{e_{rsp}-n_{bt}-1}$] $Q_{chl} \neq 0$ **then**

6: $R \leftarrow [2^{e_{rsp}-n_{bt}-r'}]Q_{chl}$

7: **else**

8: $R \leftarrow [2^{e_{rsp}-n_{bt}-r'}]P_{chl}$

9: Compute $\varphi: E_{chl} \to E'_{chl}$ of kernel $\langle R \rangle$.

10: $E_{chl} \leftarrow E'_{chl}$.

11: $P_{chl}$, $Q_{chl} \leftarrow \varphi(P_{chl})$, $\varphi(Q_{chl})$.

12: Compute $\Phi: E_{chl} \times E_{aux} \to F_1 \times F_2$ with kernel $\langle (P_{chl}, [2^{r'}]P_{aux}), (Q_{chl}, [2^{r'}]Q_{aux}) \rangle$.

13: **if** the computation of $\Phi$ fails **then**

14: **return** false

15: **return** $F_2 \cong E_{com}$
the non-backtrack portion of the challenge isogeny as in the previous paragraph. Additionally, they compute ($P_{aux}$, $Q_{aux}$), a deterministic basis of $E_{aux}$ [$2^{e_{rsp}-n_{bt}}$]

If $r' > 0$, it means that the prover has chosen a response isogeny having an even, non-backtrack component. In this case, [$2^{e_{rsp}-r'-n_{bt}}$] $P_{chl}$ and [$2^{e_{rsp}-r'-n_{bt}}$] $Q_{chl}$ are linearly dependent, and [$2^{e_{rsp}-r'-n_{bt}}$] $P_{chl}$, [$2^{e_{rsp}-r'-n_{bt}}$] $Q_{chl}$ is the kernel of the dual of the isogeny $\varphi_{rsp}^{(0)}$ (Cfr. Fig. 3). The verifier then computes the isogeny $\varphi: E_{chl} \to E'_{chl}$ with kernel [$2^{e_{rsp}-r'-n_{bt}}$] $P_{chl}$, [$2^{e_{rsp}-r'-n_{bt}}$] $Q_{chl}$ and updates $E_{chl} \leftarrow E'_{chl}$, $P_{chl} \leftarrow \varphi(P_{chl})$ and $Q_{chl} \leftarrow \varphi(Q_{chl})$.

From Kani's Lemma, it follows that the isogeny $\Phi$ with kernel

$$ \langle (P_{chl}, [2^{r'}]P_{aux}), (Q_{chl}, [2^{r'}]Q_{aux}) \rangle $$

maps $E'_{chl} \times E_{aux}$ onto $E_{aux} \times E_{com}$. This proves the existence of an isogeny connecting $E_{com}$ and $E'_{chl}$. We summarise these steps in Algorithm 8.

Remark 14 (Technical Remark). In the concrete instantiation, when computing the isogeny $\Phi$ with kernel $\mathcal{K} = \langle (P_{chl}, [2^{r'}]P_{aux}), (Q_{chl}, [2^{r'}]Q_{aux}) \rangle$, we use the formulae in [12]. In particular, in order to avoid the computation of extra square roots in the codomain computation, we use the four torsion above $\mathcal{K}$. As explained in [11, Theorem 56], this also fixes a symplectic four-torsion basis on the codomain, which in turns defines a theta structure.

In the implementation, we always pick the four-torsion above $\mathcal{K}$ such that the codomain is of the form $E'_{aux} \times E_{com}$. Therefore, in Algorithm 8, Line 15, we can restrict ourselves to checking that $F_2$ is isomorphic to $E_{com}$.

Algorithm 8 Verify

**Input:** The public key $E_{pk}$, the commitment $E_{com}$, the challenge chl, the response $E_{aux}$, $P_{chl}$, $Q_{chl}$, $r'$, $n_{bt}$.

**Output:** true or false.

1: Compute a deterministic basis ($P_{pk}$, $Q_{pk}$) of $E_{pk}$ [$2^e$].

2: Compute $\varphi_{chl}: E_0 \to E_{chl}$ with kernel [$2^{n_{bt}}$]($P_{pk}$ + [chl] $Q_{pk}$).

3: Compute a deterministic basis ($P_{aux}$, $Q_{aux}$) of $E_{aux}$ [$2^{e_{rsp}-n_{bt}}$].

4: **if** $r' > 0$ **then**

5: **if** [$2^{e_{rsp}-n_{bt}-1}$] $Q_{chl} \neq 0$ **then**

6: $R \leftarrow [2^{e_{rsp}-n_{bt}-r'}]Q_{chl}$

7: **else**

8: $R \leftarrow [2^{e_{rsp}-n_{bt}-r'}]P_{chl}$

9: Compute $\varphi: E_{chl} \to E'_{chl}$ of kernel $\langle R \rangle$.

10: $E_{chl} \leftarrow E'_{chl}$.

11: $P_{chl}$, $Q_{chl} \leftarrow \varphi(P_{chl})$, $\varphi(Q_{chl})$.

12: Compute $\Phi: E_{chl} \times E_{aux} \to F_1 \times F_2$ with kernel $\langle (P_{chl}, [2^{r'}]P_{aux}), (Q_{chl}, [2^{r'}]Q_{aux}) \rangle$.

13: **if** the computation of $\Phi$ fails **then**

14: **return** false

15: **return** $F_2 \cong E_{com}$
## 5.2 The signature protocol

To transform the $\Sigma$ protocol in a digital signature, we rely on the Fiat-Shamir transform [22], where the interactive challenge generation is replaced by hashing the commitment, together with the message, to obtain a challenge. However, our protocol differs from a straightforward application of the transform: we rely on the commitment-recoverability property of the underlying $\Sigma$ protocol to obtain a smaller signature. Namely, a signature of SQIsign2D consists only of a challenge and the corresponding response. To verify a signature, the verifier recovers the challenge from the signature, checks that the commitment, challenge, and response form a valid transcript for the $\Sigma$ protocol, and ensures that the challenge was honestly generated.

For this approach to work, it is necessary that the verifier can extract the commitment from the response. During verification, the verifier first computes the challenge isogeny codomain, and then they obtain the two-dimensional isogeny $\Phi$ (see Line 12 of Algorithm 8). The codomain of $\Phi$ is either the product $E'_{aux} \times E_{com}$ or $E_{com} \times E'_{aux}$. While a priori it is not possible to distinguish between the two cases, we rely on a specific method to compute $\Phi$, as explained in Remark 14, that guarantees that the codomain is $E'_{aux} \times E_{com}$. Hence, the verifier can extract the commitment curve $E_{com}$ from the codomain of $\Phi$ and check the challenge has been honestly generated, i.e. as the output of the hashing of $E_{com}$ and the message to be signed.

# 6 Security analysis

In this section, we prove that the identification protocol (and thereby the signature scheme obtained by the Fiat-Shamir transform) is secure: it is knowledge-sound and honest-verifier zero-knowledge.

First, note that the key recovery problem for our construction is simply the standard Supersingular Endomorphism Ring problem, a foundational problem of isogeny-based cryptography.

*Problem 15 (Supersingular Endomorphism Ring problem).* Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, find four endomorphisms (in efficient representation) which generate the ring End($E$).

The fastest known algorithms for this problem have classical complexity in $\tilde{O}(p^{1/2})$ [16] (see also [37, Theorem 8.8]). The only known quantum speedup is using Grover's algorithm [23,6], for a quantum complexity in $\tilde{O}(p^{1/4})$.

We prove in Theorem 19 that if $e_{chl} + e_{rsp} \le e$, the protocol has the 2-special soundness property for the language

$$ \{(E_{pk}, \alpha) \mid \alpha \in \text{End}(E_{pk}) \setminus \mathbb{Z} \text{ in efficient representation}\}. $$

This language corresponds to the Supersingular One Endomorphism problem.
## 5.2 The signature protocol

To transform the $\Sigma$ protocol in a digital signature, we rely on the Fiat-Shamir transform [22], where the interactive challenge generation is replaced by hashing the commitment, together with the message, to obtain a challenge. However, our protocol differs from a straightforward application of the transform: we rely on the commitment-recoverability property of the underlying $\Sigma$ protocol to obtain a smaller signature. Namely, a signature of SQIsign2D consists only of a challenge and the corresponding response. To verify a signature, the verifier recovers the challenge from the signature, checks that the commitment, challenge, and response form a valid transcript for the $\Sigma$ protocol, and ensures that the challenge was honestly generated.

For this approach to work, it is necessary that the verifier can extract the commitment from the response. During verification, the verifier first computes the challenge isogeny codomain, and then they obtain the two-dimensional isogeny $\Phi$ (see Line 12 of Algorithm 8). The codomain of $\Phi$ is either the product $E'_{aux} \times E_{com}$ or $E_{com} \times E'_{aux}$. While a priori it is not possible to distinguish between the two cases, we rely on a specific method to compute $\Phi$, as explained in Remark 14, that guarantees that the codomain is $E'_{aux} \times E_{com}$. Hence, the verifier can extract the commitment curve $E_{com}$ from the codomain of $\Phi$ and check the challenge has been honestly generated, i.e. as the output of the hashing of $E_{com}$ and the message to be signed.

# 6 Security analysis

In this section, we prove that the identification protocol (and thereby the signature scheme obtained by the Fiat-Shamir transform) is secure: it is knowledge-sound and honest-verifier zero-knowledge.

First, note that the key recovery problem for our construction is simply the standard *Supersingular Endomorphism Ring* problem, a foundational problem of isogeny-based cryptography.

*Problem 15 (Supersingular Endomorphism Ring problem).* Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, find four endomorphisms (in efficient representation) which generate the ring $\text{End}(E)$.

The fastest known algorithms for this problem have classical complexity in $\tilde{O}(p^{1/2})$ [16] (see also [37, Theorem 8.8]). The only known quantum speedup is using Grover's algorithm [23,6], for a quantum complexity in $\tilde{O}(p^{1/4})$.

We prove in Theorem 19 that if $e_{chl} + e_{rsp} \le e$, the protocol has the 2-special soundness property for the language

$$ \{(E_{pk}, \alpha) \mid \alpha \in \text{End}(E_{pk}) \setminus \mathbb{Z} \text{ in efficient representation}\}. $$

This language corresponds to the *Supersingular One Endomorphism* problem.
**Problem 16 (Supersingular One Endomorphism problem).** Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, find a non-scalar endomorphism $\alpha \in \text{End}(E) \setminus \mathbb{Z}$ (in efficient representation).

This One Endomorphism problem is equivalent to the Endomorphism Ring problem [37], i.e., to the key recovery problem for our construction.

Then, we prove in Theorem 24 that if $N_{\text{com}} \ge 2^{4\lambda}$ and $2^{e_{\text{rsp}}} \ge 2\sqrt{2p}/\pi$, then the protocol is statistically honest-verifier zero-knowledge, in a model where the simulator can sample random large-degree isogenies from a given curve (in the classical model, this can only be done efficiently for smooth degree). This model, discussed in Section 6.2, is similar to the security model of SQIsignHD [11].

**Impact on parameter selection.** In summary, for a security level ensuring $\lambda$ bits of classical security, one needs to choose a prime $p = \Theta(2^{2\lambda})$. To ensure soundness, one needs $e_{\text{chl}} + e_{\text{rsp}} \le e$ (recall that $p \approx 2^e$, so $e \approx 2\lambda$). To ensure the statistical honest-verifier zero-knowledge property, one needs $N_{\text{com}} \ge 2^{4\lambda}$ and $2^{e_{\text{rsp}}} \ge 2\sqrt{2p}/\pi$.

## 6.1 Knowledge soundness

**Lemma 17.** Given a commitment $E_{\text{com}}$, a challenge chl $< 2^{e_{\text{chl}}}$ (generating the challenge isogeny $\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$), and a response $(E_{\text{aux}}, P_{\text{chl}}, Q_{\text{chl}}, r', n_{\text{bt}})$ passing verification, one can extract in polynomial time an efficient representation of an isogeny $\tilde{\sigma}: E_{\text{com}} \to E_{\text{chl}}$ of degree at most $2^{e_{\text{rsp}}}$.

*Proof.* Write $\psi: E_{\text{chl}}^0 \to E_{\text{chl}}$ for the last $n_{\text{bt}}$ steps of the challenge isogeny. Let $n = r' + n_{\text{bt}}$. A successful verification ensures that one can extract a $2^{r'}$-isogeny

$\tilde{\varphi}^{(0)}: \tilde{E}'_{\text{chl}} \to E_{\text{chl}}^0,$
(for some curve $\tilde{E}'_{\text{chl}}$) and an $(2^{e_{\text{rsp}}-n}, 2^{e_{\text{rsp}}-n})$-isogeny

$$ \Phi: \tilde{E}'_{\text{chl}} \times E_{\text{aux}} \to E_{\text{com}} \times \tilde{E}'_{\text{aux}}, $$

(for some curve $\tilde{E}'_{\text{aux}}$), in efficient representation. Composing $\Phi$ with the inclusion $E'_{\text{chl}} \to E'_{\text{chl}} \times E_{\text{aux}}$ and the projection $E_{\text{com}} \times E'_{\text{aux}} \to E_{\text{com}}$, and taking the dual, we obtain an isogeny $\tilde{\varphi}^{(1)}: E_{\text{com}} \to E'_{\text{chl}}$ of degree at most $2^{e_{\text{rsp}}-r'}$. Let $\tilde{\sigma} = \psi \circ \tilde{\varphi}^{(0)} \circ \tilde{\varphi}^{(1)}: E_{\text{com}} \to E_{\text{chl}}$. It has degree at most

$$ \deg(\psi) \deg(\tilde{\varphi}^{(0)}) \deg(\tilde{\varphi}^{(1)}) \le 2^{n_{\text{bt}}} \cdot 2^{e_{\text{rsp}}-n} \cdot 2^{r'} = 2^{e_{\text{rsp}}}, $$

which proves the lemma. $\square$

**Lemma 18.** Let $\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$ and $\varphi'_{\text{chl}}: E_{\text{pk}} \to E'_{\text{chl}}$ be two distinct challenges from the same public curve $E_{\text{pk}}$. Then, the largest integer dividing $\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}} \in \text{Hom}(E_{\text{chl}}, E'_{\text{chl}})$ is smaller than $2^{e_{\text{chl}}}$.
**Problem 16 (Supersingular One Endomorphism problem).** Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, find a non-scalar endomorphism $\alpha \in \text{End}(E) \setminus \mathbb{Z}$ (in efficient representation).

This One Endomorphism problem is equivalent to the Endomorphism Ring problem [37], i.e., to the key recovery problem for our construction.

Then, we prove in Theorem 24 that if $N_{\text{com}} \ge 2^{4\lambda}$ and $2^{e_{\text{rsp}}} \ge 2\sqrt{2p}/\pi$, then the protocol is statistically honest-verifier zero-knowledge, in a model where the simulator can sample random large-degree isogenies from a given curve (in the classical model, this can only be done efficiently for smooth degree). This model, discussed in Section 6.2, is similar to the security model of SQIsignHD [11].

**Impact on parameter selection.** In summary, for a security level ensuring $\lambda$ bits of classical security, one needs to choose a prime $p = \Theta(2^{2\lambda})$. To ensure soundness, one needs $e_{\text{chl}} + e_{\text{rsp}} \le e$ (recall that $p \approx 2^e$, so $e \approx 2\lambda$). To ensure the statistical honest-verifier zero-knowledge property, one needs $N_{\text{com}} \ge 2^{4\lambda}$ and $2^{e_{\text{rsp}}} \ge 2\sqrt{2p}/\pi$.

## 6.1 Knowledge soundness

**Lemma 17.** Given a commitment $E_{\text{com}}$, a challenge chl $< 2^{e_{\text{chl}}}$ (generating the challenge isogeny $\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$), and a response $(E_{\text{aux}}, P_{\text{chl}}, Q_{\text{chl}}, r', n_{\text{bt}})$ passing verification, one can extract in polynomial time an efficient representation of an isogeny $\tilde{\sigma} : E_{\text{com}} \to E_{\text{chl}}$ of degree at most $2^{e_{\text{rsp}}}$.

*Proof.* Write $\psi: E_{\text{chl}}^0 \to E_{\text{chl}}$ for the last $n_{\text{bt}}$ steps of the challenge isogeny. Let $n = r' + n_{\text{bt}}$. A successful verification ensures that one can extract a $2^{r'}$-isogeny

$\tilde{\varphi}^{(0)}: \tilde{E}'_{\text{chl}} \to E_{\text{chl}}^0,$
(for some curve $\tilde{E}'_{\text{chl}}$) and an $(2^{e_{\text{rsp}}-n}, 2^{e_{\text{rsp}}-n})$-isogeny

$$ \Phi: \tilde{E}'_{\text{chl}} \times E_{\text{aux}} \to E_{\text{com}} \times \tilde{E}'_{\text{aux}}, $$

(for some curve $\tilde{E}'_{\text{aux}}$), in efficient representation. Composing $\Phi$ with the inclusion $E'_{\text{chl}} \to E'_{\text{chl}} \times E_{\text{aux}}$ and the projection $E_{\text{com}} \times E'_{\text{aux}} \to E_{\text{com}}$, and taking the dual, we obtain an isogeny $\tilde{\varphi}^{(1)}: E_{\text{com}} \to E'_{\text{chl}}$ of degree at most $2^{e_{\text{rsp}}-r'}$. Let $\tilde{\sigma} = \psi \circ \tilde{\varphi}^{(0)} \circ \tilde{\varphi}^{(1)}: E_{\text{com}} \to E_{\text{chl}}$. It has degree at most

$$ \deg(\psi) \deg(\tilde{\varphi}^{(0)}) \deg(\tilde{\varphi}^{(1)}) \le 2^{n_{\text{bt}}} \cdot 2^{e_{\text{rsp}}-n} \cdot 2^{r'} = 2^{e_{\text{rsp}}}, $$

which proves the lemma. $\square$

**Lemma 18.** Let $\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$ and $\varphi'_{\text{chl}}: E_{\text{pk}} \to E'_{\text{chl}}$ be two distinct challenges from the same public curve $E_{\text{pk}}$. Then, the largest integer dividing $\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}} \in \text{Hom}(E_{\text{chl}}, E'_{\text{chl}})$ is smaller than $2^{e_{\text{chl}}}$.
**Proof.** Recall that the challenge isogeny $\varphi_{\text{chl}}$ is defined by the kernel $\langle K(\text{chl}) \rangle$ with

$$K(\text{chl}) = P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}$$

where $0 \le \text{chl} < 2^{e_{\text{chl}}}$, and $\langle P_{\text{pk}}, Q_{\text{pk}} \rangle = E_{\text{pk}}[2^e]$. The second challenge isogeny $\varphi'_{\text{chl}}$ is defined similarly by its kernel generator $K(\text{chl}') = P_{\text{pk}} + [\text{chl}']Q_{\text{pk}}$, for some $\text{chl} \ne \text{chl}'$. Since $\varphi_{\text{chl}}$ and $\varphi'_{\text{chl}}$ are cyclic, by [11, Lemma 37] there exists three cyclic isogenies $\varphi_0 : E_{\text{pk}} \to E$, $\varphi_1 : E \to E_{\text{chl}}$ and $\varphi'_1 : E \to E'_{\text{chl}}$ such that $\varphi_{\text{chl}} = \varphi_1 \circ \varphi_0$, $\varphi'_{\text{chl}} = \varphi'_1 \circ \varphi_0$ and $\varphi'_1 \circ \hat{\varphi}_1$ is cyclic. We call $\varphi_0$ the greatest cyclic factor of $\varphi_{\text{chl}}$ and $\varphi'_{\text{chl}}$. It has kernel $\ker(\varphi_0) = \ker(\varphi_{\text{chl}}) \cap \ker(\varphi'_{\text{chl}})$. Since $\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}} = [\deg(\varphi_0)]\varphi'_1 \circ \hat{\varphi}_1$, we see that $\deg(\varphi_0)$ is the largest integer dividing $\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}}$ in $\text{Hom}(E_{\text{chl}}, E'_{\text{chl}})$, so we only have to prove that $\deg(\varphi_0) < 2^{e_{\text{chl}}}$.

Let $R \in E_{\text{pk}}$ be a generator of $\ker(\varphi_0)$. Then, $R = [a]K(\text{chl}) = [b]K(\text{chl}')$ for some $a, b \in [0; 2^e - 1]$, i.e.,

$$[a - b]P_{\text{pk}} + [a \cdot \text{chl} - b \cdot \text{chl}']Q_{\text{pk}} = 0.$$

Since $(P_{\text{pk}}, Q_{\text{pk}})$ is a basis of $E_{\text{pk}}[2^e]$, it follows that $a-b \equiv 0 \mod 2^e$ so $a=b$ and $a(\text{chl} - \text{chl}') \equiv 0 \mod 2^e$. Since $0 \le \text{chl} \ne \text{chl}' < 2^{e_{\text{chl}}}$, it follows that $2^{e_{\text{chl}}+1}|a$, so that $R \in E_{\text{pk}}[2^{e_{\text{chl}}-1}]$ and $\deg(\varphi_0) \le 2^{e_{\text{chl}}-1}$. This completes the proof. $\square$

**Theorem 19.** If $e_{\text{chl}} + e_{\text{rsp}} \le e$, then the identification protocol has 2-special soundness for the language

$$\{(E_{\text{pk}}, \alpha) \mid \alpha \in \text{End}(E_{\text{pk}}) \setminus \mathbb{Z} \text{ in efficient representation}\}.$$

**Proof.** Consider two accepting transcripts with the same commitment curve $E_{\text{com}}$ but challenge isogenies $\varphi_{\text{chl}} : E_{\text{pk}} \to E_{\text{chl}}$ and $\varphi'_{\text{chl}} : E_{\text{pk}} \to E'_{\text{chl}}$ with distinct kernels. From Lemma 17, we can extract an efficient representation of isogenies $\sigma : E_{\text{com}} \to E_{\text{chl}}$ and $\sigma' : E_{\text{com}} \to E'_{\text{chl}}$, each of degree at most $2^{e_{\text{rsp}}}$.

Suppose by contradiction that $\alpha = [m]$ for some $m \in \mathbb{Z}$. We deduce

$$[m] \circ \varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}} = [\deg(\varphi_{\text{chl}}) \deg(\varphi'_{\text{chl}})] \circ \sigma' \circ \hat{\sigma}. \quad (2)$$

Write $\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}} = [2^a] \circ \psi$ and $\sigma' \circ \hat{\sigma} = [d] \circ \nu$ where $\psi$ and $\nu$ have cyclic kernel. We deduce from Equation (2) that $2^a m = d \deg(\varphi_{\text{chl}}) \deg(\varphi'_{\text{chl}})$ is the largest integer dividing either side of the equality, and $\psi = \nu$ is the cyclic part of either side.

On one hand, we have $\deg(\nu) \le \deg(\sigma) \deg(\sigma') \le 2^{2e_{\text{rsp}}}$. On the other hand, Lemma 18 implies

$$\deg(\psi) = \frac{\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}}}{2^{2a}} > 2^{2(e - e_{\text{chl}})} \ge 2^{2e_{\text{rsp}}}.$$

This contradicts the equality $\psi = \nu$. $\square$
Proof. Recall that the challenge isogeny $\varphi_{\text{chl}}$ is defined by the kernel $\langle K(\text{chl}) \rangle$ with

$$K(\text{chl}) = P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}$$

where $0 \le \text{chl} < 2^{e_{\text{chl}}}$, and $\langle P_{\text{pk}}, Q_{\text{pk}} \rangle = E_{\text{pk}}[2^e]$. The second challenge isogeny $\varphi'_{\text{chl}}$ is defined similarly by its kernel generator $K(\text{chl}') = P_{\text{pk}} + [\text{chl}']Q_{\text{pk}}$, for some $\text{chl} \ne \text{chl}'$. Since $\varphi_{\text{chl}}$ and $\varphi'_{\text{chl}}$ are cyclic, by [11, Lemma 37] there exists three cyclic isogenies $\varphi_0 : E_{\text{pk}} \to E$, $\varphi_1 : E \to E_{\text{chl}}$ and $\varphi'_1 : E \to E'_{\text{chl}}$ such that $\varphi_{\text{chl}} = \varphi_1 \circ \varphi_0$, $\varphi'_{\text{chl}} = \varphi'_1 \circ \varphi_0$ and $\varphi'_1 \circ \hat{\varphi}_1$ is cyclic. We call $\varphi_0$ the greatest cyclic factor of $\varphi_{\text{chl}}$ and $\varphi'_{\text{chl}}$. It has kernel $\ker(\varphi_0) = \ker(\varphi_{\text{chl}}) \cap \ker(\varphi'_{\text{chl}})$. Since $\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}} = [\deg(\varphi_0)]\varphi'_1 \circ \hat{\varphi}_1$, we see that $\deg(\varphi_0)$ is the largest integer dividing $\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}}$ in $\text{Hom}(E_{\text{chl}}, E'_{\text{chl}})$, so we only have to prove that $\deg(\varphi_0) < 2^{e_{\text{chl}}}$.

Let $R \in E_{\text{pk}}$ be a generator of $\ker(\varphi_0)$. Then, $R = [a]K(\text{chl}) = [b]K(\text{chl}')$ for some $a, b \in [0; 2^e - 1]$, i.e.,

$$[a - b]P_{\text{pk}} + [a \cdot \text{chl} - b \cdot \text{chl}']Q_{\text{pk}} = 0.$$

Since $(P_{\text{pk}}, Q_{\text{pk}})$ is a basis of $E_{\text{pk}}[2^e]$, it follows that $a-b \equiv 0 \mod 2^e$ so $a=b$ and $a(\text{chl} - \text{chl}') \equiv 0 \mod 2^e$. Since $0 \le \text{chl} \ne \text{chl}' < 2^{e_{\text{chl}}}$, it follows that $2^{e_{\text{chl}}+1}|a$, so that $R \in E_{\text{pk}}[2^{e_{\text{chl}}-1}]$ and $\deg(\varphi_0) \le 2^{e_{\text{chl}}-1}$. This completes the proof. $\square$

**Theorem 19.** If $e_{\text{chl}} + e_{\text{rsp}} \le e$, then the identification protocol has 2-special soundness for the language

$$\{(E_{\text{pk}}, \alpha) \mid \alpha \in \text{End}(E_{\text{pk}}) \setminus \mathbb{Z} \text{ in efficient representation}\}.$$

Proof. Consider two accepting transcripts with the same commitment curve $E_{\text{com}}$ but challenge isogenies $\varphi_{\text{chl}} : E_{\text{pk}} \to E_{\text{chl}}$ and $\varphi'_{\text{chl}} : E_{\text{pk}} \to E'_{\text{chl}}$ with distinct kernels. From Lemma 17, we can extract an efficient representation of isogenies $\sigma : E_{\text{com}} \to E_{\text{chl}}$ and $\sigma' : E_{\text{com}} \to E'_{\text{chl}}$, each of degree at most $2^{e_{\text{rsp}}}$.

Suppose by contradiction that $\alpha = [m]$ for some $m \in \mathbb{Z}$. We deduce

$$[m] \circ \varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}} = [\deg(\varphi_{\text{chl}}) \deg(\varphi'_{\text{chl}})] \circ \sigma' \circ \hat{\sigma}. \quad (2)$$

Write $\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}} = [2^a] \circ \psi$ and $\sigma' \circ \hat{\sigma} = [d] \circ \nu$ where $\psi$ and $\nu$ have cyclic kernel. We deduce from Equation (2) that $2^a m = d \deg(\varphi_{\text{chl}}) \deg(\varphi'_{\text{chl}})$ is the largest integer dividing either side of the equality, and $\psi = \nu$ is the cyclic part of either side.

On one hand, we have $\deg(\nu) \le \deg(\sigma) \deg(\sigma') \le 2^{2e_{\text{rsp}}}$. On the other hand, Lemma 18 implies

$$\deg(\psi) = \frac{\varphi'_{\text{chl}} \circ \hat{\varphi}_{\text{chl}}}{2^{2a}} > 2^{2(e - e_{\text{chl}})} \ge 2^{2e_{\text{rsp}}}.$$

This contradicts the equality $\psi = \nu$. $\square$
## 6.2 Zero-knowledge property

In this section, we prove that the identification protocol is honest-verifier zero-knowledge. Let us first prove that the commitment curve is indistinguishable from a uniformly random curve.

**Lemma 20.** If $N_{com} \ge 2^{4\lambda}$, then an honestly generated commitment curve $E_{com}$ is at statistical distance $\tilde{O}(2^{-\lambda})$ from a uniformly random supersingular elliptic curve.

*Proof.* It follows from [11, Proposition 29] with $\varepsilon = 1$ and $p = \Theta(2^{2\lambda})$. $\square$

To prove that the protocol has the zero-knowledge property, we prove that there exists a simulator producing transcripts indistinguishable from a honest run of the protocol. Like in SQIsignHD [11], the simulator runs in polynomial time if it has access to an oracle producing random isogenies. This “random isogeny” oracle comes in two variants: the UTO and the FIDIO.

**Definition 21.** A uniform target oracle (UTO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and an integer $N \ge 2\sqrt{2p}/\pi$, and outputs a random isogeny $\varphi : E \to E'$ (in efficient representation) such that:

1. The distribution of $E'$ is uniform among all the supersingular elliptic curves.

2. The conditional distribution of $\varphi$ given $E'$ is uniform among isogenies $E \to E'$ of degree smaller or equal to $N$.

*Remark 22.* The condition $N \ge 2\sqrt{2p}/\pi$ ensures such an oracle exists: for any pair $(E_1, E_2)$, the collection of isogenies $E_1 \to E_2$ of degree smaller than $N$ is non-empty (Minkowski's bound for the lattice $\text{Hom}(E_1, E_2)$).

**Definition 23.** A fixed degree isogeny oracle (FIDIO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and an integer $N$, and outputs a uniformly random isogeny $\varphi : E \to E'$ (in efficient representation) with domain $E$ and degree $N$.

**Theorem 24.** If $2^{e_{resp}} \ge 2\sqrt{2p}/\pi$ and $N_{com} \ge 2^{4\lambda}$, then the identification protocol is statistically honest-verifier zero-knowledge in the UTO and FIDIO model. In other words, there exists a polynomial time simulator $S$ with access to a UTO and a FIDIO that produces random transcripts which are statistically indistinguishable from honest transcripts.

*Proof.* The simulator proceeds as follows:

1. Generate an isogeny $\varphi_{chl} : E_{pk} \to E_{chl}$ according to the honest challenge distribution.

2. Call the UTO on input $(E_{chl}, 2^{e_{resp}})$, resulting in the isogeny $\hat{\varphi}_{rsp} : E_{chl} \to E_{com}$.

3. Decompose $\varphi_{rsp} = \psi \circ \varphi_{rsp}^{(1)}$ with $q' = \text{deg}(\varphi_{rsp}^{(1)})$ odd and $\text{deg}(\psi) = 2^n$ a power of two. Let $2^{n_{bt}} = \#(\text{ker}(\hat{\psi}) \cap \text{ker}(\hat{\varphi}_{chl}))$. Let $r' = n - n_{bt}$.
## 6.2 Zero-knowledge property

In this section, we prove that the identification protocol is honest-verifier zero-knowledge. Let us first prove that the commitment curve is indistinguishable from a uniformly random curve.

**Lemma 20.** If $N_{com} \ge 2^{4\lambda}$, then an honestly generated commitment curve $E_{com}$ is at statistical distance $\tilde{O}(2^{-\lambda})$ from a uniformly random supersingular elliptic curve.

*Proof.* It follows from [11, Proposition 29] with $\varepsilon = 1$ and $p = \Theta(2^{2\lambda})$. $\square$

To prove that the protocol has the zero-knowledge property, we prove that there exists a simulator producing transcripts indistinguishable from a honest run of the protocol. Like in SQIsignHD [11], the simulator runs in polynomial time if it has access to an oracle producing random isogenies. This “random isogeny” oracle comes in two variants: the UTO and the FIDIO.

**Definition 21.** A uniform target oracle (UTO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and an integer $N \ge 2\sqrt{2p}/\pi$, and outputs a random isogeny $\varphi : E \to E'$ (in efficient representation) such that:

1. The distribution of $E'$ is uniform among all the supersingular elliptic curves.

2. The conditional distribution of $\varphi$ given $E'$ is uniform among isogenies $E \to E'$ of degree smaller or equal to $N$.

*Remark 22.* The condition $N \ge 2\sqrt{2p}/\pi$ ensures such an oracle exists: for any pair $(E_1, E_2)$, the collection of isogenies $E_1 \to E_2$ of degree smaller than $N$ is non-empty (Minkowski's bound for the lattice $\text{Hom}(E_1, E_2)$).

**Definition 23.** A fixed degree isogeny oracle (FIDIO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and an integer $N$, and outputs a uniformly random isogeny $\varphi : E \to E'$ (in efficient representation) with domain $E$ and degree $N$.

**Theorem 24.** If $2^{e_{rsp}} \ge 2\sqrt{2p}/\pi$ and $N_{com} \ge 2^{4\lambda}$, then the identification protocol is statistically honest-verifier zero-knowledge in the UTO and FIDIO model. In other words, there exists a polynomial time simulator $S$ with access to a UTO and a FIDIO that produces random transcripts which are statistically indistinguishable from honest transcripts.

*Proof.* The simulator proceeds as follows:

1. Generate an isogeny $\varphi_{chl} : E_{pk} \to E_{chl}$ according to the honest challenge distribution.

2. Call the UTO on input $(E_{chl}, 2^{e_{rsp}})$, resulting in the isogeny $\hat{\varphi}_{rsp} : E_{chl} \to E_{com}$.

3. Decompose $\varphi_{rsp} = \psi \circ \varphi_{rsp}^{(1)}$ with $q' = \text{deg}(\varphi_{rsp}^{(1)})$ odd and $\text{deg}(\psi) = 2^n$ a power of two. Let $2^{n_{bt}} = \#(\text{ker}(\hat{\psi}) \cap \text{ker}(\hat{\varphi}_{chl}))$. Let $r' = n - n_{bt}$.
4. Call the FIDIO on input $(E_{\text{com}}, 2^{e_{\text{rsp}}-r'} - q')$, resulting in the isogeny $\varphi_{\text{aux}} : E_{\text{com}} \to E_{\text{aux}}$.

From the properties of the UTO and FIDIO, the above procedure is equivalent
to the following one:

1. Generate a uniformly random supersingular curve $E_{\text{com}}$

2. Generate an isogeny $\varphi_{\text{chl}} : E_{\text{pk}} \to E_{\text{chl}}$ according to the honest challenge distribution.

3. Generate a uniformly random isogeny $\varphi_{\text{rsp}}$ from $E_{\text{com}}$ to $E_{\text{chl}}$, of degree at most $2^{e_{\text{rsp}}}$.

4. Decompose $\varphi_{\text{rsp}} = \psi \circ \varphi_{\text{rsp}}^{(1)}$ with $q' = \text{deg}(\varphi_{\text{rsp}}^{(1)})$ odd and $\text{deg}(\psi) = 2^n$ a power of two. Let $2^{m_{\text{bt}}} = \#(\text{ker}(\hat{\psi}) \cap \text{ker}(\hat{\varphi}_{\text{chl}}))$. Let $r' = n - n_{\text{bt}}$.

5. Generate a uniformly random isogeny $\beta$ from $E_{\text{com}}$ and of degree $2^{e_{\text{rsp}}-r'} - q'$.

This is precisely the order in which a honest run of the protocol proceeds.
The distribution for the first step matches the honest run by Lemma 20. The
distributions of following steps match the honest ones by construction. $\square$

**On the UTO and FIDIO oracles.** Let us first argue that the UTO is essentially
redundant: given a FIDIO, one can implement an oracle that is computationally
indistinguishable from a UTO, at least when the bound $N$ is sufficiently large.
We proceed in two steps:

1. First, we use the FIDIO to build an oracle which outputs a uniform isogeny $\sigma$ from $E$ with $\deg(\sigma) \le N$. In other words, one can turn a FIDIO into a RADIO, following the terminology of [11].

2. Second, we argue that this distribution (the output of a RADIO) is indistinguishable from the output of a UTO.

Recall the definition of a RADIO.

**Definition 25 ([11, Definition 41]).** A random any-degree isogeny oracle (RADIO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and an integer $N$, and outputs a uniformly random isogeny $\varphi : E \to E'$ (in efficient representation) with domain $E$ and degree at most $N$.

Let us first explain how one can turn a FIDIO into a RADIO. Let $f_N$ be the
probability distribution of the degree of the output of a RADIO: for any integer
$q$, let $f_N(q)$ be the probability that the degree of the output of a RADIO on
input $(E, N)$ is equal to $q$. Note that conditional on the degree of the output
begin $q$, the FIDIO and the RADIO follow the same distribution: uniform among
isogenies with domain $E$ and degree $q$. Therefore, to simulate a RADIO, we can
proceed as follows: on input $(E, N)$,

1. sample an integer $q$ following the distribution $f_N$;

2. call the FIDIO on input $(E, q)$, and return the output.
4. Call the FIDIO on input $(E_{\text{com}}, 2^{e_{\text{rsp}}-r'} - q')$, resulting in the isogeny $\varphi_{\text{aux}} : E_{\text{com}} \to E_{\text{aux}}$.

From the properties of the UTO and FIDIO, the above procedure is equivalent
to the following one:

1. Generate a uniformly random supersingular curve $E_{\text{com}}$

2. Generate an isogeny $\varphi_{\text{chl}} : E_{\text{pk}} \to E_{\text{chl}}$ according to the honest challenge distribution.

3. Generate a uniformly random isogeny $\varphi_{\text{rsp}}$ from $E_{\text{com}}$ to $E_{\text{chl}}$, of degree at most $2^{e_{\text{rsp}}}$.

4. Decompose $\varphi_{\text{rsp}} = \psi \circ \varphi_{\text{rsp}}^{(1)}$ with $q' = \text{deg}(\varphi_{\text{rsp}}^{(1)})$ odd and $\text{deg}(\psi) = 2^n$ a power of two. Let $2^{m_{\text{bt}}} = \#(\text{ker}(\hat{\psi}) \cap \text{ker}(\hat{\varphi}_{\text{chl}}))$. Let $r' = n - n_{\text{bt}}$.

5. Generate a uniformly random isogeny $\beta$ from $E_{\text{com}}$ and of degree $2^{e_{\text{rsp}}-r'} - q'$.

This is precisely the order in which a honest run of the protocol proceeds.
The distribution for the first step matches the honest run by Lemma 20. The
distributions of following steps match the honest ones by construction. $\square$

**On the UTO and FIDIO oracles.** Let us first argue that the UTO is essentially
redundant: given a FIDIO, one can implement an oracle that is computationally
indistinguishable from a UTO, at least when the bound $N$ is sufficiently large.
We proceed in two steps:

1. First, we use the FIDIO to build an oracle which outputs a uniform isogeny $\sigma$ from $E$ with $\deg(\sigma) \le N$. In other words, one can turn a FIDIO into a RADIO, following the terminology of [11].

2. Second, we argue that this distribution (the output of a RADIO) is indistinguishable from the output of a UTO.

Recall the definition of a RADIO.

**Definition 25 ([11, Definition 41]).** A random any-degree isogeny oracle (RADIO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and an integer $N$, and outputs a uniformly random isogeny $\varphi : E \to E'$ (in efficient representation) with domain $E$ and degree at most $N$.

Let us first explain how one can turn a FIDIO into a RADIO. Let $f_N$ be the
probability distribution of the degree of the output of a RADIO: for any integer
$q$, let $f_N(q)$ be the probability that the degree of the output of a RADIO on
input $(E, N)$ is equal to $q$. Note that conditional on the degree of the output
begin $q$, the FIDIO and the RADIO follow the same distribution: uniform among
isogenies with domain $E$ and degree $q$. Therefore, to simulate a RADIO, we can
proceed as follows: on input $(E, N)$,

1. sample an integer $q$ following the distribution $f_N$;

2. call the FIDIO on input $(E, q)$, and return the output.
To sample from the distribution $f_N$, observe that the value $f_N(q) = \tilde{\Theta}(q/N^2)$ can be computed efficiently if the factorisation of $q$ is known. Therefore, we can do rejection sampling by sampling uniformly random integers in $[1, N]$ together with their factorisation (see [1]).

We proceed as follows: sample a random degree $q \le N$, then call the FIDIO to sample a uniform isogeny of degree $q$ from $E$. The only difficulty is to sample $q \le N$ with the same distribution as the degree of a UTO-output (it is not the uniform distribution). Given the prime factorisation $q = \prod_i \ell_i^{e_i}$, there are $\prod_i \ell_i^{e_i}$.

Now that we can turn a FIDIO into a RADIO, it remains to argue that a RADIO is indistinguishable from a UTO. For $N$ large enough, it is indeed statistically indistinguishable: conditionally on the target curve, the two distributions are identical, and it is proven in [11, Theorem 42] that when $N = \Theta(p^{1+\epsilon})$ for $\epsilon \in (0, 2]$, the distribution on the target curves are at statistical distance $O(p^{-\epsilon/2})$. Therefore, when $N = \Theta(p^{1+\epsilon})$, the RADIO and the UTO are at statistical distance $O(p^{-\epsilon/2})$. The bound $N = O(p^{1/2})$ used in the protocol is not large enough for this theorem to apply, but we expect the distributions to remain computationally indistinguishable.

The conclusion of the above discussion is that in Theorem 24, the UTO is heuristically redundant. In other words, there is a (heuristic) simulator in the FIDIO model. It remains to argue that this FIDIO does not hurt the security assumption: access to a FIDIO does not help with solving the endomorphism ring problem. We refer to the analogous discussion about the security of SQIsignHD in [11, Section 5.3]. In essence, all a FIDIO does is compute a random walk from a source curve. We already know how to compute random walks of smooth degree (by taking a sequence of random isogeny steps of small prime degree), and a FIDIO extends this capability to random walks with potentially large prime steps.

## 6.3 Security of the signature protocol

In the previous sections, we have shown that the SQIsign2D $\Sigma$ protocol is 2-special sound, under the assumed hardness of Problem 15, and zero-knowledge in the UTO and FIDIO model. Hence, a direct application of the Fiat-Shamir transform [22] yields a digital signature that is EUF-CMA secure in the random oracle model (ROM) [38], under the hardness of Problem 15 when the attacker has access to the UTO and FIDIO.

However, the signature protocol whose security is proved in [38] includes commitments in the signature. As explained in Section 5.2, we replace the commitment in the signature with the challenge (by relying on the commitment-recoverability property of the $\Sigma$ protocol) to reduce the signature size. To show the security equivalence of the two approaches, we rely on [2, Theorem 2], which requires the commitment-recovering algorithm to be correct and sound. Given a transcript (com, chl, rsp), correctness requires the commitment-recovering algorithm to always produce com given chl and rsp, and it follows from Remark 14. Soundness, in this context, means that it is computationally hard to find a
To sample from the distribution $f_N$, observe that the value $f_N(q) = \tilde{\Theta}(q/N^2)$ can be computed efficiently if the factorisation of $q$ is known. Therefore, we can do rejection sampling by sampling uniformly random integers in $[1, N]$ together with their factorisation (see [1]).

We proceed as follows: sample a random degree $q \le N$, then call the FIDIO to sample a uniform isogeny of degree $q$ from $E$. The only difficulty is to sample $q \le N$ with the same distribution as the degree of a UTO-output (it is not the uniform distribution). Given the prime factorisation $q = \prod_i \ell_i^{e_i}$, there are $\prod_i \ell_i^{e_i}$.

Now that we can turn a FIDIO into a RADIO, it remains to argue that a RADIO is indistinguishable from a UTO. For $N$ large enough, it is indeed statistically indistinguishable: conditionally on the target curve, the two distributions are identical, and it is proven in [11, Theorem 42] that when $N = \Theta(p^{1+\epsilon})$ for $\epsilon \in (0, 2]$, the distribution on the target curves are at statistical distance $O(p^{-\epsilon/2})$. Therefore, when $N = \Theta(p^{1+\epsilon})$, the RADIO and the UTO are at statistical distance $O(p^{-\epsilon/2})$. The bound $N = O(p^{1/2})$ used in the protocol is not large enough for this theorem to apply, but we expect the distributions to remain computationally indistinguishable.

The conclusion of the above discussion is that in Theorem 24, the UTO is heuristically redundant. In other words, there is a (heuristic) simulator in the FIDIO model. It remains to argue that this FIDIO does not hurt the security assumption: access to a FIDIO does not help with solving the endomorphism ring problem. We refer to the analogous discussion about the security of SQIsignHD in [11, Section 5.3]. In essence, all a FIDIO does is compute a random walk from a source curve. We already know how to compute random walks of smooth degree (by taking a sequence of random isogeny steps of small prime degree), and a FIDIO extends this capability to random walks with potentially large prime steps.

## 6.3 Security of the signature protocol

In the previous sections, we have shown that the SQIsign2D $\Sigma$ protocol is 2-special sound, under the assumed hardness of Problem 15, and zero-knowledge in the UTO and FIDIO model. Hence, a direct application of the Fiat-Shamir transform [22] yields a digital signature that is EUF-CMA secure in the random oracle model (ROM) [38], under the hardness of Problem 15 when the attacker has access to the UTO and FIDIO.

However, the signature protocol whose security is proved in [38] includes commitments in the signature. As explained in Section 5.2, we replace the commitment in the signature with the challenge (by relying on the commitment-recoverability property of the $\Sigma$ protocol) to reduce the signature size. To show the security equivalence of the two approaches, we rely on [2, Theorem 2], which requires the commitment-recovering algorithm to be correct and sound. Given a transcript (com, chl, rsp), correctness requires the commitment-recovering algorithm to always produce com given chl and rsp, and it follows from Remark 14. Soundness, in this context, means that it is computationally hard to find a
pair of challenge and response (chl, rsp) for which the commitment-recovering algorithm produces a commitment com such that (com, chl, rsp) is not a valid transcript. In our case, the commitment-recovering algorithm is perfectly sound (i.e. soundness holds even against unbounded adversaries): the curve produced by the commitment-recovering algorithm introduced in Section 5.2 is always the codomain of an isogeny, efficiently represented in the response, starting from $E_{chl}$, and the curve $E_{com}$ does not need to satisfy any additional requirement to be a valid commitment; thus, the resulting transcript is always valid.

This shows that the SQIsign2D signature protocol is EUF-CMA secure in the ROM, assuming the hardness of Problem 15 when the attacker has also access to the UTO and FIDIO.

# 7 Instantiation and experimental results

We selected parameters for the scheme described in Section 5 matching NIST post-quantum security levels I, III and V, and implemented them in C building upon the SQIsign reference implementation. We now give details on our implementation and compare its performance to the other variants of SQIsign.

## 7.1 Parameter choices and signature size

*Choice of the primes.* As mentioned in Section 6, the best attacks against the Supersingular Endomorphism Ring problem have classical complexity $\tilde{O}(p^{1/2})$ and quantum complexity $\tilde{O}(p^{1/4})$, where $p$ is the characteristic of the base field. These are also the best known attacks against SQIsign (see [8, Chapter 9]) and SQIsign2D. Our security reduction, although not tight and formulated in the UTO/FIDIO model, further justifies using these complexities to set parameters.

To reach NIST's security levels I, III and V, we thus look for primes of roughly 256, 384 and 512 bits respectively. For maximum efficiency, we selected primes such that $2p$ fits in 4, 6 and 8 64-bits words. The final requirement is that $p+1 = c \cdot 2^e$ with $c$ as small as possible; it is also desirable that $c$ has small Hamming weight. Our final choices are listed in Table 2.

<table><caption>**Table 2.** Chosen parameters for SQIsign2D. Sizes in bytes.</caption><thead><tr><th></th><th>NIST I</th><th>NIST III</th><th>NIST V</th></tr></thead><tbody><tr><td>Prime</td><td>5 &middot; 2<sup>248</sup> &minus; 1</td><td>65 &middot; 2<sup>376</sup> &minus; 1</td><td>27 &middot; 2<sup>500</sup> &minus; 1</td></tr><tr><td>Public-key size</td><td>66</td><td>98</td><td>130</td></tr><tr><td>Signature size</td><td>148</td><td>222</td><td>294</td></tr></tbody></table>
pair of challenge and response (chl, rsp) for which the commitment-recovering algorithm produces a commitment com such that (com, chl, rsp) is not a valid transcript. In our case, the commitment-recovering algorithm is perfectly sound (i.e. soundness holds even against unbounded adversaries): the curve produced by the commitment-recovering algorithm introduced in Section 5.2 is always the codomain of an isogeny, efficiently represented in the response, starting from $E_{chl}$, and the curve $E_{com}$ does not need to satisfy any additional requirement to be a valid commitment; thus, the resulting transcript is always valid.

This shows that the SQIsign2D signature protocol is EUF-CMA secure in the ROM, assuming the hardness of Problem 15 when the attacker has also access to the UTO and FIDIO.

# 7 Instantiation and experimental results

We selected parameters for the scheme described in Section 5 matching NIST post-quantum security levels I, III and V, and implemented them in C building upon the SQIsign reference implementation. We now give details on our implementation and compare its performance to the other variants of SQIsign.

## 7.1 Parameter choices and signature size

*Choice of the primes.* As mentioned in Section 6, the best attacks against the Supersingular Endomorphism Ring problem have classical complexity $\tilde{O}(p^{1/2})$ and quantum complexity $\tilde{O}(p^{1/4})$, where $p$ is the characteristic of the base field. These are also the best known attacks against SQIsign (see [8, Chapter 9]) and SQIsign2D. Our security reduction, although not tight and formulated in the UTO/FIDIO model, further justifies using these complexities to set parameters.

To reach NIST's security levels I, III and V, we thus look for primes of roughly 256, 384 and 512 bits respectively. For maximum efficiency, we selected primes such that $2p$ fits in 4, 6 and 8 64-bits words. The final requirement is that $p+1 = c \cdot 2^e$ with $c$ as small as possible; it is also desirable that $c$ has small Hamming weight. Our final choices are listed in Table 2.

<table><caption>**Table 2.** Chosen parameters for SQIsign2D. Sizes in bytes.</caption><thead><tr><th></th><th>NIST I</th><th>NIST III</th><th>NIST V</th></tr></thead><tbody><tr><td>Prime</td><td>5 · 2<sup>248</sup> − 1</td><td>65 · 2<sup>376</sup> − 1</td><td>27 · 2<sup>500</sup> − 1</td></tr><tr><td>Public-key size</td><td>66</td><td>98</td><td>130</td></tr><tr><td>Signature size</td><td>148</td><td>222</td><td>294</td></tr></tbody></table>
*Signature encoding and sizes.* The resulting public key and signature sizes are reported in Table 2. We detail below how these numbers are computed.

As for other SQIsign variants, there are various possibilities to decrease the signature size at the expense of slower verification and signing. For our implementation, we prioritised verification speed over signature size, and thus chose to not use the most advanced compression tricks. As we mentioned already (see Section 5.2), our scheme is commitment recoverable which means that we do not need to include the commitment curve in the signature. This requires a little more work for the signer, but it makes close to no difference for the verification.

Outside of this, the only other real compression we use is to represent the basis $P_{\text{chl}}$, $Q_{\text{chl}}$ as four elements in $[0, 2^{e_{\text{rsp}}}]$ (that are the coefficients of $P_{\text{chl}}$, $Q_{\text{chl}}$ in a canonical basis of $E_{\text{chl}}$). For a given level security of $\lambda$, we have $\log p \approx 2\lambda$ and $e_{\text{rsp}} \approx \lambda$, so this compression allows us to decrease the size of the basis representation from $8\lambda$ (since each point is represented as one element in $\mathbb{F}_{p^2}$) to $4\lambda$. This requires the additional computation a canonical basis of $E_{\text{chl}}$. In general, this is not cheap to compute, but we can abuse tricks specialised for the generation of bases of $E[2^k]$ such as the entangled torsion basis from [45, Algorithm 3.1] or the modification described in [9, Section 5.1].

We can further reduce the cost of the basis generation for the verifier by including hints at the very reasonable cost of increasing the signature size by two bytes. The idea of hints to speed-up basis generation was first introduced as part of the compression procedure in the original SQIsign paper. Using the specialised algorithms [45,9] boils down to selecting x-coordinates with chosen Legendre symbols and checking whether the chosen x is a valid x-coordinate for a point on the curve.

In this context, the hints can be either indices of tables of “good” x-coordinates, or some integer $h$ such that $x = i + h \in \mathbb{F}_{p^2}$ are values with the correct Legendre symbol properties and points on the curve.<fnref n="9" /> Moreover, it does not cost anything to the signer to include these hints. In our experiments, the value of the hints never went over 50, thus we conjecture that for the sizes considered for our scheme, the hints for a basis can fit in two bytes with overwhelming probability.

In our scheme, we use hints for the deterministic basis generation required by the verification: one for $E_{\text{pk}}$ and one for $E_{\text{chl}}$. Thus, this increases the size of the public key by two bytes and the size of the signature by two bytes.

In the end, the size of the public key is $4\lambda + 16$ bits, and the size of the signature is $9\lambda + 16 + 2\log_2(2\lambda)$ bits ($\lambda$ for the scalar chl, $4\lambda$ for $E_{\text{aux}}$, $4\lambda + 16$ for $P_{\text{chl}}$, $Q_{\text{chl}}$ and $2\log(2\lambda)$ for $r'$ and $n_{\text{bt}}$).

*Remark 26.* The representation of $P_{\text{chl}}$, $Q_{\text{chl}}$ could be further reduced to $3\lambda$, but would require the verifier to compute a pairing to recover the last coefficient. Since pairing are quite costly, we decided not to include this optimisation, but

<footnote n="9">⁹ In our implementation, we begin sampling coordinates from two tables with twenty values. This gives a 2<sup>-20</sup> chance of failure, which we recover from by then sampling coordinates of the form $x = i + h$ as above. Regardless of whether the basis is generated from a look-up or sampling, the cost for verification is the same thanks to the supplied hint.</footnote>
*Signature encoding and sizes.* The resulting public key and signature sizes are reported in Table 2. We detail below how these numbers are computed.

As for other SQIsign variants, there are various possibilities to decrease the signature size at the expense of slower verification and signing. For our implementation, we prioritised verification speed over signature size, and thus chose to not use the most advanced compression tricks. As we mentioned already (see Section 5.2), our scheme is commitment recoverable which means that we do not need to include the commitment curve in the signature. This requires a little more work for the signer, but it makes close to no difference for the verification.

Outside of this, the only other real compression we use is to represent the basis $P_{chl}, Q_{chl}$ as four elements in $[0, 2^{e_{rsp}}]$ (that are the coefficients of $P_{chl}, Q_{chl}$ in a canonical basis of $E_{chl}$). For a given level security of $\lambda$, we have $\log p \approx 2\lambda$ and $e_{rsp} \approx \lambda$, so this compression allows us to decrease the size of the basis representation from $8\lambda$ (since each point is represented as one element in $\mathbb{F}_{p^2}$) to $4\lambda$. This requires the additional computation a canonical basis of $E_{chl}$. In general, this is not cheap to compute, but we can abuse tricks specialised for the generation of bases of $E[2^k]$ such as the entangled torsion basis from [45, Algorithm 3.1] or the modification described in [9, Section 5.1].

We can further reduce the cost of the basis generation for the verifier by including hints at the very reasonable cost of increasing the signature size by two bytes. The idea of hints to speed-up basis generation was first introduced as part of the compression procedure in the original SQIsign paper. Using the specialised algorithms [45,9] boils down to selecting $x$-coordinates with chosen Legendre symbols and checking whether the chosen $x$ is a valid $x$-coordinate for a point on the curve.

In this context, the hints can be either indices of tables of “good” $x$-coordinates, or some integer $h$ such that $x = i + h \in \mathbb{F}_{p^2}$ are values with the correct Legendre symbol properties and points on the curve.<fnref n="9" /> Moreover, it does not cost anything to the signer to include these hints. In our experiments, the value of the hints never went over 50, thus we conjecture that for the sizes considered for our scheme, the hints for a basis can fit in two bytes with overwhelming probability.

In our scheme, we use hints for the deterministic basis generation required by the verification: one for $E_{pk}$ and one for $E_{chl}$. Thus, this increases the size of the public key by two bytes and the size of the signature by two bytes.

In the end, the size of the public key is $4\lambda + 16$ bits, and the size of the signature is $9\lambda + 16 + 2\log_2(2\lambda)$ bits ($\lambda$ for the scalar chl, $4\lambda$ for $E_{aux}$, $4\lambda + 16$ for $P_{chl}$, $Q_{chl}$ and $2\log(2\lambda)$ for $r'$ and $n_{bt}$).

*Remark 26.* The representation of $P_{chl}, Q_{chl}$ could be further reduced to $3\lambda$, but would require the verifier to compute a pairing to recover the last coefficient. Since pairing are quite costly, we decided not to include this optimisation, but

<footnote n="9">⁹ In our implementation, we begin sampling coordinates from two tables with twenty values. This gives a 2<sup>-20</sup> chance of failure, which we recover from by then sampling coordinates of the form $x = i + h$ as above. Regardless of whether the basis is generated from a look-up or sampling, the cost for verification is the same thanks to the supplied hint.</footnote>
it could be part of the signature in cases where size of the signature is critical. Experimentally, for NIST level 1, this would gain 16B on the signature size, at the cost of an increase on the verification time by 5 to 10 percent.

## 7.2 Implementation choices and optimisations

We implemented SQIsign2D in C by modifying the reference implementation of SQIsign.

*Multi-precision integers and quaternion algebras* are built on top of the GMP library.<fnref n="10" /> The only significant difference with SQIsign is the use of floating point numbers in the LLL algorithm instead of exact rationals.

*Arithmetic modulo p* has two implementations: one based on the Fiat-Crypto code generator [21] and one optimised implementation using the special form of the primes used, allowing for efficient Montgomery reduction.

The special shape of our primes lends itself to several optimisations, making our implementation much faster than its counterpart in SQIsign. Indeed, primes of the form $c \cdot 2^e - 1$ are both *Montgomery-friendly* in the sense of [3] and, when *c* has small Hamming weight, *generalised Mersenne numbers* in the sense of [44]. The former have very efficient Montgomery reduction and are thus best represented in Montgomery form, which Fiat-Crypto does automatically, although without optimisations related to the Montgomery-friendliness. The latter simply have very efficient modular reduction and can be represented as integers in the interval $[0, m-1]$ for some bound *m*.

Additionally, for the level I and V parameters, for the Montgomery integer *R*, we use that $(R + 2)^2 > 4((R - 1)p + 1)$ which allows the implementation of Montgomery multiplication without a final conditional subtraction. This bound is not satisfied for the level III parameters currently used. We note that the optimised implementation does not include hand-optimised assembly, but does use architecture specific intrinsics when available.

In our optimised implementation we only explored the Montgomery representation, but we plan to experiment with the generalised Mersenne reduction in the near future, as well as including hand-optimised assembly instructions. A more thorough optimisation would also need to take into account the opportunities to simultaneously optimise the arithmetic of $\mathbb{F}_p$ and that of $\mathbb{F}_{p^2}$, like in [31].

*Elliptic curves, pairings, and isogenies.* Following standard practice, we represent elliptic curves in Montgomery form and use the formulas in [10,39] to evaluate 2-isogenies and 4-isogenies. Compared to SQIsign, we do not use formulas for isogenies of odd degrees, and in particular we do not need the costly $\sqrt{\ell}$ algorithm [5].

For pairings, we use the biextension/cubical formulas from [42], because these are currently, to the best of our knowledge, the fastest available to compute

<footnote n="10">¹⁰ https://gmplib.org/.</footnote>