it could be part of the signature in cases where size of the signature is critical. Experimentally, for NIST level 1, this would gain 16B on the signature size, at the cost of an increase on the verification time by 5 to 10 percent.

## 7.2 Implementation choices and optimisations

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

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

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

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

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

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

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

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

<footnote n="10">¹⁰ https://gmplib.org/.</footnote>
pairings on Montgomery curves. We note that since we only need to compute
pairings between points of order 2<sup>e</sup>, we only need to use biextension doublings.

*Two-dimensional abelian varieties* are represented in theta coordinates and their (2,2)-isogenies are evaluated using the formulas in [12]. We use the projective version of their formulas to remove almost all inversions along the isogeny chain.

All other algorithms are either taken from the implementation of SQIsignHD or have been written from scratch according to the description in Section 4, with minor deviations to allow for several small optimizations, such as commitment recoverability, basis compression, and hints.

This implementation, along with a SageMath implementation of SQIsign2D,
will be available soon.

7.3 Performance

We ran benchmarks to compare our implementations to the state of the art. All
code was compiled on Ubuntu using `clang 14`, with flags `-march=native -O3`,
dynamically linking to the system GMP library (version 6.2.1). Benchmarks were
run on an Intel Xeon Gold 6338 (Ice Lake) CPU clocked at 2 GHz with turbo
boost disabled.

In particular, we compare our pure-C implementation to:

- The reference implementation of SQIsign at https://github.com/SQISign/the-sqisign. Because this uses the same modular arithmetic based on Fiat-Crypto, it is a fair comparison for showcasing the higher-level algorithmic improvements of SQIsign2D.

- The implementation of SQIsignHD at https://github.com/Pierrick-Dartois/SQISignHD-lib. This codebase is momentarily lacking a C implementation of the verification, thus we only benchmark key generation and signatures.

The results are reported in Table 3.

For the optimised pure-C implementation we additionally compare to the im-
plementation of SQIsign [15] at https://github.com/SQISign/sqisign-ec23.
This has much better assembly optimisations for finite fields and is generally
faster than the reference implementation. However, our implementation is the
only one to implement all three NIST levels. The results are reported in Table 4.

We additionally implemented the heuristic variant of SQIsign2D described in Appendix A. Because it is focused on efficiency, we only report timings for the optimised arithmetic implementation in Table 5.

References

1. Bach, E.: How to generate factored random numbers. SIAM Journal on Computing 17(2), 179–193 (1988)
pairings on Montgomery curves. We note that since we only need to compute
pairings between points of order 2<sup>e</sup>, we only need to use biextension doublings.

*Two-dimensional abelian varieties* are represented in theta coordinates and their (2,2)-isogenies are evaluated using the formulas in [12]. We use the projective version of their formulas to remove almost all inversions along the isogeny chain.

All other algorithms are either taken from the implementation of SQIsignHD or have been written from scratch according to the description in Section 4, with minor deviations to allow for several small optimizations, such as commitment recoverability, basis compression, and hints.

This implementation, along with a SageMath implementation of SQIsign2D,
will be available soon.

7.3 Performance

We ran benchmarks to compare our implementations to the state of the art. All
code was compiled on Ubuntu using `clang 14`, with flags `-march=native -O3`,
dynamically linking to the system GMP library (version 6.2.1). Benchmarks were
run on an Intel Xeon Gold 6338 (Ice Lake) CPU clocked at 2 GHz with turbo
boost disabled.

In particular, we compare our pure-C implementation to:

- The reference implementation of SQIsign at https://github.com/SQISign/the-sqisign. Because this uses the same modular arithmetic based on Fiat-Crypto, it is a fair comparison for showcasing the higher-level algorithmic improvements of SQIsign2D.

- The implementation of SQIsignHD at https://github.com/Pierrick-Dartois/SQISignHD-lib. This codebase is momentarily lacking a C implementation of the verification, thus we only benchmark key generation and signatures.

The results are reported in Table 3.

For the optimised pure-C implementation we additionally compare to the im-
plementation of SQIsign [15] at https://github.com/SQISign/sqisign-ec23.
This has much better assembly optimisations for finite fields and is generally
faster than the reference implementation. However, our implementation is the
only one to implement all three NIST levels. The results are reported in Table 4.

We additionally implemented the heuristic variant of SQIsign2D described in Appendix A. Because it is focused on efficiency, we only report timings for the optimised arithmetic implementation in Table 5.

References

1. Bach, E.: How to generate factored random numbers. SIAM Journal on Computing 17(2), 179–193 (1988)
<table><caption>**Table 3.** Performance of SQIsign2D on Intel Xeon Gold 6338 (Ice Lake, 2GHz), using generic finite field arithmetic (Fiat-Crypto), GMP 6.2.1. Turbo-boost disabled. Timings in $10^6$ cycles.</caption><thead><tr><th></th><th>Level</th><th>SQIsign</th><th>SQIsignHD</th><th>SQIsign2D</th></tr></thead><tbody><tr><td rowspan="3">Keygen</td><td>I</td><td>2,800</td><td>190</td><td>120</td></tr><tr><td>III</td><td>21,300</td><td>—</td><td>440</td></tr><tr><td>V</td><td>91,600</td><td>—</td><td>1,070</td></tr><tr><td rowspan="3">Sign</td><td>I</td><td>4,600</td><td>115</td><td>290</td></tr><tr><td>III</td><td>39,300</td><td>—</td><td>1,040</td></tr><tr><td>V</td><td>165,000</td><td>—</td><td>2,490</td></tr><tr><td rowspan="3">Verify</td><td>I</td><td>93</td><td>—</td><td>25</td></tr><tr><td>III</td><td>641</td><td>—</td><td>98</td></tr><tr><td>V</td><td>2,080</td><td>—</td><td>247</td></tr></tbody></table>

<table><caption>**Table 4.** Performance of SQIsign2D on Intel Xeon Gold 6338 (Ice Lake, 2GHz), with finite field arithmetic optimised using intrinsics for the Ice Lake architecture, GMP 6.2.1. Turbo-boost disabled. Timings in $10^6$ cycles.</caption><thead><tr><th></th><th>Level</th><th>SQIsign ([8])</th><th>SQIsign ([15])</th><th>SQIsign2D</th></tr></thead><tbody><tr><td rowspan="3">Keygen</td><td>I</td><td>1,700</td><td>400</td><td>60</td></tr><tr><td>III</td><td>—</td><td>—</td><td>170</td></tr><tr><td>V</td><td>—</td><td>—</td><td>360</td></tr><tr><td rowspan="3">Sign</td><td>I</td><td>2,400</td><td>1880</td><td>160</td></tr><tr><td>III</td><td>—</td><td>—</td><td>460</td></tr><tr><td>V</td><td>—</td><td>—</td><td>940</td></tr><tr><td rowspan="3">Verify</td><td>I</td><td>39</td><td>29</td><td>9</td></tr><tr><td>III</td><td>—</td><td>—</td><td>29</td></tr><tr><td>V</td><td>—</td><td>—</td><td>62</td></tr></tbody></table>

<table><caption>**Table 5.** Performance of the heuristic variant of SQIsign2D on Intel Xeon Gold 6338 (Ice Lake, 2GHz), with finite field arithmetic optimized using intrinsics for the Ice Lake architecture, GMP 6.2.1. Turbo-boost disabled. Timings in $10^6$ cycles.</caption><thead><tr><th></th><th>Keygen</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>NIST I</td><td>58</td><td>100</td><td>9</td></tr><tr><td>NIST III</td><td>170</td><td>280</td><td>29</td></tr><tr><td>NIST V</td><td>350</td><td>570</td><td>60</td></tr></tbody></table>
<table><caption>**Table 3.** Performance of SQIsign2D on Intel Xeon Gold 6338 (Ice Lake, 2GHz), using generic finite field arithmetic (Fiat-Crypto), GMP 6.2.1. Turbo-boost disabled. Timings in $10^6$ cycles.</caption><thead><tr><th></th><th>Level</th><th>SQIsign</th><th>SQIsignHD</th><th>SQIsign2D</th></tr></thead><tbody><tr><td rowspan="3">Keygen</td><td>I</td><td>2,800</td><td>190</td><td>120</td></tr><tr><td>III</td><td>21,300</td><td>—</td><td>440</td></tr><tr><td>V</td><td>91,600</td><td>—</td><td>1,070</td></tr><tr><td rowspan="3">Sign</td><td>I</td><td>4,600</td><td>115</td><td>290</td></tr><tr><td>III</td><td>39,300</td><td>—</td><td>1,040</td></tr><tr><td>V</td><td>165,000</td><td>—</td><td>2,490</td></tr><tr><td rowspan="3">Verify</td><td>I</td><td>93</td><td>—</td><td>25</td></tr><tr><td>III</td><td>641</td><td>—</td><td>98</td></tr><tr><td>V</td><td>2,080</td><td>—</td><td>247</td></tr></tbody></table>

<table><caption>**Table 4.** Performance of SQIsign2D on Intel Xeon Gold 6338 (Ice Lake, 2GHz), with finite field arithmetic optimised using intrinsics for the Ice Lake architecture, GMP 6.2.1. Turbo-boost disabled. Timings in $10^6$ cycles.</caption><thead><tr><th></th><th>Level</th><th>SQIsign ([8])</th><th>SQIsign ([15])</th><th>SQIsign2D</th></tr></thead><tbody><tr><td rowspan="3">Keygen</td><td>I</td><td>1,700</td><td>400</td><td>60</td></tr><tr><td>III</td><td>—</td><td>—</td><td>170</td></tr><tr><td>V</td><td>—</td><td>—</td><td>360</td></tr><tr><td rowspan="3">Sign</td><td>I</td><td>2,400</td><td>1880</td><td>160</td></tr><tr><td>III</td><td>—</td><td>—</td><td>460</td></tr><tr><td>V</td><td>—</td><td>—</td><td>940</td></tr><tr><td rowspan="3">Verify</td><td>I</td><td>39</td><td>29</td><td>9</td></tr><tr><td>III</td><td>—</td><td>—</td><td>29</td></tr><tr><td>V</td><td>—</td><td>—</td><td>62</td></tr></tbody></table>

<table><caption>**Table 5.** Performance of the heuristic variant of SQIsign2D on Intel Xeon Gold 6338 (Ice Lake, 2GHz), with finite field arithmetic optimized using intrinsics for the Ice Lake architecture, GMP 6.2.1. Turbo-boost disabled. Timings in $10^6$ cycles.</caption><thead><tr><th></th><th>Keygen</th><th>Sign</th><th>Verify</th></tr></thead><tbody><tr><td>NIST I</td><td>58</td><td>100</td><td>9</td></tr><tr><td>NIST III</td><td>170</td><td>280</td><td>29</td></tr><tr><td>NIST V</td><td>350</td><td>570</td><td>60</td></tr></tbody></table>
2. Backendal, M., Bellare, M., Sorrell, J., Sun, J.: The fiat-shamir zoo: Relating the security of different signature variants. In: Gruschka, N. (ed.) Secure IT Systems - 23rd Nordic Conference, NordSec 2018, Oslo, Norway, November 28-30, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11252, pp. 154-170. Springer (2018). https://doi.org/10.1007/978-3-030-03638-6_10, https://doi.org/10.1007/978-3-030-03638-6_10

3. Bajard, J.C., Duquesne, S.: Montgomery-friendly primes and applications to cryptography. Journal of Cryptographic Engineering 11(4), 399-415 (Nov 2021). https://doi.org/10.1007/s13389-021-00260-z

4. Basso, A., Maino, L., Pope, G.: FESTA: Fast encryption from supersingular torsion attacks. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023, Part VII. LNCS, vol. 14444, pp. 98-126. Springer, Heidelberg (Dec 2023). https://doi.org/10.1007/978-981-99-8739-9_4

5. Bernstein, D.J., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. Open Book Series 4(1), 39-55 (2020). https://doi.org/10.2140/obs.2020.4.39

6. Biasse, J.F., Jao, D., Sankar, A.: A quantum algorithm for computing isogenies between supersingular elliptic curves. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 428-442. Springer, Heidelberg (Dec 2014). https://doi.org/10.1007/978-3-319-13039-2_25

7. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 423-447. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_15

8. Chavez-Saab, J., Santos, M.C., De Feo, L., Eriksen, J.K., Hess, B., Kohel, D., Leroux, A., Longa, P., Meyer, M., Panny, L., Patranabis, S., Petit, C., Rodríguez Henríquez, F., Schaeffler, S., Wesolowski, B.: SQIsign. Tech. rep., National Institute of Standards and Technology (2023), available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures

9. Corte-Real Santos, M., Eriksen, J.K., Meyer, M., Reijnders, K.: AprèsSQI: extra fast verification for SQIsign using extension-field signing. In: Joye, M., Leander, G. (eds.) Advances in Cryptology - EUROCRYPT 2024. pp. 63-93. Springer Nature Switzerland, Cham (2024). https://doi.org/10.1007/978-3-031-58716-0_3

10. Costello, C., Hisil, H.: A simple and compact algorithm for SIDH with arbitrary degree isogenies. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part II. LNCS, vol. 10625, pp. 303-329. Springer, Heidelberg (Dec 2017). https://doi.org/10.1007/978-3-319-70697-9_11

11. Dartois, P., Leroux, A., Robert, D., Wesolowski, B.: SQIsignHD: new dimensions in cryptography. In: Joye, M., Leander, G. (eds.) Advances in Cryptology - EUROCRYPT 2024. pp. 3-32. Springer Nature Switzerland, Cham (2024). https://doi.org/10.1007/978-3-031-58716-0_1

12. Dartois, P., Maino, L., Pope, G., Robert, D.: An algorithmic approach to (2, 2)-isogenies in the theta model and applications to isogeny-based cryptography. Cryptology ePrint Archive, Paper 2023/1747 (2023), https://eprint.iacr.org/2023/1747

13. De Feo, L.: Mathematics of Isogeny Based Cryptography. arXiv (2017), http://arxiv.org/abs/1711.04062

14. De Feo, L., Kohel, D., Leroux, A., Petit, C., Wesolowski, B.: SQISign: Compact post-quantum signatures from quaternions and isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part I. LNCS, vol. 12491, pp. 64-93. Springer, Heidelberg (Dec 2020). https://doi.org/10.1007/978-3-030-64837-4_3
2. Backendal, M., Bellare, M., Sorrell, J., Sun, J.: The fiat-shamir zoo: Relating the security of different signature variants. In: Gruschka, N. (ed.) Secure IT Systems - 23rd Nordic Conference, NordSec 2018, Oslo, Norway, November 28-30, 2018, Proceedings. Lecture Notes in Computer Science, vol. 11252, pp. 154-170. Springer (2018). https://doi.org/10.1007/978-3-030-03638-6_10, https://doi.org/10.1007/978-3-030-03638-6_10

3. Bajard, J.C., Duquesne, S.: Montgomery-friendly primes and applications to cryptography. Journal of Cryptographic Engineering 11(4), 399-415 (Nov 2021). https://doi.org/10.1007/s13389-021-00260-z

4. Basso, A., Maino, L., Pope, G.: FESTA: Fast encryption from supersingular torsion attacks. In: Guo, J., Steinfeld, R. (eds.) ASIACRYPT 2023, Part VII. LNCS, vol. 14444, pp. 98-126. Springer, Heidelberg (Dec 2023). https://doi.org/10.1007/978-981-99-8739-9_4

5. Bernstein, D.J., De Feo, L., Leroux, A., Smith, B.: Faster computation of isogenies of large prime degree. Open Book Series 4(1), 39-55 (2020). https://doi.org/10.2140/obs.2020.4.39

6. Biasse, J.F., Jao, D., Sankar, A.: A quantum algorithm for computing isogenies between supersingular elliptic curves. In: Meier, W., Mukhopadhyay, D. (eds.) INDOCRYPT 2014. LNCS, vol. 8885, pp. 428-442. Springer, Heidelberg (Dec 2014). https://doi.org/10.1007/978-3-319-13039-2_25

7. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 423-447. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_15

8. Chavez-Saab, J., Santos, M.C., De Feo, L., Eriksen, J.K., Hess, B., Kohel, D., Leroux, A., Longa, P., Meyer, M., Panny, L., Patranabis, S., Petit, C., Rodríguez Henríquez, F., Schaeffler, S., Wesolowski, B.: SQIsign. Tech. rep., National Institute of Standards and Technology (2023), available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures

9. Corte-Real Santos, M., Eriksen, J.K., Meyer, M., Reijnders, K.: AprèsSQI: extra fast verification for SQIsign using extension-field signing. In: Joye, M., Leander, G. (eds.) Advances in Cryptology - EUROCRYPT 2024. pp. 63-93. Springer Nature Switzerland, Cham (2024). https://doi.org/10.1007/978-3-031-58716-0_3

10. Costello, C., Hisil, H.: A simple and compact algorithm for SIDH with arbitrary degree isogenies. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part II. LNCS, vol. 10625, pp. 303-329. Springer, Heidelberg (Dec 2017). https://doi.org/10.1007/978-3-319-70697-9_11

11. Dartois, P., Leroux, A., Robert, D., Wesolowski, B.: SQIsignHD: new dimensions in cryptography. In: Joye, M., Leander, G. (eds.) Advances in Cryptology - EUROCRYPT 2024. pp. 3-32. Springer Nature Switzerland, Cham (2024). https://doi.org/10.1007/978-3-031-58716-0_1

12. Dartois, P., Maino, L., Pope, G., Robert, D.: An algorithmic approach to (2, 2)-isogenies in the theta model and applications to isogeny-based cryptography. Cryptology ePrint Archive, Paper 2023/1747 (2023), https://eprint.iacr.org/2023/1747

13. De Feo, L.: Mathematics of Isogeny Based Cryptography. arXiv (2017), http://arxiv.org/abs/1711.04062

14. De Feo, L., Kohel, D., Leroux, A., Petit, C., Wesolowski, B.: SQISign: Compact post-quantum signatures from quaternions and isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part I. LNCS, vol. 12491, pp. 64-93. Springer, Heidelberg (Dec 2020). https://doi.org/10.1007/978-3-030-64837-4_3
15. De Feo, L., Leroux, A., Longa, P., Wesolowski, B.: New algorithms for the deuring correspondence - towards practical and secure SQISign signatures. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 659–690. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_23

16. Delfs, C., Galbraith, S.D.: Computing isogenies between supersingular elliptic curves over $\mathbb{F}_p$. DCC 78(2), 425–440 (2016). https://doi.org/10.1007/s10623-014-0010-1

17. Deuring, M.: Die typen der multiplikatorenringe elliptischer funktionenkörper. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 14, 197–272 (1941), https://doi.org/10.1007/BF02940746

18. Dirichlet, P.G.L.: Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält. Abhandlungen der Königlichen Preußischen Akademie der Wissenschaften zu Berlin 48, 45–71 (1837)

19. Duparc, M., Fouotsa, T.B.: SQIprime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies. Private Communication (2024)

20. Duparc, M., Fouotsa, T.B., Vaudenay, S.: Silbe: an updatable public key encryption scheme from lollipop attacks. Cryptology ePrint Archive, Paper 2024/400 (2024), https://eprint.iacr.org/2024/400

21. Erbsen, A., Philipoom, J., Gross, J., Sloan, R., Chlipala, A.: Simple high-level code for cryptographic arithmetic - with proofs, without compromises. In: 2019 IEEE Symposium on Security and Privacy. pp. 1202–1219. IEEE Computer Society Press (May 2019). https://doi.org/10.1109/SP.2019.00005

22. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO'86. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (Aug 1987). https://doi.org/10.1007/3-540-47721-7_12

23. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: 28th ACM STOC. pp. 212–219. ACM Press (May 1996). https://doi.org/10.1145/237814.237866

24. Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford, sixth edn. (1975)

25. Jao, D., Azarderakhsh, R., Campagna, M., Costello, C., De Feo, L., Hess, B., Jalali, A., Koziel, B., LaMacchia, B., Longa, P., Naehrig, M., Renes, J., Soukharev, V., Urbanik, D., Pereira, G., Karabina, K., Hutchinson, A.: SIKE. Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions

26. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.Y. (ed.) Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011. pp. 19–34. Springer, Heidelberg (Nov / Dec 2011). https://doi.org/10.1007/978-3-642-25405-5_2

27. Kani, E.: The number of curves of genus two with elliptic differentials. Journal für die reine und angewandte Mathematik 485, 93–122 (1997)

28. Kirschmer, M., Voight, J.: Algorithmic enumeration of ideal classes for quaternion orders. SIAM Journal on Computing 39(5), 1714–1747 (2010). https://doi.org/10.1137/080734467

29. Kohel, D., Lauter, K., Petit, C., Tignol, J.P.: On the quaternion $\ell$-isogeny path problem. Cryptology ePrint Archive, Report 2014/505 (2014), https://eprint.iacr.org/2014/505
15. De Feo, L., Leroux, A., Longa, P., Wesolowski, B.: New algorithms for the deuring correspondence - towards practical and secure SQISign signatures. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 659–690. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_23

16. Delfs, C., Galbraith, S.D.: Computing isogenies between supersingular elliptic curves over $\mathbb{F}_p$. DCC 78(2), 425–440 (2016). https://doi.org/10.1007/s10623-014-0010-1

17. Deuring, M.: Die typen der multiplikatorenringe elliptischer funktionenkörper. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 14, 197–272 (1941), https://doi.org/10.1007/BF02940746

18. Dirichlet, P.G.L.: Beweis des Satzes, dass jede unbegrenzte arithmetische Progression, deren erstes Glied und Differenz ganze Zahlen ohne gemeinschaftlichen Factor sind, unendlich viele Primzahlen enthält. Abhandlungen der Königlichen Preußischen Akademie der Wissenschaften zu Berlin 48, 45–71 (1837)

19. Duparc, M., Fouotsa, T.B.: SQIprime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies. Private Communication (2024)

20. Duparc, M., Fouotsa, T.B., Vaudenay, S.: Silbe: an updatable public key encryption scheme from lollipop attacks. Cryptology ePrint Archive, Paper 2024/400 (2024), https://eprint.iacr.org/2024/400

21. Erbsen, A., Philipoom, J., Gross, J., Sloan, R., Chlipala, A.: Simple high-level code for cryptographic arithmetic - with proofs, without compromises. In: 2019 IEEE Symposium on Security and Privacy. pp. 1202–1219. IEEE Computer Society Press (May 2019). https://doi.org/10.1109/SP.2019.00005

22. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO'86. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (Aug 1987). https://doi.org/10.1007/3-540-47721-7_12

23. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: 28th ACM STOC. pp. 212–219. ACM Press (May 1996). https://doi.org/10.1145/237814.237866

24. Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers. Oxford, sixth edn. (1975)

25. Jao, D., Azarderakhsh, R., Campagna, M., Costello, C., De Feo, L., Hess, B., Jalali, A., Koziel, B., LaMacchia, B., Longa, P., Naehrig, M., Renes, J., Soukharev, V., Urbanik, D., Pereira, G., Karabina, K., Hutchinson, A.: SIKE. Tech. rep., National Institute of Standards and Technology (2022), available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions

26. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.Y. (ed.) Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011. pp. 19–34. Springer, Heidelberg (Nov / Dec 2011). https://doi.org/10.1007/978-3-642-25405-5_2

27. Kani, E.: The number of curves of genus two with elliptic differentials. Journal für die reine und angewandte Mathematik 485, 93–122 (1997)

28. Kirschmer, M., Voight, J.: Algorithmic enumeration of ideal classes for quaternion orders. SIAM Journal on Computing 39(5), 1714–1747 (2010). https://doi.org/10.1137/080734467

29. Kohel, D., Lauter, K., Petit, C., Tignol, J.P.: On the quaternion $\ell$-isogeny path problem. Cryptology ePrint Archive, Report 2014/505 (2014), https://eprint.iacr.org/2014/505
30. Leroux, A.: Quaternion algebras and isogeny-based cryptography. Ph.D. thesis, École Polytechnique, France (2022), http://www.lix.polytechnique.fr/Labo/ Antonin.LEROUX/manuscrit_these.pdf

31. Longa, P.: Efficient algorithms for large prime characteristic fields and their application to bilinear pairings. IACR TCHES 2023(3), 445-472 (2023). https://doi.org/10.46586/tches.v2023.i3.445-472

32. Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 448-471. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_16

33. Nakagawa, K., Onuki, H.: QFESTA: efficient algorithms and parameters for FESTA using quaternion algebras. Cryptology ePrint Archive, Paper 2023/1468 (2023), https://eprint.iacr.org/2023/1468

34. Nakagawa, K., Onuki, H.: Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign. Private Communication (2024)

35. Nakagawa, K., Onuki, H.: SQIsign2D-East: a new signature scheme using 2-dimensional isogenies. Private Communication (2024)

36. Page, A., Robert, D.: Introducing Clapoti(s): evaluating the isogeny class group action in polynomial time. Cryptology ePrint Archive, Paper 2023/1766 (2023), https://eprint.iacr.org/2023/1766

37. Page, A., Wesolowski, B.: The supersingular endomorphism ring and one endomorphism problems are equivalent. In: Joye, M., Leander, G. (eds.) Advances in Cryptology - EUROCRYPT 2024. pp. 388-417. Springer Nature Switzerland, Cham (2024). https://doi.org/10.1007/978-3-031-58751-1_14

38. Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U.M. (ed.) EUROCRYPT'96. LNCS, vol. 1070, pp. 387-398. Springer, Heidelberg (May 1996). https://doi.org/10.1007/3-540-68339-9_33

39. Renes, J.: Computing isogenies between Montgomery curves using the action of (0, 0). In: Lange, T., Steinwandt, R. (eds.) Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018. pp. 229-247. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-79063-3_11

40. Robert, D.: Evaluating isogenies in polylogarithmic time. Cryptology ePrint Archive, Report 2022/1068 (2022), https://eprint.iacr.org/2022/1068

41. Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 472-503. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_17

42. Robert, D.: Fast pairings via biextensions and cubical arithmetic (4 2024), https://eprint.iacr.org/2024/517

43. Silverman, J.H.: The arithmetic of elliptic curves, Graduate texts in mathematics, vol. 106. Springer (1986)

44. Solinas, J.A.: Generalized mersenne numbers. Tech. Rep. CORR 99-39, Centre for Applied Cryptographic Research, University of Waterloo (1999)

45. Zanon, G.H.M., Simplicio, M.A., Pereira, G.C.C.F., Doliskani, J., Barreto, P.S.L.M.: Faster key compression for isogeny-based cryptosystems. IEEE Transactions on Computers 68(5), 688-701 (2019). https://doi.org/10.1109/TC.2018.2878829
30. Leroux, A.: Quaternion algebras and isogeny-based cryptography. Ph.D. thesis, École Polytechnique, France (2022), http://www.lix.polytechnique.fr/Labo/ Antonin.LEROUX/manuscrit_these.pdf

31. Longa, P.: Efficient algorithms for large prime characteristic fields and their application to bilinear pairings. IACR TCHES 2023(3), 445-472 (2023). https://doi.org/10.46586/tches.v2023.i3.445-472

32. Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 448-471. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_16

33. Nakagawa, K., Onuki, H.: QFESTA: efficient algorithms and parameters for FESTA using quaternion algebras. Cryptology ePrint Archive, Paper 2023/1468 (2023), https://eprint.iacr.org/2023/1468

34. Nakagawa, K., Onuki, H.: Ideal-to-isogeny algorithm using 2-dimensional isogenies and its application to SQIsign. Private Communication (2024)

35. Nakagawa, K., Onuki, H.: SQIsign2D-East: a new signature scheme using 2-dimensional isogenies. Private Communication (2024)

36. Page, A., Robert, D.: Introducing Clapoti(s): evaluating the isogeny class group action in polynomial time. Cryptology ePrint Archive, Paper 2023/1766 (2023), https://eprint.iacr.org/2023/1766

37. Page, A., Wesolowski, B.: The supersingular endomorphism ring and one endomorphism problems are equivalent. In: Joye, M., Leander, G. (eds.) Advances in Cryptology – EUROCRYPT 2024. pp. 388-417. Springer Nature Switzerland, Cham (2024). https://doi.org/10.1007/978-3-031-58751-1_14

38. Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U.M. (ed.) EUROCRYPT'96. LNCS, vol. 1070, pp. 387-398. Springer, Heidelberg (May 1996). https://doi.org/10.1007/3-540-68339-9_33

39. Renes, J.: Computing isogenies between Montgomery curves using the action of (0, 0). In: Lange, T., Steinwandt, R. (eds.) Post-Quantum Cryptography - 9th International Conference, PQCrypto 2018. pp. 229-247. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-319-79063-3_11

40. Robert, D.: Evaluating isogenies in polylogarithmic time. Cryptology ePrint Archive, Report 2022/1068 (2022), https://eprint.iacr.org/2022/1068

41. Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 472-503. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4_17

42. Robert, D.: Fast pairings via biextensions and cubical arithmetic (4 2024), https://eprint.iacr.org/2024/517

43. Silverman, J.H.: The arithmetic of elliptic curves, Graduate texts in mathematics, vol. 106. Springer (1986)

44. Solinas, J.A.: Generalized mersenne numbers. Tech. Rep. CORR 99-39, Centre for Applied Cryptographic Research, University of Waterloo (1999)

45. Zanon, G.H.M., Simplicio, M.A., Pereira, G.C.C.F., Doliskani, J., Barreto, P.S.L.M.: Faster key compression for isogeny-based cryptosystems. IEEE Transactions on Computers 68(5), 688-701 (2019). https://doi.org/10.1109/TC.2018.2878829
A A faster variant of SQIsign2D with heuristic security

In this section, we describe a heuristic version of the Σ-protocol described in Section 5. The gist of this idea is to avoid the additional two-dimensional isogeny in Algorithm 7, Line 13 and allow only for response isogenies $\varphi_{rsp}$ of odd degree. The choice made in Section 5 for $e_{rsp}$ guarantees the existence of a response isogeny $\varphi_{rsp}$ of degree $q < 2^{e_{rsp}}$, but such an isogeny needs not be of odd degree.

Let us recall that we work over $\mathbb{F}_{p^2}$, where $p$ is a prime of the form $c \cdot 2^e - 1$. In this heuristic version, we additionally require $e = e_{rsp} + e_{chl}$. In order to increase the likelihood of finding an odd-degree response isogeny $\varphi_{rsp}$ of degree $< 2^{e_{rsp}}$, the value $e_{rsp}$ is chosen to be larger than $e_{chl}$.

The Key Generation algorithm (Cfr. Algorithm 5) is left unchanged with the only exception that it also stores the points $\varphi_{sk}(P_0), \varphi_{sk}(Q_0)$ as internal optimisations. The Commitment Algorithm is similar to the one in Algorithm 6. The main difference is that the commitment isogeny $\varphi_{com}: E_0 \to E_{pk}$ is not computed via IdealTolsogeny but using FixedDegreelsogeny($N_{com}$). The heuristic good distribution of the commitment curves is discussed in [33, Remark 4].

The challenge space remains the same, i.e. the challenge chl is a positive integer $< 2^{e_{chl}}$. However, rather than describing an isogeny $\varphi_{chl}$ of degree $2^e$, it will describe an isogeny $\varphi_{chl}: E_{pk} \to E_{chl}$ of degree $2^{e_{chl}}$. To be precise, let $(P_{pk}, Q_{pk})$ be a deterministic basis of $E_{pk}[2^e]$, then $\varphi_{chl}: E_{pk} \to E_{chl}$ is the isogeny with kernel $\langle[2^{e_{rsp}}](P_{pk} + [chl]Q_{pk})\rangle$. In the non-heuristic version, the challenge isogeny $\varphi_{chl}$ has degree $2^e$ to ensure soundness even in the presence of backtracking response isogenies. This is not the case anymore since the response isogeny $\varphi_{rsp}$ has odd degree.

As we anticipated above, the main difference between the heuristic response algorithm and Algorithm 7 is that the response isogeny $\varphi_{rsp}$ has odd degree $q$; we give experimental estimates for the failure probability of finding a response isogeny of odd degree in Appendix A.1. Let $I_{sk}, I_{com}, I_{chl}$ and $I_{rsp}$ be the ideal associated with the isogenies $\varphi_{sk}, \varphi_{com}, \varphi_{chl}$ and $\varphi_{rsp}$, respectively. The ideal $I_{sk} \cdot I_{chl} \cdot \tilde{I}_{rsp} \cdot \tilde{I}_{com}$ describes an endomorphism $\theta$ on $E_0$, i.e. $\hat{\varphi}_{com} \circ \hat{\varphi}_{rsp} \circ \varphi_{chl} \circ \varphi_{sk} = \theta$. As a result, we can evaluate $\hat{\varphi}_{rsp} \circ \varphi_{chl}$ at the $2^e$-torsion point $P$ as $[(N_{sk}N_{com})^{-1}]\varphi_{com} \circ \theta \circ \hat{\varphi}_{sk}(P)$.

To represent the isogeny $\varphi_{rsp}$ via a two-dimensional isogeny, we still need to compute an auxiliary isogeny $\varphi_{aux}: E_{com} \to E_{aux}$ of degree $2^{e_{rsp}} - q$. Similarly to Algorithm 7, we first compute a random left $O_{0}$-ideal $I'_{aux}$ of norm $2^{e_{rsp}} - q$ and then its pushforward $I_{aux}$ through $I_{com}$. Thus, we can obtain $\varphi_{aux} \circ \varphi_{com}|_{2^e}$ via IdealTolsogeny($I_{com} \cdot I_{aux}$).

Using $\varphi_{aux} \circ \varphi_{com}|_{2^e}$, we compute

$$ \varphi_{aux} \circ \hat{\varphi}_{rsp} \circ \varphi_{chl}(P_{pk}) = [(N_{sk}N_{com})^{-1}]\varphi_{aux} \circ \varphi_{com} \circ \theta \circ \hat{\varphi}_{sk}(P_{pk}) $$

and

$$ \varphi_{aux} \circ \hat{\varphi}_{rsp} \circ \varphi_{chl}(Q_{pk}) = [(N_{sk}N_{com})^{-1}]\varphi_{aux} \circ \varphi_{com} \circ \theta \circ \hat{\varphi}_{sk}(Q_{pk}). $$
A A faster variant of SQIsign2D with heuristic security

In this section, we describe a heuristic version of the Σ-protocol described
in Section 5. The gist of this idea is to avoid the additional two-dimensional
isogeny in Algorithm 7, Line 13 and allow only for response isogenies ϕ<sub>rsp</sub> of
odd degree. The choice made in Section 5 for e<sub>rsp</sub> guarantees the existence of a
response isogeny ϕ<sub>rsp</sub> of degree q < 2<sup>e<sub>rsp</sub></sup>, but such an isogeny needs not be of odd
degree.

Let us recall that we work over $\mathbb{F}_{p^2}$, where $p$ is a prime of the form $c \cdot 2^e - 1$. In this heuristic version, we additionally require $e = e_{\text{rsp}} + e_{\text{chl}}$. In order to increase the likelihood of finding an odd-degree response isogeny $\varphi_{\text{rsp}}$ of degree < $2^{e_{\text{rsp}}}$, the value $e_{\text{rsp}}$ is chosen to be larger than $e_{\text{chl}}$.

The Key Generation algorithm (Cfr. Algorithm 5) is left unchanged with
the only exception that it also stores the points $\varphi_{\text{sk}}(P_0)$, $\varphi_{\text{sk}}(Q_0)$ as internal
optimisations. The Commitment Algorithm is similar to the one in Algorithm 6.
The main difference is that the commitment isogeny $\varphi_{\text{com}}: E_0 \to E_{\text{pk}}$ is not
computed via IdealTolsogeny but using FixedDegreelsogeny($N_{\text{com}}$). The heuristic
good distribution of the commitment curves is discussed in [33, Remark 4].

The challenge space remains the same, i.e. the challenge chl is a positive integer < 2<sup>e<sub>chl</sub></sup>. However, rather than describing an isogeny ϕ<sub>chl</sub> of degree 2<sup>e</sup>, it will describe an isogeny ϕ<sub>chl</sub>: E<sub>pk</sub> → E<sub>chl</sub> of degree 2<sup>e<sub>chl</sub></sup>. To be precise, let (P<sub>pk</sub>, Q<sub>pk</sub>) be a deterministic basis of E<sub>pk</sub>[2<sup>e</sup>], then ϕ<sub>chl</sub>: E<sub>pk</sub> → E<sub>chl</sub> is the isogeny with kernel ⟨[2<sup>e<sub>rsp</sub></sup>](P<sub>pk</sub> + [chl]Q<sub>pk</sub>)/⟩. In the non-heuristic version, the challenge isogeny ϕ<sub>chl</sub> has degree 2<sup>e</sup> to ensure soundness even in the presence of backtracking response isogenies. This is not the case anymore since the response isogeny ϕ<sub>rsp</sub> has odd degree.

As we anticipated above, the main difference between the heuristic response
algorithm and Algorithm 7 is that the response isogeny $\varphi_{\text{rsp}}$ has odd degree $q$; we
give experimental estimates for the failure probability of finding a response isogeny
of odd degree in Appendix A.1. Let $I_{\text{sk}}$, $I_{\text{com}}$, $I_{\text{chl}}$ and $I_{\text{rsp}}$ be the ideal associated
with the isogenies $\varphi_{\text{sk}}$, $\varphi_{\text{com}}$, $\varphi_{\text{chl}}$ and $\varphi_{\text{rsp}}$, respectively. The ideal $I_{\text{sk}} \cdot I_{\text{chl}} \cdot \bar{I}_{\text{rsp}} \cdot \bar{I}_{\text{com}}$
describes an endomorphism $\theta$ on $E_0$, i.e. $\hat{\varphi}_{\text{com}} \circ \hat{\varphi}_{\text{rsp}} \circ \varphi_{\text{chl}} \circ \varphi_{\text{sk}} = \theta$. As a result, we
can evaluate $\hat{\varphi}_{\text{rsp}} \circ \varphi_{\text{chl}}$ at the 2<sup>e</sup>-torsion point $P$ as [(N<sub>sk</sub>N<sub>com</sub>)<sup>-1</sup>]<sub>\varphi<sub>com</sub> \circ \theta \circ \hat{\varphi}_{\text{sk}}(P)</sub>.

To represent the isogeny $\varphi_{\text{rsp}}$ via a two-dimensional isogeny, we still need to
compute an auxiliary isogeny $\varphi_{\text{aux}}: E_{\text{com}} \to E_{\text{aux}}$ of degree $2^{e_{\text{rsp}}} - q$. Similarly
to Algorithm 7, we first compute a random left $\mathcal{O}_0$-ideal $I'_{\text{aux}}$ of norm $2^{e_{\text{rsp}}} - q$
and then its pushforward $I_{\text{aux}}$ through $I_{\text{com}}$. Thus, we can obtain $\varphi_{\text{aux}} \circ \varphi_{\text{com}}|_{2^e}$
via IdealTolsogeny($I_{\text{com}} \cdot I_{\text{aux}}$).

Using $\varphi_{\text{aux}} \circ \varphi_{\text{com}}|_{2^e}$, we compute

$$
\varphi_{\text{aux}} \circ \hat{\varphi}_{\text{rsp}} \circ \varphi_{\text{chl}}(P_{\text{pk}}) = [(N_{\text{sk}} N_{\text{com}})^{-1}] \varphi_{\text{aux}} \circ \varphi_{\text{com}} \circ \theta \circ \hat{\varphi}_{\text{sk}}(P_{\text{pk}})
$$

and

$$
\varphi_{\text{aux}} \circ \hat{\varphi}_{\text{rsp}} \circ \varphi_{\text{chl}}(Q_{\text{pk}}) = [(N_{\text{sk}} N_{\text{com}})^{-1}] \varphi_{\text{aux}} \circ \varphi_{\text{com}} \circ \theta \circ \hat{\varphi}_{\text{sk}}(Q_{\text{pk}}).
$$
In particular,

$$ (P_{\text{aux}} := [q^{-1}]\varphi_{\text{aux}} \circ \hat{\varphi}_{\text{rsp}} \circ \varphi_{\text{chl}}(P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}), \\ Q_{\text{aux}} := [q^{-1}2^{e_{\text{chl}}}]\varphi_{\text{aux}} \circ \hat{\varphi}_{\text{rsp}} \circ \varphi_{\text{chl}}(Q_{\text{pk}})) $$

is a basis of $E_{\text{chl}}$.

Such a basis can be used to represent the kernel of the two-dimensional isogeny to use during verification. The output of the response algorithm will then consist in $(E_{\text{aux}}, P_{\text{aux}}, Q_{\text{aux}})$. We summarise the response algorithm in Algorithm 9.

Algorithm 9 Heuristic Response

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

**Output:** $E_{\text{aux}}$, $P_{\text{aux}}$, $Q_{\text{aux}}$

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

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

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

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

5: Let $\theta$ be an endomorphism on $E_0$ such that it generates the ideal $I_{\text{sk}} \cdot I_{\text{chl}} \cdot \overline{I_{\text{rsp}}} \cdot \overline{I_{\text{com}}}$.

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

7: Compute $I_{\text{aux}}$ as the pushforward of $I'_{\text{aux}}$ through $I_{\text{com}}$.

8: $\varphi_{\text{aux}} \circ \varphi_{\text{com}}|_{2^e}, E_{\text{aux}} \leftarrow \text{IdealTolsogeny}(I_{\text{com}} \cdot I_{\text{aux}})$.

9: $P, Q \leftarrow [(N_{\text{com}}N_{\text{sk}})^{-1}]\varphi_{\text{aux}} \circ \varphi_{\text{com}} \circ \theta \circ \hat{\varphi}_{\text{sk}}(P_{\text{pk}}), [(N_{\text{com}}N_{\text{sk}})^{-1}]\varphi_{\text{aux}} \circ \varphi_{\text{com}} \circ \theta \circ \hat{\varphi}_{\text{sk}}(Q_{\text{pk}})$.

10: $P_{\text{aux}}, Q_{\text{aux}} \leftarrow [q^{-1}](P + [\text{chl}]Q), [q^{-1}2^{e_{\text{chl}}}]Q$.

11: return $E_{\text{aux}}$, $P_{\text{aux}}$, $Q_{\text{aux}}$.

To verify the response, the verifier first recomputes the challenge isogeny $\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$ with kernel $\langle [2^{e_{\text{rsp}}}] (P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}) \rangle$. Then, defines $P_{\text{chl}}$, $Q_{\text{chl}}$ to be the points $\varphi_{\text{chl}}(P_{\text{pk}} + [\text{chl}]Q_{\text{pk}})$ and $\varphi_{\text{chl}}[2^{e_{\text{chl}}}] (Q_{\text{pk}})$. From Kani's Lemma, the isogeny $\Phi: E_{\text{chl}} \times E_{\text{aux}} \to E'_{\text{aux}} \times E_{\text{com}}$ with kernel $\langle (P_{\text{chl}}, P_{\text{aux}}), (Q_{\text{chl}}, Q_{\text{aux}}) \rangle$ has matrix form

$$ \Phi = \begin{pmatrix} \varphi'_{\text{aux}} & -\varphi'_{\text{rsp}} \\ \hat{\varphi}_{\text{rsp}} & \widehat{\varphi}_{\text{aux}} \end{pmatrix}, $$

where the isogenies $\varphi'_{\text{aux}}$ and $\varphi'_{\text{rsp}}$ fit in the $(2^{e_{\text{rsp}}} - q, q)$-isogeny diamond Fig. 4. The Verification Algorithm is described in Algorithm 10.

A.1 Comparison with SQIsign2D and Failure Probability

Compared to SQIsign2D, this heuristic version is faster with respect to Commitment, Response and Verify.
In particular,

$$ (P_{\text{aux}} := [q^{-1}]\varphi_{\text{aux}} \circ \hat{\varphi}_{\text{rsp}} \circ \varphi_{\text{chl}}(P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}), \\ Q_{\text{aux}} := [q^{-1}2^{e_{\text{chl}}}]\varphi_{\text{aux}} \circ \hat{\varphi}_{\text{rsp}} \circ \varphi_{\text{chl}}(Q_{\text{pk}}) ) $$

is a basis of $E_{\text{chl}}$.

Such a basis can be used to represent the kernel of the two-dimensional isogeny to use during verification. The output of the response algorithm will then consist in $(E_{\text{aux}}, P_{\text{aux}}, Q_{\text{aux}})$. We summarise the response algorithm in Algorithm 9.

Algorithm 9 Heuristic Response

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

**Output:** $E_{\text{aux}}$, $P_{\text{aux}}$, $Q_{\text{aux}}$

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

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

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

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

5: Let $\theta$ be an endomorphism on $E_0$ such that it generates the ideal $I_{\text{sk}} \cdot I_{\text{chl}} \cdot \overline{I_{\text{rsp}}} \cdot \overline{I_{\text{com}}}$.

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

7: Compute $I_{\text{aux}}$ as the pushforward of $I'_{\text{aux}}$ through $I_{\text{com}}$.

8: $\varphi_{\text{aux}} \circ \varphi_{\text{com}}|_{2^e}, E_{\text{aux}} \leftarrow \text{IdealTolsogeny}(I_{\text{com}} \cdot I_{\text{aux}})$.

9: $P, Q \leftarrow [(N_{\text{com}}N_{\text{sk}})^{-1}]\varphi_{\text{aux}} \circ \varphi_{\text{com}} \circ \theta \circ \hat{\varphi}_{\text{sk}}(P_{\text{pk}}), [(N_{\text{com}}N_{\text{sk}})^{-1}]\varphi_{\text{aux}} \circ \varphi_{\text{com}} \circ \theta \circ \hat{\varphi}_{\text{sk}}(Q_{\text{pk}})$.

10: $P_{\text{aux}}, Q_{\text{aux}} \leftarrow [q^{-1}](P + [\text{chl}]Q), [q^{-1}2^{e_{\text{chl}}}]Q$.

11: return $E_{\text{aux}}$, $P_{\text{aux}}$, $Q_{\text{aux}}$.

To verify the response, the verifier first recomputes the challenge isogeny $\varphi_{\text{chl}}: E_{\text{pk}} \to E_{\text{chl}}$ with kernel $\langle [2^{e_{\text{rsp}}}] (P_{\text{pk}} + [\text{chl}]Q_{\text{pk}}) \rangle$. Then, defines $P_{\text{chl}}$, $Q_{\text{chl}}$ to be the points $\varphi_{\text{chl}}(P_{\text{pk}} + [\text{chl}]Q_{\text{pk}})$ and $\varphi_{\text{chl}}[2^{e_{\text{chl}}}] (Q_{\text{pk}})$. From Kani's Lemma, the isogeny $\Phi: E_{\text{chl}} \times E_{\text{aux}} \to E'_{\text{aux}} \times E_{\text{com}}$ with kernel $\langle (P_{\text{chl}}, P_{\text{aux}}), (Q_{\text{chl}}, Q_{\text{aux}}) \rangle$ has matrix form

$$ \Phi = \begin{pmatrix} \varphi'_{\text{aux}} & -\varphi'_{\text{rsp}} \\ \hat{\varphi}_{\text{rsp}} & \widehat{\varphi}_{\text{aux}} \end{pmatrix}, $$

where the isogenies $\varphi'_{\text{aux}}$ and $\varphi'_{\text{rsp}}$ fit in the $(2^{e_{\text{rsp}}} - q, q)$-isogeny diamond Fig. 4. The Verification Algorithm is described in Algorithm 10.

A.1 Comparison with SQIsign2D and Failure Probability

Compared to SQIsign2D, this heuristic version is faster with respect to Commitment, Response and Verify.
<figure><img src="image_6.png" /><figcaption>Fig. 4. ($2^{e_{resp}} - q, q$)-isogeny diamond.</figcaption></figure>

**Algorithm 10 Heuristic Verify**

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

**Output:** true or false.

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

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

3: $P_{chl}, Q_{chl} \leftarrow \varphi_{chl}(P_{pk}) + [chl]\varphi_{chl}(Q_{pk})$, $[2^{e_{chl}}]\varphi_{chl}(Q_{pk})$

4: Attempt to compute $\tilde{\Phi}: E_{chl} \times E_{aux} \to F_1 \times F_2$ with kernel $\langle (P_{chl}, P_{aux}), (Q_{chl}, Q_{aux}) \rangle$.

5: **if** $F_2 \cong E_{com}$ **then**

6: **return** true

7: **else**

8: **return** false

**Commitment:** Rather than relying on IdealTolsogeny, the heuristic Commitment employs FixedDegreelsogeny. The dominating cost of IdealTolsogeny is the computation of three two-dimensional isogenies, whereas FixedDegreelsogeny only requires one. Note that the same commitment algorithm could be employed in SQIsign-2D, but in order to have a provable uniform distribution of the commitment elliptic curves (Cfr. Lemma 20), we preferred IdealTolsogeny.

**Response:** The main difference with Algorithm 7 is to avoid the two-dimensional isogeny in Line 13 and allow only for response isogenies $\varphi_{rsp}$ of odd degree.

**Verify:** The challenge isogeny in Algorithm 10 is shorter than the one in Algorithm 8, hence providing a slightly faster verification.

The main problem we encounter in Algorithm 9 is the generation of an ideal $I_{rsp}$ of odd norm $< 2^{e_{rsp}}$ in Line 4. If after a certain number of attempts we cannot find any odd-norm ideal connecting $E_{com}$ and $E_{chl}$, we try to connect the curve $E_{com}^{(p)}$ and $E_{chl}$ with an ideal of odd norm $< 2^{e_{rsp}}$, where $E_{com}^{(p)}$ is the Galois conjugate of $E_{com}$, i.e. $E_{com}$ and $E_{com}^{(p)}$ are p-isogenous. Let $O_{com}$ be the order isomorphic to the endomorphism ring of $E_{com}$, then the order of $E_{com}^{(p)}$ can be obtained as $j \cdot O_{com} \cdot j^{-1}$. This usually allows us to find an ideal connecting $E_{com}^{(p)}$ and $E_{chl}$ of odd norm $< 2^{e_{rsp}}$.

If we cannot find a suitable connecting ideal relying on the Galois conjugate, we then allow the response isogeny $\varphi_{rsp}$ to have even degree but not to backtrack with $\varphi_{chl}$ in the language of Algorithm 7, we require $n_{bt} = 0$. The verification
<figure><img src="image_8.png" /><figcaption>Fig. 4. ($2^{e_{resp}} - q, q$)-isogeny diamond.</figcaption></figure>

**Algorithm 10 Heuristic Verify**

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

**Output:** true or false.

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

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

3: $P_{chl}, Q_{chl} \leftarrow \varphi_{chl}(P_{pk}) + [chl]\varphi_{chl}(Q_{pk})$, $[2^{e_{chl}}]\varphi_{chl}(Q_{pk})$

4: Attempt to compute $\tilde{\Phi}: E_{chl} \times E_{aux} \to F_1 \times F_2$ with kernel $\langle(P_{chl}, P_{aux}), (Q_{chl}, Q_{aux})\rangle$.

5: **if** $F_2 \cong E_{com}$ **then**

6: **return** true

7: **else**

8: **return** false

**Commitment:** Rather than relying on IdealTolsogeny, the heuristic Commitment employs FixedDegreelsogeny. The dominating cost of IdealTolsogeny is the computation of three two-dimensional isogenies, whereas FixedDegreelsogeny only requires one. Note that the same commitment algorithm could be employed in SQIsign-2D, but in order to have a provable uniform distribution of the commitment elliptic curves (Cfr. Lemma 20), we preferred IdealTolsogeny.

**Response:** The main difference with Algorithm 7 is to avoid the two-dimensional isogeny in Line 13 and allow only for response isogenies $\varphi_{rsp}$ of odd degree.

**Verify:** The challenge isogeny in Algorithm 10 is shorter than the one in Algorithm 8, hence providing a slightly faster verification.

The main problem we encounter in Algorithm 9 is the generation of an ideal $I_{rsp}$ of odd norm $< 2^{e_{rsp}}$ in Line 4. If after a certain number of attempts we cannot find any odd-norm ideal connecting $E_{com}$ and $E_{chl}$, we try to connect the curve $E_{com}^{(p)}$ and $E_{chl}$ with an ideal of odd norm $< 2^{e_{rsp}}$, where $E_{com}^{(p)}$ is the Galois conjugate of $E_{com}$, i.e. $E_{com}$ and $E_{com}^{(p)}$ are p-isogenous. Let $O_{com}$ be the order isomorphic to the endomorphism ring of $E_{com}$, then the order of $E_{com}^{(p)}$ can be obtained as $j \cdot O_{com} \cdot j^{-1}$. This usually allows us to find an ideal connecting $E_{com}^{(p)}$ and $E_{chl}$ of odd norm $< 2^{e_{rsp}}$.

If we cannot find a suitable connecting ideal relying on the Galois conjugate, we then allow the response isogeny $\varphi_{rsp}$ to have even degree but not to backtrack with $\varphi_{chl}$ in the language of Algorithm 7, we require $n_{bt} = 0$. The verification
will then work as in Algorithm 8, with the additional condition of checking that either $F_2$ is isomorphic to $E_{com}^{(p)}$.

Experimental results show that the failure probability for the prime we used for Level 1 is of around $10^{-8}$. While this version is undoubtedly faster with regard to all possible aspects, taking into account this failure probability makes its security more difficult to prove. Since the verification times do not differ much in the two versions, we opted to focus on the more secure version of SQIsign2D. We leave as future work the task of finding a provable failure probability, hence enhancing the security arguments underlying this heuristic version of SQIsign2D.

*Remark 27 (Using a dimension four response).* We remark that in this heuristic version of SQIsign2D, rather than returning a dimension two representation of $\varphi_{rsp}$, we could return a dimension four representation. This would speed up the signature even more because we would not need to compute the auxiliary isogeny anymore, and solve the failure cases because for a dimension four response, we can split the isogeny in two. This allows us to find an ideal response of good odd degree < $2^{2e_{rsp}}$ (in the terminology of [11]) rather than just < $2^{e_{rsp}}$, leaving ample room to find a suitable response. Of course, this would come at the cost of a worse verification time, owing to the need to computing an isogeny in dimension four rather than two.

This version would essentially be an adaptation of SQIsignHD to the more arithmetic friendly SQIsign2D prime, combined with the advantage of being able to use the statically uniform secret key isogeny and commitment isogeny of SQIsign2D. We remark that the same public key can be used for SQIsign2D signatures (the main version or the heuristic version) and this adapted version of SQIsignHD, allowing the signer to choose the tradeoffs between signature and verification time on the fly.
will then work as in Algorithm 8, with the additional condition of checking that either $F_2$ is isomorphic to $E_{com}^{(p)}$.

Experimental results show that the failure probability for the prime we used for Level 1 is of around $10^{-8}$. While this version is undoubtedly faster with regard to all possible aspects, taking into account this failure probability makes its security more difficult to prove. Since the verification times do not differ much in the two versions, we opted to focus on the more secure version of SQIsign2D. We leave as future work the task of finding a provable failure probability, hence enhancing the security arguments underlying this heuristic version of SQIsign2D.

*Remark 27 (Using a dimension four response).* We remark that in this heuristic version of SQIsign2D, rather than returning a dimension two representation of $\varphi_{rsp}$, we could return a dimension four representation. This would speed up the signature even more because we would not need to compute the auxiliary isogeny anymore, and solve the failure cases because for a dimension four response, we can split the isogeny in two. This allows us to find an ideal response of good odd degree < $2^{2e_{rsp}}$ (in the terminology of [11]) rather than just < $2^{e_{rsp}}$, leaving ample room to find a suitable response. Of course, this would come at the cost of a worse verification time, owing to the need to computing an isogeny in dimension four rather than two.

This version would essentially be an adaptation of SQIsignHD to the more arithmetic friendly SQIsign2D prime, combined with the advantage of being able to use the statically uniform secret key isogeny and commitment isogeny of SQIsign2D. We remark that the same public key can be used for SQIsign2D signatures (the main version or the heuristic version) and this adapted version of SQIsignHD, allowing the signer to choose the tradeoffs between signature and verification time on the fly.