# SQIsignHD: New Dimensions in Cryptography

Pierrick Dartois, Antonin Leroux, Damien Robert, Benjamin Wesolowski

► To cite this version:

Pierrick Dartois, Antonin Leroux, Damien Robert, Benjamin Wesolowski. SQIsignHD: New Dimensions in Cryptography. Eurocrypt 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 2024, Zurich (CH), Switzerland. pp.3-32, 10.1007/978-3-031-58716-0_1. hal-04562459

HAL Id: hal-04562459

https://hal.science/hal-04562459

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.

<figure><img src="image_1.png" /></figure>
SQIsignHD: New Dimensions in Cryptography

Pierrick Dartois<sup>1,2[0009-0008-2808-9867]</sup>, Antonin Leroux<sup>3,4[0009-0002-3737-0075]</sup>, Damien Robert<sup>1,2[0000-0003-4378-4274]</sup> and Benjamin Wesolowski<sup>5[0000-0003-1249-6077]</sup>

<sup>1</sup> Univ. Bordeaux, CNRS, INRIA, IMB, UMR 5251, F-33400 Talence, France

<sup>2</sup> INRIA, IMB, UMR 5251, F-33400, Talence, France
{pierrick.dartois,damien.robert}@inria.fr

<sup>3</sup> DGA-MI, Bruz, France,

<sup>4</sup> IRMAR - UMR 6625, Université de Rennes, France
antonin.leroux@polytechnique.org

<sup>5</sup> ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France
benjamin.wesolowski@ens-lyon.fr

**Abstract.** We introduce SQIsignHD, a new post-quantum digital sig-
nature scheme inspired by SQIsign. SQIsignHD exploits the recent al-
gorithmic breakthrough underlying the attack on SIDH, which allows
to efficiently represent isogenies of arbitrary degrees as components of a
higher dimensional isogeny. SQIsignHD overcomes the main drawbacks
of SQIsign. First, it scales well to high security levels, since the public
parameters for SQIsignHD are easy to generate; the characteristic of the
underlying field needs only be of the form $2^{f_1}3^{f_2} - 1$. Second, the signing
procedure is simpler and more efficient. Our signing procedure imple-
mented in C runs in 28 ms, which is a significant improvement compared
to SQISign. Third, the scheme is easier to analyse, allowing for a much
more compelling security reduction. Finally, the signature sizes are even
more compact than (the already record-breaking) SQISign, with com-
pressed signatures as small as 109 bytes for the post-quantum NIST-1
level of security. These advantages may come at the expense of the veri-
fication, which now requires the computation of an isogeny in dimension
4, a task whose optimised cost is still uncertain, as it has been the focus
of very little attention. Our experimental sagemath implementation of
the verification runs in around 600 ms, indicating the potential cryp-
tographic interest of dimension 4 isogenies after optimisations and low
level implementation.

**Acknowledgements.** We thank Luca De Feo for his advice all along this project and for suggesting the title of this paper. This project was supported by ANR grant CIAO (ANR-19-CE48-0008), PEPR PQ-TLS (the France 2030 program under grant agreement ANR-22-PETQ-0008 PQ-TLS) and the European Research Council under grant No. 101116169 (AGATHA CRYPTY).

# 1 Introduction

Isogeny-based cryptography has been a promising area of research in post-quantum cryptography since Couveignes, Rostovtsev and Stolbunov introduced
# SQIsignHD: New Dimensions in Cryptography

Pierrick Dartois<sup>1,2[0009-0008-2808-9867]</sup>, Antonin Leroux<sup>3,4[0009-0002-3737-0075]</sup>, Damien Robert<sup>1,2[0000-0003-4378-4274]</sup> and Benjamin Wesolowski<sup>5[0000-0003-1249-6077]</sup>

<sup>1</sup> Univ. Bordeaux, CNRS, INRIA, IMB, UMR 5251, F-33400 Talence, France

<sup>2</sup> INRIA, IMB, UMR 5251, F-33400, Talence, France
{pierrick.dartois,damien.robert}@inria.fr

<sup>3</sup> DGA-MI, Bruz, France,

<sup>4</sup> IRMAR - UMR 6625, Université de Rennes, France
antonin.leroux@polytechnique.org

<sup>5</sup> ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France
benjamin.wesolowski@ens-lyon.fr

**Abstract.** We introduce SQIsignHD, a new post-quantum digital sig-nature scheme inspired by SQIsign. SQIsignHD exploits the recent al-gorithmic breakthrough underlying the attack on SIDH, which allows to efficiently represent isogenies of arbitrary degrees as components of a higher dimensional isogeny. SQIsignHD overcomes the main drawbacks of SQIsign. First, it scales well to high security levels, since the public parameters for SQIsignHD are easy to generate; the characteristic of the underlying field needs only be of the form $2^f3^f - 1$. Second, the signing procedure is simpler and more efficient. Our signing procedure imple-mented in C runs in 28 ms, which is a significant improvement compared to SQISign. Third, the scheme is easier to analyse, allowing for a much more compelling security reduction. Finally, the signature sizes are even more compact than (the already record-breaking) SQISign, with com-pressed signatures as small as 109 bytes for the post-quantum NIST-1 level of security. These advantages may come at the expense of the veri-fication, which now requires the computation of an isogeny in dimension 4, a task whose optimised cost is still uncertain, as it has been the focus of very little attention. Our experimental sagemath implementation of the verification runs in around 600 ms, indicating the potential cryp-tographic interest of dimension 4 isogenies after optimisations and low level implementation.

**Acknowledgements.** We thank Luca De Feo for his advice all along this project and for suggesting the title of this paper. This project was supported by ANR grant CIAO (ANR-19-CE48-0008), PEPR PQ-TLS (the France 2030 program under grant agreement ANR-22-PETQ-0008 PQ-TLS) and the European Research Council under grant No. 101116169 (AGATHA CRYPTY).

# 1 Introduction

Isogeny-based cryptography has been a promising area of research in post-quantum cryptography since Couveignes, Rostovtsev and Stolbunov introduced
the first key exchange using ordinary isogenies [8, 34]. Schemes from this family
often distinguish themselves by their compactness, in particular with respect to
key sizes. It is notably the case of the digital signature scheme SQIsign [10, 13],
the most compact post-quantum signature scheme by a decent margin. However,
efficiency has been a recurring challenge for isogeny-based schemes, and indeed,
SQIsign is much slower than other post-quantum signatures.

In this paper, we introduce SQIsignHD, a new digital signature scheme de-
rived from SQIsign. As in [15], SQIsign uses the Deuring correspondence between
supersingular elliptic curves and quaternion orders. This Deuring correspondence
is a powerful tool to construct cryptosystems because it is one way: it is easy to
turn an order into the corresponding elliptic curve, but the converse direction
is the presumably hard *supersingular endomorphism ring problem* [12, 41]. In
SQISign, the signer’s public key is a supersingular elliptic curve, and a signa-
ture effectively proves that the signer knows the associated quaternion order.
This requires algorithms to translate between orders (and ideals in these orders)
and elliptic curves (and isogenies from these curves). This translation is costly,
and crucially requires the ideals (or isogenies) to have smooth norms (or de-
grees). The original methods have been improved upon [13], but that remains
the bottleneck of SQISign. Another issue with SQISign is its scalability to higher
security levels. Indeed, to set public parameters, one needs to find a prime *p*
such that *p*² − 1 has a very large smooth factor. Searching for such primes *p*
becomes harder as the security level grows, and is still an active area of research
[7, 4, 1]. Besides, the security of SQISign relies on the fact that signatures are
computationally indistinguishable from random isogenies of fixed powersmooth
degrees. There is no known formal proof of this *ad hoc* heuristic assumption.

The new scheme SQIsignHD follows a similar outline as SQISign, but resolves
its main drawbacks by fundamentally reforging the computational approach. The
main ingredient is the ground-breaking technique that has recently led to the
downfall of SIDH [5, 27, 33]. Namely, these attacks use a lemma due to Kani [19]
combined with Zahrin's trick, which allows one to “embed” any isogeny into an
isogeny of higher dimension. As remarked in [32], this technique allows one to
describe an isogeny by listing only the image of a few well-chosen points; from
this description, one can efficiently evaluate the isogeny on any other point,
regardless of the factorisation pattern of the underlying isogeny. This newly
gained freedom on usable isogenies unlocks challenges in efficiency, security, and
scalability.

**Our Contribution.** We introduce the digital signature scheme SQIsignHD. It leverages recent algorithmic breakthroughs [5, 27, 33] to overcome the main drawbacks of SQISign. It has the following advantages:

- SQISignHD scales well to high security levels. Indeed, while SQISign requires a search for primes *p* with strong constraints, the primes used in SQISignHD may be of the form *c*²*f*³*f'* − 1, where *c* is some (preferably small) cofactor. Such primes, already used in SIDH [18], are easy to find, and allow for efficient field arithmetic.
the first key exchange using ordinary isogenies [8, 34]. Schemes from this family often distinguish themselves by their compactness, in particular with respect to key sizes. It is notably the case of the digital signature scheme SQIsign [10, 13], the most compact post-quantum signature scheme by a decent margin. However, efficiency has been a recurring challenge for isogeny-based schemes, and indeed, SQIsign is much slower than other post-quantum signatures.

In this paper, we introduce SQIsignHD, a new digital signature scheme derived from SQIsign. As in [15], SQIsign uses the Deuring correspondence between supersingular elliptic curves and quaternion orders. This Deuring correspondence is a powerful tool to construct cryptosystems because it is one way: it is easy to turn an order into the corresponding elliptic curve, but the converse direction is the presumably hard supersingular endomorphism ring problem [12, 41]. In SQISign, the signer's public key is a supersingular elliptic curve, and a signature effectively proves that the signer knows the associated quaternion order. This requires algorithms to translate between orders (and ideals in these orders) and elliptic curves (and isogenies from these curves). This translation is costly, and crucially requires the ideals (or isogenies) to have smooth norms (or degrees). The original methods have been improved upon [13], but that remains the bottleneck of SQISign. Another issue with SQISign is its scalability to higher security levels. Indeed, to set public parameters, one needs to find a prime *p* such that *p*² − 1 has a very large smooth factor. Searching for such primes *p* becomes harder as the security level grows, and is still an active area of research [7, 4, 1]. Besides, the security of SQISign relies on the fact that signatures are computationally indistinguishable from random isogenies of fixed powersmooth degrees. There is no known formal proof of this *ad hoc* heuristic assumption.

The new scheme SQISignHD follows a similar outline as SQISign, but resolves
its main drawbacks by fundamentally reforging the computational approach. The
main ingredient is the ground-breaking technique that has recently led to the
downfall of SIDH [5, 27, 33]. Namely, these attacks use a lemma due to Kani [19]
combined with Zahrin's trick, which allows one to "embed" any isogeny into an
isogeny of higher dimension. As remarked in [32], this technique allows one to
describe an isogeny by listing only the image of a few well-chosen points; from
this description, one can efficiently evaluate the isogeny on any other point,
regardless of the factorisation pattern of the underlying isogeny. This newly
gained freedom on usable isogenies unlocks challenges in efficiency, security, and
scalability.

**Our Contribution.** We introduce the digital signature scheme SQISignHD. It leverages recent algorithmic breakthroughs [5, 27, 33] to overcome the main drawbacks of SQISign. It has the following advantages:

- SQISignHD scales well to high security levels. Indeed, while SQISign requires a search for primes *p* with strong constraints, the primes used in SQISignHD may be of the form *c*²*f*³*f'* − 1, where *c* is some (preferably small) cofactor. Such primes, already used in SIDH [18], are easy to find, and allow for efficient field arithmetic.
- The signing procedure of SQIsignHD is simpler and more efficient than SQIsign. Let us stress that no high dimensional isogeny needs to be computed when signing. Our proof-of-concept implementation, which still lacks many standard optimisations, is already about ten times faster than the fastest SQIsign implementation. This is discussed in further detail in Section 6.2.

- SQIsignHD is easier to analyse, allowing for a much more compelling security reduction to the supersingular endomorphism problem. Unlike in SQIsign, our proof of the zero-knowledge property in SQIsignHD relies on simple and plausible heuristic assumptions. In fact, we propose two variants of SQIsign, one of which is less efficient but benefits from a heuristic-free analysis. In both cases, the zero-knowledge property is based on a simulator which is given access to a non-standard oracle. We carefully discuss the impact of this oracle on the supersingular endomorphism problem.

- SQIsignHD signatures are even more compact than SQIsign, as they are only 6.5λ bits long, for λ bits of security. In particular, they are as small as 109 bytes for the NIST-1 security level. SQIsign already had the most compact signature and public keys combined of all post-quantum signature schemes, and SQIsignHD breaks this record.

These advantages may come at the expense of the verification, which now requires the computation of a chain of 2-isogenies in dimension 4 (or 8 in the less efficient variant). We provide an algorithm for the verification, and an experimental implementation in sagemath [36, 28]. An optimised low-level implementation is left for future work, hence the true cost of verification is still uncertain. The verification in SQIsign also requires the computation of a (longer!) chain of 2-isogenies, but only in dimension 1.

## 1.1 A Modular Overview of SQIsignHD

We introduce two distinct versions of SQIsignHD, optimised in different directions. FastSQIsignHD is optimised for speed, while RigorousSQIsignHD is optimised for the security proof. Note that the security proof applies to both: the difference lies in the proof being unconditional for RigorousSQIsignHD when given access to an oracle, but requiring additional heuristics for FastSQIsignHD (see [9, § D.2] and Section 5.2). Under the hood, FastSQIsignHD relies on isogenies of dimension 4, while RigorousSQIsignHD relies on isogenies of dimension 8. The reader may sense the parallel with the heuristic (dimension 4) and rigorous (dimension 8) variants of the algorithms of [33].

We present here the main algorithmic building blocks of the identification scheme undelying SQIsignHD to give a modular overview of the protocol. Those algorithms are presented in detail in this paper for FastSQIsignHD and in [9, § B] for RigorousSQIsignHD. Unsurprisingly, the protocol shares a lot of similarities with SQIsign. The full signature scheme can be derived from there with the Fiat-Shamir transform [14] as in [10, § 3.4] (see [9, § A.1] for details).

**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
- The signing procedure of SQIsignHD is simpler and more efficient than SQIsign. Let us stress that no high dimensional isogeny needs to be computed when signing. Our proof-of-concept implementation, which still lacks many standard optimisations, is already about ten times faster than the fastest SQIsign implementation. This is discussed in further detail in Section 6.2.

- SQIsignHD is easier to analyse, allowing for a much more compelling security reduction to the supersingular endomorphism problem. Unlike in SQIsign, our proof of the zero-knowledge property in SQIsignHD relies on simple and plausible heuristic assumptions. In fact, we propose two variants of SQIsign, one of which is less efficient but benefits from a heuristic-free analysis. In both cases, the zero-knowledge property is based on a simulator which is given access to a non-standard oracle. We carefully discuss the impact of this oracle on the supersingular endomorphism problem.

- SQIsignHD signatures are even more compact than SQIsign, as they are only 6.5λ bits long, for λ bits of security. In particular, they are as small as 109 bytes for the NIST-1 security level. SQIsign already had the most compact signature and public keys combined of all post-quantum signature schemes, and SQIsignHD breaks this record.

These advantages may come at the expense of the verification, which now requires the computation of a chain of 2-isogenies in dimension 4 (or 8 in the less efficient variant). We provide an algorithm for the verification, and an experimental implementation in sagemath [36, 28]. An optimised low-level implementation is left for future work, hence the true cost of verification is still uncertain. The verification in SQIsign also requires the computation of a (longer!) chain of 2-isogenies, but only in dimension 1.

## 1.1 A Modular Overview of SQIsignHD

We introduce two distinct versions of SQIsignHD, optimised in different directions. FastSQIsignHD is optimised for speed, while RigorousSQIsignHD is optimised for the security proof. Note that the security proof applies to both: the difference lies in the proof being unconditional for RigorousSQIsignHD when given access to an oracle, but requiring additional heuristics for FastSQIsignHD (see [9, § D.2] and Section 5.2). Under the hood, FastSQIsignHD relies on isogenies of dimension 4, while RigorousSQIsignHD relies on isogenies of dimension 8. The reader may sense the parallel with the heuristic (dimension 4) and rigorous (dimension 8) variants of the algorithms of [33].

We present here the main algorithmic building blocks of the identification scheme undelying SQIsignHD to give a modular overview of the protocol. Those algorithms are presented in detail in this paper for FastSQIsignHD and in [9, § B] for RigorousSQIsignHD. Unsurprisingly, the protocol shares a lot of similarities with SQIsign. The full signature scheme can be derived from there with the Fiat-Shamir transform [14] as in [10, § 3.4] (see [9, § A.1] for details).

**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 \bmod 4$).

**Key generation.** The prover generates a random secret isogeny $\tau : E_0 \to E_A$ of fixed smooth degree $D_\tau$. Then, the prover publishes $E_A$. Knowing $\tau$, only the prover can compute the endomorphism ring $\text{End}(E_A)$. In the fast method FastKeyGen, the isogeny $\tau$ has degree $D_\tau = \Theta(p)$, which is heuristically sufficient to ensure that the distribution of $E_A$ is computationally indistinguishable from uniform. In the alternate method RigorousKeyGen, the degree is chosen a bit larger to make the distribution of $E_A$ statistically close to uniform.

**Commitment.** The prover generates a random isogeny $\psi : E_0 \to E_1$ of smooth degree $D_\psi$ and returns $E_1$ to the verifier ($\psi$ being secret). The resulting distribution for $E_1$ is as close as possible to the uniform distribution in the supersingular isogeny graph. As in the key generation, we propose a fast procedure FastCommit($E_0$) in Section 3.3 resulting in a distribution heuristically indistinguishable from uniform, and a slower variant RigorousCommit($E_0$) in [9, § B.2] which guarantees statistical closeness to uniform.

**Challenge.** The verifier generates a random isogeny $\varphi : E_A \to E_2$ of smooth degree $D_\varphi$ sufficiently large for $\varphi$ to have high entropy. Then, $\varphi$ is sent to the prover. The **Challenge** procedure is described in Section 3.2. Unlike SQIsign, we chose to start the challenge from $E_A$ instead of $E_1$ in order to optimize the response process.

**Response.** The prover generates an *efficient representation* of an isogeny $\sigma : E_1 \to E_2$ of small degree $q \approx \sqrt{p}$ in the sense of the following definition and returns it to the verifier.

**Definition 1.** Let $\mathcal{A}$ be an algorithm and $\varphi : E \to E'$ be an isogeny defined over a finite field $\mathbb{F}_q$. An *efficient representation* of $\varphi$ (with respect to $\mathcal{A}$) is some data $D \in \{0, 1\}^*$ of polynomial size in $\log(\deg(\varphi))$ and $\log(q)$ such that, on input $D$ and $P \in E(\mathbb{F}_{q^k})$, $\mathcal{A}$ returns $\varphi(P)$ in polynomial time in $k \log(q)$ and $\log(\deg(\varphi))$.

There always exists an efficient representation of a smooth degree isogeny.
For instance, it can be written as a chain of small degree isogenies. Until the
recent attacks on SIDH [5, 27, 33], we did not know how to efficiently represent
isogenies with non-smooth degrees without revealing the endomorphism ring of
the domain. For that reason, the original version of SQIsign uses smooth degree
isogenies for the signature. These smooth degree isogenies are found with a
variant of the KLPT algorithm [20] and have very big degree $\approx p^{15/4}$. This not
only hurts efficiency, but also security: the isogeny $\sigma$ is so carefully crafted that
it is hard to simulate, and as a result, the zero-knowledge property of SQIsign
is very *ad hoc*.

Now, the methods from [5, 27, 33] give much more freedom on the isogenies
that can be efficiently represented. This allows SQIsignHD to improve both
efficiency (using isogenies $\sigma$ of degree as low as $\approx \sqrt{p}$), and security (the isogenies
$\sigma$ are now nicely distributed, hence simulatable).
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 \bmod 4$).

**Key generation.** The prover generates a random secret isogeny $\tau : E_0 \to E_A$ of fixed smooth degree $D_\tau$. Then, the prover publishes $E_A$. Knowing $\tau$, only the prover can compute the endomorphism ring $\text{End}(E_A)$. In the fast method FastKeyGen, the isogeny $\tau$ has degree $D_\tau = \Theta(p)$, which is heuristically sufficient to ensure that the distribution of $E_A$ is computationally indistinguishable from uniform. In the alternate method RigorousKeyGen, the degree is chosen a bit larger to make the distribution of $E_A$ statistically close to uniform.

**Commitment.** The prover generates a random isogeny $\psi : E_0 \to E_1$ of smooth degree $D_\psi$ and returns $E_1$ to the verifier ($\psi$ being secret). The resulting distribution for $E_1$ is as close as possible to the uniform distribution in the supersingular isogeny graph. As in the key generation, we propose a fast procedure FastCommit($E_0$) in Section 3.3 resulting in a distribution heuristically indistinguishable from uniform, and a slower variant RigorousCommit($E_0$) in [9, § B.2] which guarantees statistical closeness to uniform.

**Challenge.** The verifier generates a random isogeny $\varphi : E_A \to E_2$ of smooth degree $D_\varphi$ sufficiently large for $\varphi$ to have high entropy. Then, $\varphi$ is sent to the prover. The **Challenge** procedure is described in Section 3.2. Unlike SQIsign, we chose to start the challenge from $E_A$ instead of $E_1$ in order to optimize the response process.

**Response.** The prover generates an *efficient representation* of an isogeny $\sigma : E_1 \to E_2$ of small degree $q \approx \sqrt{p}$ in the sense of the following definition and returns it to the verifier.

**Definition 1.** Let $\mathcal{A}$ be an algorithm and $\varphi : E \to E'$ be an isogeny defined over a finite field $\mathbb{F}_q$. An *efficient representation* of $\varphi$ (with respect to $\mathcal{A}$) is some data $D \in \{0, 1\}^*$ of polynomial size in $\log(\deg(\varphi))$ and $\log(q)$ such that, on input $D$ and $P \in E(\mathbb{F}_{q^k})$, $\mathcal{A}$ returns $\varphi(P)$ in polynomial time in $k \log(q)$ and $\log(\deg(\varphi))$.

There always exists an efficient representation of a smooth degree isogeny.
For instance, it can be written as a chain of small degree isogenies. Until the
recent attacks on SIDH [5, 27, 33], we did not know how to efficiently represent
isogenies with non-smooth degrees without revealing the endomorphism ring of
the domain. For that reason, the original version of SQIsign uses smooth degree
isogenies for the signature. These smooth degree isogenies are found with a
variant of the KLPT algorithm [20] and have very big degree $\approx p^{15/4}$. This not
only hurts efficiency, but also security: the isogeny $\sigma$ is so carefully crafted that
it is hard to simulate, and as a result, the zero-knowledge property of SQIsign
is very *ad hoc*.

Now, the methods from [5, 27, 33] give much more freedom on the isogenies
that can be efficiently represented. This allows SQIsignHD to improve both
efficiency (using isogenies $\sigma$ of degree as low as $\approx \sqrt{p}$), and security (the isogenies
$\sigma$ are now nicely distributed, hence simulatable).
The idea is to “embed” $\sigma$ into an isogeny of higher dimension — and that only requires knowing the image of a few points through $\sigma$. As in the attacks against SIDH, such an isogeny can have dimension 2, 4 or 8. We shall see that dimension 2 has little interest compared to the original SQIsign protocol from an efficiency and security point of view. In SQIsignHD, we propose a response procedure Fast-Respond to represent $\sigma$ in dimension 4, and an alternative procedure Rigorous-Respond based on an isogeny computation in dimension 8. The procedure Fast-Respond is fast, and its security analysis relies on reasonable heuristics. On the other hand, RigorousRespond is much slower (though still polynomial time), but allows for a rigorous analysis.

In either case, for efficiency reasons, the prover does not actually compute higher dimensional isogenies but only images of some points through $\sigma$ (we explain how these points are evaluated in the course of the paper). Those points provide an efficient representation of $\sigma$ (along with $\deg(\sigma)$) and this data is sent to the verifier who can then compute higher dimensional isogenies representing $\sigma$.

**Verification.** The verifier checks that the response returned by the prover (points of $E_2$) correctly represents an isogeny $\sigma : E_1 \to E_2$. We propose two procedures FastVerify and RigorousVerify computing isogenies embedding $\sigma$ in dimension 4 or 8. So far, isogeny computations in dimension 4 has been the subject of very little literature.

Nonetheless, our proof of concept implementation of dimension 4 isogenies in sagemath [36, 28] demonstrates the cryptographic feasibility of this phase. We expect an optimized implementation to be at worse twice as slow as the original SQIsign verification, and hopefully even closer than that. We refer to [9, § F] for an estimate of the number of operations required for the verification.

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

**Content.** The rest of this paper is organized as follows. In Section 2, we present the core idea of our paper: how to embed signature/response isogenies in higher dimension with Kani's lemma. Section 3 introduces algorithms for key generation, commitment and challenge whereas Section 4 presents the response and verification phase for FastSQIsignHD. A security analysis of FastSQIsignHD identification protocol is conducted in Section 5. Finally, we discuss the expected performance of the digital signature scheme derived from FastSQIsignHD in Section 6. To save space, some preliminaries, proofs and algorithmic details on RigorousSQIsignHD and higher dimensional isogenies are given in [9].
The idea is to “embed” $\sigma$ into an isogeny of higher dimension — and that only requires knowing the image of a few points through $\sigma$. As in the attacks against SIDH, such an isogeny can have dimension 2, 4 or 8. We shall see that dimension 2 has little interest compared to the original SQIsign protocol from an efficiency and security point of view. In SQIsignHD, we propose a response procedure Fast-Respond to represent $\sigma$ in dimension 4, and an alternative procedure Rigorous-Respond based on an isogeny computation in dimension 8. The procedure Fast-Respond is fast, and its security analysis relies on reasonable heuristics. On the other hand, RigorousRespond is much slower (though still polynomial time), but allows for a rigorous analysis.

In either case, for efficiency reasons, the prover does not actually compute higher dimensional isogenies but only images of some points through $\sigma$ (we explain how these points are evaluated in the course of the paper). Those points provide an efficient representation of $\sigma$ (along with $\deg(\sigma)$) and this data is sent to the verifier who can then compute higher dimensional isogenies representing $\sigma$.

**Verification.** The verifier checks that the response returned by the prover (points of $E_2$) correctly represents an isogeny $\sigma : E_1 \to E_2$. We propose two procedures FastVerify and RigorousVerify computing isogenies embedding $\sigma$ in dimension 4 or 8. So far, isogeny computations in dimension 4 has been the subject of very little literature.

Nonetheless, our proof of concept implementation of dimension 4 isogenies in sagemath [36, 28] demonstrates the cryptographic feasibility of this phase. We expect an optimized implementation to be at worse twice as slow as the original SQIsign verification, and hopefully even closer than that. We refer to [9, § F] for an estimate of the number of operations required for the verification.

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

**Content.** The rest of this paper is organized as follows. In Section 2, we present the core idea of our paper: how to embed signature/response isogenies in higher dimension with Kani's lemma. Section 3 introduces algorithms for key generation, commitment and challenge whereas Section 4 presents the response and verification phase for FastSQIsignHD. A security analysis of FastSQIsignHD identification protocol is conducted in Section 5. Finally, we discuss the expected performance of the digital signature scheme derived from FastSQIsignHD in Section 6. To save space, some preliminaries, proofs and algorithmic details on RigorousSQIsignHD and higher dimensional isogenies are given in [9].
## 2 Representing the Response Isogeny Efficiently in Higher Dimension

In this section, we explore our main idea to improve SQIsign by embedding the signature isogeny inside an isogeny in higher dimension. We start by recalling how the signature is represented in the original SQIsign protocol in Section 2.1 and why this representation is slow to compute. Then, we introduce Kani's lemma and explain how to embed isogenies in higher dimension in Section 2.2. Finally, we apply this idea to provide another representation of the signature isogeny in SQIsign in Section 2.3.

### 2.1 State of the Art Isogeny Representation: a Slow Signature Process

With state of the art techniques prior to the attacks against SIDH, we could only efficiently represent isogenies of smooth degrees. That is why in the original versions of SQIsign [10, 13], the signature isogeny $\sigma$ has degree a prime power $\ell^e$ and is represented as a chain of $\ell$-isogenies.

To compute such a signature $\sigma$, the prover computes the ideal $J$ associated to the isogeny path given by the secret key, commitment and challenge. They then apply a SigningKLPT algorithm to $J$, to return a random equivalent ideal $I \sim J$ of norm $\ell^e$. Then, the prover converts $I$ into an isogeny. This last computation is very costly because $\text{nd}(I) = \ell^e$ is close to $p^{15/4}$, while the accessible torsion points have much smaller order. The method introduced in [10] (and later improved in [13]) requires to cut $J$ into several pieces in order to compute $\sigma$ as a chain of isogenies. This complicated mechanism is by far the bottleneck in the signing algorithm.

In order to avoid this costly ideal to isogeny translation in SQIsignHD, we shall no longer require $\sigma$ to have smooth degree and embed it in an isogeny of dimension 4 or 8 having smooth degree. This embedding will provide an efficient representation, and is faster to compute than the one in the original SQIsign. We shall also explain why this improves security in Section 5.

### 2.2 Embedding Isogenies in Higher Dimension with Kani's Lemma

In this section, we explain in more detail this idea of embedding isogenies in higher dimension. For that, we need a few definitions first.

**Definition 2 (d-isogeny).** Let $\alpha : (A, \lambda_A) \to (B, \lambda_B)$ be an isogeny between principally polarized abelian varieties. We say that $\alpha$ is a *d-isogeny* if $\hat{\alpha} \circ \lambda_B \circ \alpha = [d]\lambda_A$, where $\hat{\alpha} : \hat{B} \to \hat{A}$ is the dual isogeny of $\alpha$.

Equivalently, $\alpha$ is a *d-isogeny* if $\tilde{\alpha} \circ \alpha = [d]_A$, where $\tilde{\alpha} := \lambda_A^{-1} \circ \hat{\alpha} \circ \lambda_B$ is the dual isogeny of $\alpha$ with respect to the principal polarisations $\lambda_A$ and $\lambda_B$.
## 2 Representing the Response Isogeny Efficiently in Higher Dimension

In this section, we explore our main idea to improve SQIsign by embedding the signature isogeny inside an isogeny in higher dimension. We start by recalling how the signature is represented in the original SQIsign protocol in Section 2.1 and why this representation is slow to compute. Then, we introduce Kani's lemma and explain how to embed isogenies in higher dimension in Section 2.2. Finally, we apply this idea to provide another representation of the signature isogeny in SQIsign in Section 2.3.

### 2.1 State of the Art Isogeny Representation: a Slow Signature Process

With state of the art techniques prior to the attacks against SIDH, we could only efficiently represent isogenies of smooth degrees. That is why in the original versions of SQIsign [10, 13], the signature isogeny $\sigma$ has degree a prime power $\ell^e$ and is represented as a chain of $\ell$-isogenies.

To compute such a signature $\sigma$, the prover computes the ideal $J$ associated to the isogeny path given by the secret key, commitment and challenge. They then apply a SigningKLPT algorithm to $J$, to return a random equivalent ideal $I \sim J$ of norm $\ell^e$. Then, the prover converts $I$ into an isogeny. This last computation is very costly because $\text{nd}(I) = \ell^e$ is close to $p^{15/4}$, while the accessible torsion points have much smaller order. The method introduced in [10] (and later improved in [13]) requires to cut $J$ into several pieces in order to compute $\sigma$ as a chain of isogenies. This complicated mechanism is by far the bottleneck in the signing algorithm.

In order to avoid this costly ideal to isogeny translation in SQIsignHD, we shall no longer require $\sigma$ to have smooth degree and embed it in an isogeny of dimension 4 or 8 having smooth degree. This embedding will provide an efficient representation, and is faster to compute than the one in the original SQIsign. We shall also explain why this improves security in Section 5.

### 2.2 Embedding Isogenies in Higher Dimension with Kani's Lemma

In this section, we explain in more detail this idea of embedding isogenies in higher dimension. For that, we need a few definitions first.

**Definition 2 (d-isogeny).** Let $\alpha : (A, \lambda_A) \to (B, \lambda_B)$ be an isogeny between principally polarized abelian varieties. We say that $\alpha$ is a *d-isogeny* if $\hat{\alpha} \circ \lambda_B \circ \alpha = [d]\lambda_A$, where $\hat{\alpha} : \hat{B} \to \hat{A}$ is the dual isogeny of $\alpha$.

Equivalently, $\alpha$ is a *d-isogeny* if $\tilde{\alpha} \circ \alpha = [d]_A$, where $\tilde{\alpha} := \lambda_A^{-1} \circ \hat{\alpha} \circ \lambda_B$ is the dual isogeny of $\alpha$ with respect to the principal polarisations $\lambda_A$ and $\lambda_B$.
**Definition 3** (Isogeny diamond). Let $a, b \in \mathbb{N}^*$. An $(a, b)$-isogeny diamond is a commutative diagram of isogenies between principally polarized abelian varieties

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

where $\varphi$ and $\varphi'$ are $a$-isogenies and $\psi$ and $\psi'$ are $b$-isogenies.

**Lemma 4** (Kani). We consider an $(a, b)$-isogeny diamond as above, with $d := a + b$ prime to the characteristic of the base field of abelian varieties. Then, the isogeny $F : A \times B' \to B \times A'$ given in matrix notation by

$$F := \begin{pmatrix} \varphi & \tilde{\psi}' \\ -\psi & \tilde{\varphi}' \end{pmatrix}$$

is a $d$-isogeny with $d = a + b$, for the product polarisations. If a and b are coprime, the kernel of $F$ is

$$\ker(F) = \{(\tilde{\varphi}(x), \psi'(x)) \mid x \in B[d]\}.$$

This lemma has first been proved in [19, Theorem 2.3]. We also give a proof in [9, § E.1].

*Remark 2.1.* The existence of $F : A \times B' \to B \times A'$, implies the existence of $\varphi : A \to B$. We can recover $\varphi$ as $\pi \circ F \circ \iota$ where $\iota$ is the embedding morphism $x \in A \mapsto (x, 0) \in A \times B'$ and $\pi$ is the projection from $B \times A'$ to $B$. Hence, $F$ is an efficient representation of $\varphi$.

## 2.3 Application of Kani's Lemma to SQIsign

Let us now see how we propose to use Kani's Lemma (Lemma 4) in SQIsignHD.

**Signaling in Dimension 4.** The idea is to embed the signature $\sigma : E_1 \to E_2$ in an isogeny of dimension 4. We consider the 2-dimensional $q$-isogeny $\Sigma := \text{Diag}(\sigma, \sigma) : E_1^2 \to E_2^2$, and for $a_1, a_2 \in \mathbb{Z}$ and $i \in \{1, 2\}$ the $(a_1^2 + a_2^2)$-isogeny

$$\alpha_i := \begin{pmatrix} a_1 & a_2 \\ -a_2 & a_1 \end{pmatrix} \in \text{End}(E_i^2).$$

Then, we have an isogeny diamond

<figure><img src="image_3.png" /></figure>
**Definition 3** (Isogeny diamond). Let $a, b \in \mathbb{N}^*$. An $(a, b)$-isogeny diamond is a commutative diagram of isogenies between principally polarized abelian varieties

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

where $\varphi$ and $\varphi'$ are $a$-isogenies and $\psi$ and $\psi'$ are $b$-isogenies.

**Lemma 4** (Kani). We consider an $(a, b)$-isogeny diamond as above, with $d := a + b$ prime to the characteristic of the base field of abelian varieties. Then, the isogeny $F : A \times B' \to B \times A'$ given in matrix notation by

$$F := \begin{pmatrix} \varphi & \tilde{\psi}' \\ -\psi & \tilde{\varphi}' \end{pmatrix}$$

is a $d$-isogeny with $d = a + b$, for the product polarisations. If a and b are coprime, the kernel of $F$ is

$$\ker(F) = \{(\tilde{\varphi}(x), \psi'(x)) \mid x \in B[d]\}.$$

This lemma has first been proved in [19, Theorem 2.3]. We also give a proof in [9, § E.1].

*Remark 2.1.* The existence of $F : A \times B' \to B \times A'$, implies the existence of $\varphi : A \to B$. We can recover $\varphi$ as $\pi \circ F \circ \iota$ where $\iota$ is the embedding morphism $x \in A \mapsto (x, 0) \in A \times B'$ and $\pi$ is the projection from $B \times A'$ to $B$. Hence, $F$ is an efficient representation of $\varphi$.

## 2.3 Application of Kani's Lemma to SQIsign

Let us now see how we propose to use Kani's Lemma (Lemma 4) in SQIsignHD.

**Signaling in Dimension 4.** The idea is to embed the signature $\sigma : E_1 \to E_2$ in an isogeny of dimension 4. We consider the 2-dimensional $q$-isogeny $\Sigma := \text{Diag}(\sigma, \sigma) : E_1^2 \to E_2^2$, and for $a_1, a_2 \in \mathbb{Z}$ and $i \in \{1, 2\}$ the $(a_1^2 + a_2^2)$-isogeny

$$\alpha_i := \begin{pmatrix} a_1 & a_2 \\ -a_2 & a_1 \end{pmatrix} \in \text{End}(E_i^2).$$

Then, we have an isogeny diamond

<figure><img src="image_4.png" /></figure>
yielding an N-isogeny (with $N := q + a_1^2 + a_2^2$):

$$F := \begin{pmatrix} \alpha_1 & \tilde{\Sigma} \\ -\Sigma & \tilde{\alpha}_2 \end{pmatrix} \in \mathrm{End}(E_1^2 \times E_2^2).$$

**Notation 5.** We shall denote $F(\sigma, a_1, a_2)$ when we want to specify the dependence of $F$ on $\sigma, a_1, a_2$.

We choose the parameters $q, a_1, a_2$, so that $N = \ell^e$, with $\ell$ a small prime and $e \in \mathbb{N}^*$ big enough. Provided that $q$ and $\ell$ are coprime, we know that

$$\ker(F) = \{(\tilde{\alpha}_1(P), \Sigma(P)) \mid P \in E_1^2[\ell^e]\}, \quad (1)$$

by Lemma 4. Then, knowing $\ker(F)$ we can compute $F$ as an $\ell$-isogeny chain and obtain an efficient representation of $\sigma$, as explained in Remark 2.1.

It follows that our idea requires to compute $\ker(F)$, which becomes easy once we know how to evaluate $\sigma$ on $E_1[\ell^e]$, by formula 1. The idea is to use the alternate isogeny path $\varphi \circ \tau \circ \tilde{\psi} : E_1 \to E_2$. Since the signature requires to compute the three isogenies $\varphi, \psi, \tau$, it will not cost too much to use them in order to evaluate $\sigma$. There are several technicalities to make it work in practice (such as to making sure that this alternate path has degree prime to $\ell$) but it is manageable (see [9, § A.5]).

Computing such a representation for the signature is simpler than in the original SQLsign protocol. This shifts the main computation effort to the verification, where the actual isogeny in dimension 4 must be computed.

**Parameters.** Even though we no longer impose $q = \deg(\sigma)$ to be smooth, we still impose conditions on $q$ to make it work. We shall need $\ell^e - q$ to be a prime congruent to 1 modulo 4 in order to decompose it easily as a sum of two squares $\ell^e - q = a_1^2 + a_2^2$ by Cornacchia's algorithm [6]. This choice of $q$ ensures its coprimality with $\ell$, as required to compute $\ker(F)$. The exponent $e$ is fixed to be as small as possible so that there always exists an isogeny $\sigma : E_1 \to E_2$ of $\ell^e$-good degree in the sense of the following definition. In practice, the smallest values for $q$ are close to $\sqrt{p}$ (Section 4.2) so $\ell^e$ will be slightly bigger than $\sqrt{p}$.

**Definition 6.** We say that an integer $q$ is $\ell^e$-good when $\ell^e - q$ is a prime number congruent to 1 modulo 4.<fnref n="6" />

**Remark 7** (The issue of the signature distribution). Those restrictions on the degree $q$ impact the distribution of signatures. The bound $\ell^e \simeq \sqrt{p}$ is also restrictive (see [9, Theorem 42]). For that reason, we need some plausible heuristic assumptions to prove the zero-knowledge property of our scheme. This can be

<footnote n="6">⁶ One could improve slightly the scheme by defining $\ell^e$-good integers as integers $q$ such that $\ell^e - q = sq'$, with $s$ a smooth integer whose prime factors are all congruent to 1 modulo 4 and $q'$ is a prime congruent to 1 modulo 4. Indeed, all we really need is that $\ell^e - q$ is easy to factor so Cornacchia's algorithm can be applied efficiently. This alternate definition would improve a bit the search for $\ell^e$-good integer, but we went for the simplest definition.</footnote>
yielding an N-isogeny (with $N := q + a_1^2 + a_2^2$):

$$F := \begin{pmatrix} \alpha_1 & \tilde{\Sigma} \\ -\Sigma & \tilde{\alpha}_2 \end{pmatrix} \in \mathrm{End}(E_1^2 \times E_2^2).$$

**Notation 5.** We shall denote $F(\sigma, a_1, a_2)$ when we want to specify the dependence of $F$ on $\sigma, a_1, a_2$.

We choose the parameters $q, a_1, a_2$, so that $N = \ell^e$, with $\ell$ a small prime and $e \in \mathbb{N}^*$ big enough. Provided that $q$ and $\ell$ are coprime, we know that

$$\ker(F) = \{(\tilde{\alpha}_1(P), \Sigma(P)) \mid P \in E_1^2[\ell^e]\}, \quad (1)$$

by Lemma 4. Then, knowing $\ker(F)$ we can compute $F$ as an $\ell$-isogeny chain and obtain an efficient representation of $\sigma$, as explained in Remark 2.1.

It follows that our idea requires to compute $\ker(F)$, which becomes easy once we know how to evaluate $\sigma$ on $E_1[\ell^e]$, by formula 1. The idea is to use the alternate isogeny path $\varphi \circ \tau \circ \tilde{\psi} : E_1 \to E_2$. Since the signature requires to compute the three isogenies $\varphi, \psi, \tau$, it will not cost too much to use them in order to evaluate $\sigma$. There are several technicalities to make it work in practice (such as to making sure that this alternate path has degree prime to $\ell$) but it is manageable (see [9, § A.5]).

Computing such a representation for the signature is simpler than in the original SQLsign protocol. This shifts the main computation effort to the verification, where the actual isogeny in dimension 4 must be computed.

**Parameters.** Even though we no longer impose $q = \deg(\sigma)$ to be smooth, we still impose conditions on $q$ to make it work. We shall need $\ell^e - q$ to be a prime congruent to 1 modulo 4 in order to decompose it easily as a sum of two squares $\ell^e - q = a_1^2 + a_2^2$ by Cornacchia's algorithm [6]. This choice of $q$ ensures its coprimality with $\ell$, as required to compute $\ker(F)$. The exponent $e$ is fixed to be as small as possible so that there always exists an isogeny $\sigma : E_1 \to E_2$ of $\ell^e$-good degree in the sense of the following definition. In practice, the smallest values for $q$ are close to $\sqrt{p}$ (Section 4.2) so $\ell^e$ will be slightly bigger than $\sqrt{p}$.

**Definition 6.** We say that an integer $q$ is $\ell^e$-good when $\ell^e - q$ is a prime number congruent to 1 modulo 4.<fnref n="6" />

**Remark 7** (The issue of the signature distribution). Those restrictions on the degree $q$ impact the distribution of signatures. The bound $\ell^e \simeq \sqrt{p}$ is also restrictive (see [9, Theorem 42]). For that reason, we need some plausible heuristic assumptions to prove the zero-knowledge property of our scheme. This can be

<footnote n="6">⁶ One could improve slightly the scheme by defining $\ell^e$-good integers as integers $q$ such that $\ell^e - q = sq'$, with $s$ a smooth integer whose prime factors are all congruent to 1 modulo 4 and $q'$ is a prime congruent to 1 modulo 4. Indeed, all we really need is that $\ell^e - q$ is easy to factor so Cornacchia's algorithm can be applied efficiently. This alternate definition would improve a bit the search for $\ell^e$-good integer, but we went for the simplest definition.</footnote>
fixed by going to dimension 8 as long as $q < \ell^e$ and $\ell^e = \Omega(p^2)$. This way, we shall obtain a uniform distribution of signatures and a provably zero-knowledge scheme which is the purpose of our scheme in dimension 8 that we present below.

**Signings in Dimension 8.** By Lagrange's four square theorem [21], if $q < \ell^e$, there always exists $a_1, \dots, a_4 \in \mathbb{Z}$ such that $q + a_1^2 + \dots + a_4^2 = \ell^e$. We can find such a decomposition in polynomial time in $e$ with Rabin and Shallit's algorithm [31] improved by Pollack and Treviño [30]. We then consider the endomorphisms

$$ \alpha_i := \begin{pmatrix} a_1 & -a_2 & -a_3 & -a_4 \\ a_2 & a_1 & a_4 & -a_3 \\ a_3 & -a_4 & a_1 & a_2 \\ a_4 & a_3 & -a_2 & a_1 \end{pmatrix} \in \mathrm{End}(E_i^4), $$

for $i \in \{1, 2\}$, which are $(a_1^2 + \dots + a_4^2)$-isogenies, and the $q$-isogeny $\Sigma := \mathrm{Diag}(\sigma, \dots, \sigma) : E_1^4 \to E_2^4$. As previously, by Kani's lemma, we have the $\ell^e$-isogeny

$$ F := \begin{pmatrix} \alpha_1 & \tilde{\Sigma} \\ -\Sigma & \tilde{\alpha}_2 \end{pmatrix} \in \mathrm{End}(E_1^4 \times E_2^4). $$

Similarly to dimension 4, we write $F(\sigma, a_1, \dots, a_4)$ to highlight the dependence of $F$ on $\sigma, a_1, \dots, a_4$. To ensure the uniformity of the response, in dimension 8 we no longer restrict to the case $q$ prime to $\ell$. This means we might have to embed in dimension 8 a factor of $\sigma$ of degree prime to $\ell$ instead of $\sigma$ (see [9, § C] for details). As in dimension 4, can compute $\ker(F)$ by evaluating $\sigma$ on $E_1[\ell^e]$ and then compute $F$ as an $\ell$-isogeny chain. This way, we can represent any signature isogeny $\sigma$ of degree $q < \ell^e$, with the implications on the security proof that we mentioned before. However, computing isogenies in dimension 8 is much more costly than in dimension 4 (though, still polynomial), so we do not recommend to use this representation and only propose it in the alternate version RigorousSQIsignHD.

More generally, the same techniques allow, given an ideal $I$ representing an isogeny of degree $q$, to give an efficient representation of the isogeny $\sigma$ associated to $I$ by the Deuring correspondence, even when $q$ is not smooth (see [9, § A.3-4]).

**Why not Signing in Dimension 2?** The cost of computing an isogeny grows exponentially with the dimension [24, 25, 26]. For that reason, finding an efficient representation in dimension 2 could be fruitful for SQIsignHD. On the other hand, the higher the dimension, the lesser the constraints on the isogeny $\sigma$. We have already seen that going from dimension 4 to 8 relaxes the constraints on $q = \mathrm{deg}(\sigma)$. Unsurprisingly, the constraints on $\sigma$ are tighter in dimension 2. So far, under those constraints, we have failed to provide an efficient and secure version of SQIsignHD. We leave this question to future works.

## 3 Key Generation, Commitment and Challenge

To evaluate $\sigma$ on the $\ell^e$-torsion, as required for the response computation, we apply the EvalTorsion$_{\ell^e}$ procedure ([9, § A.5]) which uses the alternate path
fixed by going to dimension 8 as long as $q < \ell^e$ and $\ell^e = \Omega(p^2)$. This way, we shall obtain a uniform distribution of signatures and a provably zero-knowledge scheme which is the purpose of our scheme in dimension 8 that we present below.

**Signings in Dimension 8.** By Lagrange's four square theorem [21], if $q < \ell^e$, there always exists $a_1, \dots, a_4 \in \mathbb{Z}$ such that $q + a_1^2 + \dots + a_4^2 = \ell^e$. We can find such a decomposition in polynomial time in $e$ with Rabin and Shallit's algorithm [31] improved by Pollack and Treviño [30]. We then consider the endomorphisms

$$ \alpha_i := \begin{pmatrix} a_1 & -a_2 & -a_3 & -a_4 \\ a_2 & a_1 & a_4 & -a_3 \\ a_3 & -a_4 & a_1 & a_2 \\ a_4 & a_3 & -a_2 & a_1 \end{pmatrix} \in \mathrm{End}(E_i^4), $$

for $i \in \{1, 2\}$, which are $(a_1^2 + \dots + a_4^2)$-isogenies, and the $q$-isogeny $\Sigma := \mathrm{Diag}(\sigma, \dots, \sigma) : E_1^4 \to E_2^4$. As previously, by Kani's lemma, we have the $\ell^e$-isogeny

$$ F := \begin{pmatrix} \alpha_1 & \tilde{\Sigma} \\ -\Sigma & \tilde{\alpha}_2 \end{pmatrix} \in \mathrm{End}(E_1^4 \times E_2^4). $$

Similarly to dimension 4, we write $F(\sigma, a_1, \dots, a_4)$ to highlight the dependence of $F$ on $\sigma, a_1, \dots, a_4$. To ensure the uniformity of the response, in dimension 8 we no longer restrict to the case $q$ prime to $\ell$. This means we might have to embed in dimension 8 a factor of $\sigma$ of degree prime to $\ell$ instead of $\sigma$ (see [9, § C] for details). As in dimension 4, can compute $\ker(F)$ by evaluating $\sigma$ on $E_1[\ell^e]$ and then compute $F$ as an $\ell$-isogeny chain. This way, we can represent any signature isogeny $\sigma$ of degree $q < \ell^e$, with the implications on the security proof that we mentioned before. However, computing isogenies in dimension 8 is much more costly than in dimension 4 (though, still polynomial), so we do not recommend to use this representation and only propose it in the alternate version RigorousSQIsignHD.

More generally, the same techniques allow, given an ideal $I$ representing an isogeny of degree $q$, to give an efficient representation of the isogeny $\sigma$ associated to $I$ by the Deuring correspondence, even when $q$ is not smooth (see [9, § A.3-4]).

**Why not Signing in Dimension 2?** The cost of computing an isogeny grows exponentially with the dimension [24, 25, 26]. For that reason, finding an efficient representation in dimension 2 could be fruitful for SQIsignHD. On the other hand, the higher the dimension, the lesser the constraints on the isogeny $\sigma$. We have already seen that going from dimension 4 to 8 relaxes the constraints on $q = \mathrm{deg}(\sigma)$. Unsurprisingly, the constraints on $\sigma$ are tighter in dimension 2. So far, under those constraints, we have failed to provide an efficient and secure version of SQIsignHD. We leave this question to future works.

## 3 Key Generation, Commitment and Challenge

To evaluate $\sigma$ on the $\ell^e$-torsion, as required for the response computation, we apply the EvalTorsion$_{\ell^e}$ procedure ([9, § A.5]) which uses the alternate path
$\varphi \circ \tau \circ \hat{\psi} : E_1 \to E_2$ formed by the challenge $\varphi$, secret key $\tau$ and commitment isogeny $\psi$ along with their ideals $I_\varphi, I_\tau$ and $I_\psi$. These ideals are also necessary to compute the ideal $I_\sigma$.

For the EvalTorsion$_{\ell f}$ procedure to work, the degrees of $\varphi, \tau$ and $\psi$ must be prime to $\ell$. The ideals $I_\psi$ and $I_\tau$ can be generated directly along with $\psi$ and $\tau$. However, the computation of $I_\varphi$ uses the procedure IsogenyToldeal ([9, § A.4]) which requires a precomputation in the key generation phase. Namely, the prover will need to generate an alternate secret path $\tau' : E_0 \to E_A$ of degree $D_{\tau'}$ prime to $D_\varphi$ along with the secret key $\tau : E_0 \to E_A$. This will be explained in section 3.3.

## 3.1 Accessible Torsion and Choice of the Prime Characteristic

The choice of $p$ is usually made to provide enough accessible torsion for our isogeny computations. In FastSQLisignHD, we can choose $p = c\ell^f\ell'^{f'} - 1$ with $\ell \neq \ell'$ two primes, $c \in \mathbb{N}^*$ small and $\ell f \simeq \ell'^{f'} \simeq \sqrt{p}$, as in SIDH [18]. In practice, $\ell = 2$ and $\ell' = 3$ are the best choice.

We then require $D_\tau = D_\psi = \ell'^{2f'}$, $D_\varphi = \ell'^{f'}$ and $D_{\tau'} = \ell'^{2f'}$. This choice ensures that $D_\tau, D_\psi$ and $D_\varphi$ are prime to $\ell$ and that $D_{\tau'}$ is prime to $D_\varphi$, as needed. We also have $D_\tau, D_\psi, D_{\tau'} = \Theta(p)$, which guarantees (at least heuristically) that the public key $E_A$ and the commitment $E_1$ are computationally indistinguishable from a uniformly random supersingular elliptic curve – which is essential to the security of FastSQLisignHD.

This choice of prime also provides enough accessible torsion to compute the $\ell^e$-isogeny $F$ representing the response $\sigma$ in dimension 4, where $\ell^e > q := D_\sigma$. In fact, we even have much more than the minimum requirement since it will be enough to have $2f \ge e + 4$ (so $\ell^f = \Omega(p^{1/4})$) as will be explained in Sections 4.3 and 4.4 and Remark 4.2. This freedom is welcome anyway because it allows us to take $\ell^e$ slightly bigger than $\sqrt{p}$ to make sure that we can always find an ideal $I$ of $\ell^e$-good norm $q < \ell^e$ (see Section 4.2).

We finally discuss the security requirements regarding the size of $p$. The best known classical key recovery attacks are the meet-in-the-middle algorithm or the general Delfs and Galbraith attack [11] in the supersingular isogeny graph which both have a complexity in $\tilde{O}(\sqrt{p})$. Using Grover's algorithm [16], we reach a quantum complexity of $\tilde{O}(p^{1/4})$. Hence, to ensure a classical security level of $\lambda$ bits and a quantum security level of $\lambda/2$ bits, we need to take $p = \Theta(2^{2\lambda})$, as in the original version of SQIsign [10].

We give below some concrete values of primes for NIST levels 1, 3 and 5.

<table><thead><tr><td>NIST security level</td><td>Security parameter λ (bits)</td><td>Prime p</td></tr></thead><tbody><tr><td>NIST-I</td><td>128</td><td>13 · 2<sup>126</sup> · 3<sup>78</sup> − 1</td></tr><tr><td>NIST-III</td><td>192</td><td>5 · 2<sup>193</sup> · 3<sup>122</sup> − 1</td></tr><tr><td>NIST-V</td><td>256</td><td>11 · 2<sup>257</sup> · 3<sup>163</sup> − 1</td></tr></tbody></table>

<footnote n="7">⁷ Actually, we will not have exactly $D_\tau = D_\psi = \ell'^{2f'}$ but $D_\tau$ and $D_\psi$ will be divisors of $\ell'^{2f'}$ close to $\ell'^{2f'}$. It will be the same for $D_{\psi'}$ (see Algorithm 1). We assume equality to simplify the exposition.</footnote>
$\varphi \circ \tau \circ \hat{\psi} : E_1 \to E_2$ formed by the challenge $\varphi$, secret key $\tau$ and commitment isogeny $\psi$ along with their ideals $I_\varphi, I_\tau$ and $I_\psi$. These ideals are also necessary to compute the ideal $I_\sigma$.

For the EvalTorsion$_{\ell f}$ procedure to work, the degrees of $\varphi, \tau$ and $\psi$ must be prime to $\ell$. The ideals $I_\psi$ and $I_\tau$ can be generated directly along with $\psi$ and $\tau$. However, the computation of $I_\varphi$ uses the procedure IsogenyToldeal ([9, § A.4]) which requires a precomputation in the key generation phase. Namely, the prover will need to generate an alternate secret path $\tau' : E_0 \to E_A$ of degree $D_{\tau'}$ prime to $D_\varphi$ along with the secret key $\tau : E_0 \to E_A$. This will be explained in section 3.3.

## 3.1 Accessible Torsion and Choice of the Prime Characteristic

The choice of $p$ is usually made to provide enough accessible torsion for our isogeny computations. In FastSQLisignHD, we can choose $p = c\ell^f\ell'^{f'} - 1$ with $\ell \neq \ell'$ two primes, $c \in \mathbb{N}^*$ small and $\ell f \simeq \ell'^{f'} \simeq \sqrt{p}$, as in SIDH [18]. In practice, $\ell = 2$ and $\ell' = 3$ are the best choice.

We then require $D_\tau = D_\psi = \ell'^{2f'}$, $D_\varphi = \ell'^{f'}$ and $D_{\tau'} = \ell'^{2f'}$. This choice ensures that $D_\tau, D_\psi$ and $D_\varphi$ are prime to $\ell$ and that $D_{\tau'}$ is prime to $D_\varphi$, as needed. We also have $D_\tau, D_\psi, D_{\tau'} = \Theta(p)$, which guarantees (at least heuristically) that the public key $E_A$ and the commitment $E_1$ are computationally indistinguishable from a uniformly random supersingular elliptic curve – which is essential to the security of FastSQLisignHD.

This choice of prime also provides enough accessible torsion to compute the $\ell^e$-isogeny $F$ representing the response $\sigma$ in dimension 4, where $\ell^e > q := D_\sigma$. In fact, we even have much more than the minimum requirement since it will be enough to have $2f \ge e + 4$ (so $\ell^f = \Omega(p^{1/4})$) as will be explained in Sections 4.3 and 4.4 and Remark 4.2. This freedom is welcome anyway because it allows us to take $\ell^e$ slightly bigger than $\sqrt{p}$ to make sure that we can always find an ideal $I$ of $\ell^e$-good norm $q < \ell^e$ (see Section 4.2).

We finally discuss the security requirements regarding the size of $p$. The best known classical key recovery attacks are the meet-in-the-middle algorithm or the general Delfs and Galbraith attack [11] in the supersingular isogeny graph which both have a complexity in $\tilde{O}(\sqrt{p})$. Using Grover's algorithm [16], we reach a quantum complexity of $\tilde{O}(p^{1/4})$. Hence, to ensure a classical security level of $\lambda$ bits and a quantum security level of $\lambda/2$ bits, we need to take $p = \Theta(2^{2\lambda})$, as in the original version of SQIsign [10].

We give below some concrete values of primes for NIST levels 1, 3 and 5.

<table><thead><tr><td>NIST security level</td><td>Security parameter λ (bits)</td><td>Prime p</td></tr></thead><tbody><tr><td>NIST-I</td><td>128</td><td>13 · 2<sup>126</sup> · 3<sup>78</sup> − 1</td></tr><tr><td>NIST-III</td><td>192</td><td>5 · 2<sup>193</sup> · 3<sup>122</sup> − 1</td></tr><tr><td>NIST-V</td><td>256</td><td>11 · 2<sup>257</sup> · 3<sup>163</sup> − 1</td></tr></tbody></table>

<footnote n="7">⁷ Actually, we will not have exactly $D_\tau = D_\psi = \ell'^{2f'}$ but $D_\tau$ and $D_\psi$ will be divisors of $\ell'^{2f'}$ close to $\ell'^{2f'}$. It will be the same for $D_{\psi'}$ (see Algorithm 1). We assume equality to simplify the exposition.</footnote>
## 3.2 Challenge Generation

To ensure a soundness security level of $\lambda$ bits, the challenge space needs to have size at least $2^{\lambda} \approx \sqrt{p}$. We also need the challenge degree $D_{\varphi}$ to be prime to $\ell$ to be able to push the points of order $\ell^f$ through $\psi$ during the signing procedure. The challenge generation procedure $\text{Challenge}_{D_{\varphi}}$ is the same in the fast and provably secure challenge generation procedure. It simply generates a random element $P \in E_A$ of order $D_{\varphi}$ and computes $\varphi$ of kernel $\langle P \rangle$. Only the degree $D_{\varphi}$ changes; in FastSQIsignHD, we take $D_{\varphi} = \ell^{f'}$.

## 3.3 Fast Key Generation and Commitment

We now present FastDoublePath (Algorithm 1) the main algorithmic block for the key generation and commitment of FastSQIsignHD. The goal of this algorithm is to generate two isogeny paths $\phi, \phi' : E_0 \to E$ of degree dividing $\ell^{2f} \approx p$ and $\ell^{2f'} \approx p$ respectively, computing the kernel ideals $I_{\phi}$ and $I_{\phi'}$ along the way. This algorithm is directly applicable to the key generation procedure FastKeyGen where we need to generate a double path to be able to compute the challenge kernel ideal $I_{\varphi}$ (using [9, § A.4] and an $\ell$-isogeny path of degree prime to $\ell'$) in order to apply the $\text{EvalTorsion}_{\ell f}$ procedure (with the $\ell'$-isogeny path of degree prime to $\ell'$).

For the commitment FastCommit, we only need the $\ell$-isogeny path $\psi = \phi'$ but the algorithm is essentially the same, except that we do not compute $\phi$ and $I_{\phi}$ completely. This is the reason why we changed the side of the challenge: to save time in the commitment phase. Had we started the challenge $\varphi$ from $E_1$ as in SQISign, we would have needed to compute a double isogeny path in the commitment phase. Instead, we precompute this double path during the key generation.

Note that generating isogenies of degree $\approx p$ is essential for security reasons, in order to ensure that the codomain $E$ is heuristically close to a random elliptic curve in the supersingular isogeny graph. To compute such long isogeny paths, however, we are limited by the accessible torsion in $E_0$ (we have access to the $\ell^f \ell^{f'}$-torsion only). To circumvent this difficulty, we use pushforward isogenies, as defined in [10, § 4.1].

**Definition 8.** Let $\rho : E \to E_1$ and $\theta : E \to E_2$ be two isogenies with coprime degree. The pushforward of $\rho$ via $\theta$, denoted by $\rho' := [\theta]_*\rho$ is an isogeny $E_2 \to E_3$ satisfying $\ker(\rho') = \theta(\ker(\rho))$.

**Remark 9.** $\theta$ and $\rho$ satisfy $[\theta]_*\rho \circ \theta = [\rho]_*\theta \circ \rho$. In particular, $[\theta]_*\rho$ and $[\rho]_*\theta$ have the same codomain. If $I$ and $J$ are the ideals associated to $\rho$ and $\theta$ respectively via the Deuring correspondence, we denote by $[J]_*I$ the pushforward ideal associated to $[\theta]_*\rho$. By [10, Lemma 3], the ideal $[J]_*I$ can be computed as follows: $[J]_*I = J^{-1} \cdot (I \cap J)$.
## 3.2 Challenge Generation

To ensure a soundness security level of $\lambda$ bits, the challenge space needs to have size at least $2^{\lambda} \approx \sqrt{p}$. We also need the challenge degree $D_{\varphi}$ to be prime to $\ell$ to be able to push the points of order $\ell^f$ through $\psi$ during the signing procedure. The challenge generation procedure $\text{Challenge}_{D_{\varphi}}$ is the same in the fast and provably secure challenge generation procedure. It simply generates a random element $P \in E_A$ of order $D_{\varphi}$ and computes $\varphi$ of kernel $\langle P \rangle$. Only the degree $D_{\varphi}$ changes; in FastSQIsignHD, we take $D_{\varphi} = \ell^{f'}$.

## 3.3 Fast Key Generation and Commitment

We now present FastDoublePath (Algorithm 1) the main algorithmic block for the key generation and commitment of FastSQIsignHD. The goal of this algorithm is to generate two isogeny paths $\phi, \phi' : E_0 \to E$ of degree dividing $\ell^{2f} \approx p$ and $\ell^{2f'} \approx p$ respectively, computing the kernel ideals $I_{\phi}$ and $I_{\phi'}$ along the way. This algorithm is directly applicable to the key generation procedure FastKeyGen where we need to generate a double path to be able to compute the challenge kernel ideal $I_{\varphi}$ (using [9, § A.4] and an $\ell$-isogeny path of degree prime to $\ell'$) in order to apply the $\text{EvalTorsion}_{\ell f}$ procedure (with the $\ell'$-isogeny path of degree prime to $\ell'$).

For the commitment FastCommit, we only need the $\ell$-isogeny path $\psi = \phi'$ but the algorithm is essentially the same, except that we do not compute $\phi$ and $I_{\phi}$ completely. This is the reason why we changed the side of the challenge: to save time in the commitment phase. Had we started the challenge $\varphi$ from $E_1$ as in SQISign, we would have needed to compute a double isogeny path in the commitment phase. Instead, we precompute this double path during the key generation.

Note that generating isogenies of degree $\approx p$ is essential for security reasons, in order to ensure that the codomain $E$ is heuristically close to a random elliptic curve in the supersingular isogeny graph. To compute such long isogeny paths, however, we are limited by the accessible torsion in $E_0$ (we have access to the $\ell^f \ell^{f'}$-torsion only). To circumvent this difficulty, we use pushforward isogenies, as defined in [10, § 4.1].

**Definition 8.** Let $\rho : E \to E_1$ and $\theta : E \to E_2$ be two isogenies with coprime degree. The pushforward of $\rho$ via $\theta$, denoted by $\rho' := [\theta]_*\rho$ is an isogeny $E_2 \to E_3$ satisfying $\ker(\rho') = \theta(\ker(\rho))$.

**Remark 9.** $\theta$ and $\rho$ satisfy $[\theta]_*\rho \circ \theta = [\rho]_*\theta \circ \rho$. In particular, $[\theta]_*\rho$ and $[\rho]_*\theta$ have the same codomain. If $I$ and $J$ are the ideals associated to $\rho$ and $\theta$ respectively via the Deuring correspondence, we denote by $[J]_*I$ the pushforward ideal associated to $[\theta]_*\rho$. By [10, Lemma 3], the ideal $[J]_*I$ can be computed as follows: $[J]_*I = J^{-1} \cdot (I \cap J)$.
**The Algorithm.** The idea is to construct the isogenies $\phi$ and $\phi'$ (of degree dividing $\ell^{2f}$ and $\ell'^{2f'}$ respectively) by finding an endomorphism $\gamma$ of degree dividing $\ell^{2f}\ell'^{2f'}$, and factoring it as $\gamma = \hat{\phi}' \circ \phi$. Since $\ell^{2f}\ell'^{2f'} = \Theta(p^2) = \omega(p)$, we can easily find $\gamma \in \mathcal{O}_0$ non divisible by $\ell$ or $\ell'$, of norm $\text{nd}(\gamma) = \ell^{2g}\ell'^{2g'}$ with $g \le f$ close to $f$ and $g' \le f'$ close to $f'$, using [22, Algorithm 4].

Since $\ell^{2f}$ (and $\ell'^{2f'}$) exceeds the available torsion, some “pushforward gymnastics” is required to compute the factorisation. We thus decompose $\varepsilon(\gamma) = \hat{\rho}_2 \circ \rho_1$ where $\rho_1$ and $\rho_2$ are isogenies $E_0 \to E'$ of degree $\ell^g \ell'^{g'}$ and $\varepsilon$ is an isomorphism $\mathcal{O}_0 \xrightarrow{\sim} \text{End}(E_0)$. $\varepsilon(\gamma)$ being cyclic, according to the following lemma, $\rho_1$ and its associated kernel ideal $K_1$ are given by:

$$ \ker(\rho_1) = \ker(\varepsilon(\gamma)) \cap E_0[\ell^g \ell'^{g'}] \quad \text{and} \quad K_1 = \mathcal{O}_0\gamma + \mathcal{O}_0\ell^g \ell'^{g'}. $$

Similarly, $\ker(\rho_2) = \ker(\varepsilon(\gamma)) \cap E_0[\ell^g \ell'^{g'}]$ and the associated kernel ideal is $K_2 = \mathcal{O}_0\bar{\gamma} + \mathcal{O}_0\ell^g \ell'^{g'}$.

**Lemma 10.** Let $\rho : E \to E'$ be a cyclic isogeny decomposed into $\rho = \theta \circ \rho_1$. Then we have:

(i) $\ker(\rho_1) = \ker(\rho) \cap E[d_1]$ with $d_1 := \text{deg}(\rho_1)$.

(ii) If $\rho$ is a cyclic endomorphism ($E = E'$), then the kernel ideal of $\rho_1$ is $K_1 = \mathcal{O}\rho + \mathcal{O}d_1$, where $\mathcal{O} := \text{End}(E)$.

*Proof.* Since $\rho = \theta \circ \rho_1$ and $\text{deg}(\rho_1) = d_1$, we clearly have $\ker(\rho_1) \subseteq \ker(\rho) \cap E[d_1]$. Since $\rho$ is cyclic, there exists a generator $P \in E$ of $\ker(\rho)$ of order $d := \text{deg}(\rho)$ and we have $\ker(\rho) \cap E[d_1] = \langle[d/d_1]P\rangle$, where $[d/d_1]P$ has order $d_1$, so we conclude that the inclusion is an equality by cardinality, since $\rho_1$ is separable. (i) follows.

To prove (ii), we remark that $E[\mathcal{O}\rho + \mathcal{O}d_1] = E[\rho] \cap E[d_1] = \ker(\rho_1)$, where the last equality was proved in (i). Then, we conclude that $K_1 = \mathcal{O}\rho + \mathcal{O}d_1$ by injectivity of the Deuring correspondence between left $\mathcal{O}$-ideals and isogenies of domain $E$ [40, Proposition 42.2.16]. This completes the proof. $\square$

Then, we can decompose $\rho_1$ and $\rho_2$ into $\rho_1 = \hat{\theta}'_1 \circ \theta_1$ and $\rho_2 = \hat{\theta}_2 \circ \theta'_2$ where the $\theta_i$ are isogenies of degree $\ell^g$ and the $\theta'_i$ are isogenies of degree $\ell'^{g'}$ for $i \in \{1, 2\}$, as in the following diagram:

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

The pushforward isogenies $[\theta'_1]_*\theta_2$ and $[\theta_2]_*\theta'_1$ have the same codomain $E$ and degree $\ell^g$ and $\ell'^{g'}$ respectively. Hence, $\phi := [\theta'_1]_*\theta_2 \circ \theta_1$ and $\phi' := [\theta_2]_*\theta'_1 \circ \theta'_2$ are isogenies $E_0 \to E$ of desired degrees $\ell^{2g}$ and $\ell^{2g'}$ respectively. By Lemma
**The Algorithm.** The idea is to construct the isogenies $\phi$ and $\phi'$ (of degree dividing $\ell^{2f}$ and $\ell'^{2f'}$ respectively) by finding an endomorphism $\gamma$ of degree dividing $\ell^{2f}\ell'^{2f'}$, and factoring it as $\gamma = \hat{\phi}' \circ \phi$. Since $\ell^{2f}\ell'^{2f'} = \Theta(p^2) = \omega(p)$, we can easily find $\gamma \in \mathcal{O}_0$ non divisible by $\ell$ or $\ell'$, of norm $\text{nd}(\gamma) = \ell^{2g}\ell'^{2g'}$ with $g \le f$ close to $f$ and $g' \le f'$ close to $f'$, using [22, Algorithm 4].

Since $\ell^{2f}$ (and $\ell'^{2f'}$) exceeds the available torsion, some “pushforward gymnastics” is required to compute the factorisation. We thus decompose $\varepsilon(\gamma) = \hat{\rho}_2 \circ \rho_1$ where $\rho_1$ and $\rho_2$ are isogenies $E_0 \to E'$ of degree $\ell^g \ell'^{g'}$ and $\varepsilon$ is an isomorphism $\mathcal{O}_0 \xrightarrow{\sim} \text{End}(E_0)$. $\varepsilon(\gamma)$ being cyclic, according to the following lemma, $\rho_1$ and its associated kernel ideal $K_1$ are given by:

$$ \ker(\rho_1) = \ker(\varepsilon(\gamma)) \cap E_0[\ell^g \ell'^{g'}] \quad \text{and} \quad K_1 = \mathcal{O}_0\gamma + \mathcal{O}_0\ell^g \ell'^{g'}. $$

Similarly, $\ker(\rho_2) = \ker(\varepsilon(\gamma)) \cap E_0[\ell^g \ell'^{g'}]$ and the associated kernel ideal is $K_2 = \mathcal{O}_0\bar{\gamma} + \mathcal{O}_0\ell^g \ell'^{g'}$.

**Lemma 10.** Let $\rho : E \to E'$ be a cyclic isogeny decomposed into $\rho = \theta \circ \rho_1$. Then we have:

(i) $\ker(\rho_1) = \ker(\rho) \cap E[d_1]$ with $d_1 := \text{deg}(\rho_1)$.

(ii) If $\rho$ is a cyclic endomorphism ($E = E'$), then the kernel ideal of $\rho_1$ is $K_1 = \mathcal{O}\rho + \mathcal{O}d_1$, where $\mathcal{O} := \text{End}(E)$.

*Proof.* Since $\rho = \theta \circ \rho_1$ and $\text{deg}(\rho_1) = d_1$, we clearly have $\ker(\rho_1) \subseteq \ker(\rho) \cap E[d_1]$. Since $\rho$ is cyclic, there exists a generator $P \in E$ of $\ker(\rho)$ of order $d := \text{deg}(\rho)$ and we have $\ker(\rho) \cap E[d_1] = \langle[d/d_1]P\rangle$, where $[d/d_1]P$ has order $d_1$, so we conclude that the inclusion is an equality by cardinality, since $\rho_1$ is separable. (i) follows.

To prove (ii), we remark that $E[\mathcal{O}\rho + \mathcal{O}d_1] = E[\rho] \cap E[d_1] = \ker(\rho_1)$, where the last equality was proved in (i). Then, we conclude that $K_1 = \mathcal{O}\rho + \mathcal{O}d_1$ by injectivity of the Deuring correspondence between left $\mathcal{O}$-ideals and isogenies of domain $E$ [40, Proposition 42.2.16]. This completes the proof. $\square$

Then, we can decompose $\rho_1$ and $\rho_2$ into $\rho_1 = \theta'_1 \circ \theta_1$ and $\rho_2 = \theta'_2 \circ \theta'_2$ where the $\theta_i$ are isogenies of degree $\ell^g$ and the $\theta'_i$ are isogenies of degree $\ell'^{g'}$ for $i \in \{1, 2\}$, as in the following diagram:

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

The pushforward isogenies $[\theta'_1]_*\theta_2$ and $[\theta_2]_*\theta'_1$ have the same codomain $E$ and degree $\ell^g$ and $\ell'^{g'}$ respectively. Hence, $\phi := [\theta'_1]_*\theta_2 \circ \theta_1$ and $\phi' := [\theta_2]_*\theta'_1 \circ \theta'_2$ are isogenies $E_0 \to E$ of desired degrees $\ell^{2g}$ and $\ell^{2g'}$ respectively. By Lemma
<caption>**Algorithm 1: FastDoublePath<sub>ℓf,ℓ'f'</sub>**</caption>

**Data:** A basis of $O_0$ and an isomorphism $\varepsilon: O_0 \xrightarrow{\sim} \text{End}(E_0)$.

**Result:** Two cyclic isogenies $\phi: E_0 \to E$ of degree dividing $\ell^{2f}$ and $\phi': E_0 \to E$ of degree dividing $\ell'^{2f'}$ and their respective kernel ideals $J$ and $J'$.

1. Use [22, Algorithm 4] to find $\gamma \in O_0$ non divisible by $\ell$ and $\ell'$ of norm $\text{nrd}(\gamma) = \ell^{2g}\ell'^{2g'}$ with $g \le f$ close to $f$ and $g' \le f'$ close to $f'$;
2. Evaluate $\varepsilon(\gamma)$ and $\varepsilon(\bar{\gamma})$ on a basis of $E_0[\ell^g\ell'^{g'}]$ and solve discrete logarithm problems to compute $\mathcal{G}_1 := \text{ker}(\varepsilon(\gamma)) \cap E_0[\ell^g\ell'^{g'}]$ and $\mathcal{G}_2 := \text{ker}(\varepsilon(\bar{\gamma})) \cap E_0[\ell^g\ell'^{g'}]$;
3. Compute $\rho_i: E_0 \to E'$ of kernel $\mathcal{G}_i$ for $i=1,2$;
4. Compute $\mathcal{H}_1 := \text{ker}(\varepsilon(\gamma)) \cap E_0[\ell^g], \mathcal{H}_2 := \text{ker}(\varepsilon(\bar{\gamma})) \cap E_0[\ell'^{g'}], \mathcal{H}'_1 := \text{ker}(\hat{\rho}_1) \cap E'[\ell^g]$ and $\mathcal{H}'_2 := \text{ker}(\hat{\rho}_2) \cap E'[\ell'^{g'}]$;
5. Compute $\theta_i$ of kernel $\mathcal{H}_i$ and $\theta'_i$ of kernel $\mathcal{H}'_i$ for $i=1,2$;
6. Compute $[\theta'_1]_*\theta_2$ and $[\theta_2]_*\theta'_1$ of kernels $\theta'_1(\text{ker}(\theta_2))$ and $\theta_2(\text{ker}(\theta'_1))$ respectively;
7. Let $\phi := [\theta'_1]_*\theta_2 \circ \theta_1$ and $\phi' := [\theta_2]_*\theta'_1 \circ \theta'_2$;
8. Let $J := O_0\gamma + O_0\ell^{2g}$ and $J' := O_0\bar{\gamma} + O_0\ell'^{2g'}$;
9. Return $\phi, \phi', J, J'$;

10. We can compute $\text{ker}(\theta_1)$, $\text{ker}(\theta'_2)$, $\text{ker}(\theta'_1)$ and $\text{ker}(\theta_2)$, and obtain the $\theta_i$ and $\theta'_i$ with Vélu's formulas [38]. We then compute $\text{ker}([\theta'_1]_*\theta_2) = \theta'_1(\text{ker}(\theta_2))$ and $\text{ker}([\theta_2]_*\theta'_1) = \theta_2(\text{ker}(\theta'_1))$ and use Vélu's formulas again. We then easily get $\phi$ and $\phi'$.

Since $\varepsilon(\gamma) = \hat{\rho}_2 \circ \rho_1$ and $[\theta'_1]_*\theta_2 \circ \theta'_1 = [\theta_2]_*\theta'_1 \circ \theta_2$, we get that $\varepsilon(\gamma) = \hat{\phi}' \circ \phi$. Lemma 10 implies that the ideals $J := O_0\gamma + O_0\ell^{2g}$ and $J' := O_0\bar{\gamma} + O_0\ell'^{2g'}$ are the respective kernel ideals of $\phi$ and $\phi'$. Algorithm 1 follows.

*Remark 3.1.* The FastKeyGen procedure calls Algorithm 1 directly. For FastCommit, only $\phi'$ and $J'$ are necessary, so we use a slightly modified version of Algorithm 1 where $\mathcal{H}_1$ (line 4), $\theta_1$ (line 5), $\phi$ (line 7), and $J$ (line 8) are not computed.

# 4 Response and Verification

The goal of this section is to present a precise description of the algorithmic building blocks required by our new signature scheme in dimension 4. We refer to [9, § C] for details on the dimension 8 version.

Throughout this section, we assume that the prover has generated two secret key paths $\tau, \tau': E_0 \to E_A$ of respective degrees $D_\tau = \ell'^{2f}$ and $D_{\tau'} = \ell^{2f}$ and a secret commitment path $\psi: E_0 \to E_1$ of degree $D_\psi = \ell'^{2f'}$. We also assume the prover has access to the challenge $\varphi: E_A \to E_2$ of degree $D_\varphi = \ell'^{f'}$.
<caption>**Algorithm 1: FastDoublePath<sub>ℓf,ℓ'f'</sub>**</caption>

**Data:** A basis of $O_0$ and an isomorphism $\varepsilon: O_0 \stackrel{\sim}{\to} \text{End}(E_0)$.

**Result:** Two cyclic isogenies $\phi: E_0 \to E$ of degree dividing $\ell^{2f}$ and $\phi': E_0 \to E$ of degree dividing $\ell'^{2f'}$ and their respective kernel ideals $J$ and $J'$.

1. Use [22, Algorithm 4] to find $\gamma \in O_0$ non divisible by $\ell$ and $\ell'$ of norm $\text{nrd}(\gamma) = \ell^{2g}\ell'^{2g'}$ with $g \le f$ close to $f$ and $g' \le f'$ close to $f'$;
2. Evaluate $\varepsilon(\gamma)$ and $\varepsilon(\bar{\gamma})$ on a basis of $E_0[\ell^g\ell'^{g'}]$ and solve discrete logarithm problems to compute $\mathcal{G}_1 := \text{ker}(\varepsilon(\gamma)) \cap E_0[\ell^g\ell'^{g'}]$ and $\mathcal{G}_2 := \text{ker}(\varepsilon(\bar{\gamma})) \cap E_0[\ell^g\ell'^{g'}]$;
3. Compute $\rho_i: E_0 \to E'$ of kernel $\mathcal{G}_i$ for $i=1,2$;
4. Compute $\mathcal{H}_1 := \text{ker}(\varepsilon(\gamma)) \cap E_0[\ell^g], \mathcal{H}_2 := \text{ker}(\varepsilon(\bar{\gamma})) \cap E_0[\ell'^{g'}], \mathcal{H}'_1 := \text{ker}(\hat{\rho}_1) \cap E'[\ell^g]$ and $\mathcal{H}'_2 := \text{ker}(\hat{\rho}_2) \cap E'[\ell'^{g'}]$;
5. Compute $\theta_i$ of kernel $\mathcal{H}_i$ and $\theta'_i$ of kernel $\mathcal{H}'_i$ for $i=1,2$;
6. Compute $[\theta'_1]_*\theta_2$ and $[\theta_2]_*\theta'_1$ of kernels $\theta'_1(\text{ker}(\theta_2))$ and $\theta_2(\text{ker}(\theta'_1))$ respectively;
7. Let $\phi := [\theta'_1]_*\theta_2 \circ \theta_1$ and $\phi' := [\theta_2]_*\theta'_1 \circ \theta'_2$;
8. Let $J := O_0\gamma + O_0\ell^{2g}$ and $J' := O_0\bar{\gamma} + O_0\ell'^{2g'}$;
9. Return $\phi, \phi', J, J'$;

10. We can compute $\text{ker}(\theta_1)$, $\text{ker}(\theta'_2)$, $\text{ker}(\theta'_1)$ and $\text{ker}(\theta_2)$, and obtain the $\theta_i$ and $\theta'_i$ with Vélu's formulas [38]. We then compute $\text{ker}([\theta'_1]_*\theta_2) = \theta'_1(\text{ker}(\theta_2))$ and $\text{ker}([\theta_2]_*\theta'_1) = \theta_2(\text{ker}(\theta'_1))$ and use Vélu's formulas again. We then easily get $\phi$ and $\phi'$.

Since $\varepsilon(\gamma) = \hat{\rho}_2 \circ \rho_1$ and $[\theta'_1]_*\theta_2 \circ \theta'_1 = [\theta_2]_*\theta'_1 \circ \theta_2$, we get that $\varepsilon(\gamma) = \hat{\phi}' \circ \phi$. Lemma 10 implies that the ideals $J := O_0\gamma + O_0\ell^{2g}$ and $J' := O_0\bar{\gamma} + O_0\ell'^{2g'}$ are the respective kernel ideals of $\phi$ and $\phi'$. Algorithm 1 follows.

*Remark 3.1.* The FastKeyGen procedure calls Algorithm 1 directly. For FastCommit, only $\phi'$ and $J'$ are necessary, so we use a slightly modified version of Algorithm 1 where $\mathcal{H}_1$ (line 4), $\theta_1$ (line 5), $\phi$ (line 7), and $J$ (line 8) are not computed.

# 4 Response and Verification

The goal of this section is to present a precise description of the algorithmic building blocks required by our new signature scheme in dimension 4. We refer to [9, § C] for details on the dimension 8 version.

Throughout this section, we assume that the prover has generated two secret key paths $\tau, \tau': E_0 \to E_A$ of respective degrees $D_\tau = \ell'^{2f}$ and $D_{\tau'} = \ell^{2f}$ and a secret commitment path $\psi: E_0 \to E_1$ of degree $D_\psi = \ell'^{2f'}$. We also assume the prover has access to the challenge $\varphi: E_A \to E_2$ of degree $D_\varphi = \ell'^{f'}$.
## 4.1 Overview of the Response Computation

In this section, we present the algorithm FastRespond used to compute the response in the FastSQIsignHD identification protocol (in dimension 4) and its verification counterpart FastVerify.

Those algorithms use the following sub-algorithms that will be introduced in this section (if not already):

- **IsogenyTolideal**($\varphi, \tau', I_{\tau'}$) (presented in [9, § A.4]) takes as input a basis of $End(E_0)$ that we can evaluate on points, an isogeny $\varphi : E_A \to E_2$ of degree $D_\varphi$, an isogeny $\tau' : E_0 \to E_A$ of degree prime to $D_\varphi$, its ideal $I_{\tau'} \subset O_0$ and returns the kernel ideal $I_\varphi$ of $\varphi$.

- **RandomEquivalentIdeal**$_{\ell^e}$ takes as input an $O_0$-left ideal $J$ and returns an equivalent ideal $I$ that is uniformly random among ideals of norm $\le \ell^e$.

- **EvalTorsion**$_{\ell f}$ (presented in [9, § A.5]) evaluates a non-smooth degree isogeny on $\ell^f$-torsion points knowing its kernel ideal and an alternate smooth degree path. Namely, it takes as input an ideal $I$ connecting $O \cong \text{End}(E)$ and $O' \cong \text{End}(E')$, a basis $(P_1, P_2)$ of $E[\ell^f]$, two isogenies $\rho_1 : E_0 \to E$ and $\rho_2 : E_0 \to E'$ of smooth degrees prime to $\ell$, with their respective kernel ideals $I_1$ and $I_2$ and returns $(\phi_I(P_1), \phi_I(P_2))$, where $\phi_I : E \to E'$ is the isogeny associated to $I$.

- **RepresentIsogeny**$_{4,\ell^e,\ell f}$ takes as input an $\ell^e$-good integer $q$, integers $a_1, a_2$ such that $a_1^2 + a_2^2 + q = \ell^e$, a basis $(P_1, P_2)$ of $E_1[\ell^f]$, $(\sigma(P_1), \sigma(P_2))$, where $\sigma : E_1 \to E_2$ is a $q$-isogeny, and returns a chain of 4-dimensional $\ell$-isogenies whose composition is $F(\sigma, a_1, a_2)$ as in Notation 5.

- **IsValid**$_4$, with input $F, E_1, E_2, \ell^e, \ell^f$, checks if $F$ is a valid output of **RepresentIsogeny**$_{4,\ell^e,\ell f}$ representing an isogeny $\sigma : E_1 \to E_2$ in dimension 4.

The prover sends the image of two points $P_1, P_2$ forming a basis of $E_1[\ell^f]$ by $\sigma$ and its degree $q$. The verifier can then use $q$ to compute $a_1, a_2$ and compute $F(\sigma, a_1, a_2)$ with the **RepresentIsogeny**$_{4,\ell^e,\ell f}$ procedure. If the computation succeeds and is validated by the **IsValid**$_4$ procedure, then the verification is complete. Algorithm 3 follows.

**Remark 4.1 (On the $\ell^f$-torsion basis).** It is sufficient to send the data $(\sigma(P_1), \sigma(P_2), q)$ to the verifier as the basis $(P_1, P_2)$ can be computed canonically knowing $E_1$ by classical compression techniques developed for SIDH [2, 42]. This decreases the communications size at a small computational cost. Later, with the compression/decompression algorithms (see Algorithms 6 and 7), we will see how to further compress this data.

Note that we use a basis of the $\ell^f$-torsion with $2f \ge e + 4$ here because we might not have the $\ell^e$-torsion accessible. We can still compute $F$ with this partial information as explained in Section 4.3.

To respond, the prover starts by computing an ideal $I \sim \overline{I_\psi} \cdot I_\tau \cdot I_\varphi$ connecting $O_1 \cong \text{End}(E_1)$ to $O_2 \cong \text{End}(E_2)$ of $\ell^e$-good norm $q$ and prime to $\ell'$ with uniform distribution using **RandomEquivalentIdeal**$_{\ell^e}$. The coprimality with
## 4.1 Overview of the Response Computation

In this section, we present the algorithm FastRespond used to compute the response in the FastSQIsignHD identification protocol (in dimension 4) and its verification counterpart FastVerify.

Those algorithms use the following sub-algorithms that will be introduced in this section (if not already):

- **IsogenyTolideal**($\varphi, \tau', I_{\tau'}$) (presented in [9, § A.4]) takes as input a basis of $End(E_0)$ that we can evaluate on points, an isogeny $\varphi : E_A \to E_2$ of degree $D_\varphi$, an isogeny $\tau' : E_0 \to E_A$ of degree prime to $D_\varphi$, its ideal $I_{\tau'} \subset O_0$ and returns the kernel ideal $I_\varphi$ of $\varphi$.

- **RandomEquivalentIdeal**$_{\ell^e}$ takes as input an $O_0$-left ideal $J$ and returns an equivalent ideal $I$ that is uniformly random among ideals of norm $\le \ell^e$.

- **EvalTorsion**$_{\ell f}$ (presented in [9, § A.5]) evaluates a non-smooth degree isogeny on $\ell^f$-torsion points knowing its kernel ideal and an alternate smooth degree path. Namely, it takes as input an ideal $I$ connecting $O \cong \text{End}(E)$ and $O' \cong \text{End}(E')$, a basis $(P_1, P_2)$ of $E[\ell^f]$, two isogenies $\rho_1 : E_0 \to E$ and $\rho_2 : E_0 \to E'$ of smooth degrees prime to $\ell$, with their respective kernel ideals $I_1$ and $I_2$ and returns $(\phi_I(P_1), \phi_I(P_2))$, where $\phi_I : E \to E'$ is the isogeny associated to $I$.

- **RepresentIsogeny**$_{4, \ell^e, \ell f}$ takes as input an $\ell^e$-good integer $q$, integers $a_1, a_2$ such that $a_1^2 + a_2^2 + q = \ell^e$, a basis $(P_1, P_2)$ of $E_1[\ell^f]$, $(\sigma(P_1), \sigma(P_2))$, where $\sigma : E_1 \to E_2$ is a $q$-isogeny, and returns a chain of 4-dimensional $\ell$-isogenies whose composition is $F(\sigma, a_1, a_2)$ as in Notation 5.

- **IsValid**$_4$, with input $F, E_1, E_2, \ell^e, \ell^f$, checks if $F$ is a valid output of **RepresentIsogeny**$_{4, \ell^e, \ell f}$ representing an isogeny $\sigma : E_1 \to E_2$ in dimension 4.

The prover sends the image of two points $P_1, P_2$ forming a basis of $E_1[\ell^f]$ by $\sigma$ and its degree $q$. The verifier can then use $q$ to compute $a_1, a_2$ and compute $F(\sigma, a_1, a_2)$ with the **RepresentIsogeny**$_{4, \ell^e, \ell f}$ procedure. If the computation succeeds and is validated by the **IsValid**$_4$ procedure, then the verification is complete. Algorithm 3 follows.

**Remark 4.1 (On the $\ell^f$-torsion basis).** It is sufficient to send the data $(\sigma(P_1), \sigma(P_2), q)$ to the verifier as the basis $(P_1, P_2)$ can be computed canonically knowing $E_1$ by classical compression techniques developed for SIDH [2, 42]. This decreases the communications size at a small computational cost. Later, with the compression/decompression algorithms (see Algorithms 6 and 7), we will see how to further compress this data.

Note that we use a basis of the $\ell^f$-torsion with $2f \ge e + 4$ here because we might not have the $\ell^e$-torsion accessible. We can still compute $F$ with this partial information as explained in Section 4.3.

To respond, the prover starts by computing an ideal $I \sim \overline{I_\psi} \cdot I_\tau \cdot I_\varphi$ connecting $O_1 \cong \text{End}(E_1)$ to $O_2 \cong \text{End}(E_2)$ of $\ell^e$-good norm $q$ and prime to $\ell'$ with uniform distribution using **RandomEquivalentIdeal**$_{\ell^e}$. The coprimality with
$\ell'$ is justified by security reasons (see Section 5.1). Then, the prover generates the basis $(P_1, P_2)$ of $E_1[\ell^f]$ canonically and evaluates $\sigma$ on it with $\text{EvalTorsion}_{\ell^f}$ using $I$ (kernel ideal of $\sigma$) and the paths $\psi: E_0 \to E_1$ and $\varphi \circ \tau: E_0 \to E_2$ of degrees prime to $\ell$.

As input of Algorithms 2 and 3, we denote by:

- FastSetup, the public parameters of FastSQIsignHD, $p = c\ell^f\ell'^{f'} - 1$, $\ell, \ell', f, f'$, the exponent $e$ and the elliptic curve $E_0/\mathbb{F}_p$;

- SecretKey, the isogenies $\tau, \tau': E_0 \to E_A$ of degrees $D_\tau = \ell'^{2f'}$ and $D_{\tau'} = \ell^{2f}$ respectively along with their kernel ideals $I_\tau$ and $I_{\tau'}$;

- CommitData, the isogeny $\psi: E_0 \to E_1$ of degree $D_\psi = \ell'^{2f}$ and its kernel ideal $I_\psi$;

- ChallData, the isogeny $\varphi: E_A \to E_2$ of degree $D_\varphi = \ell'^{f'}$.

**Algorithm 2: FastRespond**

**Data:** FastSetup, SecretKey, CommitData and ChallData.

**Result:** $(\sigma(P_1), \sigma(P_2), q)$, where $(P_1, P_2)$ is a canonically determined basis of $E_1[\ell^f]$ and $\sigma: E_1 \to E_2$ is an isogeny of $\ell^e$-good degree $q$ prime to $\ell'$.

1. $I_\varphi \leftarrow \text{IsogenyToldeal}(\varphi, \tau', I_{\tau'});$

2. $J \leftarrow \overline{I_\psi} \cdot I_\tau \cdot I_\varphi;$

3. $I \leftarrow \text{RandomEquivalentIdeal}_{\ell^e}(J)$ and $q \leftarrow \text{nrd}(I);$

4. If $q$ is not $\ell^e$-good or $q \wedge \ell' \neq 1$, go back to line 3;

5. Compute the canonical basis $(P_1, P_2)$ of $E_1[\ell^f]$;

6. $(\sigma(P_1), \sigma(P_2)) \leftarrow \text{EvalTorsion}_{\ell^f}(I, P_1, P_2, \psi, \varphi \circ \tau, I_\psi, I_\tau \cdot I_\varphi);$

7. Return $(\sigma(P_1), \sigma(P_2), q);$

**Algorithm 3: FastVerify**

**Data:** FastSetup, $E_1, E_2$ and an output $R$ from FastRespond.

**Result:** Determines if $R$ is a valid response.

1. Try to parse $R := (R_1, R_2, q)$, where $R_1, R_2 \in E_2[\ell^f]$ and $q < \ell^e$ and return False if it fails;

2. If $q$ is not $\ell^e$-good or $q \wedge \ell' \neq 1$, return False;

3. Compute the canonical basis $(P_1, P_2)$ of $E_1[\ell^f]$;

4. Find $a_1, a_2 \in \mathbb{Z}$ such that $a_1^2 + a_2^2 = \ell^e - q$ using Cornacchia's algorithm [6];

5. $F \leftarrow \text{RepresentIsogeny}_{4, \ell^e, \ell^f}(E_1, E_2, a_1, a_2, P_1, P_2, R_1, R_2);$

6. **if** $F \neq$ **False** **then**

7. | Return `IsValid}_{4, \ell^e, \ell^f, \ell'^{f'}}(F, E_1, E_2, a_1, a_2);$

8. **else**

9. | Return False.

10. **end**
$\ell'$ is justified by security reasons (see Section 5.1). Then, the prover generates the basis $(P_1, P_2)$ of $E_1[\ell^f]$ canonically and evaluates $\sigma$ on it with $\text{EvalTorsion}_{\ell^f}$ using $I$ (kernel ideal of $\sigma$) and the paths $\psi: E_0 \to E_1$ and $\varphi \circ \tau: E_0 \to E_2$ of degrees prime to $\ell$.

As input of Algorithms 2 and 3, we denote by:

- FastSetup, the public parameters of FastSQIsignHD, $p = c\ell^f\ell'^{f'} - 1$, $\ell, \ell', f, f'$, the exponent $e$ and the elliptic curve $E_0/\mathbb{F}_p$;

- SecretKey, the isogenies $\tau, \tau': E_0 \to E_A$ of degrees $D_\tau = \ell'^{2f'}$ and $D_{\tau'} = \ell^{2f}$ respectively along with their kernel ideals $I_\tau$ and $I_{\tau'}$;

- CommitData, the isogeny $\psi: E_0 \to E_1$ of degree $D_\psi = \ell'^{2f}$ and its kernel ideal $I_\psi$;

- ChallData, the isogeny $\varphi: E_A \to E_2$ of degree $D_\varphi = \ell'^{f'}$.

**Algorithm 2: FastRespond**

**Data:** FastSetup, SecretKey, CommitData and ChallData.

**Result:** $(\sigma(P_1), \sigma(P_2), q)$, where $(P_1, P_2)$ is a canonically determined basis of $E_1[\ell^f]$ and $\sigma: E_1 \to E_2$ is an isogeny of $\ell^e$-good degree $q$ prime to $\ell'$.

1. $I_\varphi \leftarrow \text{IsogenyToldeal}(\varphi, \tau', I_{\tau'});$

2. $J \leftarrow \overline{I_\psi} \cdot I_\tau \cdot I_\varphi;$

3. $I \leftarrow \text{RandomEquivalentIdeal}_{\ell^e}(J)$ and $q \leftarrow \text{nrd}(I);$

4. If $q$ is not $\ell^e$-good or $q \wedge \ell' \neq 1$, go back to line 3;

5. Compute the canonical basis $(P_1, P_2)$ of $E_1[\ell^f]$;

6. $(\sigma(P_1), \sigma(P_2)) \leftarrow \text{EvalTorsion}_{\ell^f}(I, P_1, P_2, \psi, \varphi \circ \tau, I_\psi, I_\tau \cdot I_\varphi);$

7. Return $(\sigma(P_1), \sigma(P_2), q);$

**Algorithm 3: FastVerify**

**Data:** FastSetup, $E_1, E_2$ and an output $R$ from FastRespond.

**Result:** Determines if $R$ is a valid response.

1. Try to parse $R := (R_1, R_2, q)$, where $R_1, R_2 \in E_2[\ell^f]$ and $q < \ell^e$ and return False if it fails;

2. If $q$ is not $\ell^e$-good or $q \wedge \ell' \neq 1$, return False;

3. Compute the canonical basis $(P_1, P_2)$ of $E_1[\ell^f]$;

4. Find $a_1, a_2 \in \mathbb{Z}$ such that $a_1^2 + a_2^2 = \ell^e - q$ using Cornacchia's algorithm [6];

5. $F \leftarrow \text{RepresentIsogeny}_{4, \ell^e, \ell^f}(E_1, E_2, a_1, a_2, P_1, P_2, R_1, R_2);$

6. **if** $F \neq$ **False** **then**

7. | Return `IsValid}_{4, \ell^e, \ell^f, \ell'^{f'}}(F, E_1, E_2, a_1, a_2);

8. **else**

9. | Return False.

10. end
## 4.2 Finding a Uniformly Random Tight Response Ideal

In this section, we present the algorithm RandomEquivalentIdeal$_{ℓ_e}$ taking a left $O_0$-ideal $J$ as input and returning an ideal $I$ which is uniformly random among the ideals $I \sim J$ of norm $q < ℓ^e$. By [10, Lemma 1], all the equivalent ideals $I \sim J$ are of the form $\chi_J(\alpha) := J\bar{\alpha}/\text{nrd}(J)$ for some $\alpha \in J$ and $\alpha$ determines $I$ up to multiplication by an element of $O_0^\times$. Besides, the norm of $I = \chi_J(\alpha)$ is $q_J(\alpha) := \text{nrd}(\alpha)/\text{nrd}(J)$, so we need $q_J(\alpha) \le ℓ^e$.

Hence, to sample an ideal $I \sim J$ such that $\text{nrd}(I) \le ℓ^e$ with uniform distribution is equivalent to sample $\alpha \in J \setminus \{0\}$ such that $q_J(\alpha) \le ℓ^e$ with uniform distribution. If we fix a basis of $J$, we can see $q_J$ as a primitive positive definite integral quadratic form with four variables. By the following lemma, which is a simple generalization of [41, Lemma 3.3], we can sample uniformly $\alpha \in J$ such that $q_J(\alpha) \le ℓ^e$. RandomEquivalentIdeal$_{ℓ_e}$ calls this procedure to get $\alpha \in J$ uniform and rejects the result if $\alpha = 0$. Then the distribution of $\alpha$ is still uniform but in $J \setminus \{0\}$. The proofs of the two following lemmas can be found in [9, § E.2].

**Lemma 11.** Let $f$ be a primitive positive definite integral quadratic form in $k$ variables and let $\rho > 0$. Then there exists an algorithm that samples uniformly random elements from the set

$$ \{x \in \mathbb{Z}^k \mid f(x) \le \rho\} $$

in polynomial time in $\log(\rho)$ and the length of $f$ (namely, the maximal number of bits of the coefficients of $f$). This algorithm runs in exponential time in $k$.

For RandomEquivalentIdeal$_{ℓ_e}(J)$ to terminate, we need to find $\alpha \in J \setminus \{0\}$ such that $q_J(\alpha) \le ℓ^e$. For such an $\alpha$ to exist, we need $ℓ^e = \Omega(\sqrt{p})$ according to the following lemma (Lemma 12).

**Lemma 12.** Let $O$ be a maximal order and $J$ be a left $O$-ideal. Then there exists $\alpha \in J$ such that $q_J(\alpha) \le 2\sqrt{2p}/\pi$.

In the procedure FastRespond, we reject the results of RandomEquivalentIdeal$_{ℓ_e}$ whose norm is not $ℓ^e$-good or divisible by $ℓ'$. If it terminates, this rejection sampling outputs ideals which are uniformly random among the targeted ones, as desired. However, we can only give a heuristic argument for the termination. Assuming that $q_J(\alpha)$ behaves like a random integer, we should expect to find a suitable $\alpha \in J$ with probability $O(1/\log(p))$. Hence, taking $ℓ^e$ a few bits over $\sqrt{p}$ might be sufficient. For that reason, in our choice of parameters, we only have accessible $ℓ^f$-torsion with $ℓ^f < \sqrt{p} < ℓ^e$ (see Section 3.1). Proving formally that we can always find an $ℓ^e$-good value of $q_J(\alpha)$ would certainly require to increase $ℓ^e$ by a lot. As [35] indicates, we should expect lower bounds close to $ℓ^e = \omega(p^2)$, causing a huge efficiency loss.

## 4.3 Dividing the Higher Dimensional Isogeny Computation in Two

As explained in Section 4.2, we do not necessarily have enough accessible torsion to compute the whole kernel of the higher dimensional representation of the
## 4.2 Finding a Uniformly Random Tight Response Ideal

In this section, we present the algorithm RandomEquivalentIdeal$_{ℓ_e}$ taking a left $O_0$-ideal J as input and returning an ideal I which is uniformly random among the ideals $I \sim J$ of norm $q < ℓ^e$. By [10, Lemma 1], all the equivalent ideals $I \sim J$ are of the form $\chi_J(\alpha) := J\bar{\alpha}/\text{nrd}(J)$ for some $\alpha \in J$ and $\alpha$ determines $I$ up to multiplication by an element of $O_0^\times$. Besides, the norm of $I = \chi_J(\alpha)$ is $q_J(\alpha) := \text{nrd}(\alpha)/\text{nrd}(J)$, so we need $q_J(\alpha) \le ℓ^e$.

Hence, to sample an ideal $I \sim J$ such that $\text{nrd}(I) \le ℓ^e$ with uniform distribution is equivalent to sample $\alpha \in J \setminus \{0\}$ such that $q_J(\alpha) \le ℓ^e$ with uniform distribution. If we fix a basis of $J$, we can see $q_J$ as a primitive positive definite integral quadratic form with four variables. By the following lemma, which is a simple generalization of [41, Lemma 3.3], we can sample uniformly $\alpha \in J$ such that $q_J(\alpha) \le ℓ^e$. RandomEquivalentIdeal$_{ℓ_e}$ calls this procedure to get $\alpha \in J$ uniform and rejects the result if $\alpha = 0$. Then the distribution of $\alpha$ is still uniform but in $J \setminus \{0\}$. The proofs of the two following lemmas can be found in [9, § E.2].

**Lemma 11.** Let $f$ be a primitive positive definite integral quadratic form in $k$ variables and let $\rho > 0$. Then there exists an algorithm that samples uniformly random elements from the set

$$ \{x \in \mathbb{Z}^k \mid f(x) \le \rho\} $$

in polynomial time in $\log(\rho)$ and the length of $f$ (namely, the maximal number of bits of the coefficients of $f$). This algorithm runs in exponential time in $k$.

For RandomEquivalentIdeal$_{ℓ_e}(J)$ to terminate, we need to find $\alpha \in J \setminus \{0\}$ such that $q_J(\alpha) \le ℓ^e$. For such an $\alpha$ to exist, we need $ℓ^e = \Omega(\sqrt{p})$ according to the following lemma (Lemma 12).

**Lemma 12.** Let $O$ be a maximal order and $J$ be a left $O$-ideal. Then there exists $\alpha \in J$ such that $q_J(\alpha) \le 2\sqrt{2p}/\pi$.

In the procedure FastRespond, we reject the results of RandomEquivalentIdeal$_{ℓ_e}$ whose norm is not $ℓ^e$-good or divisible by $ℓ'$. If it terminates, this rejection sampling outputs ideals which are uniformly random among the targeted ones, as desired. However, we can only give a heuristic argument for the termination. Assuming that $q_J(\alpha)$ behaves like a random integer, we should expect to find a suitable $\alpha \in J$ with probability $O(1/\log(p))$. Hence, taking $ℓ^e$ a few bits over $\sqrt{p}$ might be sufficient. For that reason, in our choice of parameters, we only have accessible $ℓ^f$-torsion with $ℓ^f < \sqrt{p} < ℓ^e$ (see Section 3.1). Proving formally that we can always find an $ℓ^e$-good value of $q_J(\alpha)$ would certainly require to increase $ℓ^e$ by a lot. As [35] indicates, we should expect lower bounds close to $ℓ^e = \omega(p^2)$, causing a huge efficiency loss.

## 4.3 Dividing the Higher Dimensional Isogeny Computation in Two

As explained in Section 4.2, we do not necessarily have enough accessible torsion to compute the whole kernel of the higher dimensional representation of the
response $F$. In this section, we explain in plain generality how to circumvent this difficulty. Hence, the following discussion applies to both dimension 4 and 8. Let us keep the notations of Section 2.2. Recall that we have the following isogeny

$$F := \begin{pmatrix} \varphi & \tilde{\psi}' \\ -\psi & \tilde{\varphi}' \end{pmatrix}, \quad \text{with} \quad \ker(F) = \{(\tilde{\varphi}(x), \psi'(x)) \mid x \in B[d]\}.$$

To compute $F$, we need to evaluate $\tilde{\varphi}$ and $\psi'$ on $B[d]$, so we need to have accessible $d$-torsion. However, we assume that we only have $d'$-accessible torsion with $d'|d$.

The idea is to decompose $F = F_2 \circ F_1$ where $F_1 : A := A \times B' \to C$ and $F_2 : C \to B := B \times A'$ are respectively $d_1$ and $d_2$-isogenies such that $d_1, d_2|d'$ and to use the following proposition (proved in [9, § E.3]) to compute $F_1$ and $\tilde{F}_2$ to infer $F$.

**Proposition 13.** Suppose $d$ prime to $p$ so that $F$ is separable. Then:

(i) We can always decompose $F = F_2 \circ F_1$, as above.

(ii) $\ker(F_1) \subseteq \ker(F) \cap A[d_1]$.

(iii) $\ker(\tilde{F}_2) \subseteq \ker(\tilde{F}) \cap B[d_2] = F(A[d]) \cap B[d_2]$.

(iv) When $\ker(F)$ has rank $g := \dim(A)$, those inclusions are equalities.

In SQIsignHD, $d_1 = \ell^{e_1}$ and $d_2 = \ell^{e_2}$ with $e = e_1 + e_2$ and we have accessible $\ell^f$-torsion such that $f \ge e_1, e_2$. Since $\ker(F)$ has maximal rank $g = 4$ (or 8), we have by point (iv) of the above proposition

$$\ker(F_1) = \ker(F)[\ell^{e_1}] = \{(\tilde{\alpha}_1(P), \Sigma(P)) \mid P \in E_1^{g/2}[\ell^{e_1}]\}$$

and similarly, $\ker(\tilde{F}_2) = \ker(\tilde{F})[\ell^{e_2}] = \{(\alpha_1(P), -\Sigma(P)) \mid P \in E_1^{g/2}[\ell^{e_2}]\}$, with the notations of Section 2.3.

In [9, § F], we give an overview of the higher dimensional isogeny computation required in the procedures RepresentIsogeny$_{g, \ell^e, \ell^f}$ of our SQIsignHD scheme. We provide a proof of concept sagemath implementation in dimension 4. Optimizing this implementation in a low level programming language is left for future works.

## 4.4 Computing the Response Isogeny Representation

We finally give algorithms to compute the signature representation in dimension 4 using all the ideas presented in Section 4.3 and [9, § F]. We refer to KernelTolsogeny$_{g, \ell^e}(\mathcal{B}_0)$ as the algorithm computing an $\ell$-isogeny chain in dimension $g$ given a basis $\mathcal{B}_0$ of its kernel. We refer to [9, § F] for more details on this algorithm.

In dimension 4, RepresentIsogeny$_{g, \ell^e, \ell^f}$ (Algorithm 4) computes basis of $\ker(F_1)$ and $\ker(\tilde{F}_2)$ with $F := F_2 \circ F_1$, as in Section 4.3. Then, it calls KernelTolsogeny$_{g, \ell^e}$ to obtain $F_1$ and $\tilde{F}_2$ as isogeny chains. The ideas are the same in dimension 8.
response $F$. In this section, we explain in plain generality how to circumvent this difficulty. Hence, the following discussion applies to both dimension 4 and 8. Let us keep the notations of Section 2.2. Recall that we have the following isogeny

$$F := \begin{pmatrix} \varphi & \tilde{\psi}' \\ -\psi & \tilde{\varphi}' \end{pmatrix}, \quad \text{with} \quad \ker(F) = \{(\tilde{\varphi}(x), \psi'(x)) \mid x \in B[d]\}.$$

To compute $F$, we need to evaluate $\tilde{\varphi}$ and $\psi'$ on $B[d]$, so we need to have accessible $d$-torsion. However, we assume that we only have $d'$-accessible torsion with $d'|d$.

The idea is to decompose $F = F_2 \circ F_1$ where $F_1: A := A \times B' \to C$ and $F_2: C \to B := B \times A'$ are respectively $d_1$ and $d_2$-isogenies such that $d_1, d_2|d'$ and to use the following proposition (proved in [9, § E.3]) to compute $F_1$ and $\tilde{F}_2$ to infer $F$.

**Proposition 13.** Suppose $d$ prime to $p$ so that $F$ is separable. Then:

(i) We can always decompose $F = F_2 \circ F_1$, as above.

(ii) $\ker(F_1) \subseteq \ker(F) \cap A[d_1]$.

(iii) $\ker(\tilde{F}_2) \subseteq \ker(\tilde{F}) \cap B[d_2] = F(A[d]) \cap B[d_2]$.

(iv) When $\ker(F)$ has rank $g := \dim(A)$, those inclusions are equalities.

In SQIsignHD, $d_1 = \ell^{e_1}$ and $d_2 = \ell^{e_2}$ with $e = e_1 + e_2$ and we have accessible $\ell^f$-torsion such that $f \ge e_1, e_2$. Since $\ker(F)$ has maximal rank $g = 4$ (or 8), we have by point (iv) of the above proposition

$$\ker(F_1) = \ker(F)[\ell^{e_1}] = \{(\tilde{\alpha}_1(P), \Sigma(P)) \mid P \in E_1^{g/2}[\ell^{e_1}]\}$$

and similarly, $\ker(\tilde{F}_2) = \ker(\tilde{F})[\ell^{e_2}] = \{(\alpha_1(P), -\Sigma(P)) \mid P \in E_1^{g/2}[\ell^{e_2}]\}$, with the notations of Section 2.3.

In [9, § F], we give an overview of the higher dimensional isogeny computation required in the procedures RepresentIsogeny$_{g, \ell^e, \ell^f}$ of our SQIsignHD scheme. We provide a proof of concept sagemath implementation in dimension 4. Optimizing this implementation in a low level programming language is left for future works.

## 4.4 Computing the Response Isogeny Representation

We finally give algorithms to compute the signature representation in dimension 4 using all the ideas presented in Section 4.3 and [9, § F]. We refer to KernelTolsogeny$_{g, \ell^e}$ ($\mathcal{B}_0$) as the algorithm computing an $\ell$-isogeny chain in dimension $g$ given a basis $\mathcal{B}_0$ of its kernel. We refer to [9, § F] for more details on this algorithm.

In dimension 4, RepresentIsogeny$_{4, \ell^e, \ell^f}$ (Algorithm 4) computes basis of $\ker(F_1)$ and $\ker(\tilde{F}_2)$ with $F := F_2 \circ F_1$, as in Section 4.3. Then, it calls KernelTolsogeny$_{4, \ell^e}$ to obtain $F_1$ and $\tilde{F}_2$ as isogeny chains. The ideas are the same in dimension 8.
<caption>**Algorithm 4: RepresentIsogeny<sub>4,ℓ<sup>e</sup>,ℓ<sup>f</sup></sub>**</caption>

**Data:** $E_1, E_2, a_1, a_2 \in \mathbb{Z}$, a basis $(P_1, P_2)$ of $E_1[\ell^f]$ and $(\sigma(P_1), \sigma(P_2))$, where $\sigma: E_1 \to E_2$ is a $q$-isogeny with $a_1^2 + a_2^2 + q = \ell^e$.

**Result:** An $\ell^{e_1}$-isogeny $F_1: E_1^2 \times E_2^2 \to \mathcal{C}$ and a $\ell^{e_2}$-isogeny $\tilde{F}_2: E_1^2 \times E_2^2 \to \mathcal{C}$ such that $F(\sigma, a_1, a_2) = F_2 \circ F_1$, with $e_1, e_2 \le f$ and $e_1 + e_2 = e$.

1 & $e_2 \leftarrow \lceil e/2 \rceil, e_1 \leftarrow e - e_2$;
2 & $Q_i \leftarrow [\ell^{f-e_1}]P_i, R_i \leftarrow [\ell^{f-e_1}]\sigma(P_i)$, $Q'_i \leftarrow [\ell^{f-e_2}]P_i, R'_i \leftarrow [\ell^{f-e_2}]\sigma(P_i)$ for $i \in \{1, 2\}$;
3 & $\mathcal{B}_0 \leftarrow (([a_1]Q_i, [a_2]Q_i, R_i, 0)_{i \in \{1, 2\}}, (-[a_2]Q_i, [a_1]Q_i, 0, R_i)_{i \in \{1, 2\}})$;
4 & $\mathcal{C}_0 \leftarrow (([a_1]Q'_i, -[a_2]Q'_i, -R'_i, 0)_{i \in \{1, 2\}}, ([a_2]Q'_i, [a_1]Q'_i, 0, -R'_i)_{i \in \{1, 2\}})$;
5 & **if** $\mathcal{C}_0$ and $\mathcal{B}_0$ are valid kernels of $\ell^{e_1}$ and $\ell^{e_2}$-isogenies **then**
6 & & & $F_1 \leftarrow \text{KernelTolsogeny}_{4,\ell^{e_1}}(\mathcal{B}_0)$;
7 & & & $\tilde{F}_2 \leftarrow \text{KernelTolsogeny}_{4,\ell^{e_2}}(\mathcal{C}_0)$;
8 & & & Return $F_1$ and $\tilde{F}_2$;
9 & **else**
10 & & & Return False;
11 & **end**

**Proposition 14.** *Algorithm 4 is correct. Namely, Algorithm 4 returns $F_1, \tilde{F}_2$ such that $F_2 \circ F_1 = F(\sigma, a_1, a_2)$ on entry $a_1, a_2, P_1, P_2, \sigma(P_2)$, $\sigma(P_2)$, where $\sigma: E_1 \to E_2$ is a $q$-isogeny with $a_1^2 + a_2^2 + q = \ell^e$.*

*Proof.* See [9, § E.4]. □

*Remark 4.2.* To make sure we have enough accessible torsion, we need $f \ge e_1, e_2$, so that $2f \ge e$. Actually, for *KernelTolsogeny*<sub>4,ℓ<sup>e</sup><sub>i</sub></sub> to work (with theta coordinates of level 2), we need $4\ell^{e_i}$-torsion points (see [9, § F.3]). Then, when $\ell = 2$, we have $f \ge e_i + 2$, so $2f \ge e + 4$.

## 4.5 Verification

We describe the verification procedure `IsValid<sub>4</sub>` taking as input the isogenies $F_1$ and $\tilde{F}_2$ outputted by `RepresentIsogeny<sub>4,ℓ<sup>e</sup>,ℓ<sup>f</sup></sub>` and determining if they represent an isogeny $\sigma: E_1 \to E_2$ of degree $q$. The idea is to check if $F_1$ and $\tilde{F}_2$ have the same codomain (computed as principally polarized abelian varieties) and then evaluate $F_2 \circ F_1$ on some points to check that the degree is correct.

The following results (proved in [9, § E.5]) ensure that our verification procedure is correct. In [9, § C], we provide algorithms in dimension 8 achieving similar correctness results.

**Proposition 15.** *Algorithm 5 is correct. Namely, when given $E_1, E_2, a_1, a_2, F_1, \tilde{F}_2$, if Algorithm 5 returns True, then $F_2 \circ F_1$ is an efficient representation of an isogeny $\sigma: E_1 \to E_2$ of degree $q = \ell^e - a_1^2 - a_2^2$.*

**Corollary 16.** *The verification procedure FastVerify (Algorithm 3) is correct. Namely, on input $(R_1, R_2, q)$, FastVerify returns True if and only if $(R_1, R_2, q)$*
<caption>**Algorithm 4: RepresentIsogeny<sub>4,ℓ<sup>e</sup>,ℓ<sup>f</sup></sub>**</caption>

**Data:** $E_1, E_2, a_1, a_2 \in \mathbb{Z}$, a basis $(P_1, P_2)$ of $E_1[\ell^f]$ and $(\sigma(P_1), \sigma(P_2))$, where $\sigma: E_1 \to E_2$ is a $q$-isogeny with $a_1^2 + a_2^2 + q = \ell^e$.

**Result:** An $\ell^{e_1}$-isogeny $F_1: E_1^2 \times E_2^2 \to \mathcal{C}$ and a $\ell^{e_2}$-isogeny $\tilde{F}_2: E_1^2 \times E_2^2 \to \mathcal{C}$ such that $F(\sigma, a_1, a_2) = F_2 \circ F_1$, with $e_1, e_2 \le f$ and $e_1 + e_2 = e$.

1 & $e_2 \leftarrow \lceil e/2 \rceil, e_1 \leftarrow e - e_2$;
2 & $Q_i \leftarrow [\ell^{f-e_1}]P_i, R_i \leftarrow [\ell^{f-e_1}]\sigma(P_i)$, $Q'_i \leftarrow [\ell^{f-e_2}]P_i, R'_i \leftarrow [\ell^{f-e_2}]\sigma(P_i)$ for $i \in \{1, 2\}$;
3 & $\mathcal{B}_0 \leftarrow (([a_1]Q_i, [a_2]Q_i, R_i, 0)_{i \in \{1, 2\}}, (-[a_2]Q_i, [a_1]Q_i, 0, R_i)_{i \in \{1, 2\}})$;
4 & $\mathcal{C}_0 \leftarrow ((([a_1]Q'_i, -[a_2]Q'_i, -R'_i, 0)_{i \in \{1, 2\}}, ([a_2]Q'_i, [a_1]Q'_i, 0, -R'_i)_{i \in \{1, 2\}})$;
5 & **if** $\mathcal{C}_0$ and $\mathcal{B}_0$ are valid kernels of $\ell^{e_1}$ and $\ell^{e_2}$-isogenies **then**
6 & & & $F_1 \leftarrow \text{KernelTolsogeny}_{4,\ell^{e_1}}(\mathcal{B}_0)$;
7 & & & $\tilde{F}_2 \leftarrow \text{KernelTolsogeny}_{4,\ell^{e_2}}(\mathcal{C}_0)$;
8 & & & Return $F_1$ and $\tilde{F}_2$;
9 & **else**
10 & & & Return False;
11 & **end**

**Proposition 14.** *Algorithm 4 is correct. Namely, Algorithm 4 returns $F_1, \tilde{F}_2$ such that $F_2 \circ F_1 = F(\sigma, a_1, a_2)$ on entry $a_1, a_2, P_1, P_2, \sigma(P_2)$, $\sigma(P_2)$, where $\sigma: E_1 \to E_2$ is a $q$-isogeny with $a_1^2 + a_2^2 + q = \ell^e$.*

*Proof.* See [9, § E.4]. □

*Remark 4.2.* To make sure we have enough accessible torsion, we need $f \ge e_1, e_2$, so that $2f \ge e$. Actually, for *KernelTolsogeny*<sub>4,ℓ<sup>e</sup><sub>i</sub></sub> to work (with theta coordinates of level 2), we need $4\ell^{e_i}$-torsion points (see [9, § F.3]). Then, when $\ell = 2$, we have $f \ge e_i + 2$, so $2f \ge e + 4$.

## 4.5 Verification

We describe the verification procedure `IsValid<sub>4</sub>` taking as input the isogenies $F_1$ and $\tilde{F}_2$ outputted by `RepresentIsogeny<sub>4,ℓ<sup>e</sup>,ℓ<sup>f</sup></sub>` and determining if they represent an isogeny $\sigma: E_1 \to E_2$ of degree $q$. The idea is to check if $F_1$ and $\tilde{F}_2$ have the same codomain (computed as principally polarized abelian varieties) and then evaluate $F_2 \circ F_1$ on some points to check that the degree is correct.

The following results (proved in [9, § E.5]) ensure that our verification procedure is correct. In [9, § C], we provide algorithms in dimension 8 achieving similar correctness results.

**Proposition 15.** *Algorithm 5 is correct. Namely, when given $E_1, E_2, a_1, a_2, F_1, \tilde{F}_2$, if Algorithm 5 returns True, then $F_2 \circ F_1$ is an efficient representation of an isogeny $\sigma: E_1 \to E_2$ of degree $q = \ell^e - a_1^2 - a_2^2$.*

**Corollary 16.** *The verification procedure FastVerify (Algorithm 3) is correct. Namely, on input $(R_1, R_2, q)$, FastVerify returns True if and only if $(R_1, R_2, q)$*
<caption>**Algorithm 5: lsValid<sub>4,ℓ<sup>e</sup>,ℓ<sup>f</sup>ℓ'<sup>f'</sup></sub>"</caption>

**Data:** Elliptic curves $E_1, E_2$, integers $a_1, a_2 \in \mathbb{Z}$ and the output $(F_1, \tilde{F}_2)$ of RepresentIsogeny<sub>4,ℓ<sup>e</sup>,ℓ<sup>f</sup>(E<sub>1</sub>, E<sub>2</sub>, a<sub>1</sub>, a<sub>2</sub>, *, *, *, *)

**Result:** Determines if $\tilde{F}_2 \circ F_1$ is an efficient representation of an isogeny $\sigma : E_1 \rightarrow E_2$ of degree $q := \ell^e - a_1^2 - a_2^2$.

1. Let $(C_1, \lambda_1)$ and $(C_2, \lambda_2)$ be the respective codomains of $F_1$ and $\tilde{F}_2$;
2. **if** $(C_1, \lambda_1) \neq (C_2, \lambda_2)$ **then**
3. | **Return False;**
4. **else**
5. | Find a point $Q \in E_1$ of order $\ell^f \ell'^{f'}$;
6. | Compute compute $F_2$ as the dual of $\tilde{F}_2$ and $\underline{T} \leftarrow F_2 \circ F_1(Q, 0, 0, 0)$;
7. | **if** $\underline{T} = ([a_1]Q, -[a_2]Q, *, 0)$ **then**
8. | | **Return True;**
9. | **else**
10. | | **Return False;**
11. | **end**
12. **end**

defines an efficient representation of an isogeny $\sigma : E_1 \rightarrow E_2$ of degree $q$, where $q$ is $\ell^e$-good and prime to $\ell'$.

# 5 Security Analysis

In this section, we prove that the SQIsignHD identification protocol is secure, namely that it is complete, knowledge sound and honest-verifier zero knowledge. Recall that by [39, Theorem 7], it is sufficient to ensure that our signature scheme obtained by Fiat-Shamir transform is universally unforgeable under chosen message attacks in the random oracle model.

Completeness means that a honest execution of the protocol is always accepted by the verifier. This is true by Proposition 14 and by construction of ls-Valid. Knowledge soundness means that an attacker can only "guess" a response with very low probability. It is proven under the assumption that computing an endomorphism in a supersingular elliptic curve is hard, a well known difficult problem in isogeny based cryptography.

The honest-verifier zero-knowledge property implies that the response does not leak any information on the secret key $\tau$. More precisely, we can simulate transcripts of the identification protocol without using the secret key with the same distribution as real transcripts. To construct such a simulator of SQIsignHD, we need access to an oracle evaluating isogenies of non-smooth degrees. In RigorousSQIsignHD, this oracle is very generic and we do not need any additional hypothesis to prove the zero-knowledge property (hence the name of this version). On the contrary, in FastSQIsignHD, the oracle definition is *ad hoc* and we need an additional heuristic assumption to prove the zero-knowledge property. However, it is very unlikely to build an attack on this assumption as we
<caption>**Algorithm 5: lsValid<sub>4,ℓ<sup>e</sup>,ℓ<sup>f</sup>ℓ'<sup>f'</sup></sub>"</caption>

**Data:** Elliptic curves $E_1, E_2$, integers $a_1, a_2 \in \mathbb{Z}$ and the output $(F_1, \tilde{F}_2)$ of RepresentIsogeny<sub>4,ℓ<sup>e</sup>,ℓ<sup>f</sup>(E<sub>1</sub>, E<sub>2</sub>, a<sub>1</sub>, a<sub>2</sub>, *, *, *, *).
**Result:** Determines if $\tilde{F}_2 \circ F_1$ is an efficient representation of an isogeny $\sigma$: $E_1 \rightarrow E_2$ of degree $q := \ell^e - a_1^2 - a_2^2$.
1. Let $(C_1, \lambda_1)$ and $(C_2, \lambda_2)$ be the respective codomains of $F_1$ and $\tilde{F}_2$;
2. **if** $(C_1, \lambda_1) \neq (C_2, \lambda_2)$ **then**
3. | **Return False;**
4. **else**
5. | Find a point $Q \in E_1$ of order $\ell^f \ell'^{f'}$;
6. | Compute compute $F_2$ as the dual of $\tilde{F}_2$ and $\underline{T} \leftarrow F_2 \circ F_1(Q, 0, 0, 0)$;
7. | **if** $\underline{T} = ([a_1]Q, -[a_2]Q, *, 0)$ **then**
8. | | **Return True;**
9. | **else**
10. | | **Return False;**
11. | **end**
12. **end**

defines an efficient representation of an isogeny $\sigma: E_1 \rightarrow E_2$ of degree $q$, where $q$ is $\ell^e$-good and prime to $\ell'$.

# 5 Security Analysis

In this section, we prove that the SQIsignHD identification protocol is secure, namely that it is complete, knowledge sound and honest-verifier zero knowledge. Recall that by [39, Theorem 7], it is sufficient to ensure that our signature scheme obtained by Fiat-Shamir transform is universally unforgeable under chosen message attacks in the random oracle model.

Completeness means that a honest execution of the protocol is always accepted by the verifier. This is true by Proposition 14 and by construction of ls-Valid. Knowledge soundness means that an attacker can only "guess" a response with very low probability. It is proven under the assumption that computing an endomorphism in a supersingular elliptic curve is hard, a well known difficult problem in isogeny based cryptography.

The honest-verifier zero-knowledge property implies that the response does not leak any information on the secret key $\tau$. More precisely, we can simulate transcripts of the identification protocol without using the secret key with the same distribution as real transcripts. To construct such a simulator of SQIsignHD, we need access to an oracle evaluating isogenies of non-smooth degrees. In RigorousSQIsignHD, this oracle is very generic and we do not need any additional hypothesis to prove the zero-knowledge property (hence the name of this version). On the contrary, in FastSQIsignHD, the oracle definition is *ad hoc* and we need an additional heuristic assumption to prove the zero-knowledge property. However, it is very unlikely to build an attack on this assumption as we
argue in Section 5.3 and both oracles do not undermine the knowledge soundness.
As previously, this section mainly focuses on FastSQIsignHD and refer to [9, §
D] for a complete security analysis of RigorousSQIsignHD.

**5.1 Knowledge Soundness**

The proof that FastSQIsignHD is knowledge sound is a straightforward special
soundess argument identical to the original version of SQIsign [10, Theorem
1]. Namely, we prove that given two transcripts with the same commitment but
distinct challenges, we can find an endomorphism in E<sub>A</sub>. This special soundness
property is sufficient to prove that SQIsignHD satisfies knowledge soundness [17,
Theorem 6.3.2]. However, note that we have to require the prime ideal norm q
to be not only l<sup>e</sup>-good but also prime to l' in order to complete the proof.

**Proposition 17.** *Under the assumption that $q = \deg(\sigma)$ is always prime to $\ell'$, the FastSQIsignHD identification protocol satisfies special soundness. Namely, given two transcripts $(E_1, \varphi, R_1, R_2, q)$ and $(E_1, \varphi', R'_1, R'_2, q')$ with the same commitment $E_1$ but different challenges $\varphi \neq \varphi'$, we can extract an efficient representation of a non-scalar endomorphism $\alpha \in \text{End}(E_A)$.*

*Proof.* Let $(E_1, \varphi, R_1, R_2, q)$ and $(E_1, \varphi', R'_1, R'_2, q')$ be two FastSQIsignHD transcripts with the same commitment $E_1$ but different challenges $\varphi \neq \varphi'$. Then, by Corollary 16, $(R_1, R_2, q)$ and $(R'_1, R'_2, q')$ define efficient representations of isogenies $\sigma : E_1 \to E_2$ and $\sigma' : E_1 \to E'_2$ of degrees $q$ and $q'$ respectively which are $\ell^e$-good and comprime with $\ell'$. Knowing $(R_1, R_2) = (\sigma(P_1), \sigma(P_2))$, where $(P_1, P_2)$ is a canonical basis of $E_1[\ell^f]$, we can also find $a_1, a_2 \in \mathbb{Z}$ such that $a_1^2 + a_2^2 + q = \ell^e$ and apply **RepresentIsogeny**$_{4,\ell^e,\ell^f}$ to compute $F := F(\sigma, a_1, a_2)$ by Proposition 14. Then, $F$ provides an efficient representation of $\hat{\sigma}$.

Hence, we know an efficient representation of $\alpha := \hat{\varphi}' \circ \sigma' \circ \hat{\sigma} \circ \varphi \in \text{End}(E_A)$.
We now prove that $\alpha$ is not scalar. Indeed, if it was, we would have $\alpha = [\lambda]$
for some $\lambda \in \mathbb{Z}$ and $qq'\ell'^2f' = \lambda^2$ where $q := \deg(\sigma)$ and $q' := \deg(\sigma')$ are
prime to $\ell'$. Hence, $\lambda = \ell'^{f'}\lambda'$ with $\lambda' \in \mathbb{Z}$ prime to $\ell'$ ($\lambda'^2 = qq'$). It follows that
$[q']\hat{\sigma} \circ \varphi = [\lambda']\hat{\sigma}' \circ \varphi'$. Since $q, q'$ and $\lambda'$ are prime to $\ell'$, we get that $\ker(\varphi) = \ker(\varphi')$
i.e. $\varphi = \varphi'$ up to post-composition by an automorphism. Contradiction. This
completes the proof. $\quad \square$

For RigorousSQIsignHD, our special soundness argument does not apply be-
cause we have no guarantee on $q$ in general. For that reason, we need to come
back to the formal definition of knowledge soundess given in [17, Definition 6.3.1].
This analysis is conducted in [9, § D.1].

The previous proof of knowledge would be trivial if it was easy to find an
endomorphism. Fortunately, this is a well-known hard problem in isogeny-based
cryptography.

**Problem 18** (Supersingular Endomorphism Problem). Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, find an efficient representation of a non-scalar endomorphism $\alpha \in \text{End}(E)$.
argue in Section 5.3 and both oracles do not undermine the knowledge soundness.
As previously, this section mainly focuses on FastSQIsignHD and refer to [9, §
D] for a complete security analysis of RigorousSQIsignHD.

**5.1 Knowledge Soundness**

The proof that FastSQIsignHD is knowledge sound is a straightforward special
soundess argument identical to the original version of SQIsign [10, Theorem
1]. Namely, we prove that given two transcripts with the same commitment but
distinct challenges, we can find an endomorphism in E<sub>A</sub>. This special soundness
property is sufficient to prove that SQIsignHD satisfies knowledge soundness [17,
Theorem 6.3.2]. However, note that we have to require the prime ideal norm q
to be not only l<sup>e</sup>-good but also prime to l' in order to complete the proof.

**Proposition 17.** *Under the assumption that $q = \deg(\sigma)$ is always prime to $\ell'$, the FastSQIsignHD identification protocol satisfies special soundness. Namely, given two transcripts $(E_1, \varphi, R_1, R_2, q)$ and $(E_1, \varphi', R'_1, R'_2, q')$ with the same commitment $E_1$ but different challenges $\varphi \neq \varphi'$, we can extract an efficient representation of a non-scalar endomorphism $\alpha \in \text{End}(E_A)$.*

*Proof.* Let $(E_1, \varphi, R_1, R_2, q)$ and $(E_1, \varphi', R'_1, R'_2, q')$ be two FastSQIsignHD transcripts with the same commitment $E_1$ but different challenges $\varphi \neq \varphi'$. Then, by Corollary 16, $(R_1, R_2, q)$ and $(R'_1, R'_2, q')$ define efficient representations of isogenies $\sigma : E_1 \to E_2$ and $\sigma' : E_1 \to E'_2$ of degrees $q$ and $q'$ respectively which are $\ell^e$-good and comprime with $\ell'$. Knowing $(R_1, R_2) = (\sigma(P_1), \sigma(P_2))$, where $(P_1, P_2)$ is a canonical basis of $E_1[\ell^f]$, we can also find $a_1, a_2 \in \mathbb{Z}$ such that $a_1^2 + a_2^2 + q = \ell^e$ and apply **RepresentIsogeny**$_{4,\ell^e,\ell^f}$ to compute $F := F(\sigma, a_1, a_2)$ by Proposition 14. Then, $F$ provides an efficient representation of $\hat{\sigma}$.

Hence, we know an efficient representation of $\alpha := \hat{\varphi}' \circ \sigma' \circ \hat{\sigma} \circ \varphi \in \text{End}(E_A)$.
We now prove that $\alpha$ is not scalar. Indeed, if it was, we would have $\alpha = [\lambda]$
for some $\lambda \in \mathbb{Z}$ and $qq'\ell'^2f' = \lambda^2$ where $q := \deg(\sigma)$ and $q' := \deg(\sigma')$ are
prime to $\ell'$. Hence, $\lambda = \ell'^{f'}\lambda'$ with $\lambda' \in \mathbb{Z}$ prime to $\ell'$ ($\lambda'^2 = qq'$). It follows that
$[q']\hat{\sigma} \circ \varphi = [\lambda']\hat{\sigma}' \circ \varphi'$. Since $q, q'$ and $\lambda'$ are prime to $\ell'$, we get that $\ker(\varphi) = \ker(\varphi')$
i.e. $\varphi = \varphi'$ up to post-composition by an automorphism. Contradiction. This
completes the proof. $\square$

For RigorousSQIsignHD, our special soundness argument does not apply be-
cause we have no guarantee on $q$ in general. For that reason, we need to come
back to the formal definition of knowledge soundess given in [17, Definition 6.3.1].
This analysis is conducted in [9, § D.1].

The previous proof of knowledge would be trivial if it was easy to find an
endomorphism. Fortunately, this is a well-known hard problem in isogeny-based
cryptography.

**Problem 18** (Supersingular Endomorphism Problem). Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, find an efficient representation of a non-scalar endomorphism $\alpha \in \text{End}(E)$.
This problem is very similar to [10, Problem 1], except that we do not require
the endomorphism to have smooth degree. This does not seem to make the prob-
lem easier since the endomorphisms solution to this can be evaluated (which was
the reason why smoothness was imposed in the first place). The supersingular
endomorphism ring problem (Problem 19) reduces to Problem 18. Problem 19
is notoriously hard and it has been proven it is equivalent to path finding in the
supersingular $\ell$-isogeny graph [41]. The heuristic reduction from Problem 19 to
18 is given by [12, Algorithm 8]. Basically, if we have an oracle finding endomor-
phisms of $E$, we call this oracle until we have found enough endomorphisms to
generate $\text{End}(E)$.

**Problem 19** (Supersingular Endomorphism Ring Problem). Given a supersin-
gular elliptic curve $E/\mathbb{F}_{p^2}$, find four endomorphisms of $E$ (that we can evaluate)
forming a $\mathbb{Z}$-basis of $\text{End}(E)$.

**5.2 Heuristic Zero-Knowledge Property**

The proof of the zero-knowledge property of SQIsignHD uses an oracle gener-
ating isogenies of non-smooth degree. To our knowledge, there is no efficient
algorithm implementing such an oracle. Nonetheless, it is believed that access to
such an oracle does not affect the hardness of the underlying problem (the endo-
morphism ring problem, see Section 5.3). In RigorousSQIsignHD, the definition
of such an oracle is very natural. In FastSQIsignHD, we add (mild) conditions on
the degree to account for the computational constraints imposed by the method
in dimension 4. These degree constraints are the main reason why the signatures
are represented in dimension 8 instead of 4 in RigorousSQIsignHD. Our proof is
limited to FastSQIsignHD in this section and we refer to [9, § D.2] for an analysis
of RigorousSQIsignHD.

**Definition 20.** A random uniform good degree isogeny oracle (RUGDIO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and returning an efficient representation of a random isogeny $\sigma : E \to E'$ of $\ell$-good degree prime to $\ell'$, such that: (i) the distribution of $E'$ is uniform in the supersingular isogeny graph and (ii) the conditional distribution of $\sigma$ given $E'$ is uniform among isogenies $E \to E'$ of $\ell$-good degree prime to $\ell'$.

In addition to the constraint on the degree of the RUGDIO output, we add
constraints on the distributions of isogenies. Those constraints are necessary
to construct a simulator of FastSQIsignHD. We already justified that these con-
straints can be mathematically satisfied, namely that for all supersingular elliptic
curves $E$ and $E'$, there exists $\sigma : E \to E'$ of $\ell$-good norm. As explained in
Section 4.2, taking $\ell$ slightly bigger than $\sqrt{p}$ by a few bits is heuristically suffi-
cient. Note that to prove the zero-knowledge property, we not only need access
to a RUGDIO, but also to make a heuristic assumption on the distribution of the
commitment $E_1$. This assumption is no longer necessary in RigorousSQIsignHD.

**Theorem 21.** *Assume that the commitment $E_1$ is computationally indistinguishable from an elliptic curve chosen uniformly at random in the supersingular*
This problem is very similar to [10, Problem 1], except that we do not require
the endomorphism to have smooth degree. This does not seem to make the prob-
lem easier since the endomorphisms solution to this can be evaluated (which was
the reason why smoothness was imposed in the first place). The supersingular
endomorphism ring problem (Problem 19) reduces to Problem 18. Problem 19
is notoriously hard and it has been proven it is equivalent to path finding in the
supersingular $\ell$-isogeny graph [41]. The heuristic reduction from Problem 19 to
18 is given by [12, Algorithm 8]. Basically, if we have an oracle finding endomor-
phisms of $E$, we call this oracle until we have found enough endomorphisms to
generate $\text{End}(E)$.

**Problem 19** (Supersingular Endomorphism Ring Problem). Given a supersin-
gular elliptic curve $E/\mathbb{F}_{p^2}$, find four endomorphisms of $E$ (that we can evaluate)
forming a $\mathbb{Z}$-basis of $\text{End}(E)$.

**5.2 Heuristic Zero-Knowledge Property**

The proof of the zero-knowledge property of SQIsignHD uses an oracle gener-
ating isogenies of non-smooth degree. To our knowledge, there is no efficient
algorithm implementing such an oracle. Nonetheless, it is believed that access to
such an oracle does not affect the hardness of the underlying problem (the endo-
morphism ring problem, see Section 5.3). In RigorousSQIsignHD, the definition
of such an oracle is very natural. In FastSQIsignHD, we add (mild) conditions on
the degree to account for the computational constraints imposed by the method
in dimension 4. These degree constraints are the main reason why the signatures
are represented in dimension 8 instead of 4 in RigorousSQIsignHD. Our proof is
limited to FastSQIsignHD in this section and we refer to [9, § D.2] for an analysis
of RigorousSQIsignHD.

**Definition 20.** A random uniform good degree isogeny oracle (RUGDIO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and returning an efficient representation of a random isogeny $\sigma : E \to E'$ of $\ell$-good degree prime to $\ell'$, such that: (i) the distribution of $E'$ is uniform in the supersingular isogeny graph and (ii) the conditional distribution of $\sigma$ given $E'$ is uniform among isogenies $E \to E'$ of $\ell$-good degree prime to $\ell'$.

In addition to the constraint on the degree of the RUGDIO output, we add
constraints on the distributions of isogenies. Those constraints are necessary
to construct a simulator of FastSQIsignHD. We already justified that these con-
straints can be mathematically satisfied, namely that for all supersingular elliptic
curves $E$ and $E'$, there exists $\sigma : E \to E'$ of $\ell$-good norm. As explained in
Section 4.2, taking $\ell$ slightly bigger than $\sqrt{p}$ by a few bits is heuristically suffi-
cient. Note that to prove the zero-knowledge property, we not only need access
to a RUGDIO, but also to make a heuristic assumption on the distribution of the
commitment $E_1$. This assumption is no longer necessary in RigorousSQIsignHD.

**Theorem 21.** *Assume that the commitment $E_1$ is computationally indistinguishable from an elliptic curve chosen uniformly at random in the supersingular*
isogeny graph. Then, the FastSQIsignHD identification protocol is computation-
ally honest-verifier zero knowledge in the RUGDIO model.

In other words, under this assumption, there exists a random polynomial
time simulator $S$ with access to a RUGDIO that simulates transcripts $(E_1, \varphi, R)$
with a computationally indistinguishable distribution from the transcripts of the
FastSQIsignHD identification protocol.

Proof. First, we explain how to construct the simulator $S$. The simulator starts by generating a challenge $\varphi' : E_A \to E'_2$. Then, it applies the RUGDIO on entry $E'_2$ to get an efficient representation of a dual response isogeny $\hat{\sigma}' : E'_2 \to E'_1$. We can use this efficient representation to evaluate $\hat{\sigma}'$ on $E'_2[\ell^f]$ and obtain its degree in polynomial time in $\log(p)^8$. Then, as explained in the proof of Proposition 17, we can compute a dimension 4 isogeny representation of $\hat{\sigma}'$, which is also to an efficient representation of $\sigma'$. Hence, we can compute $R' := (\sigma'(P_1), \sigma'(P_2), q')$ in polynomial time, where $(P_1, P_2)$ is a canonical basis of $E'_1[\ell^f]$ and $q' := \deg(\sigma')$.

We now prove that the transcripts $(E'_1, \varphi', R')$ of $S$ are statistically indis-
tinguishable from the transcripts $(E_1, \varphi, R)$ of the FastSQIsignHD identification
protocol. By construction, $\varphi$ and $\varphi'$ have the same distribution. Given $E'_2$, by
the definition of the RUGDIO, $E'_1$ is uniformly random in the supersingular
isogeny graph. Besides, $E_1$ is statistically close to uniformly random as well by
assumption.

Finally, conditionally to $E'_1$ and $E'_2$, $\hat{\sigma}'$ (represented by $R'$) is uniformly ran-
dom among the isogenies $E'_2 \to E'_1$ of $\ell^e$-good degree prime to $\ell'$ by the defi-
nition of the RUGDIO. The dual map $\phi \mapsto \hat{\phi}$ being a bijection preserving the
degree, conditionally to $E'_1$ and $E'_2$, $\sigma'$ is also uniformly random among the isoge-
nies $E'_2 \to E'_1$ of $\ell^e$-good degree prime to $\ell'$. By construction (see Section 4.2),
conditionally to $E_1$ and $E_2$, $\sigma$ has the same distribution. This completes the
proof. $\quad \square$

It remains to justify that the commitment $E_1$ is computationally indistin-
guishable from an elliptic curve chosen uniformly at random in the supersingular
isogeny graph. While **RigorousCommit** satisfies statistical indistinguishability, the
variant **FastCommit** relies on heuristics. Consider the distributions on $E_1$ induced
by the following procedures

1. Return the output $E_1$ of FastCommit.

2. Generate a uniformly random cyclic endomorphism $\gamma$ of $E_0$ of degree $\ell^{2f} \ell'^{2f'}$.
Factor it as $\gamma = \hat{\phi}' \circ \phi$ with $\deg(\phi) = \ell^{2f}$. Return the codomain $E_1$ of $\phi$.

3. Generate a uniformly random cyclic isogeny $\phi$ from $E_0$ of degree $\ell^{2f}$. Let $E_1$ be its codomain; let $m$ be the number of cyclic isogenies $\phi' : E_0 \to E_1$ of degree $\ell'^{2f'}$. Return $E_1$ with probability $m/M$ (for some fixed upper bound $M$ on $m$, for instance $M = (\ell' + 1)\ell'^{2f'}-1$), otherwise resample.

4. Generate a uniformly random cyclic isogeny $\phi$ from $E_0$ of degree $\ell^{2f}$; return its codomain $E_1$.

<footnote n="8">⁸ We can compute the norm of $\sigma'$ on $E'_2[m]$ (which is $\deg(\sigma') \bmod m$) for a bunch of small primes $m$ and apply the Chinese remainder theorem.</footnote>
isogeny graph. Then, the FastSQIsignHD identification protocol is computation-
ally honest-verifier zero knowledge in the RUGDIO model.

In other words, under this assumption, there exists a random polynomial
time simulator $S$ with access to a RUGDIO that simulates transcripts $(E_1, \varphi, R)$
with a computationally indistinguishable distribution from the transcripts of the
FastSQIsignHD identification protocol.

Proof. First, we explain how to construct the simulator $S$. The simulator starts by generating a challenge $\varphi' : E_A \to E'_2$. Then, it applies the RUGDIO on entry $E'_2$ to get an efficient representation of a dual response isogeny $\hat{\sigma}' : E'_2 \to E'_1$. We can use this efficient representation to evaluate $\hat{\sigma}'$ on $E'_2[\ell^f]$ and obtain its degree in polynomial time in $\log(p)^8$. Then, as explained in the proof of Proposition 17, we can compute a dimension 4 isogeny representation of $\hat{\sigma}'$, which is also to an efficient representation of $\sigma'$. Hence, we can compute $R' := (\sigma'(P_1), \sigma'(P_2), q')$ in polynomial time, where $(P_1, P_2)$ is a canonical basis of $E'_1[\ell^f]$ and $q' := \deg(\sigma')$.

We now prove that the transcripts $(E'_1, \varphi', R')$ of $S$ are statistically indis-
tinguishable from the transcripts $(E_1, \varphi, R)$ of the FastSQIsignHD identification
protocol. By construction, $\varphi$ and $\varphi'$ have the same distribution. Given $E'_2$, by
the definition of the RUGDIO, $E'_1$ is uniformly random in the supersingular
isogeny graph. Besides, $E_1$ is statistically close to uniformly random as well by
assumption.

Finally, conditionally to $E'_1$ and $E'_2$, $\hat{\sigma}'$ (represented by $R'$) is uniformly ran-
dom among the isogenies $E'_2 \to E'_1$ of $\ell^e$-good degree prime to $\ell'$ by the defi-
nition of the RUGDIO. The dual map $\phi \mapsto \hat{\phi}$ being a bijection preserving the
degree, conditionally to $E'_1$ and $E'_2$, $\sigma'$ is also uniformly random among the isoge-
nies $E'_2 \to E'_1$ of $\ell^e$-good degree prime to $\ell'$. By construction (see Section 4.2),
conditionally to $E_1$ and $E_2$, $\sigma$ has the same distribution. This completes the
proof. $\quad \square$

It remains to justify that the commitment $E_1$ is computationally indistin-
guishable from an elliptic curve chosen uniformly at random in the supersingular
isogeny graph. While **RigorousCommit** satisfies statistical indistinguishability, the
variant **FastCommit** relies on heuristics. Consider the distributions on $E_1$ induced
by the following procedures

1. Return the output $E_1$ of FastCommit.

2. Generate a uniformly random cyclic endomorphism $\gamma$ of $E_0$ of degree $\ell^{2f} \ell'^{2f'}$.
Factor it as $\gamma = \hat{\phi}' \circ \phi$ with $\deg(\phi) = \ell^{2f}$. Return the codomain $E_1$ of $\phi$.

3. Generate a uniformly random cyclic isogeny $\phi$ from $E_0$ of degree $\ell^{2f}$. Let $E_1$ be its codomain; let $m$ be the number of cyclic isogenies $\phi' : E_0 \to E_1$ of degree $\ell'^{2f'}$. Return $E_1$ with probability $m/M$ (for some fixed upper bound $M$ on $m$, for instance $M = (\ell' + 1)\ell'^{2f'}-1$), otherwise resample.

4. Generate a uniformly random cyclic isogeny $\phi$ from $E_0$ of degree $\ell^{2f}$; return its codomain $E_1$.

<footnote n="8">⁸ We can compute the norm of $\sigma'$ on $E'_2[m]$ (which is $\deg(\sigma') \bmod m$) for a bunch of small primes $m$ and apply the Chinese remainder theorem.</footnote>
5. Return a uniformly random elliptic curve $E_1$.

We argue that each distribution from the list is somewhat close to the next. The difference between 1 and 2 is that in FastCommit, the endomorphism $\gamma$ is not truly uniform: they follow a distribution biased by the fact that some intermediate result should be easy to factor. Since this property appears somewhat decorrelated from the final distribution of $\gamma$ it seems plausible to argue that the distribution of $\gamma$ in 1 is close to the one in 2. The distributions 2 and 3 are actually identical: distribution 3 simulated distribution 2 by rejection sampling. The difference between 3 and 4 is that $m$ is not necessarily a (positive) constant; it is however heuristically expected to be almost a constant: there are about $(\ell'-1)\ell'^{2f'-1}$ possible paths, and about $p/12$ vertices, so we expect about $m \approx 12(\ell'-1)\ell'^{2f'-1}/p$ distinct paths to any fixed vertex. The difference between 4 and 5 is similar, but reasoning about $\ell$-paths instead of $\ell'$-paths.

Note that the differences at some of these steps are statistically significant. We only argue that they are not computationally detectable, at least when the endomorphism rings are not known.

## 5.3 On Hardness of the Supersingular Endomorphism Problem with Access to an Auxiliary Oracle

The FastSQIsignHD identification protocol is sound assuming the hardness of the supersingular endomorphism problem 18, and zero-knowledge with respect to a simulator that has access to a RUGDIO (or a RADIO for RigorousSQIsignHD, as defined in [9, § D.2]). For the resulting signature scheme to be secure, one therefore needs to assume that the supersingular endomorphism problem remains hard even when given access to a RUGDIO.

While it currently seems out of reach to prove that the supersingular endomorphism problem is equivalent to the variant with RUGDIO access, let us argue that the RUGDIO indeed does not help. We focus the following discussion on the RUGDIO, but the same arguments apply to the RADIO despite the slightly different distribution.

The RUGDIO allows to generate random isogenies with a chosen domain $E$. Note that this task is already known to be easy, with isogenies of smooth degree. The RUGDIO only lifts this smoothness restriction and replaces it with other restrictions ($\ell^e$-good and prime to $\ell$): it allows to generate random isogenies whose degrees have large prime factors. It does not allow to reach more target curves, nor does it give more control on which specific target to hit: the target curve is uniformly distributed in the supersingular graph, which was already possible with smooth isogenies.

Smoothness of random isogenies has never been an inconvenience in finding endomorphisms. In fact, the current fastest algorithms for this problem only require very smooth degree isogenies, typically a power of 2. The reason is the following: the purpose of constructing a random isogeny from a fixed source is to reach a random target. As very smooth isogenies (even 2-smooth) are sufficient for optimal randomisation, there is no incentive to involve much larger prime
5. Return a uniformly random elliptic curve $E_1$.

We argue that each distribution from the list is somewhat close to the next. The difference between 1 and 2 is that in FastCommit, the endomorphism $\gamma$ is not truly uniform: they follow a distribution biased by the fact that some intermediate result should be easy to factor. Since this property appears somewhat decorrelated from the final distribution of $\gamma$ it seems plausible to argue that the distribution of $\gamma$ in 1 is close to the one in 2. The distributions 2 and 3 are actually identical: distribution 3 simulated distribution 2 by rejection sampling. The difference between 3 and 4 is that $m$ is not necessarily a (positive) constant; it is however heuristically expected to be almost a constant: there are about $(\ell'-1)\ell'^{2f'-1}$ possible paths, and about $p/12$ vertices, so we expect about $m \approx 12(\ell'-1)\ell'^{2f'-1}/p$ distinct paths to any fixed vertex. The difference between 4 and 5 is similar, but reasoning about $\ell$-paths instead of $\ell'$-paths.

Note that the differences at some of these steps are statistically significant. We only argue that they are not computationally detectable, at least when the endomorphism rings are not known.

## 5.3 On Hardness of the Supersingular Endomorphism Problem with Access to an Auxiliary Oracle

The FastSQIsignHD identification protocol is sound assuming the hardness of the supersingular endomorphism problem 18, and zero-knowledge with respect to a simulator that has access to a RUGDIO (or a RADIO for RigorousSQIsignHD, as defined in [9, § D.2]). For the resulting signature scheme to be secure, one therefore needs to assume that the supersingular endomorphism problem remains hard even when given access to a RUGDIO.

While it currently seems out of reach to prove that the supersingular endomorphism problem is equivalent to the variant with RUGDIO access, let us argue that the RUGDIO indeed does not help. We focus the following discussion on the RUGDIO, but the same arguments apply to the RADIO despite the slightly different distribution.

The RUGDIO allows to generate random isogenies with a chosen domain $E$. Note that this task is already known to be easy, with isogenies of smooth degree. The RUGDIO only lifts this smoothness restriction and replaces it with other restrictions ($\ell^e$-good and prime to $\ell$): it allows to generate random isogenies whose degrees have large prime factors. It does not allow to reach more target curves, nor does it give more control on which specific target to hit: the target curve is uniformly distributed in the supersingular graph, which was already possible with smooth isogenies.

Smoothness of random isogenies has never been an inconvenience in finding endomorphisms. In fact, the current fastest algorithms for this problem only require very smooth degree isogenies, typically a power of 2. The reason is the following: the purpose of constructing a random isogeny from a fixed source is to reach a random target. As very smooth isogenies (even 2-smooth) are sufficient for optimal randomisation, there is no incentive to involve much larger prime
factors. More specifically, the best known strategies to solve the supersingular
endomorphism problem [11] have classical time complexity $\tilde{O}(\sqrt{p})$ (and quantum
time complexity $\tilde{O}(p^{1/4})$ with a Grover argument [16]) and essentially perform a
meet-in-the-middle search in the supersingular isogeny graph. Access to a RUG-
DIO would allow to use isogenies of a different shape in the search, but would not
speed it up, as the probability to find isogenies with matching codomains stays
the same. Another illustration that having access to non-smooth degree isoge-
nies does not help is the fact that the discovery of the $\sqrt{\ell}$-lu algorithm [3] (which
dramatically improved the complexity of computing prime degree isogenies) did
not affect the state-of-the-art of the supersingular endomorphism problem.

The above arguments support that random isogenies of non-smooth degrees
are not more helpful than random isogenies of smooth degrees. Now, one may
be concerned that the encoding of the output of the RUGDIO may leak more
information than it should. Non-smooth degree isogenies are represented as a
component of a higher dimensional isogeny (Section 2.2). This representation
is universal, in the sense that any efficient representation of an isogeny can be
efficiently rewritten in this form. In particular, this encoding contains no more
information than any other efficient representation of the same isogeny.

# 6 The SQIsignHD Digital Signature Scheme

The SQIsignHD identification protocol that we presented yields a digital sig-
nature scheme via the Fiat-Shamir transform. The security of the transform of
both versions FastSQIsignHD and RigorousSQIsignHD follows from the analysis
conducted in Section 5 and [9, § D], so the digital signature is also secure un-
der the same computational assumptions. Namely, we have seen it is universally
unforgeable under chosen message attacks in the random oracle and RADIO or
RUGDIO model, assuming the hardness of the endomorphism ring problem. In
this section, we present the performance of the signature scheme obtained from
FastSQIsignHD.

## 6.1 Compactness

As explained before, the signature is made of the data ($E_1$, $q$, $\sigma(P_1)$, $\sigma(P_2)$),
with $q < \ell^e$, $\sigma: E_1 \rightarrow E_2$ a $q$-isogeny and ($P_1$, $P_2$) a basis of $E_1[\ell^f]$ determined
canonically.

$E_1$ can be entirely determined by its $j$-invariant $j(E_1) \in \mathbb{F}_{p^2}$. Since any
element of $\mathbb{F}_{p^2}$ can be represented by 2 integers in $[0; p-1]$, storing $j(E_1)$
takes approximately $2\log_2(p) \approx 4\lambda$ bits, given that $p = \Theta(2^{2\lambda})$ (where $\lambda$ is the
security level). Similarly, $q < \ell^e \approx \sqrt{p}$, so $q$ is an integer of $1/2\log_2(p) \approx \lambda$ bits.

The points $\sigma(P_1)$ and $\sigma(P_2)$ need not be represented explicitely with co-
ordinates in $\mathbb{F}_{p^2}$. They can be compressed. Indeed, if we generate a canon-
ical basis ($Q_1, Q_2$) of $E_2[\ell^f]$, then we may write $\sigma(P_1) = a_1Q_1 + b_1Q_2$ and
$\sigma(P_2) = a_2Q_1 + b_2Q_2$ with $a_1, b_1, a_2, b_2 \in \mathbb{Z}/\ell^f\mathbb{Z}$. Storing the scalars $a_1, b_1, a_2, b_2$
requires $4f$ bits (assuming $\ell=2$, which will be the case in practice).
factors. More specifically, the best known strategies to solve the supersingular endomorphism problem [11] have classical time complexity $\tilde{O}(\sqrt{p})$ (and quantum time complexity $\tilde{O}(p^{1/4})$ with a Grover argument [16]) and essentially perform a meet-in-the-middle search in the supersingular isogeny graph. Access to a RUGDIO would allow to use isogenies of a different shape in the search, but would not speed it up, as the probability to find isogenies with matching codomains stays the same. Another illustration that having access to non-smooth degree isogenies does not help is the fact that the discovery of the $\sqrt{\ell}$-lu algorithm [3] (which dramatically improved the complexity of computing prime degree isogenies) did not affect the state-of-the-art of the supersingular endomorphism problem.

The above arguments support that random isogenies of non-smooth degrees are not more helpful than random isogenies of smooth degrees. Now, one may be concerned that the encoding of the output of the RUGDIO may leak more information than it should. Non-smooth degree isogenies are represented as a component of a higher dimensional isogeny (Section 2.2). This representation is universal, in the sense that any efficient representation of an isogeny can be efficiently rewritten in this form. In particular, this encoding contains no more information than any other efficient representation of the same isogeny.

# 6 The SQIsignHD Digital Signature Scheme

The SQIsignHD identification protocol that we presented yields a digital signature scheme via the Fiat-Shamir transform. The security of the transform of both versions FastSQIsignHD and RigorousSQIsignHD follows from the analysis conducted in Section 5 and [9, § D], so the digital signature is also secure under the same computational assumptions. Namely, we have seen it is universally unforgeable under chosen message attacks in the random oracle and RADIO or RUGDIO model, assuming the hardness of the endomorphism ring problem. In this section, we present the performance of the signature scheme obtained from FastSQIsignHD.

## 6.1 Compactness

As explained before, the signature is made of the data $(E_1, q, \sigma(P_1), \sigma(P_2))$, with $q < \ell^e$, $\sigma: E_1 \to E_2$ a $q$-isogeny and $(P_1, P_2)$ a basis of $E_1[\ell^f]$ determined canonically.

$E_1$ can be entirely determined by its $j$-invariant $j(E_1) \in \mathbb{F}_{p^2}$. Since any element of $\mathbb{F}_{p^2}$ can be represented by 2 integers in $[0; p-1]$, storing $j(E_1)$ takes approximately $2\log_2(p) \approx 4\lambda$ bits, given that $p = \Theta(2^{2\lambda})$ (where $\lambda$ is the security level). Similarly, $q < \ell^e \approx \sqrt{p}$, so $q$ is an integer of $1/2\log_2(p) \approx \lambda$ bits.

The points $\sigma(P_1)$ and $\sigma(P_2)$ need not be represented explicitely with co-ordinates in $\mathbb{F}_{p^2}$. They can be compressed. Indeed, if we generate a canon-ical basis $(Q_1, Q_2)$ of $E_2[\ell^f]$, then we may write $\sigma(P_1) = a_1Q_1 + b_1Q_2$ and $\sigma(P_2) = a_2Q_1 + b_2Q_2$ with $a_1, b_1, a_2, b_2 \in \mathbb{Z}/\ell^f\mathbb{Z}$. Storing the scalars $a_1, b_1, a_2, b_2$ requires $4f$ bits (assuming $\ell=2$, which will be the case in practice).
Actually, we can gain $f$ bits by omitting one of the scalars $a_1, b_1, a_2, b_2$ if we use the Weil pairing. Indeed, we have

$$e_{\ell f}(\sigma(P_1), \sigma(P_2)) = e_{\ell f}(P_1, P_2)^q.$$

$$e_{\ell f}(\sigma(P_1), \sigma(P_2)) = e_{\ell f}(a_1Q_1 + b_1Q_2, a_2Q_1 + b_2Q_2) = e_{\ell f}(Q_1, Q_2)^{a_1b_2-b_1a_2}.$$

Since $(P_1, P_2)$ and $(Q_1, Q_2)$ are basis of $E_1[\ell^f]$ and $E_2[\ell^f]$ respectively, $e_{\ell f}(P_1, P_2)$ and $e_{\ell f}(Q_1, Q_2)$ are both primitive $\ell^f$-th root of unity. Hence, we may find $k \in (\mathbb{Z}/\ell^f\mathbb{Z})^\times$ such that $e_{\ell f}(P_1, P_2) = e_{\ell f}(Q_1, Q_2)^k$, and we must have

$$a_1b_2 - b_1a_2 \equiv kq \mod \ell^f \qquad (2)$$

Since $\ell^f|p-1$, the $\ell^f$-th Weil pairing takes values in $\mathbb{F}_p^*$, so we find $k$ easily by solving a discrete logarithm problem in a subgroup of order $\ell^f$ of $\mathbb{F}_p^*$ by Pohlig-Hellman [29] techniques (which apply since $p-1$ is smooth).

Since $q$ is prime to $\ell$, $\sigma(P_1)$ have order $\ell^f$ so either $a_1$ or $b_1$ is invertible modulo $\ell^f$. If $a_1$ is invertible, we can recover $b_2$ from the other scalars using equation 2 and we can recover $a_2$ otherwise. Hence we only need 3 scalars among 4.

We can make the representation of $\sigma(P_1)$ and $\sigma(P_2)$ even more compact. Indeed, by Remark 4.2 the $\ell^e$-isogeny $F$ representing $\sigma$ can be computed as long as $2f \ge e+4$. But in FastSQIsignHD, $f \simeq e \simeq \lambda$ so we may use points of $\ell^{f_1}$-torsion with $f_1 := \lceil e/2 \rceil + 3$ instead of points of $\ell^f$-torsion. This reduces the storage cost of $\sigma(P_1)$ and $\sigma(P_2)$ from $3f \simeq 3\lambda$ to $3f_1 \simeq 3/2\lambda$.

On the whole, we can represent the signatures with $s = 13/2\lambda + O(\log(\lambda))$ bits if we use the compression and decompression algorithms given by Algorithms 6 and 7, breaking the previous record of SQIsign. Indeed, in SQIsign, the kernels of the signature isogeny $\sigma$ (of degree $p^{15/4}$) and of the dual of the challenge (of degree $\sqrt{p}$) need to be transmitted so we get a signature of size $s = 17/2\lambda + O(\log(\lambda))$ at least.

**Example:** For NIST-I security level ($\lambda = 128$ bits), we can choose the parameters $p = 13 \cdot 2^{126}3^{78} - 1$, $e = 142$ and $f_1 = 73$. The total signature size in SQIsignHD is $2[\log_2(p)] + e + 3f_1 + 1 = 870$ bits or 109 bytes. SQIsign signatures took 177 bytes in the NIST-I implementation [37].

We can use the same techniques in dimension 8 but we output signatures of size $s = 14\lambda + O(\log(\lambda))$ instead of $13/2\lambda + O(\log(\lambda))$ since $e$ is bigger ($\ell^e = \Theta(p^2)$). Details may be found in [9, § C.3].

## 6.2 Time Efficiency

**Low Signing Time (and Key Generation Time).** In the latest version of SQIsign [13], the signature time was dominated by the computation of $30$ T-isogenies with $T \simeq p^{5/4}$. Each T-isogeny is rather slow as $T$ typically has prime factors as large as a few thousands. FastSQIsignHD signing only requires a handful of $\ell^f$ and $\ell^{f'}$-isogenies, where typically $\ell = 2$ and $\ell' = 3$. Computing these isogenies is orders of magnitude faster than a SQIsign [13] signature.
Actually, we can gain $f$ bits by omitting one of the scalars $a_1, b_1, a_2, b_2$ if we use the Weil pairing. Indeed, we have

$$e_{\ell f}(\sigma(P_1), \sigma(P_2)) = e_{\ell f}(P_1, P_2)^q.$$

$$e_{\ell f}(\sigma(P_1), \sigma(P_2)) = e_{\ell f}(a_1Q_1 + b_1Q_2, a_2Q_1 + b_2Q_2) = e_{\ell f}(Q_1, Q_2)^{a_1b_2-b_1a_2}.$$

Since $(P_1, P_2)$ and $(Q_1, Q_2)$ are basis of $E_1[\ell^f]$ and $E_2[\ell^f]$ respectively, $e_{\ell f}(P_1, P_2)$ and $e_{\ell f}(Q_1, Q_2)$ are both primitive $\ell^f$-th root of unity. Hence, we may find $k \in (\mathbb{Z}/\ell^f\mathbb{Z})^\times$ such that $e_{\ell f}(P_1, P_2) = e_{\ell f}(Q_1, Q_2)^k$, and we must have

$$a_1b_2 - b_1a_2 \equiv kq \mod \ell^f \qquad (2)$$

Since $\ell^f|p - 1$, the $\ell^f$-th Weil pairing takes values in $\mathbb{F}_p^*$, so we find $k$ easily by solving a discrete logarithm problem in a subgroup of order $\ell^f$ of $\mathbb{F}_p^*$ by Pohlig-Hellman [29] techniques (which apply since $p - 1$ is smooth).

Since $q$ is prime to $\ell$, $\sigma(P_1)$ have order $\ell^f$ so either $a_1$ or $b_1$ is invertible modulo $\ell^f$. If $a_1$ is invertible, we can recover $b_2$ from the other scalars using equation 2 and we can recover $a_2$ otherwise. Hence we only need 3 scalars among 4.

We can make the representation of $\sigma(P_1)$ and $\sigma(P_2)$ even more compact. Indeed, by Remark 4.2 the $\ell^e$-isogeny $F$ representing $\sigma$ can be computed as long as $2f \ge e + 4$. But in FastSQIsignHD, $f \simeq e \simeq \lambda$ so we may use points of $\ell^{f_1}$-torsion with $f_1 := \lceil e/2 \rceil + 3$ instead of points of $\ell^f$-torsion. This reduces the storage cost of $\sigma(P_1)$ and $\sigma(P_2)$ from $3f \simeq 3\lambda$ to $3f_1 \simeq 3/2\lambda$.

On the whole, we can represent the signatures with $s = 13/2\lambda + O(\log(\lambda))$ bits if we use the compression and decompression algorithms given by Algorithms 6 and 7, breaking the previous record of SQIsign. Indeed, in SQIsign, the kernels of the signature isogeny $\sigma$ (of degree $p^{15/4}$) and of the dual of the challenge (of degree $\sqrt{p}$) need to be transmitted so we get a signature of size $s = 17/2\lambda + O(\log(\lambda))$ at least.

**Example:** For NIST-I security level ($\lambda = 128$ bits), we can choose the parameters $p = 13 \cdot 2^{126}3^{78} - 1$, $e = 142$ and $f_1 = 73$. The total signature size in SQIsignHD is $2[\log_2(p)] + e + 3f_1 + 1 = 870$ bits or 109 bytes. SQIsign signatures took 177 bytes in the NIST-I implementation [37].

We can use the same techniques in dimension 8 but we output signatures of size $s = 14\lambda + O(\log(\lambda))$ instead of $13/2\lambda + O(\log(\lambda))$ since $e$ is bigger ($\ell^e = \Theta(p^2)$). Details may be found in [9, § C.3].

## 6.2 Time Efficiency

**Low Signing Time (and Key Generation Time).** In the latest version of SQIsign [13], the signature time was dominated by the computation of $30$ T-isogenies with $T \simeq p^{5/4}$. Each T-isogeny is rather slow as $T$ typically has prime factors as large as a few thousands. FastSQIsignHD signing only requires a handful of $\ell^f$ and $\ell^{f'}$-isogenies, where typically $\ell = 2$ and $\ell' = 3$. Computing these isogenies is orders of magnitude faster than a SQIsign [13] signature.
<table><caption>**Algorithm 6:** Compression</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>Compute j(E<sub>1</sub>) ∈ F<sub>p<sup>2</sup></sub>;</td></tr><tr><td>2</td><td>Let ζ be a canonical generator of F<sub>p<sup>2</sup></sub>. Write ζ := n<sub>1</sub> + n<sub>2</sub>ζ where n<sub>1</sub>, n<sub>2</sub> ∈ F<sub>p</sub> are represented by integers in ⌊0; p − 1⌋ of length ⌈log<sub>2</sub>(p)⌋ bits each;</td></tr><tr><td>3</td><td>Compute the canonical basis (Q<sub>1</sub>, Q<sub>2</sub>) of E<sub>2</sub>[ℓ<sup>f<sub>1</sub></sup>];</td></tr><tr><td>4</td><td>Find k ∈ (Z/ℓ<sup>f<sub>1</sub></sup>Z)<sup>×</sup> such that e<sub>ℓf<sub>1</sub></sub>(P<sub>1</sub>, P<sub>2</sub>) = e<sub>ℓf<sub>1</sub></sub>(Q<sub>1</sub>, Q<sub>2</sub>)<sup>k</sup>;</td></tr><tr><td>5</td><td>Find a<sub>1</sub>, b<sub>1</sub>, a<sub>2</sub>, b<sub>2</sub> ∈ Z/ℓ<sup>f<sub>1</sub></sup>Z such that σ(P<sub>1</sub>) = a<sub>1</sub>Q<sub>1</sub> + b<sub>1</sub>Q<sub>2</sub> and σ(P<sub>2</sub>) = a<sub>2</sub>Q<sub>1</sub> + b<sub>2</sub>Q<sub>2</sub>;</td></tr><tr><td>6</td><td>if ℓ ∤ a<sub>1</sub> then</td></tr><tr><td>7</td><td>&nbsp;&nbsp;&nbsp;&nbsp;Return ||n<sub>1</sub>||n<sub>2</sub>||q||a<sub>1</sub>||b<sub>1</sub>||b<sub>2</sub>||;</td></tr><tr><td>8</td><td>else</td></tr><tr><td>9</td><td>&nbsp;&nbsp;&nbsp;&nbsp;Return ||n<sub>1</sub>||n<sub>2</sub>||q||a<sub>1</sub>||b<sub>1</sub>||a<sub>2</sub>||;</td></tr><tr><td>10</td><td>end</td></tr></tbody></table>

We have implemented FastSQIsignHD in C, based on the implementation of SQIsign [37]. The signature takes an average time of 28 ms at the 128 bits security level on an Intel(R) Core(TM) i5-1335U 4600MHz CPU (average over 1000 signature computations). Key generation takes 70 ms on average on the same CPU. While signature is already close to ten times faster than the fastest implementations of SQIsign [13, 23], we refrain from reporting a detailed clock-cycle comparison, as the bottleneck of our implementation has shifted from isogeny computations to a variety of steps which have not been optimised (as they were negligible in former SQIsign implementations). Most notably, about 29% of the FastSQIsignHD signing time is spent computing two discrete logarithms; a 4.8× speedup is reported in [23] using Tate pairings for comparable discrete logarithm computations. Another 20% is spent solving a quaternion norm equation [22, Algorithm 4], a step that has not been the focus of much attention. In addition, contrary to former implementations of SQIsign, our implementation is purely in C, with no assembly-optimised field arithmetic. Providing a completely optimized implementation is left for future works, yet this first implementation is already compelling.

**Verification Time.** This efficiency gain in the signature is made at the expense of the verification time where a 4-dimensional $l^e$-isogeny has to be computed. Of course $l$-isogenies in dimension 4 are expected to be slower to compute than in dimension 1. Nonetheless, we only have to compute two chains of $l$-isogenies of length $1/4 \log_l(p)$, whereas the verifier had to compute an $l$-isogeny chain of size $15/4 \log_l(p)$ in the last version of SQIsign [13]. Furthermore, our choice of parameters allows for more efficient field arithmetic.

Our experimental sagemath implementation provides an upper bound on the verification time: for 128 bits of security the verification takes around 600 ms on the same CPU as above. We expect this time to be significantly reduced in the
<table><caption>**Algorithm 6:** Compression</caption>
  <tbody>
    <tr>
      <td>1</td>
      <td>Compute $j(E_1) \in \mathbb{F}_{p^2}$;</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Let $\zeta$ be a canonical generator of $\mathbb{F}_{p^2}$. Write $\zeta := n_1 + n_2\zeta$ where $n_1, n_2 \in \mathbb{F}_p$ are represented by integers in $\llbracket 0; p-1 \rrbracket$ of length $\lceil \log_2(p) \rceil$ bits each;</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Compute the canonical basis $(Q_1, Q_2)$ of $E_2[\ell^{f_1}]$;</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Find $k \in (\mathbb{Z}/\ell^{f_1}\mathbb{Z})^\times$ such that $e_{\ell f_1}(P_1, P_2) = e_{\ell f_1}(Q_1, Q_2)^k$;</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Find $a_1, b_1, a_2, b_2 \in \mathbb{Z}/\ell^{f_1}\mathbb{Z}$ such that $\sigma(P_1) = a_1Q_1 + b_1Q_2$ and $\sigma(P_2) = a_2Q_1 + b_2Q_2$;</td>
    </tr>
    <tr>
      <td>6</td>
      <td>if $\ell \nmid a_1$ then</td>
    </tr>
    <tr>
      <td>7</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;Return $\|n_1\|n_2\|q\|a_1\|b_1\|b_2\|$;</td>
    </tr>
    <tr>
      <td>8</td>
      <td>else</td>
    </tr>
    <tr>
      <td>9</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;Return $\|n_1\|n_2\|q\|a_1\|b_1\|a_2\|$;</td>
    </tr>
    <tr>
      <td>10</td>
      <td>end</td>
    </tr>
  </tbody>
</table>

We have implemented FastSQIsignHD in C, based on the implementation of SQIsign [37]. The signature takes an average time of 28 ms at the 128 bits security level on an Intel(R) Core(TM) i5-1335U 4600MHz CPU (average over 1000 signature computations). Key generation takes 70 ms on average on the same CPU. While signature is already close to ten times faster than the fastest implementations of SQIsign [13, 23], we refrain from reporting a detailed clock-cycle comparison, as the bottleneck of our implementation has shifted from isogeny computations to a variety of steps which have not been optimised (as they were negligible in former SQIsign implementations). Most notably, about 29% of the FastSQIsignHD signing time is spent computing two discrete logarithms; a 4.8× speedup is reported in [23] using Tate pairings for comparable discrete logarithm computations. Another 20% is spent solving a quaternion norm equation [22, Algorithm 4], a step that has not been the focus of much attention. In addition, contrary to former implementations of SQIsign, our implementation is purely in C, with no assembly-optimised field arithmetic. Providing a completely optimized implementation is left for future works, yet this first implementation is already compelling.

**Verification Time.** This efficiency gain in the signature is made at the expense of the verification time where a 4-dimensional $\ell^e$-isogeny has to be computed. Of course $\ell$-isogenies in dimension 4 are expected to be slower to compute than in dimension 1. Nonetheless, we only have to compute two chains of $\ell$-isogenies of length $1/4 \log_\ell(p)$, whereas the verifier had to compute an $\ell$-isogeny chain of size $15/4 \log_\ell(p)$ in the last version of SQIsign [13]. Furthermore, our choice of parameters allows for more efficient field arithmetic.

Our experimental sagemath implementation provides an upper bound on the verification time: for 128 bits of security the verification takes around 600 ms on the same CPU as above. We expect this time to be significantly reduced in the
<table><caption>**Algorithm 7: Decompression**</caption>
  <tr>
    <td>1</td>
    <td>Parse ||n<sub>1</sub>||n<sub>2</sub>||q||a<sub>1</sub>||b<sub>1</sub>||c<sub>2</sub>|| &larr; w;</td>
  </tr>
  <tr>
    <td>2</td>
    <td>Set j &larr; n<sub>1</sub> + n<sub>2</sub>&zeta;, where &zeta; is the canonical generator of F<sub>p<sup>2</sup></sub>;</td>
  </tr>
  <tr>
    <td>3</td>
    <td>Compute E<sub>1</sub> of j-invariant j(E<sub>1</sub>) = j;</td>
  </tr>
  <tr>
    <td>4</td>
    <td>Recover the commitment &phi; &larr; F(E<sub>1</sub>, H(E<sub>1</sub>, m)). Let E<sub>2</sub> be the codomain of<br/>&phi;;</td>
  </tr>
  <tr>
    <td>5</td>
    <td>Compute the canonical basis (P<sub>1</sub>, P<sub>2</sub>) of E<sub>1</sub>[l<sup>f<sub>1</sub></sup>] and the canonical basis<br/>(Q<sub>1</sub>, Q<sub>2</sub>) of E<sub>2</sub>[l<sup>f<sub>1</sub></sup>];</td>
  </tr>
  <tr>
    <td>6</td>
    <td>Find k &isin; (Z/l<sup>f<sub>1</sub></sup>Z)<sup>*</sup> such that e<sub>l<sup>f<sub>1</sub></sup></sub>(P<sub>1</sub>, P<sub>2</sub>) = e<sub>l<sup>f<sub>1</sub></sup></sub>(Q<sub>1</sub>, Q<sub>2</sub>)<sup>k</sup>;</td>
  </tr>
  <tr>
    <td>7</td>
    <td>if l &notin; a<sub>1</sub> then</td>
  </tr>
  <tr>
    <td>8</td>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;a<sub>2</sub> &larr; c<sub>2</sub>;</td>
  </tr>
  <tr>
    <td>9</td>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;Find b<sub>2</sub> &isin; Z/l<sup>f<sub>1</sub></sup>Z such that a<sub>1</sub>b<sub>2</sub> &minus; b<sub>1</sub>a<sub>2</sub> &equiv; kq mod l<sup>f<sub>1</sub></sup>;</td>
  </tr>
  <tr>
    <td>10</td>
    <td>else</td>
  </tr>
  <tr>
    <td>11</td>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;b<sub>2</sub> &larr; c<sub>2</sub>;</td>
  </tr>
  <tr>
    <td>12</td>
    <td>&nbsp;&nbsp;&nbsp;&nbsp;Find a<sub>2</sub> &isin; Z/l<sup>f<sub>1</sub></sup>Z such that a<sub>1</sub>b<sub>2</sub> &minus; b<sub>1</sub>a<sub>2</sub> &equiv; kq mod l<sup>f<sub>1</sub></sup>;</td>
  </tr>
  <tr>
    <td>13</td>
    <td>end</td>
  </tr>
  <tr>
    <td>14</td>
    <td>Return E<sub>1</sub>, E<sub>2</sub>, q, P<sub>1</sub>, P<sub>2</sub>, a<sub>1</sub>Q<sub>1</sub> + b<sub>1</sub>Q<sub>2</sub>, a<sub>2</sub>Q<sub>1</sub> + b<sub>2</sub>Q<sub>2</sub>;</td>
  </tr>
</table>

future: new optimisations remain to be implemented, and more importantly a
low level implementation should lead to a significant gain. Currently, the time
spent on verification is as follows: around 60 ms for the challenge computation<fnref n="9" />,
510 ms for the two dimension 4 2⁷¹-isogenies giving F, and 30 ms for the image
of a point through F.

**References**

[1] K. Ahrens. Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott. Cryptology ePrint Archive, Paper 2023/219. 2023. URL: https://eprint.iacr.org/2023/219.

[2] R. Azarderakhsh, D. Jao, K. Kalach, B. Koziel, and C. Leonardi. “Key compression for isogeny-based cryptosystems”. In: *Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography*. Xi’an, China: ACM, 2016, pp. 1–10.

<footnote n="9">⁹ Which essentially consists in computing a chain of 3-isogenies in dimension 1. The signature also needs to compute similar isogenies, and in this case the low level C implementation only takes 1-2 ms, which shows the potential of improvements of writing a low level implementation of the verification.</footnote>
<table><caption>**Algorithm 7: Decompression**</caption>
  <thead>
    <tr>
      <th>Step</th>
      <th>Description</th>
      <th>Time</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>1</td>
      <td>Parse ||n<sub>1</sub>||n<sub>2</sub>||q||a<sub>1</sub>||b<sub>1</sub>||c<sub>2</sub>|| &larr; w;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Set j &larr; n<sub>1</sub> + n<sub>2</sub>&zeta;, where &zeta; is the canonical generator of F<sub>p<sup>2</sup></sub>;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Compute E<sub>1</sub> of j-invariant j(E<sub>1</sub>) = j;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>4</td>
      <td>Recover the commitment &phi; &larr; F(E<sub>1</sub>, H(E<sub>1</sub>, m)). Let E<sub>2</sub> be the codomain of &phi;;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Compute the canonical basis (P<sub>1</sub>, P<sub>2</sub>) of E<sub>1</sub>[l<sup>f<sub>1</sub></sup>] and the canonical basis (Q<sub>1</sub>, Q<sub>2</sub>) of E<sub>2</sub>[l<sup>f<sub>1</sub></sup>];</td>
      <td>1</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Find k &isin; (Z/l<sup>f<sub>1</sub></sup>Z)<sup>*</sup> such that e<sub>l<sup>f<sub>1</sub></sup></sub>(P<sub>1</sub>, P<sub>2</sub>) = e<sub>l<sup>f<sub>1</sub></sup></sub>(Q<sub>1</sub>, Q<sub>2</sub>)<sup>k</sup>;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>7</td>
      <td>if l &nparallel; a<sub>1</sub> then</td>
      <td>1</td>
    </tr>
    <tr>
      <td>8</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;a<sub>2</sub> &larr; c<sub>2</sub>;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>9</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;Find b<sub>2</sub> &isin; Z/l<sup>f<sub>1</sub></sup>Z such that a<sub>1</sub>b<sub>2</sub> &minus; b<sub>1</sub>a<sub>2</sub> &equiv; kq mod l<sup>f<sub>1</sub></sup>;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>10</td>
      <td>else</td>
      <td>1</td>
    </tr>
    <tr>
      <td>11</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;b<sub>2</sub> &larr; c<sub>2</sub>;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>12</td>
      <td>&nbsp;&nbsp;&nbsp;&nbsp;Find a<sub>2</sub> &isin; Z/l<sup>f<sub>1</sub></sup>Z such that a<sub>1</sub>b<sub>2</sub> &minus; b<sub>1</sub>a<sub>2</sub> &equiv; kq mod l<sup>f<sub>1</sub></sup>;</td>
      <td>1</td>
    </tr>
    <tr>
      <td>13</td>
      <td>end</td>
      <td>1</td>
    </tr>
    <tr>
      <td>14</td>
      <td>Return E<sub>1</sub>, E<sub>2</sub>, q, P<sub>1</sub>, P<sub>2</sub>, a<sub>1</sub>Q<sub>1</sub> + b<sub>1</sub>Q<sub>2</sub>, a<sub>2</sub>Q<sub>1</sub> + b<sub>2</sub>Q<sub>2</sub>;</td>
      <td>1</td>
    </tr>
  </tbody>
</table>

future: new optimisations remain to be implemented, and more importantly a
low level implementation should lead to a significant gain. Currently, the time
spent on verification is as follows: around 60 ms for the challenge computation<fnref n="9" />,
510 ms for the two dimension 4 2⁷¹-isogenies giving F, and 30 ms for the image
of a point through F.

References

[1] K. Ahrens. Sieving for large twin smooth integers using single solutions to Prouhet-Tarry-Escott. Cryptology ePrint Archive, Paper 2023/219. 2023. URL: https://eprint.iacr.org/2023/219.

[2] R. Azarderakhsh, D. Jao, K. Kalach, B. Koziel, and C. Leonardi. “Key compression for isogeny-based cryptosystems”. In: *Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography*. Xi’an, China: ACM, 2016, pp. 1–10.

<footnote n="9">⁹ Which essentially consists in computing a chain of 3-isogenies in dimension 1. The signature also needs to compute similar isogenies, and in this case the low level C implementation only takes 1-2 ms, which shows the potential of improvements of writing a low level implementation of the verification.</footnote>
[3] D. J. Bernstein, L. De Feo, A. Leroux, and B. Smith. "Faster computation of isogenies of large prime degree". In: *Open Book Series, Proceedings of the Fourteenth Algorithmic Number Theory Symposium – ANTS XIV 4.1* (2020), pp. 39–55.

[4] G. Bruno, M. C.-R. Santos, C. Costello, J. K. Eriksen, M. Naehrig, M. Meyer, and B. Sterner. *Cryptographic Smooth Neighbors*. Cryptology ePrint Archive, Paper 2022/1439. URL: https://eprint.iacr.org/2022/1439.

[5] W. Castryck and T. Decru. "An Efficient Key Recovery Attack On SIDH". In: *Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V*. Lyon, France: Springer-Verlag, 2023, pp. 423–447. ISBN: 978-3-031-30588-7. URL: https://doi.org/10.1007/978-3-031-30589-4_15.

[6] G. Cornacchia. "Su di un metodo per la risoluzione in numeri interi dell'equazione $\sum_{h=0}^{n} C_h x^{n-h} y^h = P$". In: *Giornale di matematiche di Battaglini* 46 (1908), pp. 33–90.

[7] C. Costello, M. Meyer, and M. Naehrig. "Sieving for Twin Smooth Integers with Solutions to the Prouhet-Tarry-Escott Problem". In: *Advances in Cryptology – EUROCRYPT 2021*. Ed. by A. Canteaut and F.-X. Standard. Cham: Springer International Publishing, 2021, pp. 272–301. ISBN: 978-3-030-77870-5.

[8] J.-M. Couveignes. *Hard Homogeneous Spaces*. Cryptology ePrint Archive, Report 2006/291. 2006. URL: https://eprint.iacr.org/2006/291.

[9] P. Dartois, A. Leroux, D. Robert, and B. Wesolowski. *SQIsignHD: New Dimensions in Cryptography*. Cryptology ePrint Archive, Paper 2023/436. 2023. URL: https://eprint.iacr.org/2023/436.

[10] L. De Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski. "SQIsign: Compact Post-quantum Signatures from Quaternions and Isogenies". In: *Advances in Cryptology – ASIACRYPT 2020*. Ed. by S. Moriai and H. Wang. Cham: Springer International Publishing, 2020, pp. 64–93. ISBN: 978-3-030-64837-4.

[11] C. Delfs and S. D. Galbraith. "Computing isogenies between supersingular elliptic curves over $\mathbb{F}_p$". In: *Designs, Codes and Cryptography* 78.2 (2016), pp. 425–440. DOI: 10.1007/s10623-014-0010-1.

[12] K. Eisenträger, S. Hallgren, K. Lauter, T. Morrison, and C. Petit. "Spersingular Isogeny Graphs and Endomorphism Rings: Reductions and Solutions". In: *Advances in Cryptology – EUROCRYPT 2018*. Ed. by J. B. Nielsen and V. Rijmen. Cham: Springer International Publishing, 2018, pp. 329–368. ISBN: 978-3-319-78372-7.

[13] L. D. Feo, A. Leroux, P. Longa, and B. Wesolowski. "New Algorithms for the Deuring Correspondence - Towards Practical and Secure SQISign Signatures". In: *Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V*. Ed. by
[3] D. J. Bernstein, L. De Feo, A. Leroux, and B. Smith. "Faster computation of isogenies of large prime degree". In: *Open Book Series, Proceedings of the Fourteenth Algorithmic Number Theory Symposium – ANTS XIV* 4.1 (2020), pp. 39–55.

[4] G. Bruno, M. C.-R. Santos, C. Costello, J. K. Eriksen, M. Naehrig, M. Meyer, and B. Sterner. *Cryptographic Smooth Neighbors*. Cryptology ePrint Archive, Paper 2022/1439. URL: https://eprint.iacr.org/2022/1439.

[5] W. Castryck and T. Decru. "An Efficient Key Recovery Attack On SIDH". In: *Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V*. Lyon, France: Springer-Verlag, 2023, pp. 423–447. ISBN: 978-3-031-30588-7. URL: https://doi.org/10.1007/978-3-031-30589-4_15.

[6] G. Cornacchia. "Su di un metodo per la risoluzione in numeri interi dell'equazione $\sum_{h=0}^{n} C_h x^{n-h} y^h = P$". In: *Giornale di matematiche di Battaglini* 46 (1908), pp. 33–90.

[7] C. Costello, M. Meyer, and M. Naehrig. "Sieving for Twin Smooth Integers with Solutions to the Prouhet-Tarry-Escott Problem". In: *Advances in Cryptology – EUROCRYPT 2021*. Ed. by A. Canteaut and F.-X. Standard. Cham: Springer International Publishing, 2021, pp. 272–301. ISBN: 978-3-030-77870-5.

[8] J.-M. Couveignes. *Hard Homogeneous Spaces*. Cryptology ePrint Archive, Report 2006/291. 2006. URL: https://eprint.iacr.org/2006/291.

[9] P. Dartois, A. Leroux, D. Robert, and B. Wesolowski. *SQIsignHD: New Dimensions in Cryptography*. Cryptology ePrint Archive, Paper 2023/436. 2023. URL: https://eprint.iacr.org/2023/436.

[10] L. De Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski. "SQIsign: Compact Post-quantum Signatures from Quaternions and Isogenies". In: *Advances in Cryptology – ASIACRYPT 2020*. Ed. by S. Moriai and H. Wang. Cham: Springer International Publishing, 2020, pp. 64–93. ISBN: 978-3-030-64837-4.

[11] C. Delfs and S. D. Galbraith. "Computing isogenies between supersingular elliptic curves over $\mathbb{F}_p$". In: *Designs, Codes and Cryptography* 78.2 (2016), pp. 425–440. DOI: 10.1007/s10623-014-0010-1.

[12] K. Eisenträger, S. Hallgren, K. Lauter, T. Morrison, and C. Petit. "Spersingular Isogeny Graphs and Endomorphism Rings: Reductions and Solutions". In: *Advances in Cryptology – EUROCRYPT 2018*. Ed. by J. B. Nielsen and V. Rijmen. Cham: Springer International Publishing, 2018, pp. 329–368. ISBN: 978-3-319-78372-7.

[13] L. D. Feo, A. Leroux, P. Longa, and B. Wesolowski. "New Algorithms for the Deuring Correspondence - Towards Practical and Secure SQISign Signatures". In: *Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V*. Ed. by
C. Hazay and M. Stam. Vol. 14008. Lecture Notes in Computer Science. Springer, 2023, pp. 659–690. URL: https://doi.org/10.1007/978-3-031-30589-4\%5C_23.

[14] A. Fiat and A. Shamir. "How To Prove Yourself: Practical Solutions to Identification and Signature Problems". In: *Advances in Cryptology — CRYPTO' 86*. Ed. by A. M. Odlyzko. Berlin, Heidelberg: Springer Berlin Heidelberg, 1987, pp. 186–194. ISBN: 978-3-540-47721-1.

[15] S. D. Galbraith, C. Petit, and J. Silva. "Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems". In: *J. Cryptol*. 33.1 (Jan. 2020), pp. 130–175. ISSN: 0933-2790. URL: https://doi.org/10.1007/s00145-019-09316-0.

[16] L. K. Grover. "A Fast Quantum Mechanical Algorithm for Database Search". In: *Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing*. STOC '96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 212–219. ISBN: 0897917855. DOI: 10.1145/237814.237866.

[17] C. Hazay and Y. Lindell. *Efficient Secure Two-Party Protocols: Techniques and Constructions*. 1st. Berlin, Heidelberg: Springer-Verlag, 2010. ISBN: 3642143024.

[18] D. Jao and L. De Feo. "Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies". In: *Post-Quantum Cryptography*. Ed. by B.-Y. Yang. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 19–34. ISBN: 978-3-642-25405-5.

[19] E. Kani. "The number of curves of genus two with elliptic differentials". In: *Journal für die reine und angewandte Mathematik* 1997.485 (1997), pp. 93–122. DOI: 10.1515/crl1.1997.485.93.

[20] D. Kohel, K. Lauter, C. Petit, and J.-P. Tignol. "On the quaternion - isogeny path problem". In: *LMS Journal of Computation and Mathematics* 17 (June 2014). DOI: 10.1112/S1461157014000151.

[21] J. L. de Lagrange. "Démonstration d'un théoreme d'arithmétique". In: *Nouveau Mémoire de l'Académie Royale des Sciences de Berlin* (1770), pp. 123–133.

[22] A. Leroux. *Quaternion algebras and isogeny-based cryptography*. 2022. URL: http://www.lix.polytechnique.fr/Labo/Antonin.LEROUX/manuscrit_these.pdf.

[23] K. Lin, W. Wang, Z. Xu, and C.-A. Zhao. *A Faster Software Implementation of SQISign*. Cryptology ePrint Archive, Paper 2023/753. 2023. URL: https://eprint.iacr.org/2023/753.

[24] D. Lubicz and D. Robert. "Computing isogenies between abelian varieties". In: *Compositio Mathematica* 148.5 (Sept. 2012), pp. 1483–1515. DOI: 10.1112/S0010437X12000243.

[25] D. Lubicz and D. Robert. "Computing separable isogenies in quasi-optimal time". In: *LMS Journal of Computation and Mathematics* 18.1 (2015), pp. 198–216. DOI: 10.1112/S146115701400045X.
C. Hazay and M. Stam. Vol. 14008. Lecture Notes in Computer Science. Springer, 2023, pp. 659–690. URL: https://doi.org/10.1007/978-3-031-30589-4\%5C_23.

[14] A. Fiat and A. Shamir. "How To Prove Yourself: Practical Solutions to Identification and Signature Problems". In: *Advances in Cryptology — CRYPTO' 86*. Ed. by A. M. Odlyzko. Berlin, Heidelberg: Springer Berlin Heidelberg, 1987, pp. 186–194. ISBN: 978-3-540-47721-1.

[15] S. D. Galbraith, C. Petit, and J. Silva. "Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems". In: *J. Cryptol*. 33.1 (Jan. 2020), pp. 130–175. ISSN: 0933-2790. URL: https://doi.org/10.1007/s00145-019-09316-0.

[16] L. K. Grover. "A Fast Quantum Mechanical Algorithm for Database Search". In: *Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing*. STOC '96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 212–219. ISBN: 0897917855. DOI: 10.1145/237814.237866.

[17] C. Hazay and Y. Lindell. *Efficient Secure Two-Party Protocols: Techniques and Constructions*. 1st. Berlin, Heidelberg: Springer-Verlag, 2010. ISBN: 3642143024.

[18] D. Jao and L. De Feo. "Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies". In: *Post-Quantum Cryptography*. Ed. by B.-Y. Yang. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 19–34. ISBN: 978-3-642-25405-5.

[19] E. Kani. "The number of curves of genus two with elliptic differentials". In: *Journal für die reine und angewandte Mathematik* 1997.485 (1997), pp. 93–122. DOI: 10.1515/crll.1997.485.93.

[20] D. Kohel, K. Lauter, C. Petit, and J.-P. Tignol. "On the quaternion - isogeny path problem". In: *LMS Journal of Computation and Mathematics* 17 (June 2014). DOI: 10.1112/S1461157014000151.

[21] J. L. de Lagrange. "Démonstration d'un théoreme d'arithmétique". In: *Nouveau Mémoire de l'Académie Royale des Sciences de Berlin* (1770), pp. 123–133.

[22] A. Leroux. *Quaternion algebras and isogeny-based cryptography*. 2022. URL: http://www.lix.polytechnique.fr/Labo/Antonin.LEROUX/manuscrit_these.pdf.

[23] K. Lin, W. Wang, Z. Xu, and C.-A. Zhao. *A Faster Software Implementation of SQISign*. Cryptology ePrint Archive, Paper 2023/753. 2023. URL: https://eprint.iacr.org/2023/753.

[24] D. Lubicz and D. Robert. "Computing isogenies between abelian varieties". In: *Compositio Mathematica* 148.5 (Sept. 2012), pp. 1483–1515. DOI: 10.1112/S0010437X12000243.

[25] D. Lubicz and D. Robert. "Computing separable isogenies in quasi-optimal time". In: *LMS Journal of Computation and Mathematics* 18.1 (2015), pp. 198–216. DOI: 10.1112/S146115701400045X.
[26] D. Lubicz and D. Robert. "Fast change of level and applications to isogenies". In: vol. 9. 1. Springer, 2023. DOI: 10.1007/s40993-022-00407-9.

[27] L. Maino, C. Martindale, L. Panny, G. Pope, and B. Wesolowski. "A Direct Key Recovery Attack on SIDH". In: Springer-Verlag, 2023.

[28] PARI/GP version 2.13.4. available from http://pari.math.u-bordeaux.fr/. The PARI Group. Univ. Bordeaux, 2022.

[29] S. C. Pohlig and M. E. Hellman. "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance". In: *IEEE Transactions on information theory* 24.1 (Jan. 1978), pp. 106–110.

[30] P. Pollack and E. Treviño. "Finding the Four Squares in Lagrange's Theorem". In: *Integers* 18A (2018), A15.

[31] J. O. Rabin M. O.; Shallit. "Randomized Algorithms in Number Theory". In: *Communications on Pure and Applied Mathematic* 39.S1 (1986), S239–S256. DOI: 10.1002/cpa.3160390713.

[32] D. Robert. *Evaluating isogenies in polylogarithmic time*. Cryptology ePrint Archive, Paper 2022/1068. 2022. URL: https://eprint.iacr.org/2022/1068.

[33] D. Robert. "Breaking SIDH in Polynomial Time". In: *Advances in Cryptology – EUROCRYPT 2023*. Ed. by C. Hazay and M. Stam. Cham: Springer Nature Switzerland, 2023, pp. 472–503. ISBN: 978-3-031-30589-4.

[34] A. Rostovtsev and A. Stolbunov. *Public-Key Cryptosystem Based On Isogenies*. Cryptology ePrint Archive, Report 2006/145. 2006. URL: https://eprint.iacr.org/2006/145.

[35] J. Rouse and K. Thompson. *Quaternary quadratic forms with prime discriminant*. 2022. arXiv: 2206.00412 [math.NT].

[36] The Sage Developers. *SageMath, the Sage Mathematics Software System (Version 10.0)*. 2023. URL: https://www.sagemath.org.

[37] The SQIsign team. *SQIsign*. 2023. URL: https://www.sqisign.org.

[38] J. Vélu. "Isogénies entre courbes elliptiques". In: *Comptes-rendus de l'Académie des Sciences* 273 (July 1971). Available at https://gallica.bnf.fr, pp. 238–241.

[39] D. Venturi and A. Villani. *Zero-Knowledge Proofs and Applications*. May 2015. URL: http://danieleventuri.alternvista.org/files/zero-knowledge.pdf.

[40] J. Voight. *Quaternion algebras*. v.0.9.23. Aug. 2020. URL: https://math.dartmouth.edu/~jvoight/quat.html.

[41] B. Wesolowski. "The supersingular isogeny path and endomorphism ring problems are equivalent". In: *FOCS 2021 - 62nd Annual IEEE Symposium on Foundations of Computer Science*. Denver, Colorado, United States, Feb. 2022. URL: https://hal.archives-ouvertes.fr/hal-03340899.

[42] G. Zanon, M. A. Simplicio, G. Pereira, J. Doliskani, and P. L. Barreto. "Faster isogeny-based compressed key agreement". In: *Post-Quantum Cryptography*. Springer International Publishing, 2018, pp. 248–268.
[26] D. Lubicz and D. Robert. "Fast change of level and applications to isogenies". In: vol. 9. 1. Springer, 2023. DOI: 10.1007/s40993-022-00407-9.

[27] L. Maino, C. Martindale, L. Panny, G. Pope, and B. Wesolowski. "A Direct Key Recovery Attack on SIDH". In: Springer-Verlag, 2023.

[28] PARI/GP version 2.13.4. available from http://pari.math.u-bordeaux.fr/. The PARI Group. Univ. Bordeaux, 2022.

[29] S. C. Pohlig and M. E. Hellman. "An improved algorithm for computing logarithms over GF(p) and its cryptographic significance". In: *IEEE Transactions on information theory* 24.1 (Jan. 1978), pp. 106-110.

[30] P. Pollack and E. Treviño. "Finding the Four Squares in Lagrange's Theorem". In: *Integers* 18A (2018), A15.

[31] J. O. Rabin M. O.; Shallit. "Randomized Algorithms in Number Theory". In: *Communications on Pure and Applied Mathematic* 39.S1 (1986), S239-S256. DOI: 10.1002/cpa.3160390713.

[32] D. Robert. *Evaluating isogenies in polylogarithmic time*. Cryptology ePrint Archive, Paper 2022/1068. 2022. URL: https://eprint.iacr.org/2022/1068.

[33] D. Robert. "Breaking SIDH in Polynomial Time". In: *Advances in Cryptology – EUROCRYPT 2023*. Ed. by C. Hazay and M. Stam. Cham: Springer Nature Switzerland, 2023, pp. 472–503. ISBN: 978-3-031-30589-4.

[34] A. Rostovtsev and A. Stolbunov. *Public-Key Cryptosystem Based On Isogenies*. Cryptology ePrint Archive, Report 2006/145. 2006. URL: https://eprint.iacr.org/2006/145.

[35] J. Rouse and K. Thompson. *Quaternary quadratic forms with prime discriminant*. 2022. arXiv: 2206.00412 [math.NT].

[36] The Sage Developers. *SageMath, the Sage Mathematics Software System (Version 10.0)*. 2023. URL: https://www.sagemath.org.

[37] The SQIsign team. *SQIsign*. 2023. URL: https://www.sqisign.org.

[38] J. Vélu. "Isogénies entre courbes elliptiques". In: *Comptes-rendus de l'Académie des Sciences* 273 (July 1971). Available at https://gallica.bnf.fr, pp. 238–241.

[39] D. Venturi and A. Villani. *Zero-Knowledge Proofs and Applications*. May 2015. URL: http://danieleventuri.alternvista.org/files/zero-knowledge.pdf.

[40] J. Voight. *Quaternion algebras*. v.0.9.23. Aug. 2020. URL: https://math.dartmouth.edu/~jvoight/quat.html.

[41] B. Wesolowski. "The supersingular isogeny path and endomorphism ring problems are equivalent". In: *FOCS 2021 - 62nd Annual IEEE Symposium on Foundations of Computer Science*. Denver, Colorado, United States, Feb. 2022. URL: https://hal.archives-ouvertes.fr/hal-03340899.

[42] G. Zanon, M. A. Simplicio, G. Pereira, J. Doliskani, and P. L. Barreto. "Faster isogeny-based compressed key agreement". In: *Post-Quantum Cryptography*. Springer International Publishing, 2018, pp. 248–268.