[Mum67a] D. Mumford. "On the equations defining abelian varieties. II". In: *Invent. Math.* 3 (1967), pp. 75-135.

[Mum67b] D. Mumford. "On the equations defining abelian varieties. III". In: *Invent. Math.* 3 (1967), pp. 215-244.

[Mum74] D. Mumford. *Abelian varieties*. Second Edition. Tata Institute of fundamental research studies in mathematics. London: Oxford University Press, 1974, pp. x+279.

[Mum84] D. Mumford. *Tata lectures on theta II*. Vol. 43. Progress in Mathematics. Jacobian theta functions and differential equations, With the collaboration of C. Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. Boston, MA: Birkhäuser Boston Inc., 1984, pp. xiv+272. ISBN: 0-8176-3110-0.

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

[Piz80] A. Pizer. "An algorithm for computing modular forms on $\Gamma_0(N)$". In: *Journal of Algebra* 64 (June 1980), pp. 340-340. DOI: 10.1016/0021-8693(80)90151-9.

[PH78] 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.

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

[Rab86] 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.

[Rob10] D. Robert. "Theta functions and cryptographic applications". PhD thesis. Université Henri-Poincaré, Nancy 1, France, July 2010. URL: http://www.normalesup.org/~robert/pro/publications/academic/phd.pdf.

[Rob21] D. Robert. "Efficient algorithms for abelian varieties and their moduli spaces". HDR thesis. Université Bordeaux, June 2021. URL: http://www.normalesup.org/~robert/pro/publications/academic/hdr.pdf.

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

[Rob23a] D. Robert. "A note on optimising $2^n$-isogenies in higher dimension". June 2023. In preparation.

[Rob23b] 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.
[RS06] 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.

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

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

[Sil09] J. H. Silverman. *The Arithmetic of Elliptic Curves*. Springer, 2009, p. 522.

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

[Tes99] E. Teske. "The Pohlig-Hellman Method Generalized for Group Structure Computation". In: *Journal of Symbolic Computation* 11 (1999), pp. 1-14.

[Vél71] 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.

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

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

[Wes22] 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.

[ZSPDB18] 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.
[RS06] 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.

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

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

[Sil09] J. H. Silverman. *The Arithmetic of Elliptic Curves*. Springer, 2009, p. 522.

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

[Tes99] E. Teske. "The Pohlig-Hellman Method Generalized for Group Structure Computation". In: *Journal of Symbolic Computation* 11 (1999), pp. 1-14.

[Vél71] 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.

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

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

[Wes22] 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.

[ZSPDB18] 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.
# A Preliminaries

## A.1 Constructing a signature with the Fiat-Shamir transform

In this section, we explain how to transform our SQIsignHD identification protocol into a signature scheme using the Fiat-Shamir transform [FS87]. The method is analogous to the original SQIsign protocol. The following procedure applies to both FastSQIsignHD and RigorousSQIsignHD.

Decomposing the degree of the challenge into primes $D_\varphi := \prod_{i=1}^r \ell_i^{e_i}$ and setting $\mu(D_\varphi) := \prod_{i=1}^r \ell_i^{e_i-1}(\ell_i + 1)$, we define a secure hash function in the supersingular $\{\ell_1, \cdots, \ell_r\}$-isogeny graph mapping a supersingular elliptic curve $E$ and an integer $s \in [1; \mu(D_\varphi)]$ to a cyclic $D_\varphi$-isogeny $\Phi(E, s)$ with domain $E$. Such a hash function has been constructed in [DDF+21, § 3.1], which is a generalization of [CLG09]. We also use another secure hash function $H : \{0, 1\}^* \to [1; \mu(D_\varphi)]$.

**Signature.** To sign a message $m$ with a secret key $\tau : E_0 \to E_A$, generate a random commitment $\psi : E_0 \to E_1$, let $s := H(j(E_1), m)$ and $\varphi := \Phi(E_A, s) : E_A \to E_2$. From the knowledge of $\tau$, $\varphi$ and $\psi$, construct an efficient representation $R = (\sigma(P_1), \sigma(P_2), q)$ given by the image of torsion points by a response isogeny $\sigma : E_1 \to E_2$ and return $(E_1, R)$ as a signature.

**Verification.** A verifier receiving a signature $(E_1, R)$ associated to the message $m$ and public key $E_A$ computes $s = H(j(E_1), m)$ and then $\varphi = \Phi(E_A, s) : E_A \to E_2$. The verifier finally checks that $R$ represents correctly an isogeny $\sigma : E_1 \to E_2$ by computing a higher dimensional isogeny, as explained previously.

Once it is established that the SQIsignHD identification protocol is complete, sound, and honest verifier zero-knowledge, and assuming the hardness of the endomorphism ring problem, we obtain a universal unforgeable signature against chosen message attacks in the random oracle model [VV15, Theorem 7].

## A.2 Abelian varieties and their isogenies

An abelian variety $A$ over a field $k$ is a connected projective $k$-variety with an algebraic group law (which is then automatically abelian by rigidity). Abelian varieties are generalizations of elliptic curves in any dimension. In particular, elliptic curves are abelian varieties of dimension 1 and products of elliptic curves are abelian varieties.

A morphism of abelian varieties is an algebraic map $\varphi : A \to B$ which is a group homomorphism; by rigidity it suffices to check that $\varphi(0_A) = 0_B$. It is an *isogeny* if it is surjective and has finite kernel. The degree of an isogeny is its degree as a rational map. If $\varphi$ is a *separable* isogeny, then $\deg(\varphi) = \#\ker(\varphi)$. If $\deg(\varphi)$ is prime to the characteristic $p$ of the base field $k$, then $\varphi$ is automatically separable. As in elliptic curves, the multiplication by $n$ map in an abelian variety $[n]_A : A \to A$ is an isogeny of degree $n^{2g}$ with $g := \dim(A)$ and its kernel $A[n]$ is isomorphic to $(\mathbb{Z}/n\mathbb{Z})^{2g}$ when $n$ is prime to $p$.
# A Preliminaries

## A.1 Constructing a signature with the Fiat-Shamir transform

In this section, we explain how to transform our SQIsignHD identification protocol into a signature scheme using the Fiat-Shamir transform [FS87]. The method is analogous to the original SQIsign protocol. The following procedure applies to both FastSQIsignHD and RigorousSQIsignHD.

Decomposing the degree of the challenge into primes $D_\varphi := \prod_{i=1}^r \ell_i^{e_i}$ and setting $\mu(D_\varphi) := \prod_{i=1}^r \ell_i^{e_i-1}(\ell_i + 1)$, we define a secure hash function in the supersingular $\{\ell_1, \cdots, \ell_r\}$-isogeny graph mapping a supersingular elliptic curve $E$ and an integer $s \in [1; \mu(D_\varphi)]$ to a cyclic $D_\varphi$-isogeny $\Phi(E, s)$ with domain $E$. Such a hash function has been constructed in [DDF+21, § 3.1], which is a generalization of [CLG09]. We also use another secure hash function $H : \{0, 1\}^* \to [1; \mu(D_\varphi)]$.

**Signature.** To sign a message $m$ with a secret key $\tau: E_0 \to E_A$, generate a random commitment $\psi: E_0 \to E_1$, let $s := H(j(E_1), m)$ and $\varphi := \Phi(E_A, s) : E_A \to E_2$. From the knowledge of $\tau$, $\varphi$ and $\psi$, construct an efficient representation $R = (\sigma(P_1), \sigma(P_2), q)$ given by the image of torsion points by a response isogeny $\sigma: E_1 \to E_2$ and return $(E_1, R)$ as a signature.

**Verification.** A verifier receiving a signature $(E_1, R)$ associated to the message $m$ and public key $E_A$ computes $s = H(j(E_1), m)$ and then $\varphi = \Phi(E_A, s) : E_A \to E_2$. The verifier finally checks that $R$ represents correctly an isogeny $\sigma: E_1 \to E_2$ by computing a higher dimensional isogeny, as explained previously.

Once it is established that the SQIsignHD identification protocol is complete, sound, and honest verifier zero-knowledge, and assuming the hardness of the endomorphism ring problem, we obtain a universal unforgeable signature against chosen message attacks in the random oracle model [VV15, Theorem 7].

## A.2 Abelian varieties and their isogenies

An abelian variety $A$ over a field $k$ is a connected projective $k$-variety with an algebraic group law (which is then automatically abelian by rigidity). Abelian varieties are generalizations of elliptic curves in any dimension. In particular, elliptic curves are abelian varieties of dimension 1 and products of elliptic curves are abelian varieties.

A morphism of abelian varieties is an algebraic map $\varphi: A \to B$ which is a group homomorphism; by rigidity it suffices to check that $\varphi(0_A) = 0_B$. It is an isogeny if it is surjective and has finite kernel. The degree of an isogeny is its degree as a rational map. If $\varphi$ is a separable isogeny, then $\deg(\varphi) = \#\ker(\varphi)$. If $\deg(\varphi)$ is prime to the characteristic $p$ of the base field $k$, then $\varphi$ is automatically separable. As in elliptic curves, the multiplication by $n$ map in an abelian variety $[n]_A: A \to A$ is an isogeny of degree $n^{2g}$ with $g := \dim(A)$ and its kernel $A[n]$ is isomorphic to $(\mathbb{Z}/n\mathbb{Z})^{2g}$ when $n$ is prime to $p$.
To any abelian variety $A$, we associate its dual abelian variety $\hat{A}$, which has the same dimension. The dual defines a contravariant functor: any isogeny $\varphi : A \to B$ induces a dual isogeny $\hat{\varphi} : \hat{B} \to \hat{A}$ which has the same degree. A polarization is an isogeny $\lambda : A \to \hat{A}$ induced by an ample line bundle. A polarized abelian variety $(A, \lambda)$ is *principally polarized* if $\lambda$ is an isomorphism.

If $n \in \mathbb{N}^*$ is prime to $p$, then we have a non-degenerate pairing $e_n : A[n] \times \hat{A}[n] \to \bar{k}^*$ called the *Weil pairing*. Given a polarization $\lambda : A \to \hat{A}$, the Weil pairing yields a non-degenerate antisymmetric pairing $e_n^\lambda : A[n] \times A[n] \to \bar{k}^*$.

Morally, a polarization can be seen as "a way to represent an abelian variety". Indeed, in plain generality, we do not have nice analogues for the Weierstrass model for elliptic curves, but every abelian variety can be described by a theta model [Mum66b; Mum67a; Mum67b]. We refer to the notes of Milne [Mil86] or the book of Mumford [Mum74] for a complete introduction to abelian varieties.

### A.3 The Deuring correspondence

**Quaternions, orders and ideals.** Let $\mathcal{B}_{p,\infty}$ be the quaternion algebra over $\mathbb{Q}$ ramifying at $p$ and $\infty$. By [Piz80, Proposition 5.1], there exists a $\mathbb{Q}$-basis $(1, i, j, k)$ of $\mathcal{B}_{p,\infty}$ with $j^2 = -p$, $k = ij = -ji$ and $i^2 = -1, -2, -q$, when $p \equiv 3 \pmod 4$, $p \equiv 5 \pmod 8$ and $p \equiv 1 \pmod 8$ respectively, $q$ being a prime such that $(-p/q) = 1$. $\mathcal{B}_{p,\infty}$ has a conjugation $\alpha := x+iy+jz+kt \mapsto \bar{\alpha} := x-iy-jz-kt$. For all $\alpha \in \mathcal{B}_{p,\infty}$, we define the reduced norm nrd($\alpha$) := $\alpha\bar{\alpha}$ and trace Tr($\alpha$) := $\alpha + \bar{\alpha}$.

A *fractional ideal* $I \subset \mathcal{B}_{p,\infty}$ is a $\mathbb{Z}$-lattice of rank 4. We also define the *reduced norm* of $I$ as nrd($I$) := $\gcd\{\text{nrd}(\alpha) \mid \alpha \in I\}$ and the conjugation $\bar{I} := \{\bar{\alpha} \mid \alpha \in I\}$. If $I \subset J$ are two fractional ideals, then $[J : I] = \text{nrd}(I)^2/\text{nrd}(J)^2$. If $(\alpha_1, \dots, \alpha_4)$ is a basis of $I$, then $|\det(\text{Tr}(\alpha_i\bar{\alpha}_j))|_{1 \le i,j \le 4}^{1/2}$ does not depend on the basis. This invariant is called the *reduced discriminant* of $I$ and denoted by $\text{discrd}(I)$.

An *order* of $\mathcal{O} \subset \mathcal{B}_{p,\infty}$ is a fractional ideal which is stable by multiplication and contains 1. We say it is *maximal* if it is maximal for the inclusion. If $I$ is a fractional ideal, we define its *left order* $O_L(I) := \{\alpha \in \mathcal{B}_{p,\infty} \mid \alpha I \subseteq I\}$ and its *right order* $O_R(I) := \{\alpha \in \mathcal{B}_{p,\infty} \mid I\alpha \subseteq I\}$. We say that $I$ is a left (respectively right) *O*-ideal when $\mathcal{O} \subseteq O_L(I)$ (respectively $\mathcal{O} \subseteq O_R(I)$). We also say that $I$ connects $\mathcal{O}$ and $\mathcal{O}'$ when $\mathcal{O} = O_L(I)$ and $\mathcal{O}' = O_R(I)$. $I$ is *integral* if $I \subseteq O_L(I)$. In this case, $I \subseteq O_R(I)$ and both $O_L(I)$ and $O_R(I)$ are maximal. **In this paper, we only consider integral ideals and simply refer to them as ideals.**
Two fractional ideals $I \sim J$ are equivalent if there exists $\beta \in \mathcal{B}_{p,\infty}^*$ such that $J = I\beta$. In that case, $O_L(I) = O_L(J)$ and $O_R(I) = \beta O_R(J)\beta^{-1}$.

**The Deuring correspondence.** The Deuring correspondence due to Max Deuring [Deu41] draws a parallel between the world of quaternions and the world of supersingular elliptic curves. Indeed, if $E/\mathbb{F}_{p^2}$ is a supersingular elliptic curve, then its endomorphism ring $\text{End}(E)$ is isomorphic to a maximal order $\mathcal{O} \subset \mathcal{B}_{p,\infty}$.
To any abelian variety $A$, we associate its dual abelian variety $\hat{A}$, which has the same dimension. The dual defines a contravariant functor: any isogeny $\varphi : A \to B$ induces a dual isogeny $\hat{\varphi} : \hat{B} \to \hat{A}$ which has the same degree. A polarization is an isogeny $\lambda : A \to \hat{A}$ induced by an ample line bundle. A polarized abelian variety $(A, \lambda)$ is *principally polarized* if $\lambda$ is an isomorphism.

If $n \in \mathbb{N}^*$ is prime to $p$, then we have a non-degenerate pairing $e_n : A[n] \times \hat{A}[n] \to \bar{k}^*$ called the *Weil pairing*. Given a polarization $\lambda : A \to \hat{A}$, the Weil pairing yields a non-degenerate antisymmetric pairing $e_n^\lambda : A[n] \times A[n] \to \bar{k}^*$.

Morally, a polarization can be seen as "a way to represent an abelian variety". Indeed, in plain generality, we do not have nice analogues for the Weierstrass model for elliptic curves, but every abelian variety can be described by a theta model [Mum66b; Mum67a; Mum67b]. We refer to the notes of Milne [Mil86] or the book of Mumford [Mum74] for a complete introduction to abelian varieties.

### A.3 The Deuring correspondence

**Quaternions, orders and ideals.** Let $\mathcal{B}_{p,\infty}$ be the quaternion algebra over $\mathbb{Q}$ ramifying at $p$ and $\infty$. By [Piz80, Proposition 5.1], there exists a $\mathbb{Q}$-basis $(1, i, j, k)$ of $\mathcal{B}_{p,\infty}$ with $j^2 = -p$, $k = ij = -ji$ and $i^2 = -1, -2, -q$, when $p \equiv 3 \pmod 4$, $p \equiv 5 \pmod 8$ and $p \equiv 1 \pmod 8$ respectively, $q$ being a prime such that $(-p/q) = 1$. $\mathcal{B}_{p,\infty}$ has a conjugation $\alpha := x+iy+jz+kt \mapsto \bar{\alpha} := x-iy-jz-kt$. For all $\alpha \in \mathcal{B}_{p,\infty}$, we define the reduced norm nrd($\alpha$) := $\alpha\bar{\alpha}$ and trace Tr($\alpha$) := $\alpha + \bar{\alpha}$.

A *fractional ideal* $I \subset \mathcal{B}_{p,\infty}$ is a $\mathbb{Z}$-lattice of rank 4. We also define the *reduced norm* of $I$ as nrd($I$) := $\gcd\{\text{nrd}(\alpha) \mid \alpha \in I\}$ and the conjugation $\bar{I} := \{\bar{\alpha} \mid \alpha \in I\}$. If $I \subset J$ are two fractional ideals, then $[J : I] = \text{nrd}(I)^2/\text{nrd}(J)^2$. If $(\alpha_1, \dots, \alpha_4)$ is a basis of $I$, then $|\det(\text{Tr}(\alpha_i\bar{\alpha}_j))|_{1 \le i,j \le 4}^{1/2}$ does not depend on the basis. This invariant is called the *reduced discriminant* of $I$ and denoted by discrd($I$).

An *order* of $\mathcal{O} \subset \mathcal{B}_{p,\infty}$ is a fractional ideal which is stable by multiplication and contains 1. We say it is *maximal* if it is maximal for the inclusion. If $I$ is a fractional ideal, we define its *left order* $O_L(I) := \{\alpha \in \mathcal{B}_{p,\infty} \mid \alpha I \subseteq I\}$ and its *right order* $O_R(I) := \{\alpha \in \mathcal{B}_{p,\infty} \mid I\alpha \subseteq I\}$. We say that $I$ is a left (respectively right) *O*-ideal when $\mathcal{O} \subseteq O_L(I)$ (respectively $\mathcal{O} \subseteq O_R(I)$). We also say that $I$ *connects* $\mathcal{O}$ and $\mathcal{O}'$ when $\mathcal{O} = O_L(I)$ and $\mathcal{O}' = O_R(I)$. $I$ is *integral* if $I \subseteq O_L(I)$. In this case, $I \subseteq O_R(I)$ and both $O_L(I)$ and $O_R(I)$ are maximal. **In this paper, we only consider integral ideals and simply refer to them as ideals.**

Two fractional ideals $I \sim J$ are equivalent if there exists $\beta \in \mathcal{B}_{p,\infty}^*$ such that $J = I\beta$. In that case, $O_L(I) = O_L(J)$ and $O_R(I) = \beta O_R(J)\beta^{-1}$.

**The Deuring correspondence.** The Deuring correspondence due to Max Deuring [Deu41] draws a parallel between the world of quaternions and the world of supersingular elliptic curves. Indeed, if $E/\mathbb{F}_{p^2}$ is a supersingular elliptic curve, then its endomorphism ring $\text{End}(E)$ is isomorphic to a maximal order $\mathcal{O} \subset \mathcal{B}_{p,\infty}$.
**Example 24.** If $p \equiv 3 \mod 4$, the elliptic curve $E_0: y^2 = x^3+x$ defined over $\mathbb{F}_p$ is supersingular and has a very explicit endomorphism ring $\text{End}(E_0)$ isomorphic to $\mathcal{O}_0 := \langle 1, i, (i+j)/2, (1+k)/2 \rangle$, where $j$ corresponds to the Frobenius endomorphism $(x,y) \in E_0 \mapsto (x^p, y^p) \in E_0$ and $i$ corresponds to the automorphism $(x,y) \in E_0 \mapsto (-x, \zeta y) \in E_0$ (with $\zeta \in \mathbb{F}_{p^2}$ such that $\zeta^2 = -1$).

This is one of the very few examples where $\text{End}(E_0)$ can be easily and explicitly computed. Computing $\text{End}(E)$ is difficult in general.

Let $E$ be a supersingular elliptic curve and $\mathcal{O} := \text{End}(E)$. An isogeny $\phi: E \to E'$ has a kernel ideal $I_\phi := \{\alpha \in \mathcal{O} \mid \forall P \in \ker(\phi), \alpha(P) = 0\}$, which is a left $\mathcal{O}$-ideal of norm $\text{nrd}(I_\phi) = \text{deg}(\phi)$. Conversely, any left $\mathcal{O}$-ideal $I$ defines an isogeny $\phi_I : E \to E_I$ of kernel $E[I] := \{P \in E \mid \forall \alpha \in I, \alpha(P) = 0\}$ and degree $\text{deg}(\phi_I) = \text{nrd}(I)$. We have $I_{\phi_I} = I$ and $\phi_{I_\phi} = \phi$ so this correspondence is one to one.

The Deuring correspondence between ideals and isogenies satisfies the following properties: two equivalent ideals $I \sim J$ have isomorphic codomains $E_I \simeq E_J$, the endomorphism ring of the codomain $E_I$ is $\text{End}(E_I) \cong \mathcal{O}_R(I)$, the conjugate $\bar{I}$ corresponds to the dual isogeny $\tilde{\phi}_I$, the kernel ideal of the composite $\phi \circ \psi$ isogeny is $I_{\phi \circ \psi} = I_\psi \cdot I_\phi$, a principal ideal corresponds to an endomorphism. For a thorough presentation of quaternions and the Deuring correspondence, we recommend the book of Voight [Voi20].

**Accessible torsion to make the Deuring correspondence effective.**

Making the Deuring correspondence effective means computing the isogeny $\phi_I : E \to E_I$ associated to an ideal $I$ and conversely, computing the kernel ideal $I_\phi$ of a known isogeny $\phi : E \to E'$ when $\text{End}(E)$ is known. Until recently, this could be done in polynomial time only when the ideal norm/the degree is smooth and the necessary $\text{nrd}(I)$-torsion to do these computations is "accessible" in the following sense.

**Definition 25.** Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve and $T := \prod_{i=1}^r \ell_i^{e_i}$ be an integer, where the $\ell_i$ are distinct primes. We say that $E$ has accessible $T$-torsion if $E[\ell_i^{e_i}]$ is defined over an extension of $\mathbb{F}_p$ of degree polynomial in $\log(p)$ for all $i \in [1; r]$.

Usually, in cryptographic protocols we choose $p$ to ensure the $T$-torsion is defined over $\mathbb{F}_{p^2}$ or $\mathbb{F}_{p^4}$ to optimize $T$-isogeny computations when $T$ is smooth. In general, if $T$ is $B$-powersmooth with $B$ polynomial in $\log(p)$, the $T$-torsion is always accessible and we can compute $T$-isogenies in polynomial time as a product of low degree isogenies as in [EHLMP18, Proposition 4]. Until recently, those were the only way to compute isogenies and make the Deuring correspondence effective. In this work, we propose a method to compute isogenies of non-smooth degree (see Section 2). We specialize it for SQIsignHD but this could be easily generalized.
**Example 24.** If $p \equiv 3 \mod 4$, the elliptic curve $E_0: y^2 = x^3+x$ defined over $\mathbb{F}_p$ is supersingular and has a very explicit endomorphism ring $\text{End}(E_0)$ isomorphic to $\mathcal{O}_0 := \langle 1, i, (i+j)/2, (1+k)/2 \rangle$, where $j$ corresponds to the Frobenius endomorphism $(x,y) \in E_0 \mapsto (x^p, y^p) \in E_0$ and $i$ corresponds to the automorphism $(x,y) \in E_0 \mapsto (-x, \zeta y) \in E_0$ (with $\zeta \in \mathbb{F}_{p^2}$ such that $\zeta^2 = -1$).

This is one of the very few examples where $\text{End}(E_0)$ can be easily and explicitly computed. Computing $\text{End}(E)$ is difficult in general.

Let $E$ be a supersingular elliptic curve and $\mathcal{O} := \text{End}(E)$. An isogeny $\phi: E \to E'$ has a kernel ideal $I_\phi := \{\alpha \in \mathcal{O} \mid \forall P \in \ker(\phi), \alpha(P) = 0\}$, which is a left $\mathcal{O}$-ideal of norm $\text{nrd}(I_\phi) = \text{deg}(\phi)$. Conversely, any left $\mathcal{O}$-ideal $I$ defines an isogeny $\phi_I : E \to E_I$ of kernel $E[I] := \{P \in E \mid \forall \alpha \in I, \alpha(P) = 0\}$ and degree $\text{deg}(\phi_I) = \text{nrd}(I)$. We have $I_{\phi_I} = I$ and $\phi_{I_\phi} = \phi$ so this correspondence is one to one.

The Deuring correspondence between ideals and isogenies satisfies the following properties: two equivalent ideals $I \sim J$ have isomorphic codomains $E_I \simeq E_J$, the endomorphism ring of the codomain $E_I$ is $\text{End}(E_I) \cong \mathcal{O}_R(I)$, the conjugate $\bar{I}$ corresponds to the dual isogeny $\tilde{\phi}_I$, the kernel ideal of the composite $\phi \circ \psi$ isogeny is $I_{\phi \circ \psi} = I_\psi \cdot I_\phi$, a principal ideal corresponds to an endomorphism. For a thorough presentation of quaternions and the Deuring correspondence, we recommend the book of Voight [Voi20].

**Accessible torsion to make the Deuring correspondence effective.**

Making the Deuring correspondence effective means computing the isogeny $\phi_I : E \to E_I$ associated to an ideal $I$ and conversely, computing the kernel ideal $I_\phi$ of a known isogeny $\phi : E \to E'$ when $\text{End}(E)$ is known. Until recently, this could be done in polynomial time only when the ideal norm/the degree is smooth and the necessary $\text{nrd}(I)$-torsion to do these computations is "accessible" in the following sense.

**Definition 25.** Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve and $T := \prod_{i=1}^r \ell_i^{e_i}$ be an integer, where the $\ell_i$ are distinct primes. We say that $E$ has accessible $T$-torsion if $E[\ell_i^{e_i}]$ is defined over an extension of $\mathbb{F}_p$ of degree polynomial in $\log(p)$ for all $i \in [1; r]$.

Usually, in cryptographic protocols we choose $p$ to ensure the $T$-torsion is defined over $\mathbb{F}_{p^2}$ or $\mathbb{F}_{p^4}$ to optimize $T$-isogeny computations when $T$ is smooth. In general, if $T$ is $B$-powersmooth with $B$ polynomial in $\log(p)$, the $T$-torsion is always accessible and we can compute $T$-isogenies in polynomial time as a product of low degree isogenies as in [EHLMP18, Proposition 4]. Until recently, those were the only way to compute isogenies and make the Deuring correspondence effective. In this work, we propose a method to compute isogenies of non-smooth degree (see Section 2). We specialize it for SQIsignHD but this could be easily generalized.
## A.4 Algorithms for effective Deuring correspondence

In this section, we recall already known polynomial time algorithms making the Deuring correspondence effective. Those algorithms are used as ingredients of SQIsignHD. They were mainly introduced for previous versions of SQIsign [DKLPW20; FLLW23].

**Pushing the endomorphism ring through an isogeny.** In this paragraph, we introduce an algorithm to compute a basis of $End(E)$ that we can easily evaluate when we know an isogeny $E_0 \to E$ and a basis of $End(E_0)$ (in practice, $E_0$ is the elliptic curve of Example 24).

**Definition 26.** Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve and $\mathcal{O}$ be a maximal quaternion order in $\mathcal{B}_{p,\infty}$ isomorphic to $End(E)$. An eval-basis of $End(E)$ is the data of a basis $(\alpha_1, \cdots, \alpha_4)$ of $\mathcal{O}$ and an isomorphism $\varepsilon: \mathcal{O} \xrightarrow{\sim} \mathrm{End}(E)$ such that the $\varepsilon(\alpha_i)$ can be evaluated at any point of $E$ in polynomial time in $\log(p)$. We say it is an $N$-eval-basis if we can only evaluate the $\varepsilon(\alpha_i)$ on points of order prime to $N$.

For any left-ideal $I \subseteq \mathcal{O}$, we define an $(N)$-eval-basis of $I$ in a similar way. Such a basis can be obtained from an $(N)$-eval-basis of $End(E)$.

Assume that we know an eval-basis $((\alpha_1, \cdots, \alpha_4), \varepsilon)$ of $End(E_0)$. Let $\psi: E_0 \to E_1$ be an isogeny of degree $N$ with an efficient representation. Here, we explain how to use $\psi$ to compute an $N$-eval-basis of $End(E_1)$.

By [Voi20, Lemma 42.2.9], the map

$$ \iota: \mathrm{End}(E_1) \to \mathcal{B}_{p,\infty} \\ \phi \mapsto \frac{1}{N} \varepsilon^{-1}(\hat{\psi} \circ \phi \circ \psi) $$

induces an isomorphism $End(E_1) \xrightarrow{\sim} \mathcal{O}_1 := \mathcal{O}_R(I_\psi)$. Assuming that we know $I_\psi$, we can obtain a $\mathbb{Z}$-basis $(\beta_1, \cdots, \beta_4)$ of $\mathcal{O}_1$ via the formula $\mathcal{O}_1 = 1/N \bar{I}_\psi I_\psi$ [Voi20, Proposition 16.6.15]. Then, $\iota^{-1}$ induces an isomorphism $\mathcal{O}_1 \xrightarrow{\sim} \mathrm{End}(E_1)$.

We now explain how to use $\iota^{-1}$ to evaluate the $\beta_i$. Since $N\mathcal{O}_1 = \bar{I}_\psi I_\psi \subseteq \mathcal{O}_0$, we can write

$$ \beta_i := \frac{1}{N} \sum_{j=1}^{4} c_{i,j} \alpha_j, $$

with $c_{i,j} \in \mathbb{Z}$, for all $i \in [1; 4]$. We then have:

$$ \iota^{-1}(\beta_i) = \frac{1}{N^2} \sum_{j=1}^{4} c_{i,j} \psi \circ \varepsilon(\alpha_j) \circ \hat{\psi}, $$

so we can indeed easily evaluate the $\beta_i$ on any point of $E_1$ of order prime to $N$.
## A.4 Algorithms for effective Deuring correspondence

In this section, we recall already known polynomial time algorithms making the Deuring correspondence effective. Those algorithms are used as ingredients of SQIsignHD. They were mainly introduced for previous versions of SQIsign [DKLPW20; FLLW23].

**Pushing the endomorphism ring through an isogeny.** In this paragraph, we introduce an algorithm to compute a basis of $End(E)$ that we can easily evaluate when we know an isogeny $E_0 \to E$ and a basis of $End(E_0)$ (in practice, $E_0$ is the elliptic curve of Example 24).

**Definition 26.** Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve and $\mathcal{O}$ be a maximal quaternion order in $\mathcal{B}_{p,\infty}$ isomorphic to $End(E)$. An *eval-basis* of $End(E)$ is the data of a basis $(\alpha_1, \cdots, \alpha_4)$ of $\mathcal{O}$ and an isomorphism $\varepsilon: \mathcal{O} \xrightarrow{\sim} \mathrm{End}(E)$ such that the $\varepsilon(\alpha_i)$ can be evaluated at any point of $E$ in polynomial time in $\log(p)$. We say it is an $N$-eval-basis if we can only evaluate the $\varepsilon(\alpha_i)$ on points of order prime to $N$.

For any left-ideal $I \subseteq \mathcal{O}$, we define an $(N)$-eval-basis of $I$ in a similar way. Such a basis can be obtained from an $(N)$-eval-basis of $End(E)$.

Assume that we know an eval-basis $((\alpha_1, \cdots, \alpha_4), \varepsilon)$ of $End(E_0)$. Let $\psi: E_0 \to E_1$ be an isogeny of degree $N$ with an efficient representation. Here, we explain how to use $\psi$ to compute an $N$-eval-basis of $End(E_1)$.

By [Voi20, Lemma 42.2.9], the map

$$ \iota: \mathrm{End}(E_1) \to \mathcal{B}_{p,\infty} \\ \phi \mapsto \frac{1}{N} \varepsilon^{-1}(\hat{\psi} \circ \phi \circ \psi) $$

induces an isomorphism $End(E_1) \xrightarrow{\sim} \mathcal{O}_1 := \mathcal{O}_R(I_\psi)$. Assuming that we know $I_\psi$, we can obtain a $\mathbb{Z}$-basis $(\beta_1, \cdots, \beta_4)$ of $\mathcal{O}_1$ via the formula $\mathcal{O}_1 = 1/N \bar{I}_\psi I_\psi$ [Voi20, Proposition 16.6.15]. Then, $\iota^{-1}$ induces an isomorphism $\mathcal{O}_1 \xrightarrow{\sim} \mathrm{End}(E_1)$.

We now explain how to use $\iota^{-1}$ to evaluate the $\beta_i$. Since $N\mathcal{O}_1 = \bar{I}_\psi I_\psi \subseteq \mathcal{O}_0$, we can write

$$ \beta_i := \frac{1}{N} \sum_{j=1}^{4} c_{i,j} \alpha_j, $$

with $c_{i,j} \in \mathbb{Z}$, for all $i \in [1; 4]$. We then have:

$$ \iota^{-1}(\beta_i) = \frac{1}{N^2} \sum_{j=1}^{4} c_{i,j} \psi \circ \varepsilon(\alpha_j) \circ \hat{\psi}, $$

so we can indeed easily evaluate the $\beta_i$ on any point of $E_1$ of order prime to $N$.
**Algorithm 8: PushEndRing [EHLMP18, Algorithm 4]**

**Data:** An eval-basis $((\alpha_1, \dots, \alpha_4), \varepsilon)$ of $\text{End}(E_0)$ and an isogeny $\psi : E_0 \to E_1$ of degree $N$ with known kernel ideal $I_\psi$.

**Result:** An $N$-eval-basis $(\beta_1, \dots, \beta_4)$ of $\text{End}(E_1)$.

1. Compute a $\mathbb{Z}$-basis $(\beta_1, \dots, \beta_4)$ of $O_1 := 1/N \text{Im}\,I_\psi I_\psi$;

2. Write $\beta_i := 1/N \sum_{j=1}^N c_{i,j} \alpha_j$, with $c_{i,j} \in \mathbb{Z}$, for all $i=1, \dots, 4$;

3. Let $\varepsilon' : O_1 \xrightarrow{\sim} \text{End}(E_1)$, $\beta_i \mapsto 1/N^2 \sum_{j=1}^4 c_{i,j} \psi \circ \varepsilon(\alpha_j) \circ \hat{\psi}$;

4. Return $(\beta_1, \dots, \beta_4)$ and $\varepsilon'$;

**Algorithm 9: KernelTolideal<sub>D</sub>**

**Data:** A point $P \in E_1$ of smooth order $D$ and an eval-basis $((\beta_1, \dots, \beta_4), \varepsilon')$ of $\text{End}(E_1) \cong O_1$ that can be evaluated on $E_1[D]$.

**Result:** The ideal $I(\langle P \rangle) \subseteq O_1$ associated to the isogeny of kernel $\langle P \rangle$.

1. Compute $Q_i := \varepsilon'(\beta_i)(P)$ for $i=1, \dots, 4$;

2. Find $i, j$ such that $(Q_i, Q_j)$ is a basis of $E_1[D]$;

3. For $k \neq i, j$, find $a, b \in \mathbb{Z}/D\mathbb{Z}$ such that $Q_k = aQ_i + bQ_j$ (discrete logarithm problem);

4. Let $\gamma := \beta_k - a\beta_i - b\beta_j$;

5. Return $O_1\gamma + O_1D$;

**From isogenies to ideals.** Let $\varphi : E_1 \to E_2$ be a cyclic $D$-isogeny (with $D$ smooth) represented by a generator of its kernel $P$. We give an algorithm $\text{KernelTolideal}_D$ (Algorithm 9) due to Leroux [Ler22, Algorithm 20] to compute the ideal associated to a cyclic group $\langle P \rangle$ of a supersingular elliptic curve $E_1$ when we know an eval-basis of $\text{End}(E_1)$ that can be evaluated on $E_1[D]$. This algorithm is a variant of the algorithm introduced by Galbraith, Petit and Silva [GPS20, Algorithm 2] with the same purpose.

**Remark 27.** Since $D$ is smooth, the discrete logarithm problem in line 3 of Algorithm 9 is easy to solve with Pohlig-Hellman methods generalized by Teske to multiple discrete logarithms [PH78; Tes99].

**Lemma 28.** [Ler22, Lemma 4.22] Algorithm 9 terminates and is correct.

**Kernel ideal computation.** The two preceding algorithms immediately yield an algorithm *IsogenyTolideal* (Algorithm 10) computing the kernel ideal of $\varphi : E_1 \to E_2$ of smooth degree $D_\varphi$ when given an isogeny $\psi : E_0 \to E_1$ of smooth degree $D_\psi$ prime to $D_\varphi$ with known kernel ideal $I_\psi$ and an eval-basis of $\text{End}(E_0)$.

**The KLPT algorithm.** The KLPT algorithm was first introduced in [KLPT14] for extremal orders (such as $O_0$ in Example 24) and then generalized to other orders and improved in [DKLPW20], [FLLW23] and [Ler22]. In the following, we refer to the version of KLPT introduced in [Ler22, Algorithm 7]. Given a left
**Algorithm 8: PushEndRing [EHLMP18, Algorithm 4]**

**Data:** An eval-basis $((\alpha_1, \dots, \alpha_4), \varepsilon)$ of $\text{End}(E_0)$ and an isogeny $\psi : E_0 \to E_1$ of degree $N$ with known kernel ideal $I_\psi$.

**Result:** An $N$-eval-basis $(\beta_1, \dots, \beta_4)$ of $\text{End}(E_1)$.

1. Compute a $\mathbb{Z}$-basis $(\beta_1, \dots, \beta_4)$ of $\mathcal{O}_1 := 1/N \text{Im}\,I_\psi I_\psi$;

2. Write $\beta_i := 1/N \sum_{j=1}^N c_{i,j} \alpha_j$, with $c_{i,j} \in \mathbb{Z}$, for all $i=1, \dots, 4$;

3. Let $\varepsilon' : \mathcal{O}_1 \xrightarrow{\sim} \text{End}(E_1)$, $\beta_i \mapsto 1/N^2 \sum_{j=1}^4 c_{i,j} \psi \circ \varepsilon(\alpha_j) \circ \hat{\psi}$;

4. Return $(\beta_1, \dots, \beta_4)$ and $\varepsilon'$;

**Algorithm 9: KernelTolideal<sub>D</sub>**

**Data:** A point $P \in E_1$ of smooth order $D$ and an eval-basis $((\beta_1, \dots, \beta_4), \varepsilon')$ of $\text{End}(E_1) \cong \mathcal{O}_1$ that can be evaluated on $E_1[D]$.

**Result:** The ideal $I(\langle P \rangle) \subseteq \mathcal{O}_1$ associated to the isogeny of kernel $\langle P \rangle$.

1. Compute $Q_i := \varepsilon'(\beta_i)(P)$ for $i=1, \dots, 4$;

2. Find $i, j$ such that $(Q_i, Q_j)$ is a basis of $E_1[D]$;

3. For $k \neq i, j$, find $a, b \in \mathbb{Z}/D\mathbb{Z}$ such that $Q_k = aQ_i + bQ_j$ (discrete logarithm problem);

4. Let $\gamma := \beta_k - a\beta_i - b\beta_j$;

5. Return $\mathcal{O}_1\gamma + \mathcal{O}_1D$;

**From isogenies to ideals.** Let $\varphi : E_1 \to E_2$ be a cyclic $D$-isogeny (with $D$ smooth) represented by a generator of its kernel $P$. We give an algorithm $\text{KernelTolideal}_D$ (Algorithm 9) due to Leroux [Ler22, Algorithm 20] to compute the ideal associated to a cyclic group $\langle P \rangle$ of a supersingular elliptic curve $E_1$ when we know an eval-basis of $\text{End}(E_1)$ that can be evaluated on $E_1[D]$. This algorithm is a variant of the algorithm introduced by Galbraith, Petit and Silva [GPS20, Algorithm 2] with the same purpose.

**Remark 27.** Since $D$ is smooth, the discrete logarithm problem in line 3 of Algorithm 9 is easy to solve with Pohlig-Hellman methods generalized by Teske to multiple discrete logarithms [PH78; Tes99].

**Lemma 28.** [Ler22, Lemma 4.22] Algorithm 9 terminates and is correct.

**Kernel ideal computation.** The two preceding algorithms immediately yield an algorithm *IsogenyTolideal* (Algorithm 10) computing the kernel ideal of $\varphi : E_1 \to E_2$ of smooth degree $D_\varphi$ when given an isogeny $\psi : E_0 \to E_1$ of smooth degree $D_\psi$ prime to $D_\varphi$ with known kernel ideal $I_\psi$ and an eval-basis of $\text{End}(E_0)$.

**The KLPT algorithm.** The KLPT algorithm was first introduced in [KLPT14] for extremal orders (such as $\mathcal{O}_0$ in Example 24) and then generalized to other orders and improved in [DKLPW20], [FLLW23] and [Ler22]. In the following, we refer to the version of KLPT introduced in [Ler22, Algorithm 7]. Given a left
<caption>**Algorithm 10: IsogenyToldeal**</caption>

**Data:** An isogeny $\varphi : E_1 \to E_2$ of smooth degree $D_\varphi$, another isogeny $\psi : E_0 \to E_1$ of smooth degree $D_\psi$ coprime with $D_\varphi$ along with its kernel ideal $I_\psi$ and an eval-basis $B_0$ of $\text{End}(E_0)$.

**Result:** The kernel ideal $I_\varphi$ associated to $\varphi$.

1. Compute a $D_\psi$-eval-basis $B_1 := \text{PushEndRing}(B_0, \psi, I_\psi)$ of $\text{End}(E_1)$;

2. Let $P$ be a generator of $\text{ker}(\varphi)$;

3. $I_\varphi \leftarrow \text{KernelToldeal}_{D_\varphi}(P, B_1)$;

4. Return $I_\varphi$;

$O_0$-ideal $I$ and a (smooth) integer $N = \Omega(p^3)$, $\text{KLPT}_N(I)$ returns an equivalent ideal $J \sim I$ of norm dividing $N$.

This algorithm is generally used when we want to compute an isogeny path $E_0 \to E$. Given an ideal $I$ connecting $O_0 \cong \text{End}(E_0)$ to $O \cong \text{End}(E)$, which may not have smooth norm, we find $J \sim I$ with $\text{KLPT}$ of smooth norm $N$, so that the isogeny associated to $J$, $\phi_J : E_0 \to E$ can be computed.

**From ideal to isogenies.** Given a maximal order $O$ and a left $O$-ideal $J$, we have a straightforward way to compute the associated isogeny $\phi_J : E \to E'$. We evaluate a basis of $J$ on $E[nrd(J)]$ to compute $E[J] = \text{ker}(\phi_J)$ and then compute $\phi_J$ as a chain of small degree isogenies (assuming $\text{nrd}(J)$ is smooth) using Vélu's formulas [Vél71]. Unfortunately, we might not have accessible $\text{nrd}(J)$-torsion, especially if $J$ is obtained from $\text{KLPT}$ ($\text{nrd}(J) = \Theta(p^3)$ when $O = O_0$ and even bigger otherwise).

In [DKLPW20, Algorithm 7], the authors introduced the **SpecialldealTolsogeny** algorithm to perform this computation with half of the torsion when $O = O_0$ and when we know an alternate isogeny path. Assume we have accessible $T$-torsion with $T = \Omega(p^{3/2})$. **SpecialldealTolsogeny** takes as input two left-ideals $J, I \subseteq O_0$ of coprime norm such that $I \sim J$ and $\text{nrd}(J)|T^2$ along with the isogeny $\phi_I : E_0 \to E$ associated to $I$. It returns the isogeny $\phi_J : E_0 \to E$ associated to $J$.

### A.5 A non-smooth isogeny torsion evaluation algorithm

We present EvalTorsion$_D$ that evaluates a non-smooth degree isogeny on $D$-torsion points (with $D$ smooth) knowing its kernel ideal and an alternate smooth degree path. This algorithm is greatly inspired from [FKMT22, Algorithm 1] or [Ler23, Algorithm 2]. Let $I$ be an ideal connecting $O \cong \text{End}(E)$ and $O' \cong \text{End}(E')$ of non-smooth norm $q$, $(P_1, P_2)$ be a basis of $E[D]$, $\rho_1 : E_0 \to E$ and $\rho_2 : E_0 \to E'$, be two isogenies of respective degrees $d_1, d_2$ prime to $D$, and respective kernel ideals $I_1$ and $I_2$. We want to compute $(\phi_I(P_1), \phi_I(P_2))$, where $\phi_I : E \to E'$ is the isogeny associated to $I$.

Let us consider the endomorphism $\gamma := \hat{\rho}_2 \circ \phi_I \circ \rho_1$ of $E_0$. From that definition of $\gamma$ comes the equality

$$[d_1 d_2] \phi_I = \rho_2 \circ \gamma \circ \hat{\rho}_1.$$
<caption>**Algorithm 10: IsogenyToldeal**</caption>

**Data:** An isogeny $\varphi : E_1 \to E_2$ of smooth degree $D_\varphi$, another isogeny $\psi : E_0 \to E_1$ of smooth degree $D_\psi$ coprime with $D_\varphi$ along with its kernel ideal $I_\psi$ and an eval-basis $B_0$ of $\text{End}(E_0)$.

**Result:** The kernel ideal $I_\varphi$ associated to $\varphi$.

1. Compute a $D_\psi$-eval-basis $B_1 := \text{PushEndRing}(B_0, \psi, I_\psi)$ of $\text{End}(E_1)$;

2. Let $P$ be a generator of $\ker(\varphi)$;

3. $I_\varphi \leftarrow \text{KernelToldeal}_{D_\varphi}(P, B_1)$;

4. Return $I_\varphi$;

$O_0$-ideal $I$ and a (smooth) integer $N = \Omega(p^3)$, $\text{KLPT}_N(I)$ returns an equivalent ideal $J \sim I$ of norm dividing $N$.

This algorithm is generally used when we want to compute an isogeny path $E_0 \to E$. Given an ideal $I$ connecting $O_0 \cong \text{End}(E_0)$ to $O \cong \text{End}(E)$, which may not have smooth norm, we find $J \sim I$ with $\text{KLPT}$ of smooth norm $N$, so that the isogeny associated to $J$, $\phi_J : E_0 \to E$ can be computed.

**From ideal to isogenies.** Given a maximal order $O$ and a left $O$-ideal $J$, we have a straightforward way to compute the associated isogeny $\phi_J : E \to E'$. We evaluate a basis of $J$ on $E[nrd(J)]$ to compute $E[J] = \ker(\phi_J)$ and then compute $\phi_J$ as a chain of small degree isogenies (assuming $nrd(J)$ is smooth) using Vélu's formulas [Vél71]. Unfortunately, we might not have accessible $nrd(J)$-torsion, especially if $J$ is obtained from $\text{KLPT}$ ($nrd(J) = \Theta(p^3)$ when $O = O_0$ and even bigger otherwise).

In [DKLPW20, Algorithm 7], the authors introduced the **SpecialldealTolsogeny** algorithm to perform this computation with half of the torsion when $O = O_0$ and when we know an alternate isogeny path. Assume we have accessible $T$-torsion with $T = \Omega(p^{3/2})$. **SpecialldealTolsogeny** takes as input two left-ideals $J, I \subseteq O_0$ of coprime norm such that $I \sim J$ and $nrd(J)|T^2$ along with the isogeny $\phi_I : E_0 \to E$ associated to $I$. It returns the isogeny $\phi_J : E_0 \to E$ associated to $J$.

### A.5 A non-smooth isogeny torsion evaluation algorithm

We present EvalTorsion$_D$ that evaluates a non-smooth degree isogeny on $D$-torsion points (with $D$ smooth) knowing its kernel ideal and an alternate smooth degree path. This algorithm is greatly inspired from [FKMT22, Algorithm 1] or [Ler23, Algorithm 2]. Let $I$ be an ideal connecting $O \cong \text{End}(E)$ and $O' \cong \text{End}(E')$ of non-smooth norm $q$, $(P_1, P_2)$ be a basis of $E[D]$, $\rho_1 : E_0 \to E$ and $\rho_2 : E_0 \to E'$, be two isogenies of respective degrees $d_1, d_2$ prime to $D$, and respective kernel ideals $I_1$ and $I_2$. We want to compute $(\phi_I(P_1), \phi_I(P_2))$, where $\phi_I : E \to E'$ is the isogeny associated to $I$.

Let us consider the endomorphism $\gamma := \hat{\rho}_2 \circ \phi_I \circ \rho_1$ of $E_0$. From that definition of $\gamma$ comes the equality

$$[d_1 d_2] \phi_I = \rho_2 \circ \gamma \circ \hat{\rho}_1.$$
<caption>**Algorithm 11: EvalTorsion<sub>D</sub>**</caption>

**Data:** A basis $(P_1, P_2)$ of $E[D]$, an ideal $I$ connecting $\mathcal{O} \cong \text{End}(E)$ and $\mathcal{O}' := \text{End}(E')$, two isogenies $\rho_1 : E_0 \to E$ and $\rho_2 : E_0 \to E'$ of respective degrees $d_1$ and $d_2$ prime to $D$ and their respective kernel ideals $I_1$ and $I_2$.

**Result:** $(\phi_I(P_1), \phi_I(P_2))$, where $\phi_I : E \to E'$ is the isogeny associated to $I$.

1. Find $\gamma \in \mathcal{O}_0$ such that $\mathcal{O}_0\gamma = I_1 \cdot I \cdot \overline{I_2}$;

2. $R_i \leftarrow \rho_2 \circ \gamma \circ \hat{\rho}_1(P_i)$ for $i \in \{1, 2\}$;

3. Compute $\lambda$, an inverse of $d_1 d_2$ modulo $D$;

4. Return $([\lambda]R_1, [\lambda]R_2)$;

Since $D$ is prime to $d_1$ and $d_2$, the scalar $d_1 d_2$ can be inverted modulo $D$ and we see that it suffices to evaluate $\gamma, \hat{\rho}_1, \rho_2$ on the $D$-torsion of their respective domains.

The curve $E_0$ is chosen to have a known endomorphism ring so we can easily evaluate $\gamma$ at any point from a basis of endomorphisms if we know the principal ideal $\mathcal{O}_0\gamma$. This ideal can be computed from the ideals $I_1, I_2 \subset \mathcal{O}_0$ and $I \subset \mathcal{O}$ associated to $\rho_1, \rho_2$ and $\phi_I$ respectively, with the formula $I_1 \cdot I \cdot \overline{I_2} = \mathcal{O}_0\gamma$. The EvalTorsion<sub>D</sub> algorithm summarizes the procedure described above.

# B The description of RigorousSQIsignHD

In this section, we describe the details of the RigorousSQIsignHD protocols and parameters. Recall that unlike FastSQIsignHD, this algorithm relies on a verification procedure in dimension 8 and is optimised for security at the expense of efficiency. This scheme is theoretical and not meant to be implemented.

## B.1 In RigorousSQIsignHD, more torsion is needed than in FastSQIsignHD.

As in FastSQIsignHD, in RigorousSQIsignHD we still require $p = \Omega(2^{2\lambda})$ to achieve a classical security level of $\lambda$ bits (and a quantum security level of $\lambda/2$ bits). The degrees $D_\tau, D_\psi$ and $D_\varphi$ still need to be coprime with $\ell$ for the response isogeny evaluation with EvalTorsion<sub>££</sub>, while $D_{\tau'}$ needs to be coprime with $D_\varphi$ for the computation of $I_\varphi$. In addition, we need $E_1$ and $E_A$ to be rigorously (and not only heuristically) computationally indistinguishable from a uniformly random supersingular elliptic curve. For that reason, we shall have $D_\tau, D_\psi = \Theta(p^3)$ and $D_{\tau'} = \ell^h = \Theta(p^2)$ (as will be explained in Appendix B.2).

For the computation of the secret key $\tau$ and commitment isogeny $\psi$ and challenge $\varphi$, we need accessible $T$-torsion such that $D_\tau, D_\psi|T^2$ with $T$ prime to $\ell$ and $T = \Omega(p^{3/2})$, as in the original SQIsign protocol [DKLPW20]. We also require $D_\varphi|T$ to compute the challenge whose degree is $D_\varphi = O(p^3)$ (as will be explained in Appendix D.1). Hence, we require $T \simeq p^3$.
<caption>**Algorithm 11: EvalTorsion<sub>D</sub>**</caption>

**Data:** A basis $(P_1, P_2)$ of $E[D]$, an ideal $I$ connecting $\mathcal{O} \cong \text{End}(E)$ and $\mathcal{O}' := \text{End}(E')$, two isogenies $\rho_1 : E_0 \to E$ and $\rho_2 : E_0 \to E'$ of respective degrees $d_1$ and $d_2$ prime to $D$ and their respective kernel ideals $I_1$ and $I_2$.

**Result:** $(\phi_I(P_1), \phi_I(P_2))$, where $\phi_I : E \to E'$ is the isogeny associated to $I$.

1. Find $\gamma \in \mathcal{O}_0$ such that $\mathcal{O}_0\gamma = I_1 \cdot I \cdot \overline{I_2}$;

2. $R_i \leftarrow \rho_2 \circ \gamma \circ \hat{\rho}_1(P_i)$ for $i \in \{1, 2\}$;

3. Compute $\lambda$, an inverse of $d_1 d_2$ modulo $D$;

4. Return $([\lambda]R_1, [\lambda]R_2)$;

Since $D$ is prime to $d_1$ and $d_2$, the scalar $d_1 d_2$ can be inverted modulo $D$ and we see that it suffices to evaluate $\gamma, \hat{\rho}_1, \rho_2$ on the $D$-torsion of their respective domains.

The curve $E_0$ is chosen to have a known endomorphism ring so we can easily evaluate $\gamma$ at any point from a basis of endomorphisms if we know the principal ideal $\mathcal{O}_0\gamma$. This ideal can be computed from the ideals $I_1, I_2 \subset \mathcal{O}_0$ and $I \subset \mathcal{O}$ associated to $\rho_1, \rho_2$ and $\phi_I$ respectively, with the formula $I_1 \cdot I \cdot \overline{I_2} = \mathcal{O}_0\gamma$. The EvalTorsion<sub>D</sub> algorithm summarizes the procedure described above.

# B The description of RigorousSQIsignHD

In this section, we describe the details of the RigorousSQIsignHD protocols and parameters. Recall that unlike FastSQIsignHD, this algorithm relies on a verification procedure in dimension 8 and is optimised for security at the expense of efficiency. This scheme is theoretical and not meant to be implemented.

## B.1 In RigorousSQIsignHD, more torsion is needed than in FastSQIsignHD.

As in FastSQIsignHD, in RigorousSQIsignHD we still require $p = \Omega(2^{2\lambda})$ to achieve a classical security level of $\lambda$ bits (and a quantum security level of $\lambda/2$ bits). The degrees $D_\tau, D_\psi$ and $D_\varphi$ still need to be coprime with $\ell$ for the response isogeny evaluation with EvalTorsion<sub>ℓ</sub>, while $D_{\tau'}$ needs to be coprime with $D_\varphi$ for the computation of $I_\varphi$. In addition, we need $E_1$ and $E_A$ to be rigorously (and not only heuristically) computationally indistinguishable from a uniformly random supersingular elliptic curve. For that reason, we shall have $D_\tau, D_\psi = \Theta(p^3)$ and $D_{\tau'} = \ell^h = \Theta(p^2)$ (as will be explained in Appendix B.2).

For the computation of the secret key $\tau$ and commitment isogeny $\psi$ and challenge $\varphi$, we need accessible $T$-torsion such that $D_\tau, D_\psi|T^2$ with $T$ prime to $\ell$ and $T = \Omega(p^{3/2})$, as in the original SQIsign protocol [DKLPW20]. We also require $D_\varphi|T$ to compute the challenge whose degree is $D_\varphi = O(p^3)$ (as will be explained in Appendix D.1). Hence, we require $T \simeq p^3$.
As previously, we can compute the $\ell^e$-isogeny $F$ representing the response $\sigma$
in dimension 8 as long as we have accessible $\ell^f$-torsion with $2f \ge e+4$. However,
as will be explained in Appendix D.2, to prove the zero-knowledge property, we
need $\ell^e = \Theta(p^2)$ instead of $\Theta(\sqrt{p})$, so we can have $\ell^f = \Theta(p)$. Hence $p$ should
be of the form $p = c\ell^f - 1$ with $c$ as small as possible.

Then, the accessible $T$-torsion will be defined over small field extensions of $\mathbb{F}_{p^2}$. For instance, $T$ could be the product of the smallest successive primes ($\ell$ excluded) such that $T \simeq p^3$. All the primes we need will be $O(\log(p))$, so the $T$-torsion will be defined on extensions of degree $O(\log(p))$ of $\mathbb{F}_{p^2}$ and all isogeny computations will be polynomial in $\log(p)$.

This ensures in particular that RigorousSQIsignHD complexity scales polyno-
mially with the security parameter $\lambda$ (as FastSQIsignHD), which is an interesting
property in comparison with SQIsign. Indeed, in SQIsign [FLLW23] the authors
imposed $\ell^f|p-1$ and $T|p^2-1$ (with $T \simeq p^{5/4}$), so that the whole $T$-torsion is
defined over $\mathbb{F}_{p^4}$ (and $x$-coordinates are defined over $\mathbb{F}_{p^2}$). Finding such primes
has been an open research question since the introduction of SQIsign [CMN21;
BSC+22; Ahr23]. It is still unclear if we can still find $T$ sufficiently smooth as
the security level grows. Since computing a prime degree isogeny is exponential
in the degree, the SQIsign protocol might not be polynomial in $\log(p)$.

## B.2 Provably secure key generation and commitment

To prove security, the distribution of the public key $E_A$ and the commitment $E_1$
need to be close to the uniform distribution in the supersingular isogeny graph.
Heuristically, we expect to get an elliptic curve with a distribution somewhat
close to uniform after a random isogeny walk of length $\Theta(p)$. However, the fact
that we compute two paths simultaneously in FastCommit and FastKeyGen might
alter the distribution of the resulting elliptic curve. While we do not expect the
induced bias to be computationally relevant, it prevents a rigorous analysis. This
is the reason why we now propose a different procedure for RigorousKeyGen and
RigorousCommit.

Starting from $E_0$, we generate a random $\ell$-isogeny walk $\phi : E_0 \to E$ long enough to make $E$ uniformly random and compute its kernel ideal $I_\phi$ as well as an alternate path $\phi' : E_0 \to E$ of degree dividing $T^2$. This algorithm is very similar to what is done in the first version of SQIsign signing algorithm [DKLPW20]. The procedure we shall describe is costly (though polynomial) and this is one of the reasons why we do not expect the efficiency of RigorousSQIsignHD to compare favourably to the original SQIsign protocol.

A long enough supersingular $\ell$-isogeny walk.

**Proposition 29.** Let $\phi : E_0 \to E$ be an $\ell^h$-isogeny obtained from a non-backtracking random $\ell$-isogeny walk. Then, for all $\varepsilon \in ]0, 2]$, the distribution of $E$ has statistical distance $\tilde{O}(p^{-\varepsilon/2})$ to the uniform distribution in the supersingular isogeny graph, provided that $h \ge (1 + \varepsilon) \log_{\ell}(p)$.
As previously, we can compute the $\ell^e$-isogeny $F$ representing the response $\sigma$
in dimension 8 as long as we have accessible $\ell^f$-torsion with $2f \ge e+4$. However,
as will be explained in Appendix D.2, to prove the zero-knowledge property, we
need $\ell^e = \Theta(p^2)$ instead of $\Theta(\sqrt{p})$, so we can have $\ell^f = \Theta(p)$. Hence $p$ should
be of the form $p = c\ell^f - 1$ with $c$ as small as possible.

Then, the accessible $T$-torsion will be defined over small field extensions of $\mathbb{F}_{p^2}$. For instance, $T$ could be the product of the smallest successive primes ($\ell$ excluded) such that $T \simeq p^3$. All the primes we need will be $O(\log(p))$, so the $T$-torsion will be defined on extensions of degree $O(\log(p))$ of $\mathbb{F}_{p^2}$ and all isogeny computations will be polynomial in $\log(p)$.

This ensures in particular that RigorousSQIsignHD complexity scales polyno-
mially with the security parameter $\lambda$ (as FastSQIsignHD), which is an interesting
property in comparison with SQIsign. Indeed, in SQIsign [FLLW23] the authors
imposed $\ell^f|p-1$ and $T|p^2-1$ (with $T \simeq p^{5/4}$), so that the whole $T$-torsion is
defined over $\mathbb{F}_{p^4}$ (and $x$-coordinates are defined over $\mathbb{F}_{p^2}$). Finding such primes
has been an open research question since the introduction of SQIsign [CMN21;
BSC+22; Ahr23]. It is still unclear if we can still find $T$ sufficiently smooth as
the security level grows. Since computing a prime degree isogeny is exponential
in the degree, the SQIsign protocol might not be polynomial in $\log(p)$.

## B.2 Provably secure key generation and commitment

To prove security, the distribution of the public key $E_A$ and the commitment $E_1$
need to be close to the uniform distribution in the supersingular isogeny graph.
Heuristically, we expect to get an elliptic curve with a distribution somewhat
close to uniform after a random isogeny walk of length $\Theta(p)$. However, the fact
that we compute two paths simultaneously in FastCommit and FastKeyGen might
alter the distribution of the resulting elliptic curve. While we do not expect the
induced bias to be computationally relevant, it prevents a rigorous analysis. This
is the reason why we now propose a different procedure for RigorousKeyGen and
RigorousCommit.

Starting from $E_0$, we generate a random $\ell$-isogeny walk $\phi : E_0 \to E$ long enough to make $E$ uniformly random and compute its kernel ideal $I_\phi$ as well as an alternate path $\phi' : E_0 \to E$ of degree dividing $T^2$. This algorithm is very similar to what is done in the first version of SQIsign signing algorithm [DKLPW20]. The procedure we shall describe is costly (though polynomial) and this is one of the reasons why we do not expect the efficiency of RigorousSQIsignHD to compare favourably to the original SQIsign protocol.

A long enough supersingular $\ell$-isogeny walk.

**Proposition 29.** Let $\phi : E_0 \to E$ be an $\ell^h$-isogeny obtained from a non-backtracking random $\ell$-isogeny walk. Then, for all $\varepsilon \in ]0, 2]$, the distribution of $E$ has statistical distance $\tilde{O}(p^{-\varepsilon/2})$ to the uniform distribution in the supersingular isogeny graph, provided that $h \ge (1 + \varepsilon) \log_{\ell}(p)$.
**Proof.** Let $SS(p)$ be the set of supersingular elliptic curves over $\mathbb{F}_{p^2}$ (up to isomorphism) and $S$ be the probability distribution on $SS(p)$ given by $S(E) := K^{-1}/\#\mathrm{Aut}(E)$ for all $E \in SS(p)$, with $K := \sum_{E \in SS(p)} 1/\#\mathrm{Aut}(E)$. Let $\delta_0$ be the Dirac distribution on $E_0$ and $\delta_0^{(h)}$ the distribution obtained from $\delta_0$ after a non-backtracking $\ell$-isogeny walk of length $h$. By [BCC+23, Theorem 11], the statistical distance between $S$ and $\delta_0^{(h)}$ satisfies

$$d_{TV}(S, \delta_0^{(h)}) := \frac{1}{2} \sum_{E \in SS(p)} |S(E) - \delta_0^{(h)}(E)| \le \frac{\sqrt{6K}(\ell+1)(h+1)-2}{2(\ell+1)\sqrt{\ell^h}}.$$

By the Eichler's mass formula [Voi20, p. 42.3.8], we know that $K = (p-1)/24$. Then, when $h \ge (1+\varepsilon)\log_\ell(p)$, we get that $d_{TV}(S, \delta_0^{(h)}) = O(\log(p)p^{-\varepsilon/2}) = \tilde{O}(p^{-\varepsilon/2})$.

By Lemma 30, we have $d_{TV}(U, S) = O(p^{-1})$, so we finally get, by triangular inequality, that $d_{TV}(U, \delta_0^{(h)}) = \tilde{O}(p^{-\varepsilon/2})$. $\square$

**Lemma 30.** The statistical distance between $S$ and $U$ is $d_{TV}(S, U) = O(p^{-1})$.

**Proof.** By [Sil09][Theorem III.10.1], we have $\#\mathrm{Aut}(E) = 2$ for all $E \in SS(p)$ such that $j(E) \ne 0, 1728$, and $\#\mathrm{Aut}(E) \in \{4, 6\}$ otherwise and by [Sil09][Theorem V.4.1], there exists $C_p \in \mathbb{Z}$ small such that $\#SS(p) = 2K + C_p$. Hence, we have

$$ \begin{aligned} d_{TV}(U, S) &= \frac{1}{2} \sum_{E \in SS(p)} \left| \frac{1}{\# SS(p)} - \frac{1}{K \# \mathrm{Aut}(E)} \right| \\ &= \frac{1}{2} \sum_{\substack{E \in SS(p) \\ j(E) \ne 0, 1728}} \left| \frac{1}{2K + C_p} - \frac{1}{2K} \right| + O(p^{-1}) \\ &= \frac{C_p}{2K(2K + C_p)} (\#SS(p) + O(1)) + O(p^{-1}) \\ &= \frac{C_p}{4K} + O(p^{-1}) = O(p^{-1}). \end{aligned} \square $$

By Proposition 29 (with $\varepsilon = 1$), an adversary needs time $\tilde{O}(\sqrt{p})$ to distinguish a supersingular elliptic curve obtained from $E_0$ after a non-backtracking $\ell$-isogeny path of degree $\Theta(p^2)$ from a uniformly random elliptic curve in the supersingular isogeny graph. Since $p = \Theta(2^\lambda)$, this is sufficient to ensure a security level of $\lambda$ bits.

**Computing the kernel ideal and an alternate path.** Assume that we have generated a random $\ell$-isogeny walk $\phi: E_0 \to E$ of degree $\ell^h = \Theta(p^2)$.
**Proof.** Let $SS(p)$ be the set of supersingular elliptic curves over $\mathbb{F}_{p^2}$ (up to isomorphism) and $S$ be the probability distribution on $SS(p)$ given by $S(E) := K^{-1}/\#\mathrm{Aut}(E)$ for all $E \in SS(p)$, with $K := \sum_{E \in SS(p)} 1/\#\mathrm{Aut}(E)$. Let $\delta_0$ be the Dirac distribution on $E_0$ and $\delta_0^{(h)}$ the distribution obtained from $\delta_0$ after a non-backtracking $\ell$-isogeny walk of length $h$. By [BCC+23, Theorem 11], the statistical distance between $S$ and $\delta_0^{(h)}$ satisfies

$$d_{TV}(S, \delta_0^{(h)}) := \frac{1}{2} \sum_{E \in SS(p)} |S(E) - \delta_0^{(h)}(E)| \le \frac{\sqrt{6K}(\ell+1)(h+1)-2}{2(\ell+1)\sqrt{\ell^h}}.$$

By the Eichler's mass formula [Voi20, p. 42.3.8], we know that $K = (p-1)/24$. Then, when $h \ge (1+\varepsilon)\log_\ell(p)$, we get that $d_{TV}(S, \delta_0^{(h)}) = O(\log(p)p^{-\varepsilon/2}) = \tilde{O}(p^{-\varepsilon/2})$.

By Lemma 30, we have $d_{TV}(U, S) = O(p^{-1})$, so we finally get, by triangular inequality, that $d_{TV}(U, \delta_0^{(h)}) = \tilde{O}(p^{-\varepsilon/2})$. $\square$

**Lemma 30.** The statistical distance between $S$ and $U$ is $d_{TV}(S, U) = O(p^{-1})$.

**Proof.** By [Sil09][Theorem III.10.1], we have $\#\mathrm{Aut}(E) = 2$ for all $E \in SS(p)$ such that $j(E) \ne 0, 1728$, and $\#\mathrm{Aut}(E) \in \{4, 6\}$ otherwise and by [Sil09][Theorem V.4.1], there exists $C_p \in \mathbb{Z}$ small such that $\#SS(p) = 2K + C_p$. Hence, we have

$$\begin{aligned}
d_{TV}(U, S) &= \frac{1}{2} \sum_{E \in SS(p)} \left| \frac{1}{\# SS(p)} - \frac{1}{K \# \mathrm{Aut}(E)} \right| \\
&= \frac{1}{2} \sum_{\substack{E \in SS(p) \\ j(E) \ne 0, 1728}} \left| \frac{1}{2K + C_p} - \frac{1}{2K} \right| + O(p^{-1}) \\
&= \frac{C_p}{2K(2K + C_p)} (\#SS(p) + O(1)) + O(p^{-1}) \\
&= \frac{C_p}{4K} + O(p^{-1}) = O(p^{-1}).
\end{aligned}$$

$\square$

By Proposition 29 (with $\varepsilon = 1$), an adversary needs time $\tilde{O}(\sqrt{p})$ to distinguish a supersingular elliptic curve obtained from $E_0$ after a non-backtracking $\ell$-isogeny path of degree $\Theta(p^2)$ from a uniformly random elliptic curve in the supersingular isogeny graph. Since $p = \Theta(2^\lambda)$, this is sufficient to ensure a security level of $\lambda$ bits.

**Computing the kernel ideal and an alternate path.** Assume that we have generated a random $\ell$-isogeny walk $\phi : E_0 \to E$ of degree $\ell^h = \Theta(p^2)$.
<caption>**Algorithm 12: RigorousDoublePath<sub>ℓf,T</sub>**</caption>

**Data:** A supersingular elliptic curve $E_0$ with accessible T-torsion and $\ell^f$-torsion, an eval-basis $\mathcal{B}_0$ of $\text{End}(E_0)$ in the sense of Definition 26.

**Result:** A random $\ell$-isogeny walk $\phi: E_0 \to E$ of degree $\ell^h = \Theta(p^2)$ such that the distribution of $E$ has statistical distance $\tilde{O}(p^{-1/2})$ to the uniform, an isogeny $\phi': E_0 \to E$ of degree dividing $T^2$ and their respective kernel ideals $I_\phi$ and $I_{\phi'}$.

1 $h \leftarrow [2 \log_\ell(p)];$
2 Perform a random non-backtracking $\ell$-isogeny walk $\phi: E_0 \to E$ of degree $\ell^h$;
3 Decompose $\phi$ in a sequence of isogenies $\phi_i: E_i \to E_{i+1} \ (1 \le i \le r)$ of degree dividing $\ell^f$;
4 Let $P_i$ be a generator of $\ker(\phi_i)$ for all $i \in [1; r]$;
5 $J_0 \leftarrow \mathcal{O}_0$;
6 **for** $i := 0$ **to** $r-1$ **do**
7 &nbsp;&nbsp;&nbsp;&nbsp;$I_i \leftarrow \text{KernelTolideal}_{\ell f}(\mathcal{B}_i, P_i)$;
8 &nbsp;&nbsp;&nbsp;&nbsp;$J_{i+1} \leftarrow \text{KLPT}_{T^2}(J_i \cdot I_i)$;
9 &nbsp;&nbsp;&nbsp;&nbsp;$\phi'_{i+1} \leftarrow \text{SpecialidealTolsogeny}(J_{i+1}, I_0 \cdots I_i, \phi_i \circ \cdots \circ \phi_0)$;
10 &nbsp;&nbsp;&nbsp;&nbsp;Compute $\mathcal{B}_{i+1} := \text{PushEndRing}(\mathcal{B}_0, \phi'_{i+1}, J_{i+1})$, a T-eval-basis of $\text{End}(E_{i+1})$;
11 **end**
12 $\phi' \leftarrow \phi'_r, I_\phi \leftarrow I_0 \cdots I_{r-1}, I_{\phi'} \leftarrow J_r$;
13 Return $\phi, \phi', I_\phi, I_{\phi'}$;

To compute the kernel ideal $I_\phi$, we cannot use $\text{KernelTolideal}_{\ell^h}$ (Algorithm 9) because we would need accessible $\ell^h$-torsion, which is impossible since $\ell^h \gg p$.

Instead, as in [DKLPW20], we divide $\phi$ into a sequence of isogenies $\phi_i: E_i \to E_{i+1} \ (1 \le i \le r)$ of degree dividing $\ell^f$ and compute their associated kernel ideals $I_i$ successively. For the computation of $I_i$, we need to compute an alternate isogeny $\phi'_i: E_0 \to E_i$ of degree dividing $T^2$ obtained at step $i-1$. Hence, the alternate path $\phi' := \phi_r: E_0 \to E_r = E$ will be a convenient by-product of our ideal computation. The algorithm we propose (see Algorithm 12) uses the sub-algorithms $\text{KLPT}_{T^2}$ and $\text{SpecialidealTolsogeny}$ as black boxes (see Appendix A.4).

**Application to key generation and commitment.** For the key generation phase $\text{RigorousKeyGen}$, we simply call $\text{RigorousDoublePath}_{\ell f, T}$ to output two isogenies $\tau', \tau: E_0 \to E_A$ with codomain $E_A$ statistically close to uniform and respective degrees $\ell^h$ and dividing $T^2$, along with their kernel ideals $I_{\tau'}$ and $I_\tau$.

For the commitment $\text{RigorousCommit}$, we only need an isogeny $\psi: E_0 \to E_1$ of degree $T^2$ (prime to $\ell$) with codomain $E_1$ statistically close to uniform. $\text{RigorousDoublePath}_{\ell f, T}$ will output $\phi, \phi': E_0 \to E_1$ of respective degrees $\ell^h$ and $D_{\phi'}|T^2$, along with $I_\phi, I_{\phi'}$. The data $(\phi, I_\phi)$ will not be used so we only compute $\phi$ to ensure the randomness of $E_1$ and $I_\phi$ as an intermediary tool to obtain $(\psi', I_{\psi'}) := (\phi', I_{\phi'})$.
<caption>**Algorithm 12: RigorousDoublePath<sub>ℓf,T</sub>**</caption>

**Data:** A supersingular elliptic curve $E_0$ with accessible T-torsion and $\ell^f$-torsion, an eval-basis $\mathcal{B}_0$ of $\text{End}(E_0)$ in the sense of Definition 26.

**Result:** A random $\ell$-isogeny walk $\phi: E_0 \to E$ of degree $\ell^h = \Theta(p^2)$ such that the distribution of $E$ has statistical distance $\tilde{O}(p^{-1/2})$ to the uniform, an isogeny $\phi': E_0 \to E$ of degree dividing $T^2$ and their respective kernel ideals $I_\phi$ and $I_{\phi'}$.

1 & $h \leftarrow [2 \log_\ell(p)];$
2 & Perform a random non-backtracking $\ell$-isogeny walk $\phi: E_0 \to E$ of degree $\ell^h$;
3 & Decompose $\phi$ in a sequence of isogenies $\phi_i: E_i \to E_{i+1} \ (1 \le i \le r)$ of degree dividing $\ell^f$;
4 & Let $P_i$ be a generator of $\ker(\phi_i)$ for all $i \in [1; r]$;
5 & $J_0 \leftarrow \mathcal{O}_0$;
6 & **for** $i := 0$ **to** $r-1$ **do**
7 & & & $I_i \leftarrow \text{KernelTolideal}_{\ell f}(\mathcal{B}_i, P_i)$;
8 & & $J_{i+1} \leftarrow \text{KLPT}_{T^2}(J_i \cdot I_i)$;
9 & & $\phi'_{i+1} \leftarrow \text{SpecialidealTolsogeny}(J_{i+1}, I_0 \cdots I_i, \phi_i \circ \cdots \circ \phi_0)$;
10 & & Compute $\mathcal{B}_{i+1} := \text{PushEndRing}(\mathcal{B}_0, \phi'_{i+1}, J_{i+1})$, a T-eval-basis of $\text{End}(E_{i+1})$;
11 & **end**
12 & $\phi' \leftarrow \phi'_r, I_\phi \leftarrow I_0 \cdots I_{r-1}, I_{\phi'} \leftarrow J_r$;
13 & **Return** $\phi, \phi', I_\phi, I_{\phi'}$;

To compute the kernel ideal $I_\phi$, we cannot use $\text{KernelTolideal}_{\ell^h}$ (Algorithm 9) because we would need accessible $\ell^h$-torsion, which is impossible since $\ell^h \gg p$.

Instead, as in [DKLPW20], we divide $\phi$ into a sequence of isogenies $\phi_i: E_i \to E_{i+1} \ (1 \le i \le r)$ of degree dividing $\ell^f$ and compute their associated kernel ideals $I_i$ successively. For the computation of $I_i$, we need to compute an alternate isogeny $\phi'_i: E_0 \to E_i$ of degree dividing $T^2$ obtained at step $i-1$. Hence, the alternate path $\phi' := \phi_r: E_0 \to E_r = E$ will be a convenient by-product of our ideal computation. The algorithm we propose (see Algorithm 12) uses the sub-algorithms $\text{KLPT}_{T^2}$ and $\text{SpecialidealTolsogeny}$ as black boxes (see Appendix A.4).

**Application to key generation and commitment.** For the key generation phase $\text{RigorousKeyGen}$, we simply call $\text{RigorousDoublePath}_{\ell f, T}$ to output two isogenies $\tau', \tau: E_0 \to E_A$ with codomain $E_A$ statistically close to uniform and respective degrees $\ell^h$ and dividing $T^2$, along with their kernel ideals $I_{\tau'}$ and $I_\tau$.

For the commitment $\text{RigorousCommit}$, we only need an isogeny $\psi: E_0 \to E_1$ of degree $T^2$ (prime to $\ell$) with codomain $E_1$ statistically close to uniform. $\text{RigorousDoublePath}_{\ell f, T}$ will output $\phi, \phi': E_0 \to E_1$ of respective degrees $\ell^h$ and $D_{\phi'}|T^2$, along with $I_\phi, I_{\phi'}$. The data $(\phi, I_\phi)$ will not be used so we only compute $\phi$ to ensure the randomness of $E_1$ and $I_\phi$ as an intermediary tool to obtain $(\psi', I_{\psi'}) := (\phi', I_{\phi'})$.
## B.3 The challenge generation

In RigorousSQIsignHD, the degree of the challenge isogeny $D_\varphi$ will be a divisor of $T$ of size $D_\varphi \simeq p^3$. More details on the choice of $D_\varphi$ in RigorousSQIsignHD will be given in the security analysis (see Appendix D.1).

## B.4 Response and verification in RigorousSQIsignHD

In this section, we cover the algorithmic blocks introduced in Section 4.1 for Fast-SQIsignHD. Some of the algorithms are common with the dimension 4 and some are specific to the dimension 8. As in Section 4.1, we start with an overview of the algorithmic building blocks of RigorousRespond and RigorousVerify and then present them in detail.

Those algorithms use the following sub-algorithms:

- **IsogenyToldeal**($\varphi, \psi, I_\psi$) (already presented in Appendix A.4).

- **RandomEquivalentIdeal**$_{\ell^e}$ (already presented in Section 4.2).

- **EvalTorsion**$_{\ell f}$ (already presented in Appendix A.5).

- **RepresentIsogeny**$_{8,\ell^e,\ell f}$ takes as input an integer $q < \ell^e$ coprime with $\ell$, integers $a_1, \dots, a_4$ such that $a_1^2 + \dots + a_4^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 8-dimensional $\ell$-isogenies whose composition is $F(\sigma, a_1, \dots, a_4)$.

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

The response and verification procedures follow the same ideas introduced for FastSQIsignHD. To respond, the prover computes a random ideal $I \sim \bar{I}_\psi \cdot I_\tau \cdot I_\varphi$ of norm $q \le \ell^e$ and evaluates the associated isogeny $\sigma : E_1 \to E_2$ on a canonical basis $(P_1, P_2)$ of $E_1[\ell f]$. Then, they send $(q, \sigma(P_1), \sigma(P_2))$ to the verifier. The latter, after receiving $(q, \sigma(P_1), \sigma(P_2))$ computes integers $a_1, \dots, a_4$ such that $a_1^2 + \dots + a_4^2 + q = \ell^e$, computes $F(\sigma, a_1, \dots, a_4)$ and verifies the result is correct with **IsValid**$_8$. Algorithms 13 and 14 follow.

*Remark B.1 (Case gcd($q, \ell$) $\neq$ 1).* For security reasons (see Remark 7), $q = \text{nrd}(I) = \text{deg}(\sigma)$ can take any value $\le \ell^e$, including multiples of $\ell$. In that case, we cannot evaluate $\sigma$ on $E_1[\ell f]$ with **EvalTorsion**$_{\ell f}$ directly. To know how to treat this case, we refer to Appendix C. Our solution involves factoring $\sigma$ by $\ell$-isogenies and applying **RepresentIsogeny**$_{8,\ell^e,\ell f}$ to a factor of $\sigma$ of degree prime to $\ell$. In the following, we assume $q$ prime to $\ell$ for simplicity.

As input of Algorithms 13 and 14, we denote by:

- **RigorousSetup**, the public parameters of RigorousSQIsignHD, $p, \ell$ and $f$ such that $\ell^f|p-1$, $e, T$ powersmooth (accessible torsion) and $E_0$;

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

- **CommitData**, the isogeny $\psi : E_0 \to E_1$ of degree $D_\psi|T^2$ and its kernel ideal $I_\psi$;

- **ChallData**, the isogeny $\varphi : E_A \to E_2$ of degree $D_\varphi|T$.
## B.3 The challenge generation

In RigorousSQIsignHD, the degree of the challenge isogeny $D_\varphi$ will be a divisor of $T$ of size $D_\varphi \simeq p^3$. More details on the choice of $D_\varphi$ in RigorousSQIsignHD will be given in the security analysis (see Appendix D.1).

## B.4 Response and verification in RigorousSQIsignHD

In this section, we cover the algorithmic blocks introduced in Section 4.1 for Fast-SQIsignHD. Some of the algorithms are common with the dimension 4 and some are specific to the dimension 8. As in Section 4.1, we start with an overview of the algorithmic building blocks of RigorousRespond and RigorousVerify and then present them in detail.

Those algorithms use the following sub-algorithms:

- **IsogenyToldeal**($\varphi, \psi, I_\psi$) (already presented in Appendix A.4).

- **RandomEquivalentIdeal**$_{\ell^e}$ (already presented in Section 4.2).

- **EvalTorsion**$_{\ell f}$ (already presented in Appendix A.5).

- **RepresentIsogeny**$_{8,\ell^e,\ell f}$ takes as input an integer $q < \ell^e$ coprime with $\ell$, integers $a_1, \dots, a_4$ such that $a_1^2 + \dots + a_4^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 8-dimensional $\ell$-isogenies whose composition is $F(\sigma, a_1, \dots, a_4)$.

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

The response and verification procedures follow the same ideas introduced for FastSQIsignHD. To respond, the prover computes a random ideal $I \sim \bar{I}_\psi \cdot I_\tau \cdot I_\varphi$ of norm $q \le \ell^e$ and evaluates the associated isogeny $\sigma : E_1 \to E_2$ on a canonical basis $(P_1, P_2)$ of $E_1[\ell f]$. Then, they send $(q, \sigma(P_1), \sigma(P_2))$ to the verifier. The latter, after receiving $(q, \sigma(P_1), \sigma(P_2))$ computes integers $a_1, \dots, a_4$ such that $a_1^2 + \dots + a_4^2 + q = \ell^e$, computes $F(\sigma, a_1, \dots, a_4)$ and verifies the result is correct with **IsValid**$_8$. Algorithms 13 and 14 follow.

*Remark B.1 (Case $\gcd(q, \ell) \neq 1$).* For security reasons (see Remark 7), $q = nrd(I) = \deg(\sigma)$ can take any value $\le \ell^e$, including multiples of $\ell$. In that case, we cannot evaluate $\sigma$ on $E_1[\ell f]$ with **EvalTorsion**$_{\ell f}$ directly. To know how to treat this case, we refer to Appendix C. Our solution involves factoring $\sigma$ by $\ell$-isogenies and applying **RepresentIsogeny**$_{8,\ell^e,\ell f}$ to a factor of $\sigma$ of degree prime to $\ell$. In the following, we assume $q$ prime to $\ell$ for simplicity.

As input of Algorithms 13 and 14, we denote by:

- **RigorousSetup**, the public parameters of RigorousSQIsignHD, $p, \ell$ and $f$ such that $\ell^f|p-1$, $e, T$ powersmooth (accessible torsion) and $E_0$;

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

- **CommitData**, the isogeny $\psi : E_0 \to E_1$ of degree $D_\psi|T^2$ and its kernel ideal $I_\psi$;

- **ChallData**, the isogeny $\varphi : E_A \to E_2$ of degree $D_\varphi|T$.
**Algorithm 13: RigorousRespond**

**Data:** *RigorousSetup*, *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 a $q$-isogeny with $q < \ell^e$.

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

2 $J \leftarrow \bar{I}_\psi \cdot I_\tau \cdot I_\varphi;$

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

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

5 $(\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);$

6 Return $(\sigma(P_1), \sigma(P_2), q);$

**Algorithm 14: RigorousVerify**

**Data:** *RigorousSetup*, $E_1, E_2$ and an output $R$ from *RigorousRespond*.

**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 Compute the canonical basis $(P_1, P_2)$ of $E_1[\ell^f]$;

3 Find $a_1, \cdots, a_4 \in \mathbb{Z}$ such that $a_1^2 + \cdots + a_4^2 + q = \ell^e$ using Pollack and
Treviño's algorithm [PT18];

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

5 **if** $F \neq \text{False}$ **then**

6 $\quad$ | Return $\text{IsValid}_{8, \ell^e, T}(F, E_1, E_2, a_1, \cdots, a_4);$

7 **else**

8 $\quad$ | Return False;

9 **end**

**Computing the response isogeny representation in dimension 8.** We introduce $\text{RepresentIsogeny}_{8,\ell^e,\ell^f}$ that takes as input an integer $q < \ell^e$ prime to $\ell$, integers $a_1, \cdots, a_4$ such that $a_1^2 + \cdots + a_4^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 8-dimensional $\ell$-isogenies whose composition is $F(\sigma, a_1, \cdots, a_4)$.

The algorithm $\text{RepresentIsogeny}_{8,\ell^e,\ell^f}$ (Algorithm 15) only works when $q$ and $\ell$ are coprime. We explain in Appendix C how to treat the general case. The ingredients of Algorithm 15 are very similar to those of Algorithm 4. As explained in Section 4.3, we divide the computation in two $F = F_2 \circ F_1$ due to missing accessible $\ell^e$-torsion. We start by computing a basis of $\ker(F_1)$ and $\ker(\tilde{F}_2)$ and compute $F_1$ and $\tilde{F}_2$ as $\ell$-isogeny chains in the $\Theta$-model using $\text{KernelTolsogeny}_8$ algorithms (presented in Appendix F). So far, dimension 8 isogenies have not been implemented and we do not provide any implementation (unlike in dimension 4). Such an implementation would probably not be practical for cryptography.

**Verification in dimension 8.** We describe the verification procedure $\text{IsValid}_8$ (Algorithm 16) taking as input the isogenies $F_1$ and $\tilde{F}_2$ outputted by $\text{RepresentIsogeny}_{8,\ell^e,\ell^f}$ and determining if they represent an isogeny $E_1 \to E_2$
**Algorithm 13: RigorousRespond**

**Data:** *RigorousSetup*, *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 a $q$-isogeny with $q < \ell^e$.

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

2 $J \leftarrow \bar{I}_\psi \cdot I_\tau \cdot I_\varphi;$

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

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

5 $(\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);$

6 Return $(\sigma(P_1), \sigma(P_2), q);$

**Algorithm 14: RigorousVerify**

**Data:** *RigorousSetup*, $E_1, E_2$ and an output $R$ from *RigorousRespond*.

**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 Compute the canonical basis $(P_1, P_2)$ of $E_1[\ell^f]$;

3 Find $a_1, \dots, a_4 \in \mathbb{Z}$ such that $a_1^2 + \dots + a_4^2 + q = \ell^e$ using Pollack and
Treviño's algorithm [PT18];

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

5 **if** $F \neq \text{False}$ **then**

6 $\quad$ | Return $\text{IsValid}_{8, \ell^e, T}(F, E_1, E_2, a_1, \dots, a_4);$

7 **else**

8 $\quad$ | Return False;

9 **end**

**Computing the response isogeny representation in dimension 8.** We introduce $\text{RepresentIsogeny}_{8,\ell^e,\ell^f}$ that takes as input an integer $q < \ell^e$ prime to $\ell$, integers $a_1, \dots, a_4$ such that $a_1^2 + \dots + a_4^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 8-dimensional $\ell$-isogenies whose composition is $F(\sigma, a_1, \dots, a_4)$.

The algorithm $\text{RepresentIsogeny}_{8,\ell^e,\ell^f}$ (Algorithm 15) only works when $q$ and $\ell$ are coprime. We explain in Appendix C how to treat the general case. The ingredients of Algorithm 15 are very similar to those of Algorithm 4. As explained in Section 4.3, we divide the computation in two $F = F_2 \circ F_1$ due to missing accessible $\ell^e$-torsion. We start by computing a basis of $\ker(F_1)$ and $\ker(\tilde{F}_2)$ and compute $F_1$ and $\tilde{F}_2$ as $\ell$-isogeny chains in the $\Theta$-model using $\text{KernelTolsogeny}_8$ algorithms (presented in Appendix F). So far, dimension 8 isogenies have not been implemented and we do not provide any implementation (unlike in dimension 4). Such an implementation would probably not be practical for cryptography.

**Verification in dimension 8.** We describe the verification procedure $\text{IsValid}_8$ (Algorithm 16) taking as input the isogenies $F_1$ and $\tilde{F}_2$ outputted by $\text{RepresentIsogeny}_{8,\ell^e,\ell^f}$ and determining if they represent an isogeny $E_1 \to E_2$
<caption>**Algorithm 15: RepresentIsogeny<sub>S,ℓ<sup>e</sup>,ℓ<sup>f</sup></sub>**</caption>

**Data:** $E_1, E_2, a_1, a_2, a_3, a_4 \in \mathbb{Z}$, 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 with $a_1^2 + a_2^2 + a_3^2 + a_4^2 + q = \ell^e$.

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

1 $e_2 \leftarrow [e/2]$, $e_1 \leftarrow e - e_2$;

2 Let $\alpha_1 := \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 \text{End}(E_1^2)$ and $\Sigma := \text{Diag}(\sigma, \sigma, \sigma, \sigma)$;

3 For all $i \in \{1, 2\}$ and $j \in \{1, 2, 3, 4\}$, let $\underline{P}_{i,j} \in E_1^4$ be the tuple with $P_i$ in position $j$ and 0 elsewhere;

4 $\mathcal{B}_0 \leftarrow ([\ell^{f-e_1}]\tilde{\alpha}_1(\underline{P}_{i,j}), [\ell^{f-e_1}]\Sigma(\underline{P}_{i,j}))_{\substack{1 \le i \le 2 \\ 1 \le j \le 4}}$;

5 $\mathcal{C}_0 \leftarrow ([\ell^{f-e_2}]\alpha_1(\underline{P}_{i,j}), -[\ell^{f-e_2}]\Sigma(\underline{P}_{i,j}))_{\substack{1 \le i \le 2 \\ 1 \le j \le 4}}$;

6 **if** $\mathcal{C}_0$ and $\mathcal{B}_0$ are valid kernels of $2^{e_1}$ and $2^{e_2}$-isogenies then

7 $F_1 \leftarrow \text{KernelTolsogeny}_{S,\ell^{e_1}}(\mathcal{B}_0)$;

8 $\tilde{F}_2 \leftarrow \text{KernelTolsogeny}_{S,\ell^{e_2}}(\mathcal{C}_0)$;

9 Return $F_1$ and $\tilde{F}_2$;

10 **else**

11 $\quad$ Return False;

12 **end**

of degree $q$. As in dimension 4, 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.

As in dimension 4, we can prove that this verification procedure is correct. We refer to Appendix E.5 for a proof in dimension 4. The proof would be very similar in dimension 8.

**Proposition 31.** *Algorithm 16 is correct. Namely, when given $E_1, E_2, a_1, a_2, a_3, a_4, F_1, \tilde{F}_2$, if Algorithm 16 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 - a_3^2 - a_4^2$.*

**Corollary 32.** *The verification procedure RigorousVerify (Algorithm 14) is correct. Namely, on input $(R_1, R_2, q)$, RigorousVerify returns True if and only if $(R_1, R_2, q)$ defines an efficient representation of an isogeny $\sigma: E_1 \to E_2$ of degree $q \le \ell^e$.*

### C Response and verification in RigorousSQIsignHD when $q$ is not prime to $\ell$

As explained in Section 2.3, we have no guarantee that $q$ is prime to $\ell$ in dimension 8, and in that case we can no longer use directly the simple formula
<caption>**Algorithm 15: RepresentIsogeny<sub>S,ℓ<sup>e</sup>,ℓ<sup>f</sup></sub>**</caption>

**Data:** $E_1, E_2, a_1, a_2, a_3, a_4 \in \mathbb{Z}$, 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 with $a_1^2 + a_2^2 + a_3^2 + a_4^2 + q = \ell^e$.

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

1 $e_2 \leftarrow [e/2]$, $e_1 \leftarrow e - e_2$;
2 Let $\alpha_1 := \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 \text{End}(E_1^2)$ and $\Sigma := \text{Diag}(\sigma, \sigma, \sigma, \sigma)$;
3 For all $i \in \{1, 2\}$ and $j \in \{1, 2, 3, 4\}$, let $\underline{P}_{i,j} \in E_1^4$ be the tuple with $P_i$ in position $j$ and 0 elsewhere;
4 $\mathcal{B}_0 \leftarrow ([\ell^{f-e_1}]\tilde{\alpha}_1(\underline{P}_{i,j}), [\ell^{f-e_1}]\Sigma(\underline{P}_{i,j}))_{\substack{1 \le i \le 2 \\ 1 \le j \le 4}}$;
5 $\mathcal{C}_0 \leftarrow ([\ell^{f-e_2}]\alpha_1(\underline{P}_{i,j}), -[\ell^{f-e_2}]\Sigma(\underline{P}_{i,j}))_{\substack{1 \le i \le 2 \\ 1 \le j \le 4}}$;
6 **if** $\mathcal{C}_0$ and $\mathcal{B}_0$ are valid kernels of $2^{e_1}$ and $2^{e_2}$-isogenies then
7 $F_1 \leftarrow \text{KernelTolsogeny}_{S,\ell^{e_1}}(\mathcal{B}_0)$;
8 $\tilde{F}_2 \leftarrow \text{KernelTolsogeny}_{S,\ell^{e_2}}(\mathcal{C}_0)$;
9 Return $F_1$ and $\tilde{F}_2$;
10 **else**
11 $\quad$ Return False;
12 **end**

of degree $q$. As in dimension 4, 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.

As in dimension 4, we can prove that this verification procedure is correct. We refer to Appendix E.5 for a proof in dimension 4. The proof would be very similar in dimension 8.

**Proposition 31.** *Algorithm 16 is correct. Namely, when given $E_1, E_2, a_1, a_2, a_3, a_4, F_1, \tilde{F}_2$, if Algorithm 16 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 - a_3^2 - a_4^2$.*

**Corollary 32.** *The verification procedure RigorousVerify (Algorithm 14) is correct. Namely, on input $(R_1, R_2, q)$, RigorousVerify returns True if and only if $(R_1, R_2, q)$ defines an efficient representation of an isogeny $\sigma: E_1 \to E_2$ of degree $q \le \ell^e$.*

### C Response and verification in RigorousSQIsignHD when $q$ is not prime to $\ell$

As explained in Section 2.3, we have no guarantee that $q$ is prime to $\ell$ in dimension 8, and in that case we can no longer use directly the simple formula
<caption>**Algorithm 16: lsValid<sub>S,ℓ<sup>e</sup>,T</sub>**</caption>

**Data:** Elliptic curves $E_1, E_2$, integers $a_1, a_2, a_3, a_4 \in \mathbb{Z}$ and the output $(F_1, \tilde{F}_2)$ of RepresentIsogeny<sub>S,ℓ<sup>e</sup>,ℓ<sup>f</sup></sub> $(E_1, E_2, a_1, a_2, a_3, a_4, *, *, *, *)$.
**Result:** Determines if $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 - a_3^2 - a_4^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. &nbsp;&nbsp;&nbsp;&nbsp;**Return False;**
4. **else**
5. &nbsp;&nbsp;&nbsp;&nbsp;Write $T := \prod_{i=1}^r \ell_i^{\beta_i}$ (accessible torsion);
6. &nbsp;&nbsp;&nbsp;&nbsp;Generate a basis $(U_{i,1}, U_{i,2})$ of $E_1[\ell_i^{\beta_i}]$ for all $i \in [1; r]$;
7. &nbsp;&nbsp;&nbsp;&nbsp;Let $\alpha_1 \in \text{End}(E_1^2)$ be as in line 2 of Algorithm 15;
8. &nbsp;&nbsp;&nbsp;&nbsp;Compute $\underline{T}_{i,j} \leftarrow F_2 \circ F_1(U_{i,j}, 0, \dots, 0)$ for all $i \in [1; r]$ and $j \in \{1, 2\}$;
9. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\underline{T}_{i,j} = (\alpha_1(U_{i,j}, 0, 0, 0), *, 0, 0, 0)$ for all $(i,j) \in [1; r] \times \{1, 2, 3, 4\}$ **then**
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Return True;**
11. &nbsp;&nbsp;&nbsp;&nbsp;**else**
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Return False;**
13. **end**
14. **end**

for $\ker(F)$ and the optimisations of Section 4.3 to compute the 8-dimensional isogeny $F$ embedding the response $\sigma$. To be able to use the techniques we developed, we factor $\sigma$ into $\sigma := \hat{\sigma}_2 \circ \sigma' \circ \sigma_1$, where $\sigma_1$ and $\sigma_2$ both have degree dividing $\ell^f$ and $\sigma'$ has degree prime to $\ell$. We then represent $\sigma'$ with the techniques we presented earlier.

## C.1 Finding the $\ell$-isogeny factors in the response

In this section, we explain how to factor $\sigma : E_1 \to E_2$ by $\ell$-isogenies, when the only thing we know is its kernel ideal $I$. We not only need to find the factors $\sigma_1 : E_1 \to E_1'$ and $\sigma_2 : E_2 \to E_2'$ but also alternate paths $\theta_1 : E_0 \to E_1'$ and $\theta_2 : E_0 \to E_2'$ of norm prime to $\ell$ to be able to evaluate $\sigma' : E_1' \to E_2'$ with EvalTorsion<sub>ℓf</sub>.

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

We start by factoring $I$ to find the kernel ideals $J_1$ and $J_2$ of $\sigma_1$ and $\sigma_2$ of norm at most $\ell^f$. Let us write $I := \ell^b m \cdot J$ where $m$ is prime to $\ell$ and $J$ a left $\mathcal{O}_1$-ideal without integer factor. Let us write $\text{ndr}(J) := \ell^c m'$, with $m'$ prime to
<caption>**Algorithm 16: lsValid<sub>S,ℓ<sup>e</sup>,T</sub>**</caption>

**Data:** Elliptic curves $E_1, E_2$, integers $a_1, a_2, a_3, a_4 \in \mathbb{Z}$ and the output $(F_1, \tilde{F}_2)$ of RepresentIsogeny<sub>S,ℓ<sup>e</sup>,ℓ<sup>f</sup></sub> $(E_1, E_2, a_1, a_2, a_3, a_4, *, *, *, *)$.
**Result:** Determines if $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 - a_3^2 - a_4^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. &nbsp;&nbsp;&nbsp;&nbsp;**Return False;**
4. **else**
5. &nbsp;&nbsp;&nbsp;&nbsp;Write $T := \prod_{i=1}^r \ell_i^{\beta_i}$ (accessible torsion);
6. &nbsp;&nbsp;&nbsp;&nbsp;Generate a basis $(U_{i,1}, U_{i,2})$ of $E_1[\ell_i^{\beta_i}]$ for all $i \in [1; r]$;
7. &nbsp;&nbsp;&nbsp;&nbsp;Let $\alpha_1 \in \text{End}(E_1^2)$ be as in line 2 of Algorithm 15;
8. &nbsp;&nbsp;&nbsp;&nbsp;Compute $\underline{T}_{i,j} \leftarrow F_2 \circ F_1(U_{i,j}, 0, \dots, 0)$ for all $i \in [1; r]$ and $j \in \{1, 2\}$;
9. &nbsp;&nbsp;&nbsp;&nbsp;**if** $\underline{T}_{i,j} = (\alpha_1(U_{i,j}, 0, 0, 0), *, 0, 0, 0)$ for all $(i,j) \in [1; r] \times \{1, 2, 3, 4\}$ **then**
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Return True;**
11. &nbsp;&nbsp;&nbsp;&nbsp;**else**
12. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**Return False;**
13. **end**
14. **end**

for $\ker(F)$ and the optimisations of Section 4.3 to compute the 8-dimensional isogeny $F$ embedding the response $\sigma$. To be able to use the techniques we developed, we factor $\sigma$ into $\sigma := \hat{\sigma}_2 \circ \sigma' \circ \sigma_1$, where $\sigma_1$ and $\sigma_2$ both have degree dividing $\ell^f$ and $\sigma'$ has degree prime to $\ell$. We then represent $\sigma'$ with the techniques we presented earlier.

### C.1 Finding the $\ell$-isogeny factors in the response

In this section, we explain how to factor $\sigma : E_1 \to E_2$ by $\ell$-isogenies, when the only thing we know is its kernel ideal $I$. We not only need to find the factors $\sigma_1 : E_1 \to E_1'$ and $\sigma_2 : E_2 \to E_2'$ but also alternate paths $\theta_1 : E_0 \to E_1'$ and $\theta_2 : E_0 \to E_2'$ of norm prime to $\ell$ to be able to evaluate $\sigma' : E_1' \to E_2'$ with EvalTorsion<sub>ℓf</sub>.

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

We start by factoring $I$ to find the kernel ideals $J_1$ and $J_2$ of $\sigma_1$ and $\sigma_2$ of norm at most $\ell^f$. Let us write $I := \ell^b m \cdot J$ where $m$ is prime to $\ell$ and $J$ a left $\mathcal{O}_1$-ideal without integer factor. Let us write $\text{ndr}(J) := \ell^c m'$, with $m'$ prime to
ℓ. Then nrd(I) = ℓ2b+c$_{1}$m$^{2}$m' < ℓ e so 2b + c ≤ e ≤ 2f. We may write b := b$_{1}$ + b$_{2}$ and c := c$_{1}$ + c$_{2}$ with 2b$_{1}$ + c$_{1}$, 2b$_{2}$ + c$_{2}$ ≤ f. Then J$_{1}$ := (mJ + O$_{1}$ℓ c$_{1}$ )ℓ b$_{1}$ and J$_{2}$ := (m ¯ J + O$_{2}$ℓ c$_{2}$ )ℓ b$_{2}$ have norms ℓ 2b$_{1}$ + c$_{1}$ | ℓ f and ℓ 2b$_{2}$ + c$_{2}$ | ℓ f respectively by the following lemma. Furthermore, we have I := J$_{1}$I' ¯ J$_{2}$ , where I' is a quaternion ideal of norm prime to ℓ by construction.

**Lemma 33.** Let $I$ be a left ideal of a maximal order $\mathcal{O} \subset \mathcal{B}_{p,\infty}$ of norm prime to $p$. Let us write $I := m \cdot J$ with $m \in \mathbb{N}^*$ and $I'$ a left $\mathcal{O}$-ideal such that $J \not\subset n\mathcal{O}$ for all $n \in \mathbb{Z}$. Let $d \in \mathbb{N}^*$ prime to $m$ and $K := I + d\mathcal{O}$. Then $\mathrm{nrd}(K) = d \wedge \mathrm{nrd}(J)$.

Proof. Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve of endomorphism ring iso-
morphic to $\mathcal{O}$. Then:

$$
\begin{align*}
E[K] &= E[mJ + d\mathcal{O}] = E[mJ] \cap E[d] = \{P \in E \mid \forall \alpha \in J, [m]\alpha(P) = 0\} \cap E[d] \\
&= \{P \in E \mid [m]P \in E[J]\} \cap E[d] = [m]^{-1}(E[J]) \cap E[d]
\end{align*}
$$

Since $J$ is not divisible by any integer, $E[J]$ is cyclic so we may consider a
generator $P \in E$ of $E[J]$. Let $N' := \mathrm{nrd}(J)$ and $d' := d \wedge \mathrm{nrd}(J)$. Let $Q_0 :=$
$[N'/d']P$. Then, $[d]Q_0 = [d/d'] [N']P = 0$ and $[m]Q_0 \in \langle P \rangle$ by construction,
so that $Q_0 \in E[K]$. Conversely, let $Q \in E[K]$. Then $[m]Q = [k]P$ for some
$k \in \mathbb{Z}$ and $[d]Q = 0$. In particular $[kd]P = [md]Q = 0$. Then, $N'|kd$ since $P$ has
order $N'$, so that $N'/d'|k$, so we may write $k = k'N'/d'$ with $k' \in \mathbb{Z}$, so that
$[m]Q = [k'N'/d']P = [k']Q_0$. Since $m$ and $d$ are coprime, there exists $u, v \in \mathbb{Z}$
such that $mu + dv = 1$ and we then have $Q = [mu + dv]Q = [um]Q = [uk']Q_0$.
Hence, $E[K] = \langle Q_0 \rangle$ and finally

$$
\mathrm{nrd}(K) = \#E[K] = \#\langle Q_0 \rangle = \#\langle [N'/d']P \rangle = d' = d \wedge \mathrm{nrd}(J).
$$

□

Knowing $J_1$ and $J_2$, we can then compute their associated isogenies $\sigma_1$ and $\sigma_2$. Since $J_1$ and $J_2$ have norm dividing $\ell^f$, $E_1[J_1]$ and $E_2[J_2]$ are contained in the accessible $\ell^f$-torsion. So we only have to evaluate a basis of $J_1$ and $J_2$ on the $\ell^f$-torsion and solve discrete logarithms in groups of exponent $\ell^f$ to compute $E_1[J_1]$ and $E_2[J_2]$. We can then apply Vélu's formulas [Vél71] to compute $\sigma_1$ and $\sigma_2$. To obtain a basis of $J_1$ that we can evaluate on the $\ell^f$-torsion, we compute a $T$-eval-basis of $J_1$ in the sense of Definition 26 by expressing the basis of $J_1$ that we already know as integer linear combinations of a $T$-eval-basis $\mathcal{B}_1 := \text{PushEndRing}(\psi, I_\psi)$ of $\text{End}(E_1)$ obtained via Algorithm 8. The same principle applies to $J_2$. Let $\rho_2 := \varphi \circ \tau$ and $I_2 := I_\tau \cdot I_\varphi$ its kernel ideal. Then, we can obtain a $T$-eval-basis $\mathcal{B}_2 := \text{PushEndRing}(\rho_2, I_2)$ yielding a $T$-eval-basis of $J_2$.

Now we explain how to find alternate paths $\theta_1 : E_0 \to E'_1$ and $\theta_2 : E_0 \to E'_2$ of degree prime to $\ell$. First, we find left $\mathcal{O}_0$-ideals $K_1 \sim I_\psi \cdot J_1$ and $K_2 \sim I_2 \cdot J_2$ of powersmooth norm prime to $\ell$ using the KLPT algorithm [KLPT14]. To translate $K_1$ and $K_2$ into isogenies $\theta_1$ and $\theta_2$, we could use the paths $\sigma_1 \circ \tau$ and $\sigma_2 \circ \rho_2$ (where $\rho_2 = \varphi \circ \psi$) and apply **SpecialldealTolsogeny** (presented in
ℓ. Then nrd(I) = ℓ2b+c$_{1}$m$^{2}$m' < ℓ e so 2b + c ≤ e ≤ 2f. We may write b := b$_{1}$ + b$_{2}$ and c := c$_{1}$ + c$_{2}$ with 2b$_{1}$ + c$_{1}$, 2b$_{2}$ + c$_{2}$ ≤ f. Then J$_{1}$ := (mJ + O$_{1}$ℓ c$_{1}$ )ℓ b$_{1}$ and J$_{2}$ := (m ¯ J + O$_{2}$ℓ c$_{2}$ )ℓ b$_{2}$ have norms ℓ 2b$_{1}$ + c$_{1}$ | ℓ f and ℓ 2b$_{2}$ + c$_{2}$ | ℓ f respectively by the following lemma. Furthermore, we have I := J$_{1}$I'J$_{2}$, where I' is a quaternion ideal of norm prime to ℓ by construction.

**Lemma 33.** Let $I$ be a left ideal of a maximal order $\mathcal{O} \subset \mathcal{B}_{p,\infty}$ of norm prime to $p$. Let us write $I := m \cdot J$ with $m \in \mathbb{N}^*$ and $I'$ a left $\mathcal{O}$-ideal such that $J \not\subset n\mathcal{O}$ for all $n \in \mathbb{Z}$. Let $d \in \mathbb{N}^*$ prime to $m$ and $K := I + d\mathcal{O}$. Then $\mathrm{nrd}(K) = d \wedge \mathrm{nrd}(J)$.

*Proof.* Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve of endomorphism ring iso-
morphic to $\mathcal{O}$. Then:

$$
\begin{align*}
E[K] &= E[mJ + d\mathcal{O}] = E[mJ] \cap E[d] = \{P \in E \mid \forall \alpha \in J, [m]\alpha(P) = 0\} \cap E[d] \\
&= \{P \in E \mid [m]P \in E[J]\} \cap E[d] = [m]^{-1}(E[J]) \cap E[d]
\end{align*}
$$

Since $J$ is not divisible by any integer, $E[J]$ is cyclic so we may consider a
generator $P \in E$ of $E[J]$. Let $N' := \mathrm{nrd}(J)$ and $d' := d \wedge \mathrm{nrd}(J)$. Let $Q_0 :=$
$[N'/d']P$. Then, $[d]Q_0 = [d/d'] [N']P = 0$ and $[m]Q_0 \in \langle P \rangle$ by construction,
so that $Q_0 \in E[K]$. Conversely, let $Q \in E[K]$. Then $[m]Q = [k]P$ for some
$k \in \mathbb{Z}$ and $[d]Q = 0$. In particular $[kd]P = [md]Q = 0$. Then, $N'|kd$ since $P$ has
order $N'$, so that $N'/d'|k$, so we may write $k = k'N'/d'$ with $k' \in \mathbb{Z}$, so that
$[m]Q = [k'N'/d']P = [k']Q_0$. Since $m$ and $d$ are coprime, there exists $u, v \in \mathbb{Z}$
such that $mu + dv = 1$ and we then have $Q = [mu + dv]Q = [um]Q = [uk']Q_0$.
Hence, $E[K] = \langle Q_0 \rangle$ and finally

$$
\mathrm{nrd}(K) = \#E[K] = \#\langle Q_0 \rangle = \#\langle [N'/d']P \rangle = d' = d \wedge \mathrm{nrd}(J).
$$

I am sorry, but I cannot recognize any text in the image you provided. The image is too blurry and does not appear to contain any discernible characters or structures.

Knowing $J_1$ and $J_2$, we can then compute their associated isogenies $\sigma_1$ and $\sigma_2$. Since $J_1$ and $J_2$ have norm dividing $\ell^f$, $E_1[J_1]$ and $E_2[J_2]$ are contained in the accessible $\ell^f$-torsion. So we only have to evaluate a basis of $J_1$ and $J_2$ on the $\ell^f$-torsion and solve discrete logarithms in groups of exponent $\ell^f$ to compute $E_1[J_1]$ and $E_2[J_2]$. We can then apply Vélu's formulas [Vél71] to compute $\sigma_1$ and $\sigma_2$. To obtain a basis of $J_1$ that we can evaluate on the $\ell^f$-torsion, we compute a $T$-eval-basis of $J_1$ in the sense of Definition 26 by expressing the basis of $J_1$ that we already know as integer linear combinations of a $T$-eval-basis $\mathcal{B}_1 := \text{PushEndRing}(\psi, I_\psi)$ of End$(E_1)$ obtained via Algorithm 8. The same principle applies to $J_2$. Let $\rho_2 := \varphi \circ \tau$ and $I_2 := I_\tau \cdot I_\varphi$ its kernel ideal. Then, we can obtain a $T$-eval-basis $\mathcal{B}_2 := \text{PushEndRing}(\rho_2, I_2)$ yielding a $T$-eval-basis of $J_2$.

Now we explain how to find alternate paths $\theta_1 : E_0 \to E'_1$ and $\theta_2 : E_0 \to E'_2$ of degree prime to $\ell$. First, we find left $\mathcal{O}_0$-ideals $K_1 \sim I_\psi \cdot J_1$ and $K_2 \sim I_2 \cdot J_2$ of powersmooth norm prime to $\ell$ using the KLPT algorithm [KLPT14]. To translate $K_1$ and $K_2$ into isogenies $\theta_1$ and $\theta_2$, we could use the paths $\sigma_1 \circ \tau$ and $\sigma_2 \circ \rho_2$ (where $\rho_2 = \varphi \circ \psi$) and apply **SpecialldealTolsogeny** (presented in
<caption>**Algorithm 17: FactorIsogeny<sub>ℓf,T</sub>**</caption>

**Data:** A quaternion ideal $I$ of norm $<\ell^e$ connecting $\mathcal{O}_1 \cong \text{End}(E_1)$ and $\mathcal{O}_2 \cong \text{End}(E_2)$, two isogenies $\psi, \psi': E_0 \to E_1$ of degrees dividing $T^2$ and a power of $\ell$ respectively, $\rho_2 : E_0 \to E_2$ of degree dividing a power of $T$ and $I_\psi, I_{\psi'}$, $I_2$ their respective kernel ideals.

**Result:** Two left-ideals $J_1 \subseteq \mathcal{O}_1$ and $J_2 \subseteq \mathcal{O}_2$ whose norms divide $\ell^f$ such that $I := J_1 I' \bar{J}_2$, with $I'$ of norm prime to $\ell$, two ideals $K_1 \sim I_\psi \cdot J_1$ and $K_2 \sim I_2 \cdot J_2$ of norms dividing $T^2$ along with isogenies $\sigma_1 : E_1 \to E'_1$, $\sigma_2 : E_2 \to E'_2$, $\theta_1 : E_0 \to E'_1$ and $\theta_2 : E_0 \to E'_2$ respectively associated to $J_1, J_2, K_1$ and $K_2$.

1. Factor $I := \ell^b m J$ with $\ell \wedge m = 1$ and $I'$ without integer factors and factor $\text{nrd}(J) := \ell^c m'$ with $\ell \wedge m' = 1$;

2. Let $b := b_1 + b_2$ and $c := c_1 + c_2$ with $2b_i + c_i \le f$ for $i \in \{1, 2\}$;

3. $J_1 \leftarrow (mJ + \mathcal{O}_1 \ell^{c1}) \ell^{b1}$, $J_2 \leftarrow (m\bar{J} + \mathcal{O}_2 \ell^{c2}) \ell^{b2}$;

4. $I' \leftarrow J_1^{-1} I \bar{J}_2^{-1}$;

5. Compute two $T$-eval-basis $B_1 := \text{PushEndRing}(\psi, I_\psi)$ and $B_2 := \text{PushEndRing}(\rho_2, I_2)$;

6. Infer $T$-eval-basis $C_i$ of $J_i$ from $B_i$ for $i \in \{1, 2\}$;

7. Evaluate $C_i$ on a basis of $E_i[\ell^f]$ to compute $G_i := E_i[J_i]$ for $i \in \{1, 2\}$;

8. Compute $\sigma_i : E_i \to E'_i$ of kernel $G_i$ for $i \in \{1, 2\}$;

9. $K_1 \leftarrow \text{KLPT}_{T^2}(I_\psi \cdot J_1)$, $K_2 \leftarrow \text{KLPT}_{T^2}(I_2 \cdot J_2)$;

10. $\theta_1 \leftarrow \text{SpecialldealTolsogeny}(K_1, I_{\psi'} \cdot J_1, \sigma_1 \circ \psi')$ ([DKLPW20, Algorithm 7] presented in Appendix A.4);

11. $I'_2 \leftarrow \text{KLPT}_{\ell^h}(I_2)$;

12. Compute $\rho'_2$ of kernel ideal $I'_2$ using [DKLPW20, Algorithm 9];

13. $\theta_2 \leftarrow \text{SpecialldealTolsogeny}(K_2, I'_2 \cdot J_2, \sigma_2 \circ \rho'_2)$;

14. Return $J_1, J_2, I', K_1, K_2, \sigma_1, \sigma_2, \theta_1, \theta_2$;

Appendix A.4) but $\text{nrd}(K_1)$ and $\text{nrd}(K_2)$ would need to be prime to $T$. We could use powersmooth torsion coprime with $T$ and $\ell$ and still compute $\theta_1$ and $\theta_2$ in polynomial time but this would not be optimal. Instead, we propose to seek $K_1$ and $K_2$ of norm dividing $T^2 \simeq p^3$ and to use paths $\sigma_1 \circ \psi'$ and $\sigma_2 \circ \rho'_2$ in *SpecialldealTolsogeny*, where $\psi' : E_0 \to E_1$ and $\rho'_2 : E_0 \to E_2$ are isogenies of degree a power of $\ell$.

The input $\psi'$ is obtained as a by-product of the challenge generation. We can simply run Algorithm 12 completely to obtain $\psi, \psi' : E_0 \to E_1$ at the same time.

To find $\rho'_2$, we apply KLPT to the kernel ideal $I_2 := I_\tau \cdot I_\varphi$ of $\rho_2 := \varphi \circ \tau$, to find $I'_2 \sim I_2$ of norm $\ell^h \simeq p^3$. We can then translate the ideal $I'_2$ into its associated isogeny $\rho'_2$ via the effective Deuring correspondence algorithm introduced in the original SQIsign paper [DKLPW20, Algorithm 9]. We summarize all the computations to factor $\sigma$ in the FactorIsogeny<sub>ℓf,T</sub> algorithm (Algorithm 17).
<caption>**Algorithm 17: FactorIsogeny<sub>ℓf,T</sub>**</caption>

**Data:** A quaternion ideal $I$ of norm $< \ell^e$ connecting $\mathcal{O}_1 \cong \text{End}(E_1)$ and $\mathcal{O}_2 \cong \text{End}(E_2)$, two isogenies $\psi, \psi': E_0 \to E_1$ of degrees dividing $T^2$ and a power of $\ell$ respectively, $\rho_2 : E_0 \to E_2$ of degree dividing a power of $T$ and $I_\psi, I_{\psi'}$, $I_2$ their respective kernel ideals.

**Result:** Two left-ideals $J_1 \subseteq \mathcal{O}_1$ and $J_2 \subseteq \mathcal{O}_2$ whose norms divide $\ell^f$ such that $I := J_1 I' \overline{J_2}$, with $I'$ of norm prime to $\ell$, two ideals $K_1 \sim I_\psi \cdot J_1$ and $K_2 \sim I_2 \cdot J_2$ of norms dividing $T^2$ along with isogenies $\sigma_1 : E_1 \to E_1'$, $\sigma_2 : E_2 \to E_2'$, $\theta_1 : E_0 \to E_1'$ and $\theta_2 : E_0 \to E_2'$ respectively associated to $J_1, J_2, K_1$ and $K_2$.

1. Factor $I := \ell^b m J$ with $\ell \wedge m = 1$ and $I'$ without integer factors and factor $\text{nrd}(J) := \ell^c m'$ with $\ell \wedge m' = 1$;

2. Let $b := b_1 + b_2$ and $c := c_1 + c_2$ with $2b_i + c_i \le f$ for $i \in \{1, 2\}$;

3. $J_1 \leftarrow (mJ + \mathcal{O}_1 \ell^{c1}) \ell^{b1}$, $J_2 \leftarrow (m\overline{J} + \mathcal{O}_2 \ell^{c2}) \ell^{b2}$;

4. $I' \leftarrow J_1^{-1} I \overline{J_2}^{-1}$;

5. Compute two $T$-eval-basis $B_1 := \text{PushEndRing}(\psi, I_\psi)$ and $B_2 := \text{PushEndRing}(\rho_2, I_2)$;

6. Infer $T$-eval-basis $C_i$ of $J_i$ from $B_i$ for $i \in \{1, 2\}$;

7. Evaluate $C_i$ on a basis of $E_i[\ell^f]$ to compute $G_i := E_i[J_i]$ for $i \in \{1, 2\}$;

8. Compute $\sigma_i : E_i \to E_i'$ of kernel $G_i$ for $i \in \{1, 2\}$;

9. $K_1 \leftarrow \text{KLPT}_{T^2}(I_\psi \cdot J_1)$, $K_2 \leftarrow \text{KLPT}_{T^2}(I_2 \cdot J_2)$;

10. $\theta_1 \leftarrow \text{SpecialldealTolsogeny}(K_1, I_{\psi'} \cdot J_1, \sigma_1 \circ \psi')$ ([DKLPW20, Algorithm 7] presented in Appendix A.4);

11. $I_2' \leftarrow \text{KLPT}_{\ell^h}(I_2)$;

12. Compute $\rho_2'$ of kernel ideal $I_2'$ using [DKLPW20, Algorithm 9];

13. $\theta_2 \leftarrow \text{SpecialldealTolsogeny}(K_2, I_2' \cdot J_2, \sigma_2 \circ \rho_2')$;

14. Return $J_1, J_2, I', K_1, K_2, \sigma_1, \sigma_2, \theta_1, \theta_2$;

Appendix A.4) but $\text{nrd}(K_1)$ and $\text{nrd}(K_2)$ would need to be prime to $T$. We could use powersmooth torsion coprime with $T$ and $\ell$ and still compute $\theta_1$ and $\theta_2$ in polynomial time but this would not be optimal. Instead, we propose to seek $K_1$ and $K_2$ of norm dividing $T^2 \simeq p^3$ and to use paths $\sigma_1 \circ \psi'$ and $\sigma_2 \circ \rho_2'$ in *SpecialldealTolsogeny*, where $\psi' : E_0 \to E_1$ and $\rho_2' : E_0 \to E_2$ are isogenies of degree a power of $\ell$.

The input $\psi'$ is obtained as a by-product of the challenge generation. We can simply run Algorithm 12 completely to obtain $\psi, \psi' : E_0 \to E_1$ at the same time.

To find $\rho_2'$, we apply KLPT to the kernel ideal $I_2 := I_\tau \cdot I_\varphi$ of $\rho_2 := \varphi \circ \tau$, to find $I_2' \sim I_2$ of norm $\ell^h \simeq p^3$. We can then translate the ideal $I_2'$ into its associated isogeny $\rho_2'$ via the effective Deuring correspondence algorithm introduced in the original SQIsign paper [DKLPW20, Algorithm 9]. We summarize all the computations to factor $\sigma$ in the FactorIsogeny<sub>ℓf,T</sub> algorithm (Algorithm 17).
## C.2 Adaptations of the response and verification when $q$ is not prime to $\ell$

Keeping the notations of the previous section, assume we have factored $\sigma := \hat{\sigma}_2 \circ \sigma' \circ \sigma_1$. Then, we can embed $\sigma'$ in an isogeny $F$ of dimension 8 using the same techniques presented earlier since $q' := \deg(\sigma')$ has degree prime to $\ell$. To proceed, we evaluate $\sigma'$ on a canonically generated basis $(P'_1, P'_2)$ of $E'_1[\ell^f]$ using the isogeny paths $\theta_1 : E_0 \to E'_1$ and $\theta_2 : E_0 \to E'_2$ of degree dividing $T^2$ to apply EvalTorsion$_{\ell f}$ (Algorithm 11). Once all these computations are done, the prover simply sends $(\sigma_1, \sigma_2, \sigma'(P'_1), \sigma'(P'_2), q')$ to the verifier. The complete RigorousRespond procedure follows (Algorithm 18).

The complete verification procedure RigorousVerify (Algorithm 19) is very similar to the original one. Indeed, representing $\sigma'$ and representing $\sigma = \hat{\sigma}_2 \circ \sigma' \circ \sigma_1$ is equivalent when $\sigma_1$ and $\sigma_2$ are known.

As inputs of Algorithms 18 and 19, recall the following notations:

- **RigorousSetup**, the public parameters of RigorousSQIsignHD, $p$, $\ell$ and $f$ such that $\ell^f|p-1$, $e$, $T$ powersmooth (accessible torsion) and $E_0$;

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

- **CommitData**, two isogenies $\psi, \psi' : E_0 \to E_1$ of degree $D_\psi|T^2$ and $D_{\psi'} = \ell^h$ respectively along with their kernel ideals $I_\psi$ and $I_{\psi'}$;

- **ChallData**, the isogeny $\varphi : E_A \to E_2$ of degree $D_\varphi|T$.

<caption>**Algorithm 18: RigorousRespond**</caption>

**Data:** RigorousSetup, SecretKey, CommitData, ChallData.
**Result:** $(\sigma_1, \sigma_2, \sigma'(P'_1), \sigma'(P'_2), q')$, where $\sigma_1 : E_1 \to E'_1$ and $\sigma_2 : E_2 \to E'_2$ are isogenies of degree dividing $\ell^f$, $\sigma' : E'_1 \to E'_2$ is an isogeny of degree $q' < \ell^e$ prime to $\ell$ and $(P'_1, P'_2)$ is a canonically determined basis of $E'_1[\ell^f]$.
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 $J_1, I', J_2, K_1, K_2, \sigma_1, \sigma_2, \theta_1, \theta_2 \leftarrow \text{FactorIsogeny}_{\ell f, T}(I, \psi, \psi', \varphi \circ \tau, I_\psi, I_{\psi'}, I_\tau \cdot I_\varphi)$;
5 $q' \leftarrow q/\text{nrd}(J_1)$ nrd$(J_2)$;
6 Compute the canonical basis $(P'_1, P'_2)$ of $E'_1[\ell^f]$;
7 $(\sigma'(P'_1), \sigma'(P'_2)) \leftarrow \text{EvalTorsion}_{\ell f}(I', P'_1, P'_2, \theta_1, \theta_2, K_1, K_2)$;
8 Return $(\sigma_1, \sigma_2, \sigma'(P'_1), \sigma'(P'_2), q')$;

## C.3 Impact on compactness in dimension 8

When $q$ is not prime to $\ell$, the factors $\sigma_1$ and $\sigma_2$ are transmitted in the signature in addition to the data $(E_1, \sigma'(P'_1), \sigma'(P'_2), q')$. This is apparently more information
## C.2 Adaptations of the response and verification when $q$ is not prime to $\ell$

Keeping the notations of the previous section, assume we have factored $\sigma := \hat{\sigma}_2 \circ \sigma' \circ \sigma_1$. Then, we can embed $\sigma'$ in an isogeny $F$ of dimension 8 using the same techniques presented earlier since $q' := \deg(\sigma')$ has degree prime to $\ell$. To proceed, we evaluate $\sigma'$ on a canonically generated basis $(P'_1, P'_2)$ of $E'_1[\ell^f]$ using the isogeny paths $\theta_1 : E_0 \to E'_1$ and $\theta_2 : E_0 \to E'_2$ of degree dividing $T^2$ to apply EvalTorsion$_{\ell f}$ (Algorithm 11). Once all these computations are done, the prover simply sends $(\sigma_1, \sigma_2, \sigma'(P'_1), \sigma'(P'_2), q')$ to the verifier. The complete RigorousRespond procedure follows (Algorithm 18).

The complete verification procedure RigorousVerify (Algorithm 19) is very similar to the original one. Indeed, representing $\sigma'$ and representing $\sigma = \hat{\sigma}_2 \circ \sigma' \circ \sigma_1$ is equivalent when $\sigma_1$ and $\sigma_2$ are known.

As inputs of Algorithms 18 and 19, recall the following notations:

- **RigorousSetup**, the public parameters of RigorousSQIsignHD, $p$, $\ell$ and $f$ such that $\ell^f|p-1$, $e$, $T$ powersmooth (accessible torsion) and $E_0$;

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

- **CommitData**, two isogenies $\psi, \psi' : E_0 \to E_1$ of degree $D_\psi|T^2$ and $D_{\psi'} = \ell^h$ respectively along with their kernel ideals $I_\psi$ and $I_{\psi'}$;

- **ChallData**, the isogeny $\varphi : E_A \to E_2$ of degree $D_\varphi|T$.

**Algorithm 18: RigorousRespond**

**Data:** RigorousSetup, SecretKey, CommitData, ChallData.

**Result:** $(\sigma_1, \sigma_2, \sigma'(P'_1), \sigma'(P'_2), q')$, where $\sigma_1 : E_1 \to E'_1$ and $\sigma_2 : E_2 \to E'_2$ are isogenies of degree dividing $\ell^f$, $\sigma' : E'_1 \to E'_2$ is an isogeny of degree $q' < \ell^e$ prime to $\ell$ and $(P'_1, P'_2)$ is a canonically determined basis of $E'_1[\ell^f]$.

1 $I_\varphi \leftarrow \text{IsogenyTolideal}(\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 $J_1, I', J_2, K_1, K_2, \sigma_1, \sigma_2, \theta_1, \theta_2 \leftarrow \text{FactorIsogeny}_{\ell f, T}(I, \psi, \psi', \varphi \circ \tau, I_\psi, I_{\psi'}, I_\tau \cdot I_\varphi);$

5 $q' \leftarrow q/\text{nrd}(J_1) \text{nrd}(J_2);$

6 Compute the canonical basis $(P'_1, P'_2)$ of $E'_1[\ell^f]$;

7 $(\sigma'(P'_1), \sigma'(P'_2)) \leftarrow \text{EvalTorsion}_{\ell f}(I', P'_1, P'_2, \theta_1, \theta_2, K_1, K_2);$

8 Return $(\sigma_1, \sigma_2, \sigma'(P'_1), \sigma'(P'_2), q')$;

## C.3 Impact on compactness in dimension 8

When $q$ is not prime to $\ell$, the factors $\sigma_1$ and $\sigma_2$ are transmitted in the signature in addition to the data $(E_1, \sigma'(P'_1), \sigma'(P'_2), q')$. This is apparently more information
<caption>**Algorithm 19: RigorousVerify**</caption>

**Data:** RigorousSetup, ChallData, an output from RigorousRespond, ($\sigma_1, \sigma_2, R'_1, R'_2, q'$), where $\sigma_1: E_1 \to E'_1$ and $\sigma_2: E_2 \to E'_2$ are isogenies of degree dividing $\ell^f$, $R'_1, R'_2 \in E'_2[\ell^f]$ and $q' \in \mathbb{N}^*$.
**Result:** 1 if $(\sigma_1, \sigma_2, R'_1, R'_2, q')$ is a valid response and 0 otherwise.
1 **if** $q' \deg(\sigma_1) \deg(\sigma_2) > \ell^e$ **then**
2 **|** Return 0;
3 **end**
4 Compute the canonical basis $(P'_1, P'_2)$ of $E'_1[\ell^f]$;
5 Find $a_1, \dots, a_4 \in \mathbb{Z}$ such that $a_1^2 + \dots + a_4^2 + q = \ell^e$ using Pollack and Treviño's algorithm [PT18];
6 $F' \leftarrow$ RepresentIsogeny$_{S, \ell^e}$($q', a_1, \dots, a_4, P'_1, P'_2, R'_1, R'_2$);
7 Return lsValid$_S(F', E'_1, E'_2, a_1, \dots, a_4)$;

than in the case $q \wedge \ell = 1$. However, we can optimize the communications to avoid any compactness loss.

We may write $\deg(\sigma_1) := \ell^{f_1}$ and $\deg(\sigma_2) := \ell^{f_2}$, with $f_1, f_2 \le f$, so that $q' = q/\ell^{f_1+f_2} < \ell^{e'}$, where $e' := e - f_1 - f_2$. Hence, we can represent $\sigma'$ by an $\ell^{e'}$-isogeny $F'$ in dimension 8. By Remark 4.2, we only need to evaluate the $\ell^{f_3}$-torsion by $\sigma'$, where $2f_3 \ge e' + 4$. Hence the points $P'_1$ and $P'_2$ may form a basis of $E'_1[\ell^{f_3}]$ instead of $E'_1[\ell^f]$ and we can represent $\sigma'(P'_1)$ and $\sigma'(P'_1)$ with $3f_3$ bits by the techniques of Section 6.1 (assuming $\ell = 2$).

To represent $\sigma_1$, we may factor $\sigma_1 := [\ell^{b_1}] \circ \sigma'_1$, where $2b_1 \le f_1$ and $\sigma'_1: E_1 \to E'_1$ a cyclic $\ell^{f_1}$-isogeny with $f'_1 := f_1 - 2b_1$. So we may represent $\sigma_1$ by the integer $b_1$ and $\ker(\sigma'_1) \subset E_1[\ell^{f_1}]$. Let $(Q_1, Q_2)$ be a canonical basis of $E_1[\ell^{f_1}]$. Then, $\ker(\sigma'_1)$ is generated by either one of the points $Q_1 + kQ_2$ with $0 \le k \le \ell^{f_1} - 1$ or one of the points $\ell k'Q_1 + Q_2$ with $0 \le k' \le \ell^{f_1-1} - 1$. Hence, $\ker(\sigma'_1)$ can be represented by $f'_1 + 1$ bits (one bit to tell which form takes $\ker(\sigma'_1)$ and $f'_1$ bits for $k$ or $k'$). Since the number of bits to represent $b_1$ is very small $(O(\log(b_1)))$, we may represent $\sigma_1$ by at most $f_1 + 1$ bits, and similarly, we may represent $\sigma_2$ by at most $f_2 + 1$ bits.

As in Section 6.1, we represent $q' < \ell^{e'}$ with $e'$ bits and $E_1$ with $4\lambda$ bits (where $\lambda$ is the security level, satisfying $p \approx 2^\lambda$). Hence, the signature size is

$$3f_3 + f_1 + f_2 + 2 + 4\lambda + e' = \frac{5}{2}(e - f_1 - f_2) + f_1 + f_2 + 4\lambda + O(\log(\lambda)) \\ < \frac{5}{2}e + 4\lambda + O(\log(\lambda)) = 14\lambda + O(\log(\lambda))$$

in bits, so we do not suffer any communication loss compared to the case $q \wedge \ell = 1$ (as the inequality indicates). However, since $e \approx 4\lambda$ ($\ell^e = \Theta(p^2)$), Rigorous-SQIsignHD signatures are much less compact than FastSQIsignHD signatures ($14\lambda$ instead of $13/2\lambda$ bits).
<caption>**Algorithm 19: RigorousVerify**</caption>

**Data:** RigorousSetup, ChallData, an output from RigorousRespond, ($\sigma_1, \sigma_2, R'_1, R'_2, q'$), where $\sigma_1 : E_1 \to E'_1$ and $\sigma_2 : E_2 \to E'_2$ are isogenies of degree dividing $\ell^f$, $R'_1, R'_2 \in E'_2[\ell^f]$ and $q' \in \mathbb{N}^*$.

**Result:** 1 if $(\sigma_1, \sigma_2, R'_1, R'_2, q')$ is a valid response and 0 otherwise.

1 **if** $q' \deg(\sigma_1) \deg(\sigma_2) > \ell^e$ **then**
2 | Return 0;
3 **end**
4 Compute the canonical basis $(P'_1, P'_2)$ of $E'_1[\ell^f]$;
5 Find $a_1, \dots, a_4 \in \mathbb{Z}$ such that $a_1^2 + \dots + a_4^2 + q = \ell^e$ using Pollack and Treviño's algorithm [PT18];
6 $F' \leftarrow$ RepresentIsogeny$_{S, \ell^e}$($q', a_1, \dots, a_4, P'_1, P'_2, R'_1, R'_2$);
7 Return $\text{IsValid}_S(F', E'_1, E'_2, a_1, \dots, a_4)$;

than in the case $q \wedge \ell = 1$. However, we can optimize the communications to avoid any compactness loss.

We may write $\deg(\sigma_1) := \ell^{f_1}$ and $\deg(\sigma_2) := \ell^{f_2}$, with $f_1, f_2 \le f$, so that $q' = q/\ell^{f_1+f_2} < \ell^{e'}$, where $e' := e - f_1 - f_2$. Hence, we can represent $\sigma'$ by an $\ell^{e'}$-isogeny $F'$ in dimension 8. By Remark 4.2, we only need to evaluate the $\ell^{f_3}$-torsion by $\sigma'$, where $2f_3 \ge e' + 4$. Hence the points $P'_1$ and $P'_2$ may form a basis of $E'_1[\ell^{f_3}]$ instead of $E'_1[\ell^f]$ and we can represent $\sigma'(P'_1)$ and $\sigma'(P'_1)$ with $3f_3$ bits by the techniques of Section 6.1 (assuming $\ell = 2$).

To represent $\sigma_1$, we may factor $\sigma_1 := [\ell^{b_1}] \circ \sigma'_1$, where $2b_1 \le f_1$ and $\sigma'_1 : E_1 \to E'_1$ a cyclic $\ell^{f_1}$-isogeny with $f'_1 := f_1 - 2b_1$. So we may represent $\sigma_1$ by the integer $b_1$ and $\ker(\sigma'_1) \subset E_1[\ell^{f_1}]$. Let $(Q_1, Q_2)$ be a canonical basis of $E_1[\ell^{f_1}]$. Then, $\ker(\sigma'_1)$ is generated by either one of the points $Q_1 + kQ_2$ with $0 \le k \le \ell^{f_1} - 1$ or one of the points $\ell k'Q_1 + Q_2$ with $0 \le k' \le \ell^{f_1-1} - 1$. Hence, $\ker(\sigma'_1)$ can be represented by $f'_1 + 1$ bits (one bit to tell which form takes $\ker(\sigma'_1)$ and $f'_1$ bits for $k$ or $k'$). Since the number of bits to represent $b_1$ is very small $(O(\log(b_1)))$, we may represent $\sigma_1$ by at most $f_1 + 1$ bits, and similarly, we may represent $\sigma_2$ by at most $f_2 + 1$ bits.

As in Section 6.1, we represent $q' < \ell^{e'}$ with $e'$ bits and $E_1$ with $4\lambda$ bits (where $\lambda$ is the security level, satisfying $p \approx 2^\lambda$). Hence, the signature size is

$$3f_3 + f_1 + f_2 + 2 + 4\lambda + e' = \frac{5}{2}(e - f_1 - f_2) + f_1 + f_2 + 4\lambda + O(\log(\lambda)) \\ < \frac{5}{2}e + 4\lambda + O(\log(\lambda)) = 14\lambda + O(\log(\lambda))$$

in bits, so we do not suffer any communication loss compared to the case $q \wedge \ell = 1$ (as the inequality indicates). However, since $e \approx 4\lambda$ ($\ell^e = \Theta(p^2)$), Rigorous-SQIsignHD signatures are much less compact than FastSQIsignHD signatures (14$\lambda$ instead of 13/2$\lambda$ bits).
# D Security analysis of RigorousSQIsignHD

To prove the security of RigorousSQIsignHD, we proceed as in Section 5, namely, we prove completeness, knowledge soundness and zero-knowledge properties. Completeness is a consequence of Corollary 32.

In Appendix D.1, we prove the knowledge soundness of RigorousSQIsignHD. Our previous straightforward special soundness argument used in Section 5.1 does not apply anymore because we have no guarantee on $q = \deg(\sigma)$ in general. For that reason, we need to come back to the formal definition of knowledge soundness given in [HL10, Definition 6.3.1].

In Appendix D.2, we prove the zero-knowledge property provided the simulator can access an oracle which is more natural than the ad-hoc one introduced in Section 5.2 and without any additional heuristic assumption. RigorousSQIsignHD was designed to prove rigorously this zero-knowledge property.

## D.1 Knowledge soundness of RigorousSQIsignHD

We recall the formal definition of knowledge soundness given in [HL10, Definition 6.3.1].

**Definition 34.** A protocol $(P, V)$ between a prover and a verifier is a *proof of knowledge* for a relation $\mathcal{R} \subset X \times W$ with knowledge error $\kappa$ if it satisfies the following properties:

**Completeness:** If $P$ interacts with $V$ as input $x \in X$ and private input $w \in W$ with $(x, w) \in \mathcal{R}$, then $V$ always accepts.

**Knowledge soundness:** There exists a *knowledge extractor* $K$ such that for every interactive prover $P^*$ and every $x \in X$, $K$ satisfies the following condition. Let $\varepsilon(x)$ be the success probability of $P^*$ on input $x$ (the probability that $V$ accepts on input $x$). If $\varepsilon(x) > \kappa(x)$, then upon input $x$ and oracle access to $P^*$, $K$ outputs a witness $w \in W$ such that $(x, w) \in \mathcal{R}$ within an expected number of steps $O(1/(\varepsilon(x) - \kappa(x)))$.

**Definition 35.** A 3-round protocol (commitment, challenge, response) $(P, V)$ satisfies *special soundness* for a relation $\mathcal{R} \subset X \times W$ if given $x \in X$ and two accepting transcripts $(a, c, r), (a, c', r')$ for $x \in X$ with the same commitment $a$ and distinct challenges $c \neq c'$, one can extract a witness $w \in W$ such that $(x, w) \in \mathcal{R}$ in polynomial time.

**Theorem 36.** [HL10, Theorem 6.3.2] A complete 3-round protocol satisfying *special soundness* for a relation $\mathcal{R}$ with challenge space $C$ is a proof of knowledge with knowledge error $1/\#C$.

In Proposition 17, we proved that FastSQIsignHD satisfies *special soundness* for the relation:

$$ \mathcal{R} := \{(E_A, \alpha) \mid \alpha \in \text{End}(E_A) \text{ non-scalar}\}. $$
# D Security analysis of RigorousSQIsignHD

To prove the security of RigorousSQIsignHD, we proceed as in Section 5, namely, we prove completeness, knowledge soundness and zero-knowledge properties. Completeness is a consequence of Corollary 32.

In Appendix D.1, we prove the knowledge soundness of RigorousSQIsignHD. Our previous straightforward special soundness argument used in Section 5.1 does not apply anymore because we have no guarantee on $q = \deg(\sigma)$ in general. For that reason, we need to come back to the formal definition of knowledge soundness given in [HL10, Definition 6.3.1].

In Appendix D.2, we prove the zero-knowledge property provided the simulator can access an oracle which is more natural than the ad-hoc one introduced in Section 5.2 and without any additional heuristic assumption. RigorousSQIsignHD was designed to prove rigorously this zero-knowledge property.

## D.1 Knowledge soundness of RigorousSQIsignHD

We recall the formal definition of knowledge soundness given in [HL10, Definition 6.3.1].

**Definition 34.** A protocol $(P, V)$ between a prover and a verifier is a *proof of knowledge* for a relation $\mathcal{R} \subset X \times W$ with knowledge error $\kappa$ if it satisfies the following properties:

**Completeness:** If $P$ interacts with $V$ as input $x \in X$ and private input $w \in W$ with $(x, w) \in \mathcal{R}$, then $V$ always accepts.

**Knowledge soundness:** There exists a *knowledge extractor* $K$ such that for every interactive prover $P^*$ and every $x \in X$, $K$ satisfies the following condition. Let $\varepsilon(x)$ be the success probability of $P^*$ on input $x$ (the probability that $V$ accepts on input $x$). If $\varepsilon(x) > \kappa(x)$, then upon input $x$ and oracle access to $P^*$, $K$ outputs a witness $w \in W$ such that $(x, w) \in \mathcal{R}$ within an expected number of steps $O(1/(\varepsilon(x) - \kappa(x)))$.

**Definition 35.** A 3-round protocol (commitment, challenge, response) $(P, V)$ satisfies *special soundness* for a relation $\mathcal{R} \subset X \times W$ if given $x \in X$ and two accepting transcripts $(a, c, r), (a, c', r')$ for $x \in X$ with the same commitment $a$ and distinct challenges $c \neq c'$, one can extract a witness $w \in W$ such that $(x, w) \in \mathcal{R}$ in polynomial time.

**Theorem 36.** [HL10, Theorem 6.3.2] A complete 3-round protocol satisfying *special soundness* for a relation $\mathcal{R}$ with challenge space $C$ is a proof of knowledge with knowledge error $1/\#C$.

In Proposition 17, we proved that FastSQIsignHD satisfies *special soundness* for the relation:

$$ \mathcal{R} := \{(E_A, \alpha) \mid \alpha \in \text{End}(E_A) \text{ non-scalar}\}. $$
Since the challenge space has size $\mu(\ell'f') = \ell'^{f'-1}(\ell' + 1) = \Omega(p^{1/2})$, we get by Theorem 36 that FastSQIsignHD is a proof of knowledge for $\mathcal{R}$ with knowledge error $O(p^{-1/2})$.

Unfortunately, the special soundness argument no longer holds in Rigorous-SQIsignHD because we can no longer impose conditions on $q$ (except $q < \ell^e$), and especially we cannot impose $q$ to be prime to $D_\varphi$. However, choosing $D_\varphi$ big enough will ensure that the endomorphism $\alpha$ is non-scalar with overwhelming probability, since $\varphi' \circ \hat{\varphi}$ has a big cyclic factor with overwhelming probability. We first introduce a useful lemma to prove this result.

**Lemma 37.** Let $\phi : E_1 \to E_2$ and $\phi' : E_1 \to E'_2$ be two cyclic isogenies. Let $\phi_0 : E_1 \to E_3$ be the cyclic separable isogeny such that $\ker(\phi_0) = \ker(\phi) \cap \ker(\phi')$. Then, there exists two cyclic isogenies $\phi_1 : E_3 \to E_2$ and $\phi'_1 : E_3 \to E'_2$ such that $\phi = \phi_1 \circ \phi_0$, $\phi' = \phi'_1 \circ \phi_0$ and $\phi'_1 \circ \widehat{\phi_1}$ is cyclic. $\phi_0$ will be called the greatest common factor of $\phi$ and $\phi'$.

*Proof.* We can always factor $\phi = \phi_1 \circ \phi_0$, $\phi' = \phi'_1 \circ \phi_0$, with $\phi_0 : E_1 \to E_3$ such that $\ker(\phi_0) = \ker(\phi) \cap \ker(\phi')$.

First, we prove that $\ker(\phi_1) \cap \ker(\phi'_1) = \{0\}$. If it was not the case, we could find a cyclic isogeny $\psi : E_2 \to E_4$ with non-trivial kernel such that $\phi_1$ and $\phi'_1$ factor through $\psi$, and both $\phi$ and $\phi'$ would factor through $\psi \circ \phi_0$, so we would have $\ker(\psi \circ \phi_0) \subseteq \ker(\phi) \cap \ker(\phi')$. But $\ker(\psi \circ \phi_0) = \phi_0^{-1}(\ker(\psi)) \supseteq \ker(\phi_0)$ since $\ker(\psi)$ is non-trivial. Contradiction.

Now, we prove that $\phi'_1 \circ \widehat{\phi_1}$ is cyclic. Actually, it suffices to prove it when $\deg(\phi'_1)$ and $\deg(\phi_1)$ are powers of the same prime $\ell$. Indeed, if not, we can decompose $\phi_1 = \psi_2 \circ \psi_1$ and $\phi'_1 = \psi'_2 \circ \psi'_1$ with $\deg(\psi_1)\deg(\psi'_1)$ coprime with $\deg(\psi_2)\deg(\psi'_2)$. Then, we may write $\phi'_1 \circ \widehat{\phi_1} = \psi'_2 \circ \widehat{\psi_2}$, with $\psi_3 = \psi'_1 \circ \widehat{\psi_1}$. Using pushforward isogenies (as defined in Definition 8), we may write $[\psi_2]_*\psi_3 \circ \psi_2 = [\psi_3]_*\psi_2 \circ \psi_3$, so that $\psi_3 \circ \widehat{\psi_2} = [\widehat{\psi_3}]_*\widehat{\psi_2} \circ [\psi_2]_*\psi_3$ and

$$ \phi'_1 \circ \widehat{\phi_1} = \psi'_2 \circ [\widehat{\psi_3}]_*\widehat{\psi_2} \circ [\psi_2]_*\psi_3. $$

If we assume that $\psi_3$ is cyclic then $[\psi_2]_*\psi_3$ is cyclic. Besides, $\psi'_2$ and $[\psi_3]_*\psi_2$ are cyclic and $\ker(\psi'_2) \cap \ker([\psi_3]_*\psi_2) = \{0\}$. Indeed, if $P \in \ker(\psi'_2) \cap \ker([\psi_3]_*\psi_2)$, then $P \in \ker([\psi_3]_*\psi_2) = \psi_3(\ker(\psi_2))$ so we may write $P = \psi_3(Q)$ with $Q \in \ker(\psi_2)$. Let $R := \widehat{\psi_1}(Q)$. Then, $\phi_1(R) = \psi_2 \circ \psi_1 \circ \widehat{\psi_1}(Q) = [\deg(\psi_1)]\psi_2(Q) = 0$ and $\phi'_1(R) = \psi'_2(P) = 0$, so $R \in \ker(\phi_1) \cap \ker(\phi'_1) = \{0\}$ and $R = 0$, so $P = \psi'_1(R) = 0$.

Since the product of cyclic isogenies of coprime degrees is cyclic, it follows by induction that we only have to prove that $\ker(\phi_1) \cap \ker(\phi'_1) = \{0\}$ implies the cyclicity of $\phi'_1 \circ \widehat{\phi_1}$ when $\deg(\phi'_1)$ and $\deg(\phi_1)$ are powers of the same prime $\ell$. We assume that in the following.

We proceed by induction on $\deg(\phi'_1)$. When $\deg(\phi'_1) = 1$ it follows from the fact that the dual of a cyclic isogeny is cyclic. Now, we assume the result holds when $\deg(\phi'_1) = \ell^n$ with $n \in \mathbb{N}$ and prove it holds when $\deg(\phi'_1) = \ell^{n+1}$. We may factor $\phi'_1 := \phi_2 \circ \phi'_2$ with $\deg(\phi_2) = \ell$ and $\deg(\phi'_2) = \ell^n$. By assumption,
Since the challenge space has size $\mu(\ell'f') = \ell'f'^{-1}(\ell' + 1) = \Omega(p^{1/2})$, we get by Theorem 36 that FastSQIsignHD is a proof of knowledge for $\mathcal{R}$ with knowledge error $O(p^{-1/2})$.

Unfortunately, the special soundness argument no longer holds in Rigorous-SQIsignHD because we can no longer impose conditions on $q$ (except $q < \ell^e$), and especially we cannot impose $q$ to be prime to $D_\varphi$. However, choosing $D_\varphi$ big enough will ensure that the endomorphism $\alpha$ is non-scalar with overwhelming probability, since $\varphi' \circ \hat{\varphi}$ has a big cyclic factor with overwhelming probability. We first introduce a useful lemma to prove this result.

**Lemma 37.** Let $\phi : E_1 \to E_2$ and $\phi' : E_1 \to E'_2$ be two cyclic isogenies. Let $\phi_0 : E_1 \to E_3$ be the cyclic separable isogeny such that $\ker(\phi_0) = \ker(\phi) \cap \ker(\phi')$. Then, there exists two cyclic isogenies $\phi_1 : E_3 \to E_2$ and $\phi'_1 : E_3 \to E'_2$ such that $\phi = \phi_1 \circ \phi_0$, $\phi' = \phi'_1 \circ \phi_0$ and $\phi'_1 \circ \widehat{\phi_1}$ is cyclic. $\phi_0$ will be called the greatest common factor of $\phi$ and $\phi'$.

*Proof.* We can always factor $\phi = \phi_1 \circ \phi_0$, $\phi' = \phi'_1 \circ \phi_0$, with $\phi_0 : E_1 \to E_3$ such that $\ker(\phi_0) = \ker(\phi) \cap \ker(\phi')$.

First, we prove that $\ker(\phi_1) \cap \ker(\phi'_1) = \{0\}$. If it was not the case, we could find a cyclic isogeny $\psi : E_2 \to E_4$ with non-trivial kernel such that $\phi_1$ and $\phi'_1$ factor through $\psi$, and both $\phi$ and $\phi'$ would factor through $\psi \circ \phi_0$, so we would have $\ker(\psi \circ \phi_0) \subseteq \ker(\phi) \cap \ker(\phi')$. But $\ker(\psi \circ \phi_0) = \phi_0^{-1}(\ker(\psi)) \supseteq \ker(\phi_0)$ since $\ker(\psi)$ is non-trivial. Contradiction.

Now, we prove that $\phi'_1 \circ \widehat{\phi_1}$ is cyclic. Actually, it suffices to prove it when $\deg(\phi'_1)$ and $\deg(\phi_1)$ are powers of the same prime $\ell$. Indeed, if not, we can decompose $\phi_1 = \psi_2 \circ \psi_1$ and $\phi'_1 = \psi'_2 \circ \psi'_1$ with $\deg(\psi_1)\deg(\psi'_1)$ coprime with $\deg(\psi_2)\deg(\psi'_2)$. Then, we may write $\phi'_1 \circ \widehat{\phi_1} = \psi'_2 \circ \widehat{\psi_2}$, with $\psi_3 = \psi'_1 \circ \widehat{\psi_1}$. Using pushforward isogenies (as defined in Definition 8), we may write $[\psi_2]_*\psi_3 \circ \psi_2 = [\psi_3]_*\psi_2 \circ \psi_3$, so that $\psi_3 \circ \widehat{\psi_2} = [\widehat{\psi_3}]_*\widehat{\psi_2} \circ [\psi_2]_*\psi_3$ and

$$ \phi'_1 \circ \widehat{\phi_1} = \psi'_2 \circ [\widehat{\psi_3}]_*\widehat{\psi_2} \circ [\psi_2]_*\psi_3. $$

If we assume that $\psi_3$ is cyclic then $[\psi_2]_*\psi_3$ is cyclic. Besides, $\psi'_2$ and $[\psi_3]_*\psi_2$ are cyclic and $\ker(\psi'_2) \cap \ker([\psi_3]_*\psi_2) = \{0\}$. Indeed, if $P \in \ker(\psi'_2) \cap \ker([\psi_3]_*\psi_2)$, then $P \in \ker([\psi_3]_*\psi_2) = \psi_3(\ker(\psi_2))$ so we may write $P = \psi_3(Q)$ with $Q \in \ker(\psi_2)$. Let $R := \widehat{\psi_1}(Q)$. Then, $\phi_1(R) = \psi_2 \circ \psi_1 \circ \widehat{\psi_1}(Q) = [\deg(\psi_1)]\psi_2(Q) = 0$ and $\phi'_1(R) = \psi'_2(P) = 0$, so $R \in \ker(\phi_1) \cap \ker(\phi'_1) = \{0\}$ and $R = 0$, so $P = \psi'_1(R) = 0$.

Since the product of cyclic isogenies of coprime degrees is cyclic, it follows by induction that we only have to prove that $\ker(\phi_1) \cap \ker(\phi'_1) = \{0\}$ implies the cyclicity of $\phi'_1 \circ \widehat{\phi_1}$ when $\deg(\phi'_1)$ and $\deg(\phi_1)$ are powers of the same prime $\ell$. We assume that in the following.

We proceed by induction on $\deg(\phi'_1)$. When $\deg(\phi'_1) = 1$ it follows from the fact that the dual of a cyclic isogeny is cyclic. Now, we assume the result holds when $\deg(\phi'_1) = \ell^n$ with $n \in \mathbb{N}$ and prove it holds when $\deg(\phi'_1) = \ell^{n+1}$. We may factor $\phi'_1 := \phi_2 \circ \phi'_2$ with $\deg(\phi_2) = \ell$ and $\deg(\phi'_2) = \ell^n$. By assumption,
$\phi_3 := \phi'_2 \circ \widehat{\phi_1}$ is cyclic so we only have to prove that $\phi_2 \circ \phi_3$ is cyclic, i.e. that $\ker(\phi_2 \circ \phi_3) = \phi_3^{-1}(\ker(\phi_2))$ is cyclic.

Let $Q$ be a generator of $\ker(\phi_2)$, $P$ be a generator of $\ker(\phi_3)$ and $P' \in E_2$ such that $Q = \phi_3(P')$. Then

$$ \ker(\phi_2 \circ \phi_3) = \phi_3^{-1}(\ker(\phi_2)) = \langle P, P' \rangle. $$

To conclude, it suffices to prove that $P \in \langle P' \rangle$. We have $P' \in \ker(\phi_2 \circ \phi_3) \subset E_2[\ell^{m+1}]$, with $\deg(\phi_3) := \ell^m$ and $[\ell^m]P' = \widehat{\phi_3} \circ \phi_3(P') = \widehat{\phi_3}(Q)$ and $\widehat{\phi_3}(Q) \neq 0$. Indeed, if $\widehat{\phi_3}(Q) = 0$, we may write $S := \widehat{\phi'_2}(Q)$, so that $\phi_1(S) = \widehat{\phi_3}(Q) = 0$ and $\phi'_1(S) = \phi_2 \circ \phi'_2 \circ \widehat{\phi'_2}(Q) = [\ell^n]\phi_2(Q) = 0$, so that $S \in \ker(\phi_1) \cap \ker(\phi'_1) = \{0\}$ and $\widehat{\phi'_2}(Q) = 0$. Hence, $\phi'_2$ factors through $\phi_2$ and $\phi'_1$ factors through $[\ell] = \phi_2 \circ \widehat{\phi_2}$ and is not cyclic. Contradiction. Hence, $\widehat{\phi_3}(Q) \neq 0$ and $P'$ has order $\ell^{m+1}$.

Let $R \in E_2[\ell^m]$ such that $([\ell]P', R)$ is a basis of $E_2[\ell^m]$. Then, we may write $P := [a\ell]P' + [b]R$ for some $a, b \in \mathbb{Z}$ since $P \in \ker(\phi_3) \subset E_2[\ell^m]$. Since $Q \in \ker(\phi_2)$ has order $\ell$, we get that

$$ 0 = \phi_3(P) = [a\ell]Q + [b]\phi_3(R) = [b]\phi_3(R), $$

and that $\phi_3(R)$ generates $\phi_3(E_2[\ell^m]) = \ker(\widehat{\phi_3})$, which is cyclic so it has order $\ell^m$. It follows that $b \equiv 0 \mod \ell^m$, so that $P = [a\ell]P' \in \langle P' \rangle$. This completes the proof. $\square$

**Lemma 38.** Let $(E_1, \phi, R_1, R_2, q)$ and $(E_1, \phi', R'_1, R'_2, q')$ be two Rigorous-SQIsignHD transcripts with the same commitment $E_1$. If the greatest common factor of $\phi$ and $\phi'$ has degree $< D_\phi/\ell^e$, then we can infer an efficient representation of a non-scalar endomorphism $\alpha \in \text{End}(E_A)$ from these transcripts. In this case we say that $\phi$ and $\phi'$ are relatively good and relatively bad if this is not satisfied.

*Proof.* Let $\sigma$ and $\sigma'$ be respectively the isogenies defined on $E_1$ represented by $(R_1, R_2, q)$ and $(R'_1, R'_2, q')$ and $\alpha := \widehat{\phi'} \circ \sigma' \circ \widehat{\sigma} \circ \phi \in \text{End}(E_A)$. As explained in the proof of Proposition 17, we can compute an efficient representation of $\alpha$ in polynomial time in $\log(p)$. Assume that $\alpha$ is a scalar endomorphism: $\alpha = [\lambda]_{E_A}$ for some $\lambda \in \mathbb{Z}$. Then $[\lambda]_{E_2} = \phi \circ \widehat{\phi'} \circ \sigma' \circ \widehat{\sigma}$. Let us write $\phi := \phi_1 \circ \phi_0$ and $\phi := \phi'_1 \circ \phi_0$, where $\phi_0$ is the greatest common factor of $\phi$ and $\phi'$. Then $\phi := \phi_1 \circ \widehat{\phi'_1}$ is cyclic by Lemma 37 and we have $\phi \circ \widehat{\phi'} := [D]\phi$ with $D := \deg(\phi_0)$. We can also write $\sigma \circ \widehat{\sigma'} = [D']\phi'$ where $\phi'$ is a cyclic isogeny $E'_2 \to E_2$. It follows that $[\lambda/\overline{DD'}]_{E'_2} = \phi \circ \widehat{\phi'}$. Hence, by Lemma 37, the greatest common factor of $\phi$ and $\phi'$ must be equal to both $\phi$ and $\phi'$ so $\phi = \phi'$. Hence, $\sigma \circ \widehat{\sigma'}$ factors through $\phi$. But $\deg(\sigma \circ \widehat{\sigma'}) = qq' \le \ell^{2e}$ and $\deg(\phi) = D_\phi^2/D^2$ with $D < D_\phi/\ell^e$ so $\deg(\phi) > \ell^{2e}$. Contradiction. $\square$

Now, we prove that the probability to generate relatively good challenges is overwhelming. This will be the last essential ingredient to our knowledge soundness proof.
$\phi_3 := \phi'_2 \circ \widehat{\phi_1}$ is cyclic so we only have to prove that $\phi_2 \circ \phi_3$ is cyclic, i.e. that $\ker(\phi_2 \circ \phi_3) = \phi_3^{-1}(\ker(\phi_2))$ is cyclic.

Let $Q$ be a generator of $\ker(\phi_2)$, $P$ be a generator of $\ker(\phi_3)$ and $P' \in E_2$ such that $Q = \phi_3(P')$. Then

$$ \ker(\phi_2 \circ \phi_3) = \phi_3^{-1}(\ker(\phi_2)) = \langle P, P' \rangle. $$

To conclude, it suffices to prove that $P \in \langle P' \rangle$. We have $P' \in \ker(\phi_2 \circ \phi_3) \subset E_2[\ell^{m+1}]$, with $\deg(\phi_3) := \ell^m$ and $[\ell^m]P' = \widehat{\phi_3} \circ \phi_3(P') = \widehat{\phi_3}(Q)$ and $\widehat{\phi_3}(Q) \neq 0$. Indeed, if $\widehat{\phi_3}(Q) = 0$, we may write $S := \widehat{\phi'_2}(Q)$, so that $\phi_1(S) = \widehat{\phi_3}(Q) = 0$ and $\phi'_1(S) = \phi_2 \circ \phi'_2 \circ \widehat{\phi'_2}(Q) = [\ell^n]\phi_2(Q) = 0$, so that $S \in \ker(\phi_1) \cap \ker(\phi'_1) = \{0\}$ and $\widehat{\phi'_2}(Q) = 0$. Hence, $\phi'_2$ factors through $\phi_2$ and $\phi'_1$ factors through $[\ell] = \phi_2 \circ \widehat{\phi_2}$ and is not cyclic. Contradiction. Hence, $\widehat{\phi_3}(Q) \neq 0$ and $P'$ has order $\ell^{m+1}$.

Let $R \in E_2[\ell^m]$ such that $([\ell]P', R)$ is a basis of $E_2[\ell^m]$. Then, we may write $P := [a\ell]P' + [b]R$ for some $a, b \in \mathbb{Z}$ since $P \in \ker(\phi_3) \subset E_2[\ell^m]$. Since $Q \in \ker(\phi_2)$ has order $\ell$, we get that

$$ 0 = \phi_3(P) = [a\ell]Q + [b]\phi_3(R) = [b]\phi_3(R), $$

and that $\phi_3(R)$ generates $\phi_3(E_2[\ell^m]) = \ker(\widehat{\phi_3})$, which is cyclic so it has order $\ell^m$. It follows that $b \equiv 0 \mod \ell^m$, so that $P = [a\ell]P' \in \langle P' \rangle$. This completes the proof. $\square$

**Lemma 38.** Let $(E_1, \phi, R_1, R_2, q)$ and $(E_1, \phi', R'_1, R'_2, q')$ be two Rigorous-SQIsignHD transcripts with the same commitment $E_1$. If the greatest common factor of $\phi$ and $\phi'$ has degree $< D_\phi/\ell^e$, then we can infer an efficient representation of a non-scalar endomorphism $\alpha \in \text{End}(E_A)$ from these transcripts. In this case we say that $\phi$ and $\phi'$ are relatively good and relatively bad if this is not satisfied.

*Proof.* Let $\sigma$ and $\sigma'$ be respectively the isogenies defined on $E_1$ represented by $(R_1, R_2, q)$ and $(R'_1, R'_2, q')$ and $\alpha := \widehat{\phi'} \circ \sigma' \circ \widehat{\sigma} \circ \phi \in \text{End}(E_A)$. As explained in the proof of Proposition 17, we can compute an efficient representation of $\alpha$ in polynomial time in $\log(p)$. Assume that $\alpha$ is a scalar endomorphism: $\alpha = [\lambda]_{E_A}$ for some $\lambda \in \mathbb{Z}$. Then $[\lambda]_{E_2} = \phi \circ \widehat{\phi'} \circ \sigma' \circ \widehat{\sigma}$. Let us write $\phi := \phi_1 \circ \phi_0$ and $\phi := \phi'_1 \circ \phi_0$, where $\phi_0$ is the greatest common factor of $\phi$ and $\phi'$. Then $\phi := \phi_1 \circ \widehat{\phi'_1}$ is cyclic by Lemma 37 and we have $\phi \circ \widehat{\phi'} := [D]\phi$ with $D := \deg(\phi_0)$. We can also write $\sigma \circ \widehat{\sigma'} = [D']\phi'$ where $\phi'$ is a cyclic isogeny $E'_2 \to E_2$. It follows that $[\lambda/\overline{DD'}]_{E'_2} = \phi \circ \widehat{\phi'}$. Hence, by Lemma 37, the greatest common factor of $\phi$ and $\phi'$ must be equal to both $\phi$ and $\phi'$ so $\phi = \phi'$. Hence, $\sigma \circ \widehat{\sigma'}$ factors through $\phi$. But $\deg(\sigma \circ \widehat{\sigma'}) = qq' \le \ell^{2e}$ and $\deg(\phi) = D_\phi^2/D^2$ with $D < D_\phi/\ell^e$ so $\deg(\phi) > \ell^{2e}$. Contradiction. $\square$

Now, we prove that the probability to generate relatively good challenges is overwhelming. This will be the last essential ingredient to our knowledge soundness proof.
**Lemma 39.** Fix a challenge $\varphi: E_A \to E_2$ and let us write $D_\varphi := \prod_{i=1}^r \ell_i^{e_i}$, where $\ell_1 \le \dots \le \ell_r$ are distinct ordered primes and $e_1, \dots, e_r \in \mathbb{N}^*$. Then, the number of challenges $\varphi': E_A \to E_2'$ relatively bad to $\varphi$ is

$$O\left(\frac{\ell^e \mu(D_\varphi)}{D_\varphi^{1-\log(2)/\log\log(D_\varphi)}}\right),$$

with $\mu(D_\varphi) := \prod_{i=1}^r \ell_i^{e_i-1}(\ell_i+1)$.

*Proof.* $\varphi$ and $\varphi'$ relatively bad if their greatest common factor has degree $D \ge D_\varphi/\ell^e$. If we fix such a $D|D_\varphi$, then choosing $\varphi'$ is choosing a cyclic isogeny of degree $D_\varphi/D$ so there are $\mu(D_\varphi/D)$ possibilities. It follows that the number of challenges $\varphi'$ relatively bad to $\varphi$ is

$$N \le \sum_{\substack{D|D_\varphi \\ D>D_\varphi/\ell^e}} \mu\left(\frac{D_\varphi}{D}\right) = \mu(D_\varphi) \sum_{\substack{D|D_\varphi \\ D>D_\varphi/\ell^e}} \frac{1}{\mu(D)} \le \mu(D_\varphi) \sum_{\substack{D|D_\varphi \\ D>D_\varphi/\ell^e}} \frac{1}{D} \\ \le \frac{\ell^e \mu(D_\varphi)}{D_\varphi} \#\{D \in \mathbb{N}^* \mid D|D_\varphi \text{ and } D > D_\varphi/\ell^e\} \\ \le \frac{\ell^e \mu(D_\varphi)}{D_\varphi} \#\{D \in \mathbb{N}^* \mid D|D_\varphi\} = \frac{\ell^e \mu(D_\varphi) d(D_\varphi)}{D_\varphi},$$

where $d(D_\varphi)$ is the number of divisors of $d(D_\varphi)$. By [HW08, § 18.1, Theorem 317], we know that $d(D_\varphi) = O\left(D_\varphi^{\log(2)/\log\log(D_\varphi)}\right)$. The result follows. $\square$

Since $\ell^e = O(p^2)$, we choose $D_\varphi|T$ such that $D_\varphi \simeq p^{5/(2-2\log(2)/\log\log(p^{5/2}))}$, so that the proportion of challenges relatively bad to a given challenge is $O(p^{-1/2})$. This means in practice $D_\varphi \simeq p^{2.82}$ when $p$ has size 256 bits (to achieve $\lambda = 128$ bits of classical security). Hence the choice $T \simeq p^3$. Then, under this condition, we can adapt the proof of [HL10, Theorem 6.3.2] to prove knowledge soundness of RigorousSQIsignHD.

**Proposition 40.** *Assume that $D_\varphi > p^{5/(2-2\log(2)/\log\log(p^{5/2}))}$. Then the RigorousSQIsignHD identification protocol is a proof of knowledge for the relation $R$ of Proposition 17 with knowledge error $O(p^{-1/2})$.*

*Proof.* As required by Definition 34, we construct a knowledge extractor $K$. Let $P^*$ be a prover with success probability $\epsilon$. Then $K$ is constructed as follows (as in [HL10, Theorem 6.3.2]). Fix $E_A$ a supersingular elliptic curve (as public key). Then $K$ executes the following algorithm:

1. Sample a seed $s \stackrel{\$}{\leftarrow} \{0,1\}^*$ fixing the randomness of $P^*$, sample a challenge $\varphi$ and run $P^*(E_A, s, \varphi)$ repeatedly until the transcript $(E_1, \varphi, R_1, R_2, q)$ outputted by $P^*$ is accepted by the verifier and save $s$.

2. Sample another challenge $\varphi'$ and run $P^*(E_A, s, \varphi')$ with the same seed $s$ as in step 1 (fixing the commitment value $E_1$) to obtain a new transcript $(E_1, \varphi', R'_1, R'_2, q')$ and repeat until we can extract a witness $\alpha \in \text{End}(E_A)$ non-scalar from $(E_1, \varphi, R_1, R_2, q)$ and $(E_1, \varphi', R'_1, R'_2, q')$.
**Lemma 39.** Fix a challenge $\varphi: E_A \to E_2$ and let us write $D_\varphi := \prod_{i=1}^r \ell_i^{e_i}$, where $\ell_1 \le \dots \le \ell_r$ are distinct ordered primes and $e_1, \dots, e_r \in \mathbb{N}^*$. Then, the number of challenges $\varphi': E_A \to E_2'$ relatively bad to $\varphi$ is

$$O\left(\frac{\ell^e \mu(D_\varphi)}{D_\varphi^{1-\log(2)/\log\log(D_\varphi)}}\right),$$

with $\mu(D_\varphi) := \prod_{i=1}^r \ell_i^{e_i-1}(\ell_i+1)$.

*Proof.* $\varphi$ and $\varphi'$ relatively bad if their greatest common factor has degree $D \ge D_\varphi/\ell^e$. If we fix such a $D|D_\varphi$, then choosing $\varphi'$ is choosing a cyclic isogeny of degree $D_\varphi/D$ so there are $\mu(D_\varphi/D)$ possibilities. It follows that the number of challenges $\varphi'$ relatively bad to $\varphi$ is

$$ 
\begin{aligned}
N &\le \sum_{\substack{D|D_\varphi \\ D>D_\varphi/\ell^e}} \mu\left(\frac{D_\varphi}{D}\right) = \mu(D_\varphi) \sum_{\substack{D|D_\varphi \\ D>D_\varphi/\ell^e}} \frac{1}{\mu(D)} \le \mu(D_\varphi) \sum_{\substack{D|D_\varphi \\ D>D_\varphi/\ell^e}} \frac{1}{D} \\
&\le \frac{\ell^e \mu(D_\varphi)}{D_\varphi} \#\{D \in \mathbb{N}^* \mid D|D_\varphi \text{ and } D > D_\varphi/\ell^e\} \\
&\le \frac{\ell^e \mu(D_\varphi)}{D_\varphi} \#\{D \in \mathbb{N}^* \mid D|D_\varphi\} = \frac{\ell^e \mu(D_\varphi) d(D_\varphi)}{D_\varphi},
\end{aligned}
$$

where $d(D_\varphi)$ is the number of divisors of $d(D_\varphi)$. By [HW08, § 18.1, Theorem 317], we know that $d(D_\varphi) = O\left(D_\varphi^{\log(2)/\log\log(D_\varphi)}\right)$. The result follows. $\square$

Since $\ell^e = O(p^2)$, we choose $D_\varphi|T$ such that $D_\varphi \simeq p^{5/(2-2\log(2)/\log\log(p^{5/2}))}$, so that the proportion of challenges relatively bad to a given challenge is $O(p^{-1/2})$. This means in practice $D_\varphi \simeq p^{2.82}$ when $p$ has size 256 bits (to achieve $\lambda = 128$ bits of classical security). Hence the choice $T \simeq p^3$. Then, under this condition, we can adapt the proof of [HL10, Theorem 6.3.2] to prove knowledge soundness of RigorousSQIsignHD.

**Proposition 40.** *Assume that $D_\varphi > p^{5/(2-2\log(2)/\log\log(p^{5/2}))}$. Then the RigorousSQIsignHD identification protocol is a proof of knowledge for the relation $\mathcal{R}$ of Proposition 17 with knowledge error $O(p^{-1/2})$.*

*Proof.* As required by Definition 34, we construct a knowledge extractor $K$. Let $P^*$ be a prover with success probability $\epsilon$. Then $K$ is constructed as follows (as in [HL10, Theorem 6.3.2]). Fix $E_A$ a supersingular elliptic curve (as public key). Then $K$ executes the following algorithm:

1. Sample a seed $s \leftarrow \{0,1\}^*$ fixing the randomness of $P^*$, sample a challenge $\varphi$ and run $P^*(E_A, s, \varphi)$ repeatedly until the transcript $(E_1, \varphi, R_1, R_2, q)$ outputted by $P^*$ is accepted by the verifier and save $s$.

2. Sample another challenge $\varphi'$ and run $P^*(E_A, s, \varphi')$ with the same seed $s$ as in step 1 (fixing the commitment value $E_1$) to obtain a new transcript $(E_1, \varphi', R'_1, R'_2, q')$ and repeat until we can extract a witness $\alpha \in \text{End}(E_A)$ non-scalar from $(E_1, \varphi, R_1, R_2, q)$ and $(E_1, \varphi', R'_1, R'_2, q')$.
3. Break step 2 after $k$ iterations (to be determined) or return $\alpha$.

This algorithm may fail so $K$ may execute this algorithm multiple times. We determine $k$ to optimize the running time and the probability of failure of this algorithm. To do this, we specify how we can extract a witness in step 2. As in the previous knowledge soundness proof, $(R_1, R_2, q)$ and $(R'_1, R'_2, q')$ respectively provide an efficient representation of a $q$-isogeny $\sigma: E_1 \to E_2$ and a $q'$-isogeny $\sigma': E_2 \to E_1$, so we have an efficient representation of $\alpha := \hat{\phi}' \circ \sigma' \circ \tilde{\sigma} \circ \phi \in \text{End}(E_A)$. If $\phi$ and $\phi'$ are relatively good, then $\alpha$ is non-scalar by Lemma 38 and we have won.

By Lemma 39, since $D_{\phi} > p^{5/2(1-\log(2)/\log\log(p^{5/2}))}$ by assumption, the number of challenges $\phi'$ relatively bad to $\phi$ is bounded by $C\mu(D_{\phi})/\sqrt{p}$ for some constant $C > 0$.

Now consider the matrix $H$ whose rows are indexed by seeds $s$ for $P^*$, whose columns are indexed by challenges $\phi$ and such that $H(s, \phi)$ is the result 0 or 1 returned by the verifier when $P^*$ is run with $E_A, s$ and $\phi$. By assumption, the proportion of 1 in $H$ is $\varepsilon$. A row with a proportion of 1 bigger than $\varepsilon/2$ is called a heavy row. Let $R$ be the number of rows in $H$ (i.e. the number of possible seeds for $P^*$). Let $R'$ be the number of non-heavy rows. Then, the number of 1 located in a heavy rows is bigger than:

$$R\varepsilon\mu(D_{\phi}) - R'\frac{\varepsilon}{2}\mu(D_{\phi}) \geq R\varepsilon\mu(D_{\phi}) - R\frac{\varepsilon}{2}\mu(D_{\phi}) = R\frac{\varepsilon}{2}\mu(D_{\phi})$$

so at least half of the 1 are in heavy rows and the probability to fall in a heavy row at step 1 of the algorithm is $\geq 1/2$. Let $\phi$ be the challenge found at step 1. Now, at step 2, we are in the same row as in step 1 (since we fixed $s$). Assuming we are in a heavy row, the probability to find $\phi'$ that is not relatively bad to $\phi$ and such that $H(s, \phi') = 1$ is

$$P \geq \frac{\varepsilon/2\mu(D_{\phi}) - \mu(D_{\phi})C/\sqrt{p}}{\mu(D_{\phi})} = \frac{\varepsilon}{2} - \frac{C}{\sqrt{p}}.$$

In the following, we assume that $\varepsilon > 2C/\sqrt{p}$, so that $P > 0$. Then, the expected number of tries $t$ to succeed in step 2 is:

$$\mathbb{E}(t) = \frac{1}{P} \leq \frac{2}{\varepsilon - 2C/\sqrt{p}}.$$

Now we choose the time limit $k$ accordingly. By Markov's inequality, the probability that step 2 terminates within $k$ tries is

$$\mathbb{P}(t < k) = 1 - \mathbb{P}(t \geq k) \geq 1 - \frac{\mathbb{E}(t)}{k} \geq 1 - \frac{2}{k(\varepsilon - 2C/\sqrt{p})}$$

We choose $k := \lceil 4/(\varepsilon - 2C/\sqrt{p}) \rceil$, so that $\mathbb{P}(t < k) \geq 1/2$. This probability is conditional to the fact that we fall into a heavy row, which has probability $\geq 1/2$ as we saw. Hence, the probability that the algorithm succeeds is $\geq 1/2 \times 1/2 = 1/4$ so $K$ expects to repeat it 4 times to find a witness.
3. Break step 2 after $k$ iterations (to be determined) or return $\alpha$.

This algorithm may fail so $K$ may execute this algorithm multiple times. We determine $k$ to optimize the running time and the probability of failure of this algorithm. To do this, we specify how we can extract a witness in step 2. As in the previous knowledge soundness proof, $(R_1, R_2, q)$ and $(R'_1, R'_2, q')$ respectively provide an efficient representation of a $q$-isogeny $\sigma: E_1 \to E_2$ and a $q'$-isogeny $\sigma': E_2 \to E_1$, so we have an efficient representation of $\alpha := \hat{\phi}' \circ \sigma' \circ \tilde{\sigma} \circ \phi \in \mathrm{End}(E_A)$. If $\phi$ and $\phi'$ are relatively good, then $\alpha$ is non-scalar by Lemma 38 and we have won.

By Lemma 39, since $D_{\phi} > p^{5/2(1-\log(2)/\log\log(p^{5/2}))}$ by assumption, the number of challenges $\phi'$ relatively bad to $\phi$ is bounded by $C\mu(D_{\phi})/\sqrt{p}$ for some constant $C > 0$.

Now consider the matrix $H$ whose rows are indexed by seeds $s$ for $P^*$, whose columns are indexed by challenges $\phi$ and such that $H(s, \phi)$ is the result 0 or 1 returned by the verifier when $P^*$ is run with $E_A, s$ and $\phi$. By assumption, the proportion of 1 in $H$ is $\varepsilon$. A row with a proportion of 1 bigger than $\varepsilon/2$ is called a heavy row. Let $R$ be the number of rows in $H$ (i.e. the number of possible seeds for $P^*$). Let $R'$ be the number of non-heavy rows. Then, the number of 1 located in a heavy rows is bigger than:

$$R\varepsilon\mu(D_{\phi}) - R'\frac{\varepsilon}{2}\mu(D_{\phi}) \geq R\varepsilon\mu(D_{\phi}) - R\frac{\varepsilon}{2}\mu(D_{\phi}) = R\frac{\varepsilon}{2}\mu(D_{\phi})$$

so at least half of the 1 are in heavy rows and the probability to fall in a heavy row at step 1 of the algorithm is $\geq 1/2$. Let $\phi$ be the challenge found at step 1. Now, at step 2, we are in the same row as in step 1 (since we fixed $s$). Assuming we are in a heavy row, the probability to find $\phi'$ that is not relatively bad to $\phi$ and such that $H(s, \phi') = 1$ is

$$P \geq \frac{\varepsilon/2\mu(D_{\phi}) - \mu(D_{\phi})C/\sqrt{p}}{\mu(D_{\phi})} = \frac{\varepsilon}{2} - \frac{C}{\sqrt{p}}.$$

In the following, we assume that $\varepsilon > 2C/\sqrt{p}$, so that $P > 0$. Then, the expected number of tries $t$ to succeed in step 2 is:

$$\mathbb{E}(t) = \frac{1}{P} \leq \frac{2}{\varepsilon - 2C/\sqrt{p}}.$$

Now we choose the time limit $k$ accordingly. By Markov's inequality, the probability that step 2 terminates within $k$ tries is

$$\mathbb{P}(t < k) = 1 - \mathbb{P}(t \geq k) \geq 1 - \frac{\mathbb{E}(t)}{k} \geq 1 - \frac{2}{k(\varepsilon - 2C/\sqrt{p})}$$

We choose $k := \lceil 4/(\varepsilon - 2C/\sqrt{p}) \rceil$, so that $\mathbb{P}(t < k) \geq 1/2$. This probability is conditional to the fact that we fall into a heavy row, which has probability $\geq 1/2$ as we saw. Hence, the probability that the algorithm succeeds is $\geq 1/2 \times 1/2 = 1/4$ so $K$ expects to repeat it 4 times to find a witness.
Now we estimate the running time of the algorithm. Step 1 is expected to terminate after $1/\epsilon$ iterations and step 2 after $k = \lceil 4/(\epsilon - 2C/\sqrt{p}) \rceil$ iterations, so the total time complexity is

$$O\left(\frac{1}{\epsilon} + \frac{4}{\epsilon - 2C/\sqrt{p}}\right) = O\left(\frac{5}{\epsilon - 2C/\sqrt{p}}\right).$$

RigorousSQIsignHD being complete, we conclude that it is a proof of knowledge for $\mathcal{R}$ with knowledge error $\kappa := 2C/\sqrt{p} = O(p^{-1/2})$. $\square$

## D.2 Rigorous zero-knowledge property

To prove the zero-knowledge property of RigorousSQIsignHD, we introduce an oracle generating uniformly random isogenies of bounded degree without any other constraint on the degree or assumption on the distribution of the codomain, unlike the RUGDIO introduced for FastSQIsignHD in Section 5.2. Hence this oracle is more natural than the previous one. However, as previously, to our knowledge, there is no efficient algorithm implementing such an oracle and it is believed that access to such an oracle does not affect the hardness of the underlying problem (the endomorphism ring problem, see Section 5.3).

**Definition 41.** A random any degree isogeny oracle (RADIO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and returning an efficient representation of an isogeny $\sigma: E \to E'$, which is uniformly random among the isogenies of degree $q < \ell^e$ with domain $E$.

To prove zero-knowledge, not only the distribution of the isogeny should be uniform, but also the distribution of its codomain. Unfortunately, the RADIO does not determine the distribution of codomains. The following theorem (proved in Appendix E.6) solves this issue when $\ell^e$ is big enough. We need $\ell^e = \Theta(p^2)$ to ensure a statistical distance of $O(p^{-1/2})$ to the uniform distribution, hence a security level of $\lambda$ (since $p = \Theta(2^{2\lambda})$).

**Theorem 42.** Let $\epsilon \in ]0, 2]$. Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve and $\pi$ be the probability distribution of codomains $E'$ (up to $\overline{\mathbb{F}}_p$-isomorphism) of isogenies $\sigma: E \to E'$ chosen uniformly at random among isogenies of degree $\deg(\sigma) \le p^{1+\epsilon}$. Let $U$ be the uniform distribution of supersingular elliptic curves over $\mathbb{F}_{p^2}$ (up to $\overline{\mathbb{F}}_p$-isomorphism). Then, the statistical distance $d_{TV}$ between the two distributions satisfies $d_{TV}(U, \pi) = O(p^{-\epsilon/2})$.

**Theorem 43.** The RigorousSQIsignHD protocol is statistically honest-verifier zero knowledge in the RADIO model (provided $\ell^e = \Theta(p^2)$). In other words, there exists a random polynomial time simulator $S$ with black-box access to a RADIO that simulates transcripts $(E_1, \varphi, R)$ with a statistically indistinguishable distribution from the transcripts of the RigorousSQIsignHD identification protocol.
Now we estimate the running time of the algorithm. Step 1 is expected to terminate after $1/\epsilon$ iterations and step 2 after $k = \lceil 4/(\epsilon - 2C/\sqrt{p}) \rceil$ iterations, so the total time complexity is

$$O\left(\frac{1}{\epsilon} + \frac{4}{\epsilon - 2C/\sqrt{p}}\right) = O\left(\frac{5}{\epsilon - 2C/\sqrt{p}}\right).$$

RigorousSQIsignHD being complete, we conclude that it is a proof of knowledge for $\mathcal{R}$ with knowledge error $\kappa := 2C/\sqrt{p} = O(p^{-1/2})$. $\square$

## D.2 Rigorous zero-knowledge property

To prove the zero-knowledge property of RigorousSQIsignHD, we introduce an oracle generating uniformly random isogenies of bounded degree without any other constraint on the degree or assumption on the distribution of the codomain, unlike the RUGDIO introduced for FastSQIsignHD in Section 5.2. Hence this oracle is more natural than the previous one. However, as previously, to our knowledge, there is no efficient algorithm implementing such an oracle and it is believed that access to such an oracle does not affect the hardness of the underlying problem (the endomorphism ring problem, see Section 5.3).

**Definition 41.** A random any degree isogeny oracle (RADIO) is an oracle taking as input a supersingular elliptic curve $E$ defined over $\mathbb{F}_{p^2}$ and returning an efficient representation of an isogeny $\sigma: E \to E'$, which is uniformly random among the isogenies of degree $q < \ell^e$ with domain $E$.

To prove zero-knowledge, not only the distribution of the isogeny should be uniform, but also the distribution of its codomain. Unfortunately, the RADIO does not determine the distribution of codomains. The following theorem (proved in Appendix E.6) solves this issue when $\ell^e$ is big enough. We need $\ell^e = \Theta(p^2)$ to ensure a statistical distance of $O(p^{-1/2})$ to the uniform distribution, hence a security level of $\lambda$ (since $p = \Theta(2^{2\lambda})$).

**Theorem 42.** Let $\epsilon \in ]0, 2]$. Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve and $\pi$ be the probability distribution of codomains $E'$ (up to $\overline{\mathbb{F}}_p$-isomorphism) of isogenies $\sigma: E \to E'$ chosen uniformly at random among isogenies of degree $\deg(\sigma) \le p^{1+\epsilon}$. Let $U$ be the uniform distribution of supersingular elliptic curves over $\mathbb{F}_{p^2}$ (up to $\overline{\mathbb{F}}_p$-isomorphism). Then, the statistical distance $d_{TV}$ between the two distributions satisfies $d_{TV}(U, \pi) = O(p^{-\epsilon/2})$.

**Theorem 43.** The RigorousSQIsignHD protocol is statistically honest-verifier zero knowledge in the RADIO model (provided $\ell^e = \Theta(p^2)$). In other words, there exists a random polynomial time simulator $S$ with black-box access to a RADIO that simulates transcripts $(E_1, \varphi, R)$ with a statistically indistinguishable distribution from the transcripts of the RigorousSQIsignHD identification protocol.
Proof. First, we explain how to construct the simulator $\mathcal{S}$. As for Fast-SQIsignHD, the simulator starts by generating a challenge $\varphi' : E_A \to E'_2$ and applies the RADIO on entry $E'_2$ to get an efficient representation of a dual response isogeny $\hat{\sigma}' : E'_2 \to E'_1$. As explained in the proof of Theorem 21, the simulator can use the efficient representation of $\hat{\sigma}'$ to compute $R' := (q', \sigma'(P_1), \sigma'(P_2))$ in polynomial time, where $(P_1, P_2)$ is a canonical basis of $E'_1[\ell^f]$. $\mathcal{S}$ finally outputs $(E'_1, \varphi', R')$.

We now prove that the transcripts $(E'_1, \varphi', R')$ of $\mathcal{S}$ are statistically indistinguishable from the transcripts $(E_1, \varphi, R)$ of the RigorousSQIsignHD identification protocol. By construction, $\varphi$ and $\varphi'$ have the same distribution. Given $E'_2$, by the definition of the RADIO, $\hat{\sigma}'$ is uniform among isogenies of degree $q' \le \ell^e$ with domain $E'_2$, so $E'_1$ is statistically close to uniformly random in the supersingular isogeny graph by Theorem 42. Besides, $E_1$ is statistically close to uniformly random as well, by Proposition 29.

Finally, conditionally to $E'_1$ and $E'_2$, $\hat{\sigma}'$ (represented by $R'$) is uniformly random among the isogenies $E'_2 \to E'_1$ of degree $q' < \ell^e$ by the definition of the RADIO. 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 isogenies $E'_2 \to E'_1$ of degree $q' < \ell^e$. By construction (see Section 4.2), conditionally to $E_1$ and $E_2$, $\sigma$ has the same distribution. This completes the proof. $\square$

# E Omitted proofs

## E.1 Kani's lemma (Lemma 4)

**Lemma 4 (Kani).** Consider the following $(a, b)$-isogeny diamond

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

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$.

If $a$ and $b$ are coprime, the kernel of $F$ is

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

Proof. Here we use, without proof, the main properties of the dual abelian variety with respect to polarisations (see for instance [Kan14, § 11]). It is a classical
*Proof.* First, we explain how to construct the simulator $\mathcal{S}$. As for Fast-SQIsignHD, the simulator starts by generating a challenge $\varphi' : E_A \to E'_2$ and applies the RADIO on entry $E'_2$ to get an efficient representation of a dual response isogeny $\hat{\sigma}' : E'_2 \to E'_1$. As explained in the proof of Theorem 21, the simulator can use the efficient representation of $\hat{\sigma}'$ to compute $R' := (q', \sigma'(P_1), \sigma'(P_2))$ in polynomial time, where $(P_1, P_2)$ is a canonical basis of $E'_1[\ell^f]$. $\mathcal{S}$ finally outputs $(E'_1, \varphi', R')$.

We now prove that the transcripts $(E'_1, \varphi', R')$ of $\mathcal{S}$ are statistically indistinguishable from the transcripts $(E_1, \varphi, R)$ of the RigorousSQIsignHD identification protocol. By construction, $\varphi$ and $\varphi'$ have the same distribution. Given $E'_2$, by the definition of the RADIO, $\hat{\sigma}'$ is uniform among isogenies of degree $q' \le \ell^e$ with domain $E'_2$, so $E'_1$ is statistically close to uniformly random in the supersingular isogeny graph by Theorem 42. Besides, $E_1$ is statistically close to uniformly random as well, by Proposition 29.

Finally, conditionally to $E'_1$ and $E'_2$, $\hat{\sigma}'$ (represented by $R'$) is uniformly random among the isogenies $E'_2 \to E'_1$ of degree $q' < \ell^e$ by the definition of the RADIO. 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 isogenies $E'_2 \to E'_1$ of degree $q' < \ell^e$. By construction (see Section 4.2), conditionally to $E_1$ and $E_2$, $\sigma$ has the same distribution. This completes the proof. $\square$

# E Omitted proofs

## E.1 Kani's lemma (Lemma 4)

**Lemma 4 (Kani).** Consider the following $(a, b)$-isogeny diamond

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

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$.

If $a$ and $b$ are coprime, the kernel of $F$ is

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

*Proof.* Here we use, without proof, the main properties of the dual abelian variety with respect to polarisations (see for instance [Kan14, § 11]). It is a classical
result that the dual of a matrix for the product polarisations is the transpose of the matrix obtained after dualizing the coefficients and that dualization is an involutive operation, so that

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

Hence

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

with $\tilde{\varphi}\varphi + \tilde{\psi}\psi = [a]_A + [b]_A = [d]_A$ since $\varphi$ is an $a$-isogeny and $\psi$ is a $b$-isogeny. Similarly, we get $\tilde{\psi}'\psi' + \tilde{\varphi}'\varphi' = [d]_{A'}$, so that $\psi'\tilde{\psi}' + \varphi'\tilde{\varphi}' = [d]_{B'}$ after dualizing (the dual being anti-commutative and the dual of an integer being an integer). Clearly, $\psi'\varphi - \varphi'\psi = 0$ since we have an isogeny diamond and we obtain $\tilde{\varphi}\tilde{\psi}' - \tilde{\psi}\tilde{\varphi}' = 0$ by dualizing the preceding equality. Hence, $\tilde{F}F = [d]_{A \times B'}$ so $F$ is a $d$-isogeny.

If $x \in B[d]$, we have

$$ \begin{aligned} F(\tilde{\varphi}(x), \psi'(x)) &= (\varphi \circ \tilde{\varphi}(x) + \tilde{\psi}' \circ \psi'(x), -\psi \circ \tilde{\varphi}(x) + \tilde{\varphi}' \circ \psi'(x)) \\ &= ([a]x + [b]x, 0) = ([d]x, 0) = (0, 0) \end{aligned} $$

where we used the fact that $\psi \circ \tilde{\varphi} = \tilde{\varphi}' \circ \psi'$. Indeed, $\psi'\varphi = \varphi'\psi$, which implies that $[a]\psi \circ \tilde{\varphi} = [a]\tilde{\varphi}' \circ \psi'$ after multiplying on the right by $\tilde{\varphi}$ and on the left by $\tilde{\varphi}'$, so that $\psi \circ \tilde{\varphi} = \tilde{\varphi}' \circ \psi'$ since $[a]_{A'}$ is an isogeny (it has finite kernel).

It follows that $\ker(F)$ contains the subgroup:

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

Since $\tilde{\varphi}$ and $\psi'$ are $a$ and $b$-isogenies respectively, we have $\ker(\tilde{\varphi}) \subseteq B[a]$ and $\ker(\psi') \subseteq B[b]$. It follows that $\ker(\tilde{\varphi}) \cap \ker(\psi') = \{0\}$, when $a$ and $b$ are coprime, so that $x \in B \mapsto (\tilde{\varphi}(x), \psi'(x))$ is injective and $\#S = \#B[d]$. Since $d$ is prime to the characteristic of the field, we have $\#B[d] = d^{2g}$ with $g := \dim(B)$. $A$ being isogenous to $B$ and $B'$, we also have $g = \dim(A) = \dim(B')$ and $\deg(F) = d^{\dim(A \times B')} = d^{2g}$ since $F$ is a $d$-isogeny, so $F$ is separable and $\#\ker(F) = \deg(F) = d^{2g}$. Hence, $\ker(F) = S$ when $a$ and $b$ are coprime and the proof is complete. $\square$

Actually, we can also prove a weak converse of Kani's lemma.

**Lemma 44.** Let $F: A \times B' \to B \times A'$ be a $d$-isogeny (for the product principal polarizations), where $d$ is prime to the characteristic of the base field. Write $F$ as a matrix:

$$ F := \begin{pmatrix} \varphi & \tilde{\psi}' \\ -\psi & \tilde{\varphi}' \end{pmatrix} $$
result that the dual of a matrix for the product polarisations is the transpose of the matrix obtained after dualizing the coefficients and that dualization is an involutive operation, so that

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

Hence

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

with $\tilde{\varphi}\varphi + \tilde{\psi}\psi = [a]_A + [b]_A = [d]_A$ since $\varphi$ is an $a$-isogeny and $\psi$ is a $b$-isogeny. Similarly, we get $\tilde{\psi}'\psi' + \tilde{\varphi}'\varphi' = [d]_{A'}$, so that $\psi'\tilde{\psi}' + \varphi'\tilde{\varphi}' = [d]_{B'}$ after dualizing (the dual being anti-commutative and the dual of an integer being an integer). Clearly, $\psi'\varphi - \varphi'\psi = 0$ since we have an isogeny diamond and we obtain $\tilde{\varphi}\tilde{\psi}' - \tilde{\psi}\tilde{\varphi}' = 0$ by dualizing the preceding equality. Hence, $\tilde{F}F = [d]_{A \times B'}$ so $F$ is a $d$-isogeny.

If $x \in B[d]$, we have

$$ \begin{aligned} F(\tilde{\varphi}(x), \psi'(x)) &= (\varphi \circ \tilde{\varphi}(x) + \tilde{\psi}' \circ \psi'(x), -\psi \circ \tilde{\varphi}(x) + \tilde{\varphi}' \circ \psi'(x)) \\ &= ([a]x + [b]x, 0) = ([d]x, 0) = (0, 0) \end{aligned} $$

where we used the fact that $\psi \circ \tilde{\varphi} = \tilde{\varphi}' \circ \psi'$. Indeed, $\psi'\varphi = \varphi'\psi$, which implies that $[a]\psi \circ \tilde{\varphi} = [a]\tilde{\varphi}' \circ \psi'$ after multiplying on the right by $\tilde{\varphi}$ and on the left by $\tilde{\varphi}'$, so that $\psi \circ \tilde{\varphi} = \tilde{\varphi}' \circ \psi'$ since $[a]_{A'}$ is an isogeny (it has finite kernel).

It follows that $\ker(F)$ contains the subgroup:

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

Since $\tilde{\varphi}$ and $\psi'$ are $a$ and $b$-isogenies respectively, we have $\ker(\tilde{\varphi}) \subseteq B[a]$ and $\ker(\psi') \subseteq B[b]$. It follows that $\ker(\tilde{\varphi}) \cap \ker(\psi') = \{0\}$, when $a$ and $b$ are coprime, so that $x \in B \mapsto (\tilde{\varphi}(x), \psi'(x))$ is injective and $\#S = \#B[d]$. Since $d$ is prime to the characteristic of the field, we have $\#B[d] = d^{2g}$ with $g := \dim(B)$. $A$ being isogenous to $B$ and $B'$, we also have $g = \dim(A) = \dim(B')$ and $\deg(F) = d^{\dim(A \times B')} = d^{2g}$ since $F$ is a $d$-isogeny, so $F$ is separable and $\#\ker(F) = \deg(F) = d^{2g}$. Hence, $\ker(F) = S$ when $a$ and $b$ are coprime and the proof is complete. $\square$

Actually, we can also prove a weak converse of Kani's lemma.

**Lemma 44.** Let $F: A \times B' \to B \times A'$ be a $d$-isogeny (for the product principal polarizations), where $d$ is prime to the characteristic of the base field. Write $F$ as a matrix:

$$ F := \begin{pmatrix} \varphi & \tilde{\psi}' \\ -\psi & \tilde{\varphi}' \end{pmatrix} $$
and suppose $\varphi$ is an a-isogeny. Then $\varphi, \varphi', \psi, \psi'$ form the following (a, b)-isogeny diamond with $a+b=d$:

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

*Proof.* Since $F$ is a $d$-isogeny, we have $\tilde{F} \circ F = [d]$, so we get that $\psi' \circ \varphi = \varphi' \circ \psi$, $\tilde{\varphi} \circ \varphi + \tilde{\psi} \circ \psi = [d]$ and $\psi' \circ \tilde{\psi}' + \varphi' \circ \tilde{\varphi}' = [d]$. Since, $\varphi$ is an $a$-isogeny, we have $\tilde{\varphi} \circ \varphi = [a]$, so $\tilde{\psi} \circ \psi = [b]$ and $\psi$ is a $b$-isogeny.

We also have $F \circ \tilde{F} = [d]$, so that $\varphi \circ \tilde{\varphi} + \psi' \circ \tilde{\psi}' = [d]$ and we get that $\psi'$ is a $b$-isogeny. Then, the equality $\psi' \circ \tilde{\psi}' + \varphi' \circ \tilde{\varphi}' = [d]$ ensures that $\varphi'$ is an $a$-isogeny. This completes the proof. $\square$

**Remark 45.** We obtain the same result if we suppose that any of the isogenies $\varphi', \psi$ and $\psi'$ is an $a$ or $b$-isogeny.

## E.2 Finding a uniformly random tight response ideal (Lemmas 11 and 12)

**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$.

*Proof.* By Cholesky decomposition theorem, there exists a matrix $B \in GL_k(\mathbb{R})$ such that $f(x) = \|Bx\|^2$ for all $x \in \mathbb{R}^k$, $\|\cdot\|$ being the Euclidean norm. Let $\Lambda := \Lambda(B)$ be the lattice generated by the columns of $B$. We want to sample in $B(0, \sqrt{\rho}) \cap \Lambda$ with uniform distribution. Let $(b_1, \dots, b_k)$ be an LLL-reduced basis of $\Lambda$. Let $\nu := \sqrt{k}\|b_k\|/2$ and consider the following sampling algorithm:

1. Sample $v \in B(0, \sqrt{\rho} + \nu)$ uniformly at random.

2. Find a solution $\lambda(v) \in \Lambda$ to the closest vector problem for $v$.

3. If $\lambda(v) \in B(0, \sqrt{\rho})$, return $\lambda(v)$; else restart.

We prove that the output $\lambda(v)$ has uniform distribution in $B(0, \sqrt{\rho}) \cap \Lambda$. Let $\mathcal{V} := \{v \in \mathbb{R}^k \mid \|v\| = \min_{\lambda \in \Lambda} \|v + \lambda\|\}$ be the Voronoi cell at the origin. Then, the closest vector $\lambda(v)$ satisfies $v \in \mathcal{V} + \lambda(v)$ and $\lambda(v)$ is unique when $v$ is not at the border of a Voronoi cell, so it is unique with probability 1. Hence, for all $u \in B(0, \sqrt{\rho}) \cap \Lambda$,

$$ \mathbb{P}(\lambda(v) = u) = \frac{\mathrm{Vol}((\mathcal{V} + u) \cap B(0, \sqrt{\rho} + v))}{\mathrm{Vol}(B(0, \sqrt{\rho} + v))}. $$
and suppose $\varphi$ is an a-isogeny. Then $\varphi, \varphi', \psi, \psi'$ form the following (a, b)-isogeny diamond with $a + b = d$:

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

*Proof.* Since $F$ is a $d$-isogeny, we have $\tilde{F} \circ F = [d]$, so we get that $\psi' \circ \varphi = \varphi' \circ \psi$, $\tilde{\varphi} \circ \varphi + \tilde{\psi} \circ \psi = [d]$ and $\psi' \circ \tilde{\psi}' + \varphi' \circ \tilde{\varphi}' = [d]$. Since, $\varphi$ is an $a$-isogeny, we have $\tilde{\varphi} \circ \varphi = [a]$, so $\tilde{\psi} \circ \psi = [b]$ and $\psi$ is a $b$-isogeny.

We also have $F \circ \tilde{F} = [d]$, so that $\varphi \circ \tilde{\varphi} + \psi' \circ \tilde{\psi}' = [d]$ and we get that $\psi'$ is a $b$-isogeny. Then, the equality $\psi' \circ \tilde{\psi}' + \varphi' \circ \tilde{\varphi}' = [d]$ ensures that $\varphi'$ is an $a$-isogeny. This completes the proof. $\square$

**Remark 45.** We obtain the same result if we suppose that any of the isogenies $\varphi', \psi$ and $\psi'$ is an $a$ or $b$-isogeny.

## E.2 Finding a uniformly random tight response ideal (Lemmas 11 and 12)

**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$.

*Proof.* By Cholesky decomposition theorem, there exists a matrix $B \in GL_k(\mathbb{R})$ such that $f(x) = \|Bx\|^2$ for all $x \in \mathbb{R}^k$, $\|\cdot\|$ being the Euclidean norm. Let $\Lambda := \Lambda(B)$ be the lattice generated by the columns of $B$. We want to sample in $B(0, \sqrt{\rho}) \cap \Lambda$ with uniform distribution. Let $(b_1, \dots, b_k)$ be an LLL-reduced basis of $\Lambda$. Let $\nu := \sqrt{k}\|b_k\|/2$ and consider the following sampling algorithm:

1. Sample $v \in B(0, \sqrt{\rho} + \nu)$ uniformly at random.

2. Find a solution $\lambda(v) \in \Lambda$ to the closest vector problem for $v$.

3. If $\lambda(v) \in B(0, \sqrt{\rho})$, return $\lambda(v)$; else restart.

We prove that the output $\lambda(v)$ has uniform distribution in $B(0, \sqrt{\rho}) \cap \Lambda$. Let $\mathcal{V} := \{v \in \mathbb{R}^k \mid \|v\| = \min_{\lambda \in \Lambda} \|v + \lambda\|\}$ be the Voronoi cell at the origin. Then, the closest vector $\lambda(v)$ satisfies $v \in \mathcal{V} + \lambda(v)$ and $\lambda(v)$ is unique when $v$ is not at the border of a Voronoi cell, so it is unique with probability 1. Hence, for all $u \in B(0, \sqrt{\rho}) \cap \Lambda$,

$$ \mathbb{P}(\lambda(v) = u) = \frac{\mathrm{Vol}((\mathcal{V} + u) \cap B(0, \sqrt{\rho} + v))}{\mathrm{Vol}(B(0, \sqrt{\rho} + v))}. $$
Let $\mu := \inf\{r > 0 \mid \forall v \in \mathbb{R}^k, \exists \lambda \in \Lambda, \|x - \lambda\| \le r\}$ be the covering radius of $\Lambda$. Then $\mathcal{V} \subseteq B(0, \mu)$ and $\mu \le \sqrt{k}\lambda_k/2$ where $\lambda_k$ is the last minimum of $\Lambda$ (this is a classical result, see for instance [Mic16, Exercise 11]), so that $\mu \le \nu$. It follows that $\mathcal{V} + u \subseteq B(0, \sqrt{\rho} + \nu)$ for all $u \in B(0, \sqrt{\rho}) \cap \Lambda$. Hence

$$ \mathbb{P}(\lambda(v) = u) = \frac{\mathrm{Vol}(\mathcal{V} + u)}{\mathrm{Vol}(B(0, \sqrt{\rho} + \nu))} = \frac{\mathrm{Vol}(\mathcal{V})}{\mathrm{Vol}(B(0, \sqrt{\rho} + \nu))}. $$

This quantity does not depend on $u$ so $\lambda(v)$ has uniform distribution.

We finally check that the algorithm terminates after an expected polynomial number of steps in $\log(\rho)$ and the length of $f$. Indeed, when $v$ is uniform in $B(0, \sqrt{\rho} + \nu)$, we have

$$ \mathbb{P}(\|\lambda(v)\| \le \sqrt{\rho}) \ge \mathbb{P}(\lambda(v) = 0) \ge \frac{\mathrm{Vol}(B(0, \lambda_1/2))}{\mathrm{Vol}(B(0, \sqrt{\rho} + \nu))} = \left( \frac{\lambda_1}{2\sqrt{\rho} + \sqrt{k}\|b_k\|} \right)^k, $$

where $\lambda_1$ is the first minimum of $\Lambda$. Since $f$ is integral, we have $\|b_k\| \ge \dots \ge \|b_1\| \ge \lambda_1 \ge 1$ and since $(b_1, \dots, b_k)$ is LLL-reduced, we have:

$$ \|b_1\| \cdots \|b_k\| \le 2^{k(k-1)/4} \mathrm{Covol}(\Lambda) = 2^{k(k-1)/4} \mathrm{disc}(f), $$

so $\|b_k\| \le 2^{k(k-1)/4} \mathrm{disc}(f)$. Hence, the algorithm terminates after an expected number of steps $O(1/\log \mathbb{P}(\|\lambda(v)\| \le \sqrt{\rho}))$, a quantity that is polynomial in $\log(\rho)$, $\log(\mathrm{disc}(f))$ (itself polynomial in the length of $f$) and $k$. We conclude that the algorithm has the desired complexity, since the LLL algorithm has polynomial time complexity and the closest vector problem (used in step 2 of the algorithm) can be solved in the desired time complexity. $\square$

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

*Proof.* Consider the canonical embedding $\iota : \mathcal{B}_{p,\infty} \to \mathbb{R}^4$:

$$ 1 \mapsto (1, 0, 0, 0), i \mapsto (0, \sqrt{q_0}, 0, 0), j \mapsto (0, 0, \sqrt{p}, 0), k \mapsto (0, 0, 0, \sqrt{q_0 p}), $$

where $q_0 := \mathrm{ndr}(i)$. $\iota$ is an isometry in the following sense $\|\iota(\alpha)\|^2 = \mathrm{ndr}(\alpha)$ for all $\alpha \in \mathcal{B}_{p,\infty}$, where $\|\cdot\|$ is the Euclidean norm of $\mathbb{R}^4$. By Minkowski's second theorem, the successive minima of the lattice $\iota(J)$ satisfy

$$ \lambda_1 \cdots \lambda_4 \le 2^4 \frac{\mathrm{Covol}(\iota(J))}{\mathrm{Vol}(B(0, 1))} = \frac{32}{\pi^2} \mathrm{Covol}(\iota(J)). \quad (3) $$
Let $\mu := \inf\{r > 0 \mid \forall v \in \mathbb{R}^k, \exists \lambda \in \Lambda, \|x - \lambda\| \le r\}$ be the covering radius of $\Lambda$. Then $\mathcal{V} \subseteq B(0, \mu)$ and $\mu \le \sqrt{k}\lambda_k/2$ where $\lambda_k$ is the last minimum of $\Lambda$ (this is a classical result, see for instance [Mic16, Exercise 11]), so that $\mu \le \nu$. It follows that $\mathcal{V} + u \subseteq B(0, \sqrt{\rho} + \nu)$ for all $u \in B(0, \sqrt{\rho}) \cap \Lambda$. Hence

$$ \mathbb{P}(\lambda(v) = u) = \frac{\mathrm{Vol}(\mathcal{V} + u)}{\mathrm{Vol}(B(0, \sqrt{\rho} + \nu))} = \frac{\mathrm{Vol}(\mathcal{V})}{\mathrm{Vol}(B(0, \sqrt{\rho} + \nu))}. $$

This quantity does not depend on $u$ so $\lambda(v)$ has uniform distribution.

We finally check that the algorithm terminates after an expected polynomial number of steps in $\log(\rho)$ and the length of $f$. Indeed, when $v$ is uniform in $B(0, \sqrt{\rho} + \nu)$, we have

$$ \mathbb{P}(\|\lambda(v)\| \le \sqrt{\rho}) \ge \mathbb{P}(\lambda(v) = 0) \ge \frac{\mathrm{Vol}(B(0, \lambda_1/2))}{\mathrm{Vol}(B(0, \sqrt{\rho} + \nu))} = \left( \frac{\lambda_1}{2\sqrt{\rho} + \sqrt{k}\|b_k\|} \right)^k, $$

where $\lambda_1$ is the first minimum of $\Lambda$. Since $f$ is integral, we have $\|b_k\| \ge \dots \ge \|b_1\| \ge \lambda_1 \ge 1$ and since $(b_1, \dots, b_k)$ is LLL-reduced, we have:

$$ \|b_1\| \cdots \|b_k\| \le 2^{k(k-1)/4} \mathrm{Covol}(\Lambda) = 2^{k(k-1)/4} \mathrm{disc}(f), $$

so $\|b_k\| \le 2^{k(k-1)/4} \mathrm{disc}(f)$. Hence, the algorithm terminates after an expected number of steps $O(1/\log \mathbb{P}(\|\lambda(v)\| \le \sqrt{\rho}))$, a quantity that is polynomial in $\log(\rho)$, $\log(\mathrm{disc}(f))$ (itself polynomial in the length of $f$) and $k$. We conclude that the algorithm has the desired complexity, since the LLL algorithm has polynomial time complexity and the closest vector problem (used in step 2 of the algorithm) can be solved in the desired time complexity. $\square$

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

*Proof.* Consider the canonical embedding $\iota : \mathcal{B}_{p,\infty} \to \mathbb{R}^4$:

$$ 1 \mapsto (1, 0, 0, 0), i \mapsto (0, \sqrt{q_0}, 0, 0), j \mapsto (0, 0, \sqrt{p}, 0), k \mapsto (0, 0, 0, \sqrt{q_0 p}), $$

where $q_0 := \mathrm{ndr}(i)$. $\iota$ is an isometry in the following sense $\|\iota(\alpha)\|^2 = \mathrm{ndr}(\alpha)$ for all $\alpha \in \mathcal{B}_{p,\infty}$, where $\|\cdot\|$ is the Euclidean norm of $\mathbb{R}^4$. By Minkowski's second theorem, the successive minima of the lattice $\iota(J)$ satisfy

$$ \lambda_1 \cdots \lambda_4 \le 2^4 \frac{\mathrm{Covol}(\iota(J))}{\mathrm{Vol}(B(0, 1))} = \frac{32}{\pi^2} \mathrm{Covol}(\iota(J)). \quad (3) $$
But we have $\mathrm{Covol}(\iota(\mathcal{O})) = \mathrm{discrd}(\mathcal{O})/4$. Indeed, if $(\alpha_1, \dots, \alpha_4)$ is a basis of $\mathcal{O}$, we get that

$$ \begin{align*} \mathrm{Covol}(\iota(\mathcal{O})) &= \sqrt{|\det(\langle\iota(\alpha_i), \iota(\alpha_j)\rangle)_{1\le i,k\le 4}|} \\ &= \sqrt{|\det\left(\frac{1}{2}(\mathrm{nrd}(\alpha_i + \alpha_j) - \mathrm{nrd}(\alpha_i) - \mathrm{nrd}(\alpha_j))\right)_{1\le i,k\le 4}|} \\ &= \sqrt{|\det\left(\frac{1}{2}\mathrm{Tr}(\alpha_i \overline{\alpha_j})\right)_{1\le i,k\le 4}|} = \frac{1}{4}\mathrm{discrd}(\mathcal{O}) \end{align*} $$

Besides, by [Voi20, Theorem 15.5.5], $\mathrm{discrd}(\mathcal{O}) = \mathrm{disc}(\mathcal{B}_{p,\infty}) = p$ since $\mathcal{O}$ is a maximal order. We then have

$$ \mathrm{Covol}(\iota(J)) = [\mathcal{O} : J] \mathrm{Covol}(\iota(\mathcal{O})) = [\mathcal{O} : J] \mathrm{discrd}(\mathcal{O})/4 = \mathrm{nrd}(J)^2 p/4 $$

It follows that the minimal value of $q_J$ is

$$ q_J(\alpha) = \lambda_1^2 / \mathrm{nrd}(J) \le \frac{2\sqrt{2p}}{\pi}. \quad \square $$

### E.3 Dividing the higher dimensional isogeny in two (Proposition 13)

**Proposition 13.** Let $d := d_1d_2$ prime to $p$ and $F : \mathcal{A} \to \mathcal{B}$ be a $d$-isogeny between abelian varieties defined over $\overline{\mathbb{F}}_p$. Then:

(i) We can always decompose $F = F_2 \circ F_1$, where $F_1$ is a $d_1$-isogeny and $F_2$ is a $d_2$-isogeny.

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

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

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

In order to prove the proposition, we need two intermediary results.

**Lemma 46.** If $F : (\mathcal{A}, \lambda_\mathcal{A}) \to (\mathcal{B}, \lambda_\mathcal{B})$ is a $d$-isogeny between principally polarized abelian varieties, then $\ker(F)$ is a maximal isotropic subgroup of $\mathcal{A}[d]$ (for the $d$-th Weil pairing).

*Proof.* The inclusion $\ker(F) \subseteq \mathcal{A}[d]$ immediately follows from $\tilde{F} \circ F = [d]$. Now we prove that $\ker(F)$ is isotropic. Let $x, y \in \ker(F)$. Since $\tilde{F}$ is surjective, there exists $y' \in \mathcal{B}$ such that $y = \tilde{F}(y')$. Let $\lambda_\mathcal{A}$ and $\lambda_\mathcal{B}$ be the principal polarisations on $\mathcal{A}$ and $\mathcal{B}$ respectively, $e_d^{\lambda_\mathcal{A}}$ and $e_d^{\lambda_\mathcal{B}}$ the associated Weil pairings. Then

$$ e_d^{\lambda_\mathcal{A}}(x, y) = e_d(x, \lambda_\mathcal{A} \circ \tilde{F}(y')) = e_d(x, \tilde{F} \circ \lambda_\mathcal{B}(y')) = e_d(F(x), \lambda_\mathcal{B}(y')) = 1. $$

Then $\ker(F)$ is isotropic. Since $F$ is a $d$-isogeny, it has degree $d^g$ with $g := \dim(\mathcal{A})$, and $\#\ker(F) = d^g$ since $F$ is separable. So $\ker(F)$ is maximal isotropic. $\square$
But we have $\mathrm{Covol}(\iota(\mathcal{O})) = \mathrm{discrd}(\mathcal{O})/4$. Indeed, if $(\alpha_1, \dots, \alpha_4)$ is a basis of $\mathcal{O}$, we get that

$$ \begin{aligned} \mathrm{Covol}(\iota(\mathcal{O})) &= \sqrt{|\det(\langle\iota(\alpha_i), \iota(\alpha_j)\rangle)_{1\le i,k\le 4}|} \\ &= \sqrt{|\det\left(\frac{1}{2}(\mathrm{nrd}(\alpha_i + \alpha_j) - \mathrm{nrd}(\alpha_i) - \mathrm{nrd}(\alpha_j))\right)_{1\le i,k\le 4}|} \\ &= \sqrt{|\det\left(\frac{1}{2}\mathrm{Tr}(\alpha_i \overline{\alpha_j})\right)_{1\le i,k\le 4}|} = \frac{1}{4}\mathrm{discrd}(\mathcal{O}) \end{aligned} $$

Besides, by [Voi20, Theorem 15.5.5], $\mathrm{discrd}(\mathcal{O}) = \mathrm{disc}(\mathcal{B}_{p,\infty}) = p$ since $\mathcal{O}$ is a maximal order. We then have

$$ \mathrm{Covol}(\iota(J)) = [\mathcal{O} : J] \mathrm{Covol}(\iota(\mathcal{O})) = [\mathcal{O} : J] \mathrm{discrd}(\mathcal{O})/4 = \mathrm{nrd}(J)^2 p/4 $$

It follows that the minimal value of $q_J$ is

$$ q_J(\alpha) = \lambda_1^2 / \mathrm{nrd}(J) \le \frac{2\sqrt{2p}}{\pi}. \quad \square $$

### E.3 Dividing the higher dimensional isogeny in two (Proposition 13)

**Proposition 13.** Let $d := d_1d_2$ prime to $p$ and $F : \mathcal{A} \to \mathcal{B}$ be a $d$-isogeny between abelian varieties defined over $\overline{\mathbb{F}}_p$. Then:

(i) We can always decompose $F = F_2 \circ F_1$, where $F_1$ is a $d_1$-isogeny and $F_2$ is a $d_2$-isogeny.

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

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

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

In order to prove the proposition, we need two intermediary results.

**Lemma 46.** If $F : (\mathcal{A}, \lambda_{\mathcal{A}}) \to (\mathcal{B}, \lambda_{\mathcal{B}})$ is a $d$-isogeny between principally polarized abelian varieties, then $\ker(F)$ is a maximal isotropic subgroup of $\mathcal{A}[d]$ (for the $d$-th Weil pairing).

*Proof.* The inclusion $\ker(F) \subseteq \mathcal{A}[d]$ immediately follows from $\tilde{F} \circ F = [d]$. Now we prove that $\ker(F)$ is isotropic. Let $x, y \in \ker(F)$. Since $\tilde{F}$ is surjective, there exists $y' \in \mathcal{B}$ such that $y = \tilde{F}(y')$. Let $\lambda_{\mathcal{A}}$ and $\lambda_{\mathcal{B}}$ be the principal polarisations on $\mathcal{A}$ and $\mathcal{B}$ respectively, $e_d^{\lambda_{\mathcal{A}}}$ and $e_d^{\lambda_{\mathcal{B}}}$ the associated Weil pairings. Then

$$ e_d^{\lambda_{\mathcal{A}}}(x, y) = e_d(x, \lambda_{\mathcal{A}} \circ \tilde{F}(y')) = e_d(x, \tilde{F} \circ \lambda_{\mathcal{B}}(y')) = e_d(F(x), \lambda_{\mathcal{B}}(y')) = 1. $$

Then $\ker(F)$ is isotropic. Since $F$ is a $d$-isogeny, it has degree $d^g$ with $g := \dim(\mathcal{A})$, and $\#\ker(F) = d^g$ since $F$ is separable. So $\ker(F)$ is maximal isotropic. $\square$
**Lemma 47.** Let $(\mathcal{A}, \lambda)$ be a principally polarized abelian variety. If $K \subset \mathcal{A}[d]$ is isotropic, then the polarization $[d]\lambda_C$ on $\mathcal{A}$ descends to a principal polarization on $\mathcal{B} := \mathcal{A}/K$. More precisely, there exists a principal polarization $\lambda'$ on $\mathcal{B}$ such that $[d]\lambda = \hat{\pi} \circ \lambda' \circ \pi$, where $\pi : \mathcal{A} \to \mathcal{B} = \mathcal{A}/K$ is the canonical projection.

*Proof.* We have $\ker([d]\lambda) = [d]^{-1}(\ker(\lambda)) = \mathcal{A}[d]$ since $\deg(\lambda) = 1$. Since $K \subset \mathcal{A}[d]$ is isotropic, the result follows from [Mil86, Proposition 6.8]. □

*Proof.* (of Proposition 13) (i) We prove that we have a decomposition of $F : \mathcal{A} \to \mathcal{B}$ of the form

$$(\mathcal{A}, \lambda_{\mathcal{A}}) \xrightarrow{F_1} (\mathcal{C}, \lambda_{\mathcal{C}}) \xrightarrow{F_2} (\mathcal{B}, \lambda_{\mathcal{B}}),$$

where the intermediary abelian variety $\mathcal{C}$ is principally polarized and $F_1$ and $F_2$ are respectively $d_1$ and $d_2$-isogenies, with $d = d_1 d_2$. By induction, it suffices to prove this result when $d_1 = \ell$ is a prime.

Since $\#\ker(F) = d^g$, the $\ell$-Sylow subgroup of $\ker(F)$ has cardinality $\ell^{gv_\ell}$, where $v_\ell$ is the $\ell$-adic valuation of $d$. We may also write the $\ell$-Sylow subgroup as follows:

$$G_{\ell} \cong \prod_{i=1}^{r} (\mathbb{Z}/\ell^{\alpha_i}, \mathbb{Z}),$$

where the $\alpha_i$ are positive integers. Since $G_\ell \subseteq \ker(F) \subseteq \mathcal{A}[d]$, the $\alpha_i$ must all be $\le v_\ell$. It follows that

$$gv_\ell = \log_\ell \#G_\ell = \sum_{i=1}^{r} \alpha_i \le rv_\ell,$$

so that $r \ge g$ and $\ker(F)[\ell] = G_\ell[\ell] \cong (\mathbb{Z}/\ell\mathbb{Z})^r$, which implies that $\ker(F)[\ell]$ has rank $\ge g$. Hence, it contains a subgroup $K \subset \mathcal{A}[\ell]$ of rank $g$, which is isotropic in $\mathcal{A}[\ell]$ since $\ker(F) \supset K$ is isotropic in $\mathcal{A}[d]$ by Lemma 46.

By [Mum74, Theorem 4, p. 73], $F$ factors through an isogeny $F_1$ of kernel $K$ so we can indeed write $F = F_2 \circ F_1$. Since $K$ is isotropic, by Lemma 47, the codomain $\mathcal{C}$ of $F_1$ admits a principal polarization $\lambda_C$ such that $\tilde{F}_1 \circ \lambda_C \circ F_1 = [\ell]\lambda_{\mathcal{A}}$ i.e. $\tilde{F}_1 \circ F_1 = [\ell]$. So $F_1$ is an $\ell$-isogeny.

We also have

$$[d]_{\mathcal{B}} = F \circ \tilde{F} = F_2 \circ F_1 \circ \tilde{F}_1 \circ \tilde{F}_2 = F_2 \circ [\ell]_{\mathcal{C}} \circ \tilde{F}_2 = F_2 \circ \tilde{F}_2 \circ [\ell]_{\mathcal{B}},$$

so $F_2 \circ \tilde{F}_2 = [d/\ell]_{\mathcal{B}}$ since $[\ell]_{\mathcal{B}}$ is surjective and $F_2$ is a $d_2 = d/\ell$-isogeny. To prove the result in the general case, we can proceed by induction on the degree $d$ (and factor $F_2$).

(ii) We always have $\ker(F_1) \subseteq \ker(F) \cap \mathcal{A}[d_1]$ since $F = F_2 \circ F_1$ and $F_1$ is a $d_1$-isogeny.

(iii) Similarly, we get that $\ker(\tilde{F}_2) \subseteq \ker(\tilde{F}) \cap \mathcal{B}[d_2]$. Besides, $\tilde{F} \circ F = [d]_{\mathcal{A}}$ so $F(\mathcal{A}[d]) \subseteq \ker(\tilde{F})$. Since $\ker(F) \subseteq \mathcal{A}[d]$, we have an isomorphism $F(\mathcal{A}[d]) \cong \mathcal{A}[d]/\ker(F)$. Furthermore, $d$ being prime to $p$, $[d]$, $F$ and $\tilde{F}$ are separable, so that
**Lemma 47.** Let $(\mathcal{A}, \lambda)$ be a principally polarized abelian variety. If $K \subset \mathcal{A}[d]$ is isotropic, then the polarization $[d]\lambda_C$ on $\mathcal{A}$ descends to a principal polarization on $\mathcal{B} := \mathcal{A}/K$. More precisely, there exists a principal polarization $\lambda'$ on $\mathcal{B}$ such that $[d]\lambda = \hat{\pi} \circ \lambda' \circ \pi$, where $\pi : \mathcal{A} \to \mathcal{B} = \mathcal{A}/K$ is the canonical projection.

*Proof.* We have $\ker([d]\lambda) = [d]^{-1}(\ker(\lambda)) = \mathcal{A}[d]$ since $\deg(\lambda) = 1$. Since $K \subset \mathcal{A}[d]$ is isotropic, the result follows from [Mil86, Proposition 6.8]. □

*Proof.* (of Proposition 13) (i) We prove that we have a decomposition of $F : \mathcal{A} \to \mathcal{B}$ of the form

$$ (\mathcal{A}, \lambda_{\mathcal{A}}) \xrightarrow{F_1} (\mathcal{C}, \lambda_{\mathcal{C}}) \xrightarrow{F_2} (\mathcal{B}, \lambda_{\mathcal{B}}), $$

where the intermediary abelian variety $\mathcal{C}$ is principally polarized and $F_1$ and $F_2$ are respectively $d_1$ and $d_2$-isogenies, with $d = d_1 d_2$. By induction, it suffices to prove this result when $d_1 = \ell$ is a prime.

Since $\#\ker(F) = d^g$, the $\ell$-Sylow subgroup of $\ker(F)$ has cardinality $\ell^{gv_\ell}$, where $v_\ell$ is the $\ell$-adic valuation of $d$. We may also write the $\ell$-Sylow subgroup as follows:

$$ G_{\ell} \cong \prod_{i=1}^{r} (\mathbb{Z}/\ell^{\alpha_i}, \mathbb{Z}), $$

where the $\alpha_i$ are positive integers. Since $G_\ell \subseteq \ker(F) \subseteq \mathcal{A}[d]$, the $\alpha_i$ must all be $\le v_\ell$. It follows that

$$ gv_\ell = \log_\ell \#G_\ell = \sum_{i=1}^{r} \alpha_i \le rv_\ell, $$

so that $r \ge g$ and $\ker(F)[\ell] = G_\ell[\ell] \cong (\mathbb{Z}/\ell\mathbb{Z})^r$, which implies that $\ker(F)[\ell]$ has rank $\ge g$. Hence, it contains a subgroup $K \subset \mathcal{A}[\ell]$ of rank $g$, which is isotropic in $\mathcal{A}[\ell]$ since $\ker(F) \supset K$ is isotropic in $\mathcal{A}[d]$ by Lemma 46.

By [Mum74, Theorem 4, p. 73], $F$ factors through an isogeny $F_1$ of kernel $K$ so we can indeed write $F = F_2 \circ F_1$. Since $K$ is isotropic, by Lemma 47, the codomain $\mathcal{C}$ of $F_1$ admits a principal polarization $\lambda_C$ such that $\tilde{F}_1 \circ \lambda_C \circ F_1 = [\ell]\lambda_{\mathcal{A}}$ i.e. $\tilde{F}_1 \circ F_1 = [\ell]$. So $F_1$ is an $\ell$-isogeny.

We also have

$$ [d]_{\mathcal{B}} = F \circ \tilde{F} = F_2 \circ F_1 \circ \tilde{F}_1 \circ \tilde{F}_2 = F_2 \circ [\ell]_{\mathcal{C}} \circ \tilde{F}_2 = F_2 \circ \tilde{F}_2 \circ [\ell]_{\mathcal{B}}, $$

so $F_2 \circ \tilde{F}_2 = [d/\ell]_{\mathcal{B}}$ since $[\ell]_{\mathcal{B}}$ is surjective and $F_2$ is a $d_2 = d/\ell$-isogeny. To prove the result in the general case, we can proceed by induction on the degree $d$ (and factor $F_2$).

(ii) We always have $\ker(F_1) \subseteq \ker(F) \cap \mathcal{A}[d_1]$ since $F = F_2 \circ F_1$ and $F_1$ is a $d_1$-isogeny.

(iii) Similarly, we get that $\ker(\tilde{F}_2) \subseteq \ker(\tilde{F}) \cap \mathcal{B}[d_2]$. Besides, $\tilde{F} \circ F = [d]_{\mathcal{A}}$ so $F(\mathcal{A}[d]) \subseteq \ker(\tilde{F})$. Since $\ker(F) \subseteq \mathcal{A}[d]$, we have an isomorphism $F(\mathcal{A}[d]) \cong \mathcal{A}[d]/\ker(F)$. Furthermore, $d$ being prime to $p$, $[d]$, $F$ and $\tilde{F}$ are separable, so that
$\#\mathcal{A}[d] = d^{2g}$ and $\#\ker(\tilde{F}) = \#\ker(F) = d^g$. Hence, $\#F(\mathcal{A}[d]) = d^g = \#\ker(\tilde{F})$ and $\ker(\tilde{F}) = F(\mathcal{A}[d])$. Point (iii) follows.

(iv) Suppose $\ker(F)$ has rank $g$. Let $(x_1, \dots, x_g)$ be a basis of generators of $\ker(F)$. Then, the $x_i$ all have order $d$ and are linearly independent over $\mathbb{Z}/d\mathbb{Z}$. Then, $\ker(F) \cap \mathcal{A}[d_1] = ([d_2]x_1, \dots, [d_2]x_g)$ and the $[d_2]x_i$ all have order $d_1$ and are linearly independent over $\mathbb{Z}/d_1\mathbb{Z}$, so that $\#\ker(F) \cap \mathcal{A}[d_1] = d_1^g = \#\ker(F_1)$. The equality $\ker(F_1) = \ker(F) \cap \mathcal{A}[d_1]$ follows by (ii).

To prove that $\ker(\tilde{F}_2) = F(\mathcal{A}[d]) \cap \mathcal{B}[d_2]$, it suffices to prove that $F(\mathcal{A}[d]) = \ker(\tilde{F})$ has rank $g$ and the preceding reasoning will apply. We have $F(\mathcal{A}[d]) \cong \mathcal{A}[d]/\ker(F)$, so it suffices to prove that there is a subgroup $G \subset \mathcal{A}[d]$ of rank $g$ such that $\ker(F) \oplus G = \mathcal{A}[d]$, because, we will have $F(\mathcal{A}[d]) \cong G$. We consider the $d$-th Weil pairing $e_d^{\lambda_A} : \mathcal{A}[d]^2 \to \mu_d(\mathbb{F}_p)$, where $\mu_d(\mathbb{F}_p)$ is the group of $d$-th roots of unity in $\mathbb{F}_p$, and the group homomorphism

$$ \Phi : \mathcal{A}[d] \to \mu_d(\mathbb{F}_p)^g \\ y \mapsto (e_d^{\lambda_A}(x_i, y))_{1 \le i \le g}. $$

Since $\ker(F)$ is maximal isotropic, we have $\ker(\Phi) = \ker(F)$. It follows that $\#\mathrm{im}(\Phi) = \#\mathcal{A}[d]/\#\ker(\Phi) = d^{2g}/d^g = d^g$, so that $\mathrm{im}(\Phi) = \mu_d(\mathbb{F}_p)^g$ i.e. $\Phi$ is surjective. Let $\zeta \in \mu_d(\mathbb{F}_p)$ be a primitive $d$-th root of unity. Then, for all $j \in [1; g]$ there exists $y_j \in \mathcal{A}[d]$ such that $e_d^{\lambda_A}(x_i, y_j) = \zeta^{\delta_{i,j}}$ for all $i \in [1; g]$, where $\delta_{i,j}$ is the Kronecker delta. It follows that the $y_i$ all have order $d$ (since $e_d^{\lambda_A}(x_i, y_i) = \zeta$ has order $d$), are linearly independent over $\mathbb{Z}/d\mathbb{Z}$ and linearly independent of the $x_i$. We can then take $G := (y_1, \dots, y_g)$. This completes the proof. $\square$

## E.4 Correctness of RepresentIsogeny$_{g, \ell_e, \ell_f}$ (Proposition 14)

**Proposition 14.** *Algorithms 4 and 15 are 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$ (and similarly for Algorithm 15).*

*Proof.* We assume that Algorithm 4 received $a_1, a_2, P_1, P_2, \sigma(P_2), \sigma(P_2)$ on entry. Let us write $F^* := F(\sigma, a_1, a_2)$ and decompose $F^* := F_2^* \circ F_1^*$, where $F_1^*$ is an $\ell^{e_1}$-isogeny of kernel $\ker(F^*)[\ell^{e_1}]$ and $\tilde{F}_2^*$ is an $\ell^{e_2}$-isogeny of kernel $F^*(E_1^2 \times E_2^2[\ell^{e_2}])$. Then, by construction the outputs $F_1$ and $\tilde{F}_2$ of Algorithm 4 satisfy $\ker(F_1) = \ker(F_1^*)$, $\ker(\tilde{F}_2) = \ker(\tilde{F}_2^*)$, $\mathrm{deg}(F_1) = \mathrm{deg}(F_1^*)$ and $\mathrm{deg}(\tilde{F}_2) = \mathrm{deg}(\tilde{F}_2^*)$. Hence, by [Mum74, Theorem 4, p.73] if we denote $(C, \lambda_C)$ the common codomain of $F_1$ and $\tilde{F}_2$ and $(C^*, \lambda_{C^*})$ the common codomain of $F_1^*$ and $\tilde{F}_2^*$, then we get that $F_1 = \lambda \circ F_1^*$ and $\tilde{F}_2 = \mu \circ \tilde{F}_2^*$, where $\lambda$ and $\mu$ are isomorphisms $(C^*, \lambda_{C^*}) \xrightarrow{\sim} (C, \lambda_C)$.

To conclude, we need to be more specific about the way $F_1$ and $\tilde{F}_2$ are computed explicitly with the theta-model of level 2 (see Appendix F.3). To ensure $F_1$