# A Complete Security Proof of SQIsign

Marius Aardal, Andrea Basso, Luca de Feo, Sikhar Patranabis, Benjamin Wesolowski

► To cite this version:

Marius Aardal, Andrea Basso, Luca de Feo, Sikhar Patranabis, Benjamin Wesolowski. A Complete Security Proof of SQIsign. CRYPTO 2025, Aug 2025, Santa Barbara, United States. pp.190-222, 10.1007/978-3-032-01887-8_7. hal-05377021

HAL Id: hal-05377021

https://hal.science/hal-05377021v1

Submitted on 21 Nov 2025

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# A Complete Security Proof of SQIsign

Marius A. Aardal¹, Andrea Basso², Luca De Feo², Sikhar Patranabis³, and Benjamin Wesolowski⁴

¹ Aarhus University, Denmark; maardal@cs.au.dk

² IBM Research Europe, Zürich, Switzerland;
andrea.basso@ibm.com, crypto25@defeo.lu

³ IBM Research India, Bangalore, India; sikhar.patranabis@ibm.com

⁴ ENS de Lyon, CNRS, UMPA, UMR 5669, Lyon, France; benjamin.wesolowski@ens-lyon.fr

**Abstract.** SQIsign is the leading digital signature from isogenies. Despite the many improvements that have appeared in the literature, all its recent variants lack a complete security proof. In this work, we provide the first full security proof of SQIsign, as submitted to the second round of NIST's on-ramp track for digital signatures.

To do so, we introduce a new framework, which we call Fiat-Shamir with hints, that captures all those protocols where the simulator needs additional information to simulate a transcript. Using this framework, we show that SQIsign is EUF-CMA secure in the ROM, assuming the hardness of the One Endomorphism problem with hints, or the hardness of the Full Endomorphism Ring problem with hints together with a hint indistinguishability assumption; all assumptions, unlike previous ones in the literature, are non-interactive. Along the way, we prove several intermediate results that may be of independent interest.

**Date of this document:** August 1, 2025

## 1 Introduction

SQISIGN is a digital signature candidate in NIST's Post-Quantum Cryptography Standardization process [CSD+23, AAA+25]. Based on the theory of isogenies between supersingular elliptic curves, its security is usually claimed to reduce to the *Supersingular Endomorphism Ring Problem* or, equivalently, to the *Supersingular Isogeny Path Problem* [Wes22]. Despite the claims, the literature only contains incomplete sketches of a security proof, glossing over key details, heuristics, and logical gaps. To complicate matters, since the scheme was first introduced in [DKL+20], several variants have appeared [DLLW23, DLRW24, NOC+24, BDD+24, DF24], each calling for different proof techniques.

In all its incarnations, SQISIGN is based on a $\Sigma$-protocol which, informally, proves knowledge of the endomorphism ring of a supersingular curve $E_{pk}$. All variants follow the same pattern:<fnref n="5" />

1. The prover generates a random “commitment curve” $E_{com}$;

2. The verifier challenges with a random isogeny $E_{pk} \leftrightarrow E_{chl}$;

3. The prover responds with a random isogeny $E_{com} \leftrightarrow E_{chl}$;

4. The verifier checks that the response is a valid isogeny connecting $E_{com}$ to $E_{chl}$ and rejects if that is not the case.

Such a protocol is 2-special-sound: two responses $E_{com} \leftrightarrow E_{chl}$ and $E_{com} \leftrightarrow E'_{chl}$ to distinct challenges for the same commitment form a cycle $E_{pk} \leftrightarrow E_{chl} \leftrightarrow E_{com} \leftrightarrow E'_{chl} \leftrightarrow E_{pk}$ of isogenies and thus an endomorphism of $E_{pk}$. Although this comes short of a full description of the endomorphism ring, Page and Wesolowski have given a polynomial time reduction from the Endomorphism Ring Problem to the problem of computing a single non-scalar endomorphism [PW24].

Zero knowledge is much more delicate and crucially depends on the distribution of the response. In the original version of SQISIGN and in the first round NIST candidate [DKL+20, DLLW23, CSD+23], the response is a cyclic isogeny of fixed degree $2^x$ sampled in an algorithmically defined set. It is unknown how to efficiently sample from this distribution without knowledge of the secret key, thus the security proof simulates it with the uniform distribution on all cyclic isogenies of degree $2^x$, conjecturing that the associated distinguishing problem is hard. This weak form of zero-knowledge has been the source of several issues, e.g. in [DKL+20, Sec. 6] and [BLL25].

<footnote n="5">⁵ Older variants of SQISIGN [DKL+20, CSD+23] swap the roles of $E_{com}$ and $E_{pk}$ in the challenge and response. Here we focus on the version encountered in the current NIST candidate.</footnote>
In part to bypass the issue above, in part for efficiency, SQIsignHD [DLRW24] changed the definition of the response to be any isogeny $E_{com} \leftrightarrow E_{chl}$ of any degree up to a certain bound $B$. The same design was inherited by follow up works [NOC$^+$24, BDD$^+$24, DF24] and ultimately by the round-2 candidate [AAA$^+$25]. Although sampling from the set of all isogenies up to a certain degree feels more natural and possibly easier to simulate, there is a catch: isogenies of large prime degree can only be efficiently represented using so-called higher-dimensional (HD) representations, which can only be efficiently produced when given a description of the endomorphism rings of the curves, i.e. of the secrets.

Thus, HD variants appear to be even worse than the original SQISIGN in terms of zero-knowledge: there is no efficient algorithm to sample from a distribution even remotely similar to the response distribution, without knowledge of the secret. The way SQIsignHD and follow-ups get around this problem is by working with one or more interactive oracles that produce HD-representations of random isogenies of degree $\le B$. This means that, either explicitly or implicitly, all HD variants have only proved security in an ad-hoc model where every party has access to these oracles producing HD-representations. These proofs do not produce any statement that applies in the more standard Random Oracle Model. Furthermore, these proofs limit themselves to showing special soundness and zero-knowledge of the underlying $\Sigma$-protocol: given the ad-hoc nature of the model, it is unclear whether the standard proof for the Fiat-Shamir transform [PS96] applies. Thus, all HD variants of SQISIGN in the literature fall short of a meaningful security statement.

**Contributions.** In this work, we give the first full security proof of SQISIGN$^6$ as of the second round of NIST's on-ramp track for digital signatures [AAA$^+$25]. We innovate on several aspects:

- We introduce a new framework, which we call *Fiat-Shamir with hints*, that captures all those protocols where the simulator needs additional information to simulate a transcript. This framework can be applied to all HD variants of SQIsign, providing the first proof of security in the random oracle model (i.e., without any ad-hoc model) for all those protocols.

- To model the extra information needed by the simulator, previous works introduced interactive oracles to fill the gaps in the simulation. We replace the oracles with non-interactive *hints*, reducing the EUF-CMA security of SQISIGN only to non-interactive assumption, whose hardness is easier to analyze. We also study different hints, identifying one type of hints that allows us to reduce the EUF-CMA security of SQISIGN to a variant with hints of the endomorphism ring problem and a new indistinguishability problem.

- We carefully account for losses in the reduction, thereby obtaining precise statements on the security of SQISIGN's NIST parameters. Based on this, we also make suggestions that have negligible impact on the efficiency of the protocol while benefiting the strength of the security statements.

- Along our security proof, we obtain two smaller results that may be of independent interest: 1. we show that it is possible, in polynomial time, to sample from a distribution statistically close to the distribution of degrees of random isogenies of bounded degree; 2. we show there exists a tight quantum reduction (we only need a factoring oracle) from the endomorphism ring problem to the one endomorphism problem, reducing the runtime loss in the reduction from a factor approximately $2^{94} \log(p)^{13}$ to a factor 24.

## 1.1 Technical overview

**Fiat-Shamir with hints.** We would like to reduce the unforgeability of SQISIGN to the $EndRing_p$ problem. However, the protocol does not quite fit into the usual framework for proving security of Fiat-Shamir signatures. In particular, it has two shortcomings:

1. $\Sigma_{SQI}$ is special-sound, but not with respect to the original relation $R_{SQI}$.

2. We do not know how to construct a weak Honest-Verifier Zero-Knowledge simulator for $\Sigma_{SQI}$. Without knowledge of the endomorphism ring of a curve $E$, we can only efficiently evaluate random isogenies from $E$ of smooth degree. The SQISIGN protocol, however, uses isogenies of arbitrary degree in its response: thus, the degree of the simulated response isogenies could not follow the correct distribution.

While the first point only requires a little extra care, the second point is a significant obstacle. Notwithstanding, to the best of current knowledge the hardness of constructing isogenies of arbitrary degree seems independent of that of $EndRing_p$. If we could give the simulator a little “extra help” to

<footnote>$^6$ The round-2 SQISIGN submission slightly diverges from the protocol we analyse: for efficiency reasons, it relies on certain algorithms that may fail with very small probabilities. We discuss this in Section 7.</footnote>
produce these HD representations, then it could simulate the responses without needing to break the
scheme.

In Section 3, we thus introduce a new framework, which we call *Fiat-Shamir with hints*, for proving
EUF-CMA security of Fiat-Shamir signatures where the simulator needs access to some additional data,
which allows us to capture protocols like SQISIGN and prove their security. We remark that our approach
is significantly different from previous literature: all variants of SQISIGN that rely on higher-dimensional
representations [DLRW24, BDD<sup>+24</sup>, NOC<sup>+24</sup>, DF24] solved the simulation issue by proving security, either
explicitly or implicitly, in an ad-hoc model that provides one or more oracles to compute isogenies of
arbitrary degree. In contrast, we aim to prove security in the random oracle model, without any additional
oracles.

**EUF-CMA security of SQIsign.** In Section 4, we analyze the EUF-CMA security of SQIsign in the Fiat-Shamir with hints framework, using a hint distribution that we call $\mathcal{H}^{\text{sim}}$. We show that $\Sigma_{\text{SQI}}$ has high commitment min-entropy, is hint-assisted wHVZK, and is special-sound with respect to some soundness relation. This gives us our first result, namely that SQIsign is EUF-CMA secure in the ROM, assuming the hardness of the OneEnd problem (i.e. computing one non-trivial endomorphism) with hints.

However, we want to show that SQIsign is EUF-CMA secure as long as the EndRing problem (i.e.
computing all endomorphisms) is hard since the EndRing problem is a much more natural and well-studied
problem [EHL<sup>+18</sup>, EHL<sup>+20</sup>, Wes22, PW24]. In Section 5, we obtain a similar result by relying on a variant
with hints of the EndRing problem. To do so, however, we cannot rely on the $\mathcal{H}^{\text{sim}}$ hint distribution used so
far. The reduction from the EndRing problem to the OneEnd problem requires translating endomorphisms
from one curve to another, and the hint distribution $\mathcal{H}^{\text{sim}}$ enforces a specific distribution that is hard to
translate from one curve to another.

We sidestep this issue by introducing a new hint distribution $\mathcal{H}^{\text{unif}}$ that is more suitable for the reduction.
In particular, we show that the new hint distribution is pushable: given a $2^n$-isogeny<sup>7</sup> $\sigma: E \to E'$ and a
hint $h \leftarrow \mathcal{H}_{E}^{\text{unif}}$ for $E$, we can push it through $\sigma$ to get a hint for $E'$ distributed according to $\mathcal{H}_{E'}^{\text{unif}}$. We need
to introduce a new assumption to switch between distributions (which we argue is hard in Remark 5.1),
but the pushability property implies that the new hint distribution $\mathcal{H}^{\text{unif}}$ has several advantages over $\mathcal{H}^{\text{sim}}$:

- The hint formulation is simpler: the hint does not need to include what becomes the challenge isogeny in a SQISIGN transcript since a hint from the public key curve can be pushed to the challenge curve.

- The OneEnd problem with $\mathcal{H}^{\text{unif}}$ hints is equivalent to the EndRing problem with (the same) hints, which allows us to reduce the hardness of the EndRing problem with hints to the EUF-CMA security of SQISIGN.

- A similar argument shows the EndRing problem with $\mathcal{H}^{\text{unif}}$ hints is random self-reducible, and thus it admits an average-case to worst-case reduction.

- Lastly, the sampling of hints is conceptually easier, which allows us to provide an argument for
why we do not expect these hints to make the EndRing problem easier.

Putting everything together, we obtain a proof of the EUF-CMA security of SQISIGN in the ROM,
based on the hardness of a variant of the endomorphism ring problem with hints and of the hint
indistinguishability problem. When the reduction is classical, the runtime loss in the reduction is about
the same as in [PW24], which is polynomial but considerably large. To obtain a tighter proof of security,
we show that quantum reduction (or, equivalently, a classical reduction with access to a factoring oracle)
has a runtime loss that is constant and small. This is our main result, which is summarized in Theorem 6.

2 Preliminaries

2.1 Notation

We let $\lambda \in \mathbb{N}$ denote the security parameter. All algorithms will (implicitly) take as input the unary encoding of the security parameter $1^{\lambda}$. We refer to algorithms running in probabilistic polynomial time in the length of their inputs as PPT. We let $\text{poly}(x_1, \dots, x_n)$ denote an unspecified positive polynomial in $x_1, \dots, x_n$. Similarly, $\text{negl}(\lambda)$ denotes an unspecified negligible function in $\lambda$. When an algorithm $\mathcal{A}$ has black-box query access to an oracle $\mathcal{O}$, we denote this as $\mathcal{A}^{\mathcal{O}}$.

<footnote n="7">⁷ We use isogenies of degree $2^n$ because that is the degree of the challenge isogeny in SQISIGN, but the distribution is pushable through any smooth-degree isogeny.</footnote>
We write $ln$ and $log$ for the natural and the base-2 logarithm respectively. For $x, y \in \{0, 1\}^*$, we write $x \parallel y$ for their concatenation and $|x|$ for the length of $x$.

For a probability distribution $D$, we write $x \leftarrow D$ for sampling $x$ from $D$. For a finite set $S$, we denote the uniform distribution over $S$ by $\mathcal{U}(S)$ and write $x \xleftarrow{\$} S$ for sampling $x$ from $\mathcal{U}(S)$. For two distributions $D_0, D_1$ over $S$, the statistical distance between $D_0$ and $D_1$ is

$$ \Delta(D_0, D_1) := \frac{1}{2} \sum_{s \in S} |\Pr[D_0 = s] - \Pr[D_1 = s]| $$

For an algorithm $\mathcal{A}$ outputting a bit $b$, we define its advantage in distinguishing between $D_0$ and $D_1$ as

$$ \mathbf{Adv}^{\text{dist}}[D_0, D_1](\mathcal{A}) := \left| \Pr[1 \leftarrow \mathcal{A}(x) \mid x \leftarrow D_0] - \Pr[1 \leftarrow \mathcal{A}(x) \mid x \leftarrow D_1] \right|. $$

Throughout this document, $p$ is a prime congruent to $3 \mod 4$ of cryptographic size ($p \approx 2^{2\lambda}$). $E_A$ denotes the Montgomery curve $y^2 = x^3 + Ax^2 + x$. We write $\text{Supersingular}_p$ for the set of supersingular Montgomery curves $E_A$ with $A \in \mathbb{F}_{p^2}$ and $j(\text{Supersingular}_p)$ for their $j$-invariants.

## 2.2 Probability distributions

The statistical distance satisfies several well known properties.

**Proposition 2.1.** Let $D_0$ and $D_1$ be random variables over a finite set $S$.

(i) $\Delta(D_0, D_1)$ is a metric on distributions.

(ii) For every subset $T \subseteq S$,

$$ \Pr[D_0 \in T] \leq \Pr[D_1 \in T] + \Delta(D_0, D_1). $$

(iii) Let $F$ be a random variable over functions $f: S \to T$ for some finite set $T$. Then

$$ \Delta(F(D_0), F(D_1)) \leq \Delta(D_0, D_1). $$

There is equality if and only if every possible $f$ is injective.

**Proposition 2.2.** Let $X_1, \dots, X_n, Y_1, \dots, Y_n$ be mutually independent random variables, where for each $i = 1, \dots, n$, $X_i$ and $Y_i$ are defined over a finite set $S_i$. Then the statistical distance between the joint distributions $(X_1, \dots, X_n)$ and $(Y_1, \dots, Y_n)$ satisfies

$$ \Delta((X_1, \dots, X_n), (Y_1, \dots, Y_n)) \leq \sum_{i=1}^{n} \Delta(X_i, Y_i). $$

**Proposition 2.3.** Let $D_0$ and $D_1$ be random variables over a finite set $S$. Let $\mathcal{A}$ be an algorithm taking as input an element from $S$ and outputting a single bit. Then

$$ \mathbf{Adv}^{\text{dist}}[D_0, D_1](\mathcal{A}) = \Delta(\mathcal{A}(D_0), \mathcal{A}(D_1)) \leq \Delta(D_0, D_1). $$

*Proof.* If we fix the random tape of $\mathcal{A}$, it becomes a deterministic function $S \to \{0, 1\}$. Therefore, $\mathcal{A}$ can be seen as a random variable over functions $S \to \{0, 1\}$.

$$ \begin{aligned} \Delta(\mathcal{A}(D_0), \mathcal{A}(D_1)) &= \frac{1}{2} |\Pr[\mathcal{A}(D_0) = 0] - \Pr[\mathcal{A}(D_1) = 0]| \\ &\quad + \frac{1}{2} |\Pr[\mathcal{A}(D_0) = 1] - \Pr[\mathcal{A}(D_1) = 1]| \\ &= \frac{1}{2} |(1 - \Pr[\mathcal{A}(D_0) = 1]) - (1 - \Pr[\mathcal{A}(D_1) = 1])| \\ &\quad + \frac{1}{2} |\Pr[\mathcal{A}(D_0) = 1] - \Pr[\mathcal{A}(D_1) = 1]| \\ &= \mathbf{Adv}^{\text{dist}}[D_0, D_1](\mathcal{A}) \end{aligned} $$

The inequality $\Delta(\mathcal{A}(D_0), \mathcal{A}(D_1)) \leq \Delta(D_0, D_1)$ follows by Proposition 2.1. $\square$

<figure><img src="image_2.png" /></figure>
Experiment 1: Weak honest-verifier zero-knowledge

$\mathrm{Real}_{\Sigma}(1^{\lambda})$

1: $(x, w) \leftarrow \mathrm{Gen}_R(1^{\lambda})$

2: $(\mathrm{com}, \mathrm{state}) \leftarrow \mathcal{P}_1(x, w)$

3: chl $\stackrel{\$}{\leftarrow}$ C

4: rsp $\leftarrow \mathcal{P}_2(\mathrm{state}, \mathrm{chl})$

5: **return** $(x, \mathrm{com}, \mathrm{chl}, \mathrm{rsp})$

$\mathrm{Sim}_{\Sigma}(1^{\lambda}, S)$

1: $(x, w) \leftarrow \mathrm{Gen}_R(1^{\lambda})$

2: $(\mathrm{com}, \mathrm{chl}, \mathrm{rsp}) \leftarrow S(x)$

3: **return** $(x, \mathrm{com}, \mathrm{chl}, \mathrm{rsp})$

## 2.3 Relations and $\Sigma$-protocols

A binary relation $R$ is a set of tuples $(x, w) \in \mathcal{X} \times \mathcal{W} \subseteq \{0, 1\}^* \times \{0, 1\}^*$. We refer to $x$ as the statement and $w$ as the witness. All relations in this paper are NP relations. Given $(x, w)$, we can check if it is in $R$ in polynomial time in $|x|$.

An instance generator $\mathrm{Gen}_R$ for $R$ is a PPT algorithm which on input $1^{\lambda}$ outputs a pair $(x, w)$ such that $(x, w) \in R$ and $|x| = \mathrm{poly}(\lambda)$. All relations we will consider come equipped with an instance generator.

**Definition 2.1 (Hard relation).** Let $R$ be a relation. We say that $R$ is a hard relation if for all PPT algorithms $\mathcal{A}$,

$$ \mathrm{Adv}_{R}^{\mathrm{rel}}(\mathcal{A}) := \mathrm{Pr} \left[ (x, w^*) \in R \mid (x, w) \leftarrow \mathrm{Gen}_R(1^{\lambda}), w^* \leftarrow \mathcal{A}(x) \right] = \mathrm{negl}(\lambda). $$

**Definition 2.2 ($\Sigma$-protocol).** A $\Sigma$-protocol for a relation $R$ is a 3-message interactive protocol between a prover and a verifier, given by a tuple of PPT algorithms $(\mathcal{P}_1, \mathcal{P}_2, \mathcal{V})$ as follows:

1. On input $(x, w) \in R$, the prover runs $(\mathrm{com}, \mathrm{state}) \leftarrow \mathcal{P}_1(x, w)$, obtaining a commitment $\mathrm{com}$ and the state $\mathrm{state}$ needed for the response computation. It sends $\mathrm{com}$ to the verifier.

2. The verifier samples a challenge chl uniformly from the challenge space $C$ and sends it to the prover.

3. The prover replies to the verifier with the response rsp $\leftarrow \mathcal{P}_2(\mathrm{state}, \mathrm{chl})$.

4. Finally, the verifier runs the verification algorithm on input the statement $x$ and the transcript $(\mathrm{com}, \mathrm{chl}, \mathrm{rsp})$ to obtain a bit $b \leftarrow \mathcal{V}(x, \mathrm{com}, \mathrm{chl}, \mathrm{rsp})$. It accepts if and only if $b = 1$.

The $\Sigma$-protocol should always have correctness. If the prover and verifier run the protocol honestly, the verifier should accept except with negligible probability in $\lambda$. In addition, there are several other security properties of interest.

**Definition 2.3 (wHVZK).** $\Sigma$ is weak honest-verifier zero-knowledge (wHVZK) if there exists a PPT algorithm $\mathcal{S}$, called the simulator, such that for all PPT algorithms $\mathcal{A}$,

$$ \mathrm{Adv}_{\Sigma, \mathcal{S}}^{\mathrm{wHVZK}}(\mathcal{A}) := \mathrm{Adv}^{\mathrm{dist}}[\mathrm{Real}_{\Sigma}(1^{\lambda}), \mathrm{Sim}_{\Sigma}(1^{\lambda}, \mathcal{S})](\mathcal{A}) = \mathrm{negl}(\lambda), $$

where $\mathrm{Real}_{\Sigma}(1^{\lambda})$ and $\mathrm{Sim}_{\Sigma}(1^{\lambda}, \mathcal{S})$ are the distributions defined in Experiment 1.

**Definition 2.4 (MinEnt).** $\Sigma$ has high commitment min-entropy if it holds that

$$ \mathrm{MinEnt}(\Sigma) := \max_{(x,w) \text{ com}} \max \mathrm{Pr} \left[ \mathrm{com} = \mathrm{com}' \mid (\mathrm{com}', \mathrm{state}) \leftarrow \mathcal{P}_1(x, w) \right] = \mathrm{negl}(\lambda), $$

where the first max ranges over the pairs that might be output by $\mathrm{Gen}_R(1^{\lambda})$.

Note that this definition is slightly different from previous works (e.g. [AABN02]). The actual min-entropy of the commitment is $-\log(\mathrm{MinEnt}(\Sigma))$.

**Definition 2.5 (Special soundness).** $\Sigma$ is special-sound if, given a statement $x$ and two accepting transcripts $(\mathrm{com}, \mathrm{chl}, \mathrm{rsp})$ and $(\mathrm{com}, \mathrm{chl}', \mathrm{rsp}')$ for $x$ with $\mathrm{chl} \neq \mathrm{chl}'$, we can compute a witness s.t. $(x, w) \in R$ in polynomial time in $|x|$.
**Game 1:** IMP-PA<sub>Σ</sub>(A<sub>1</sub>, A<sub>2</sub>)

1: (x, w) ← Gen<sub>R</sub>(1<sup>λ</sup>)

2: (com<sup>*</sup>, state<sup>*</sup>) ← A<sub>1</sub><sup>OTrans<sub>x,w</sub></sup>(x)

3: chl<sup>*</sup> $\leftarrow C$

4: rsp<sup>*</sup> ← A<sub>2</sub>(state<sup>*</sup>, chl<sup>*</sup>)

5: return Ver<sub>Σ</sub>(x, com<sup>*</sup>, chl<sup>*</sup>, rsp<sup>*</sup>)

OTrans<sub>x,w</sub>( ):

1: com, state $\leftarrow P_1(x, w)$

2: chl $\leftarrow C$

3: rsp $\leftarrow P_2(x, w, state)$

4: return (com, chl, rsp)

**Definition 2.6 (Knowledge soundness).** Σ is knowledge sound with knowledge error κ : $\mathbb{N} \to [0, 1]$ if there exists a knowledge extractor $\mathcal{E}$, defined as follows: On input a statement $x$ and given rewindable black-box query-access to a prover $P^*$, it runs in an expected polynomial number of steps in $|x|$ (counting each invocation of $P^*$ as a single step), and finds a witness for $x$ with probability

$$ \Pr[(x, w^*) \in R \mid w^* \leftarrow \mathcal{E}^{P^*}(x)] \geq \varepsilon(\mathcal{P}^*) - \kappa(|x|), $$

where $\varepsilon(\mathcal{P}^*)$ is the probability that the verifier accepts in the protocol with $\mathcal{P}^*$.

We say that Σ is knowledge sound when $\kappa(|x|) = \text{negl}(|x|)$.

**Lemma 2.1 ([ACK21]).** If Σ is special-sound, then it is knowledge sound with knowledge error $\kappa = 1/|C|$. In expectation, the extractor invokes the prover at most 2 times.

A Σ-protocol can be seen as an identification scheme [AABN02]. The prover is trying to convince the verifier that it knows a secret $w$ associated to the identity $x$. We consider security against an attacker that might have eavesdropped on honest runs of the protocol before it attempts to impersonate the identity $x$.

**Definition 2.7 (IMP-PA [AABN02]).** We say that Σ is secure under passive impersonation attacks (IMP-PA) if for all PPT two-stage algorithms $\mathcal{A} = (A_1, A_2)$ it holds that

$$ \text{Adv}_{\Sigma}^{\text{IMP-PA}}(\mathcal{A}) := \Pr[\text{IMP-PA}_{\Sigma}(\mathcal{A}) = 1] = \text{negl}(\lambda), $$

where IMP-PA<sub>Σ</sub> is the game presented in Game 1.

If Σ is a Σ-protocol for a hard relation $R$ that is special-sound, wHVZK and has $1/|C| = \text{negl}(\lambda)$, then it can be shown that Σ is IMP-PA-secure. In fact, we prove a generalization of this result in Section 3.2.

## 2.4 Signature schemes in the ROM

In the random oracle model (ROM) all algorithms are given black-box query access to the random oracle RO, implementing a uniformly random function $\{0, 1\}^* \to C$. We usually omit the dependency on the random oracle from our notation, writing $\mathcal{A}$ instead of $\mathcal{A}^{\text{RO}}$.

**Definition 2.8 (Signature scheme).** Let $M$ be some set. A signature scheme in the ROM for a message space $M$ is a tuple of PPT algorithms (Gen, Sign, Ver) defined as follows.

- Gen(1<sup>λ</sup>): On input the security parameter $\lambda$, the key generation algorithm outputs the public key pk and the secret key sk.

- Sign(sk, msg): On input the secret key sk and a message msg $\in M$, the signing algorithm outputs a signature sig.

- Ver(pk, msg, sig): On input the public key pk, a message msg and a signature sig, the verification algorithm outputs 1 (accept) or 0 (reject).

A signature scheme should satisfy two security properties, correctness and EUF-CMA. The former says that the verification of a correctly generated signature should only fail with negligible probability in $\lambda$. The latter is defined as follows.

**Definition 2.9 (EUF-CMA).** Let $S = (\text{Gen}, \text{Sign}, \text{Ver})$ be a signature scheme. We say that $S$ satisfies existential unforgeability under chosen message attacks (EUF-CMA) if it holds for all PPT random-oracle algorithms $\mathcal{A}$ that

$$ \text{Adv}_{S}^{\text{EUF-CMA}}(\mathcal{A}) := \Pr[\text{EUF-CMA}_{S}(\mathcal{A}) = 1] = \text{negl}(\lambda), $$

where EUF-CMA<sub>S</sub> is the game presented in Game 2.
### Game 2: EUF-CMA<sub>S</sub>(A)

1. $(pk, sk) \leftarrow \text{Gen}(1^{\lambda})$

2. $Q := \emptyset$

3. $(msg^*, sig^*) \leftarrow A^{\text{OSign}}(pk)$

4. if $\text{Ver}(pk, msg^*, sig^*) = 1 \wedge msg^* \notin Q$ then

5. return 1

6. else

7. return 0

$\text{OSign}(msg)$

1. $sig \leftarrow \text{Sign}(sk, msg)$

2. $Q := Q \cup \{msg\}$

3. return sig

$\Sigma$-protocols can be used to construct signature schemes in the ROM, using the *Fiat-Shamir transform*. The Fiat-Shamir transform $\text{FS}[\Sigma]$ of $\Sigma$ is the non-interactive protocol where the challenge is obtained as $chl \leftarrow \text{RO}(\text{com} \parallel x)$.

**Definition 2.10 (Fiat-Shamir signature).** Let $\Sigma$ be a $\Sigma$-protocol for a relation $R$ and let $M \subseteq \{0, 1\}^*$. We define the signature scheme $\text{SIG}[\Sigma]$ as follows.

- $\text{Gen}(1^{\lambda})$: Sample $(x, w) \leftarrow \text{Gen}_R(1^{\lambda})$. Set $pk := x$ and $sk := (x, w)$, and output $(pk, sk)$.

- $\text{Sign}(sk, msg)$: Generate a transcript $(com, chl, rsp)$ using the prover algorithm in $\text{FS}[\Sigma]$, but compute the challenge as $chl \leftarrow \text{RO}(\text{com} \parallel x \parallel msg)$. Output $\text{sig} := (com, chl, rsp)$.

- $\text{Ver}(pk, msg, sig)$: Accept if and only if $\text{sig} = (\text{com}, \text{chl}, \text{rsp})$ such that $\mathcal{V}(x, \text{com}, \text{chl}, \text{rsp}) = 1$ and $chl = \text{RO}(\text{com} \parallel x \parallel msg)$.

Observe that $\text{SIG}[\Sigma]$ is essentially the Fiat-Shamir transform of $\Sigma$, but with the relation modified to $R^* = \{(x \parallel msg, w) | (x, w) \in R, msg \in M\}$.

If $\Sigma$ is an IMP-PA-secure identification scheme and has high commitment min-entropy, then $\text{SIG}[\Sigma]$ is EUF-CMA-secure.

**Lemma 2.2 ([AABN02, Lemma 1]).** For any PPT algorithm $A$ attacking the EUF-CMA of $\text{SIG}[\Sigma]$, there exists a PPT two-stage algorithm $B$ such that

$$ \text{Adv}_{\text{SIG}[\Sigma]}^{\text{EUF-CMA}}(A) \le (q+1) \cdot \text{Adv}_{\Sigma}^{\text{IMP-PA}}(B) + (q+s+1)s \cdot \text{MinEnt}(\Sigma), $$

where $q$ and $s$ are upper bounds on the number of queries that $A$ makes to RO and $\text{OSign}$, respectively. Furthermore, $B$ makes at most $s$ queries to the transcript oracle $\text{OTrans}$.

## 2.5 Computing isogenies

SQISIGN uses three distinct ways to encode and compute with isogenies. It is useful to define a computational abstraction.

**Definition 2.11 ([BDD<sup>+</sup>24]).** Let $\mathbb{F}_q$ be a finite field. An isogeny evaluator $\mathcal{E}$ is a pair of polynomial time algorithms:

- $\mathcal{E}.\text{valid}(D)$: On input a string $D \in \{0, 1\}^*$ it outputs $\perp$ or a triple $(E, E', d)$. In the latter case, $E$ and $E'$ are elliptic curves defined over $\mathbb{F}_q$ and $D$ represents an isogeny $\varphi: E \to E'$ of degree $d$.

- $\mathcal{E}.\text{eval}(D, P)$: On input a string $D \in \{0, 1\}^*$ and a point $P \in E(\mathbb{F}_{q^k})$, it outputs the image point $\varphi(P) \in E'(\mathbb{F}_{q^k})$ if $\mathcal{E}.\text{valid}(D) = (E, E', d)$, otherwise the output is undefined.

In the case that $\mathcal{E}.\text{valid}(D) \neq \perp$ and $D$ is of size polynomial in $\log(q)$ and $\log(d)$, we say that $D$ is an efficient representation of $\varphi$ (with respect to $\mathcal{E}$).

The first representation used in SQISIGN is restricted to isogenies of degree $2^n$, represented as 2-isogeny walks: the isogeny is stored as a chain $\varphi = \varphi_1 \circ \varphi_2 \circ \dots \circ \varphi_n$ of isogenies of degree 2. It is clear this representation is efficient.

The second is the ideal representation. If $O \simeq \text{End}(E)$ is a maximal order of the quaternion algebra ramified at $p$ and $\infty$, the Deuring correspondence establishes a bijection between left ideals of $O$ and isogenies with domain $E$. Algorithmically, given a basis of a left ideal of $O$, there are PPT algorithms to compute the degree and the image of the associated isogeny and to evaluate it on arbitrary points [EHL<sup>+</sup>18, Wes22, Ler22]. This efficient representation intrinsically makes use of the secret key in SQISIGN, and is thus only used internally by the prover.
The final representation is the so-called *higher-dimensional (HD) representation*. Following Robert [Rob22], any isogeny between elliptic curves can be “embedded” into an isogeny of higher dimensional abelian varieties using Kani’s lemma [Kan97]. SQISIGN only uses embeddings into chains of (2,2)-isogenies of (2-dimensional) abelian surfaces, which can be efficiently stored and evaluated. Although these yield efficient representations of any isogeny, they are in general difficult to produce in the first place. In SQISIGN they are easily computed given knowledge of the secret key, but the difficulty of computing them in general is the key obstacle to proving security which we address in Section 3.

Both the ideal and the HD representation support an extended list of additional algorithms operating on them.

**Lemma 2.3 (Algorithms on representations).** For each of the operations below there is a PPT algorithm which operates on ideal (resp. HD) representations:

- **Dual:** On input $\varphi: E_1 \to E_2$, compute $\hat{\varphi}: E_2 \to E_1$.

- **Equality check:** On input $\varphi, \psi: E_1 \to E_2$, check whether $\varphi = \psi$.

- **Composition:** On input $\varphi: E_1 \to E_2$ and $\psi: E_2 \to E_3$, compute $\psi \circ \varphi: E_1 \to E_3$.

- **Splitting:** On input $\varphi: E_1 \to E_2$ and coprime $n_1, n_2$ s.t. $\deg(\varphi) = n_1n_2$, find $\varphi_1, \varphi'_1$ of degree $n_1$ and $\varphi_2, \varphi'_2$ of degree $n_2$ s.t. $\varphi = \varphi'_2 \circ \varphi_1 = \varphi'_1 \circ \varphi_2$.

- **Division:** On input $\varphi: E_1 \to E_2$, $\varphi_l: E_1 \to E_2'$ and $\varphi_r: E_1' \to E_2$, check if there exist $\varphi'_l, \varphi'_r$ s.t. $\varphi = \varphi'_r \circ \varphi_l$ or $\varphi = \varphi_r \circ \varphi'_l$, and if so output them.

- **Pushforward:** On input $\varphi: E_1 \to E_2$ and $\psi: E_1 \to E_3$ with coprime degrees, compute a pushforward $\varphi': E_3 \to E_{23}$ of $\varphi$ by $\psi$, meaning that $\ker(\varphi') = \psi(\ker(\varphi))$.

- **Backtracking:** On input $\varphi: E_2 \to E_3$ and $\sigma: E_4 \to E_2$ with $\gcd(\deg \varphi, \deg \sigma)$ smooth, find $\psi, \sigma'$, and $\varphi'$ s.t. $\sigma = \hat{\psi} \circ \sigma'$, $\varphi = \varphi' \circ \psi$, and $\ker(\psi) = \ker(\varphi) \cap \ker(\hat{\sigma})$. We say that $\psi$ is the backtracking component of $\varphi$ and $\sigma$. If $\varphi'$ and $\sigma'$ are cyclic, then so is $\varphi' \circ \sigma'$.

*Proof.* All of the above operations are discussed in the literature [Ler22, Rob24], with the exception of **Backtracking**, which we now detail.

We start with the ideal representation. Let $I_\varphi$ and $I_{\hat{\sigma}}$ be the left End$(E_2)$-ideals vanishing on $\ker(\varphi)$ and $\ker(\hat{\sigma})$ respectively. Then $I_\varphi + I_{\hat{\sigma}}$ is the vanishing ideal of $\ker \psi$ and thus an ideal representation of $\psi$. Now we can use **Division** to compute ideal representations of $\varphi'$ and $\sigma'$.

For the HD representation we need more work. First, using **Splitting** and the fact that $\gcd(\deg \varphi, \deg \sigma)$ is smooth we reduce to the case where $\deg \varphi$ and $\deg \sigma$ are powers of a small prime $\ell$.

Next, we factor the common factors $[\ell]$ from $\varphi$ and $\sigma$, by constructing an HD representation of $[\ell]$ ([Rob24, Proposition 6.6]) and applying **Division** repeatedly. We thus reduce to the case where at least one of $\varphi$ and $\sigma$ is cyclic; without loss of generality, assume $\varphi$ is.

Finally, we enumerate all $\ell$-isogenies $\psi_i$ from $E_2$ using Vélu's formulas, and use **Division** to factor $\varphi = \varphi_0 \circ \psi_i$, then again **Division** to factor $\hat{\sigma} = \hat{\sigma}_0 \circ \psi_i$, and continue recursively on $\varphi_0$ and $\sigma_0$. We stop when one of the **Division** attempts fails, at which point, if both $\varphi$ and $\sigma$ are cyclic, $\varphi \circ \sigma$ must also be. $\square$

**Computational assumptions.** We recall two foundational computational problems in isogeny-based cryptography.

**Problem 1 (EndRing$_p$).** Given a curve $E \in \text{Supersingular}_p$, find four endomorphisms in efficient representation that form a basis of $\text{End}(E)$ as a lattice.

**Problem 2 (OneEnd$_p$).** Given a curve $E \in \text{Supersingular}_p$, find an endomorphism in $\text{End}(E) \setminus \mathbb{Z}$ in efficient representation.

These problems are believed to computationally hard, even for quantum adversaries. Specifically, we assume that they have worst-case hardness, meaning that no algorithm can solve them in polynomial time in $\log p$ for all curves. This implies that the problems must be hard for uniformly random curves, by well-known worst-case to average-case reductions. Furthermore, a recent line of work [Wes22, PW24] shows that they are equivalent under polynomial-time reductions.

**The stationary distribution** $S_j$ is the limit distribution of the random walking process which from a $j(E) \in j(\text{Supersingular}_p)$ selects uniformly at random an $\ell$-isogeny $\varphi: E \to E'$ among those that do not backtrack and moves to $j(E')$. [BCC$^{+}$23, Theorem 11] proves the following fact.
<table><caption>Table 1: The public parameters of SQIsign</caption><thead><tr><th>Parameter</th><th>p</th><th>e<sub>rsp</sub></th><th>e<sub>chl</sub></th><th>N<sub>mix</sub></th></tr></thead><tbody><tr><td>Description</td><td>p = c &middot; 2<sup>e</sup> &minus; 1 prime,<br/>p &lt; 2<sup>2&lambda;</sup>, e &asymp; 2&lambda;</td><td>[log<sub>2</sub>(&radic;p)]</td><td>e &minus; e<sub>rsp</sub></td><td>Smallest prime &gt; 2<sup>4&lambda;</sup></td></tr></tbody></table>

**Proposition 2.4.** The stationary distribution $S_j$ on $j(\text{Supersingular}_p)$ is the distribution with

$$ \Pr[j(E) \leftarrow S_j] = \frac{24}{(p-1)|\text{Aut}(E)|}. $$

Let $\ell \neq p$ be prime. Let $\pi$ be a distribution on $j(\text{Supersingular}_p)$ and let $D_{\pi}^{\ell k}$ be the distribution after $k$ steps of a non-backtracking random walk, then

$$ \Delta(D_{\pi}^{\ell k}, S_j) \leq \frac{(k+1)}{4} \sqrt{\frac{p}{\ell^k}}. $$

We define the stationary distribution $S$ on $\text{Supersingular}_p$ such that $j^* \leftarrow S_j$ and $A$ is uniformly distributed among those such that $j(E_A) = j^*$.

## 2.6 The SQIsign signature scheme

We recap SQISIGN, as submitted to the round-two NIST standardization process for additional post-quantum signatures [AAA$^{+25}$]. It is a Fiat-Shamir signature constructed from a $\Sigma$-protocol $\Sigma_{\text{SQI}}$. We reproduce high-level pseudocode for the protocol; for a more detailed description see [AAA$^{+25}$].

**Public parameters.** For each security level $\lambda$, SQISIGN defines some public parameters $pp$, presented in Table 1. We denote the algorithm that deterministically outputs $pp$ by $\text{PublicParam}_{\text{SQI}}(1^{\lambda})$. In addition, $E_0$ denotes the starting curve with $j$-invariant 1728 and known endomorphism ring $\text{End}(E_0) \cong \mathcal{O}_0$.

**Algorithmic building blocks.** We highlight a few recurring algorithmic building blocks in Table 2.

<table><caption>Table 2: Algorithmic building blocks</caption><thead><tr><th>Algorithm</th><th>Inputs</th><th>Outputs</th></tr></thead><tbody><tr><td>DeterministicBasis</td><td>E ∈ Supersingular<sub>p</sub></td><td>A deterministically computed basis (P, Q) for E[2<sup>e</sup>].</td></tr><tr><td>IdealTolsogeny</td><td>Left O<sub>0</sub>-ideal I</td><td>E<sub>I</sub> and (P<sub>I</sub>, Q<sub>I</sub>), where<br/>φ<sub>I</sub>: E<sub>0</sub> → E<sub>I</sub> corresponds to I,<br/>and P<sub>I</sub>, Q<sub>I</sub> = φ<sub>I</sub>(P<sub>0</sub>), φ<sub>I</sub>(Q<sub>0</sub>),<br/>(P<sub>0</sub>, Q<sub>0</sub>) = DeterministicBasis(E<sub>0</sub>).</td></tr><tr><td>IsogenyEval2-2</td><td>E, E<sub>12</sub> ∈ Supersingular<sub>p</sub>,<br/>K<sub>1</sub> and K<sub>2</sub> in E × E<sub>12</sub><br/>isotropic<sup>8</sup> of order 2<sup>f+2</sup>,<br/>a list eval-pts of points<br/>in E × E<sub>12</sub>.</td><td>E<sub>1</sub>, E<sub>2</sub> and [Φ(P) | P ∈ eval-pts],<br/>where Φ: E × E<sub>12</sub> → E<sub>1</sub> × E<sub>2</sub><br/>is a deterministically computed<br/>(2<sup>f</sup>, 2<sup>f</sup>)-isogeny with<br/>ker(Φ) = ⟨[4]K<sub>1</sub>, [4]K<sub>2</sub>⟩.</td></tr><tr><td>MontgomeryRandomize</td><td>A ∈ F<sub>p<sup>2</sup></sub></td><td>A' ∈ F<sub>p<sup>2</sup></sub> uniformly random s.t.<br/>j(E<sub>A</sub>) = j(E<sub>A'</sub>).</td></tr><tr><td>RandomIdealGivenNorm</td><td>N ∈ N s.t. p ≁ N.</td><td>Uniformly random primitive left<br/>O<sub>0</sub>-ideal I of norm N.</td></tr></tbody></table>

<footnote n="8">⁸ Two points of order $n$ are said isotropic if their Weil pairing of order $n$ is trivial.</footnote>
**Relation.** The relation of $\Sigma_{SQL}$ is

$$R_{SQL} = \left\{ ((pp, A_{pk}), I_{sk}) \mid \begin{array}{l} \text{pp public parameters,} \\ A_{pk} \in \mathbb{F}_{p^2}, E_{pk} := E_{A_{pk}} \in \text{Supersingular}_{p}, \\ I_{sk} \text{ is a left } \mathcal{O}_0\text{-ideal and} \\ \mathcal{O}_R(I_{sk}) \cong \text{End}(E_{pk}) \end{array} \right\}.$$

The Montgomery A-invariant $A_{pk}$ will be the public key, and $I_{sk}$ will be the secret key. We can view $R_{SQL}$ as a relation for the EndRing$_p$ problem, since a basis for End($E_{pk}$) can be efficiently recovered from $I_{sk}$.

The instance generator $Gen_{R_{SQL}}$ is defined in Algorithm 1. The prime $N_{mix}$ is chosen so that $\Delta(j(E_{pk}), S) \le 2^{-\lambda}$. In addition, $A_{pk}$ is randomized, to prevent any leakage from the choice of Montgomery coefficient.

**The $\Sigma$-protocol $\Sigma_{SQL}$.** The commitment, challenge and response algorithms are presented in Algorithm 2 and the verification algorithm is in Algorithm 3. For an overview of the isogenies involved in the protocol, see Fig. 1.

**Remark 2.1.** We have modified the description of $\Sigma_{SQL}$ slightly by adding the lines 24-25 in the response algorithm of Algorithm 2. These steps normalize the points $P_{chl}, Q_{chl}$ by making a deterministic choice of sign. This makes the distribution easier to simulate. However, in the optimized implementation of SQIsign, the points are represented by their x-coordinate. Since $P_{chl}$ and $-P_{chl}$ have the same x-coordinate, this means that the point normalization is not needed there.

**Signature scheme.** SQISIGN is the Fiat-Shamir signature obtained from $\Sigma_{SQL}$. We denote it $\text{SIG}[\Sigma_{SQL}]$:

- Key generation is identical to $Gen_{R_{SQL}}$.

- The signer runs $\Sigma_{SQL}$ as the prover, using the challenge chl $\leftarrow \text{RO}(j(E_{com}) \parallel A_{pk} \parallel \text{msg})$. The signature is (chl, rsp).

- The verifier recovers $E_{com} \simeq F_1$ from the signature$^9$, checks that it defines a valid isogeny $E_{pk} \to E_{com}$ and that chl = $\text{RO}(j(E_{com}) \parallel A_{pk} \parallel \text{msg})$.

**Algorithm 1: The instance generator $Gen_{R_{SQL}}(1^{\lambda})$**

1: pp $\leftarrow$ PublicParam$_{SQL}$(1$^{\lambda}$).

2: $I_{sk} \leftarrow$ RandomIdealGivenNorm($N_{mix}$).

3: $E_A, \_ := \text{IdealTolsogeny}(I_{sk})$.

4: $A_{pk} := \text{MontgomeryRandomize}(A)$.

5: $x := (pp, A_{pk})$ and $w := I_{sk}$.

6: return $(x, w)$.

<figure><img src="image_3.png" /><figcaption>Fig. 1: Diagram of $\Sigma_{SQL}$.</figcaption></figure>

<footnote>$^9$ SQISIGN is commitment recoverable with perfect uniqueness, so dropping the commitment from the signature does not affect security [BBSS18].</footnote>
<caption>**Algorithm 2:** The Σ-protocol ΣSQL</caption>

**Commitment(pp, A<sub>pk</sub>, I<sub>sk</sub>):**
1: I<sub>com</sub> ← RandomIdealGivenNorm(N<sub>mix</sub>).
2: E<sub>com</sub>, (P<sub>com</sub>, Q<sub>com</sub>) ← IdealTolsogeny(I<sub>com</sub>).
3: com := j(E<sub>com</sub>); state := (pp, A<sub>pk</sub>, I<sub>sk</sub>, I<sub>com</sub>, E<sub>com</sub>, P<sub>com</sub>, Q<sub>com</sub>).
4: return com, state.

**Challenge:**
1: chl ← {0, ..., 2<sup>e<sub>chl</sub></sup> − 1}. // Defines the challenge isogeny ϕ<sub>chl</sub> : E<sub>pk</sub> → E<sub>chl</sub> with ker(ϕ<sub>chl</sub>) = ⟨P<sub>pk</sub> + [chl]Q<sub>pk</sub⟩, where (P<sub>pk</sub>, Q<sub>pk</sub>) := DeterministicBasis(E<sub>pk</sub>).
2: return chl.

**Response(state, chl):**
1: Compute the left O<sub>pk</sub>-ideal I<sub>chl</sub> corresponding to ϕ<sub>chl</sub>, where O<sub>pk</sub> = O<sub>R</sub>(I<sub>sk</sub>).
2: Sample a uniformly random ideal J equivalent to I<sub>com</sub> · I<sub>sk</sub> · I<sub>chl</sub> of norm < 2<sup>e<sub>rsp</sub></sup>.
3: Decompose J = m · I<sub>rsp</sub> with I<sub>rsp</sub> a primitive ideal.
// I<sub>rsp</sub> corresponds to the cyclic response isogeny ϕ<sub>rsp</sub> : E<sub>com</sub> → E<sub>chl</sub>.
4: Write nrd(I<sub>rsp</sub>) = 2<sup>n</sup>d' with d' an odd integer.
5: Let n<sub>bt</sub> be the largest integer s.t. I<sub>chl</sub> · I<sub>rsp</sub> ⊆ 2<sup>n<sub>bt</sub></sup> O<sub>pk</sub>, and r' := n − n<sub>bt</sub>.
// n<sub>bt</sub> is the length of the part of ϕ̄<sub>rsp</sub> that backtracks with ϕ<sub>chl</sub>.
6: Factor I<sub>rsp</sub> as I<sub>rsp</sub><sup>(1)</sup> · I<sub>rsp</sub><sup>(0)</sup> · I' s.t. nrd(I<sub>rsp</sub><sup>(1)</sup>) = d', nrd(I<sub>rsp</sub><sup>(0)</sup>) = 2<sup>r'</sup>, I<sub>chl</sub> · I' ⊆ 2<sup>n<sub>bt</sub></sup> O<sub>pk</sub>.
// ϕ<sub>rsp</sub> : E<sub>com</sub> &rarr; E<sub>rsp</sub><sup>odd</sup> &rarr; E<sub>rsp</sub><sup>odd</sup> &rarr; E<sub>rsp</sub><sup>even</sup> &rarr; E<sub>chl</sub>, with ψ backtracking ϕ<sub>chl</sub>.
7: I''<sub>aux</sub> ← RandomIdealGivenNorm(2<sup>e<sub>rsp</sub> − n</sup> − d').
8: Let I<sub>aux</sub> be the pushforward of I''<sub>aux</sub> by I<sub>com</sub>. // ϕ<sub>aux</sub> : E<sub>com</sub> → E<sub>aux</sub>.
9: Let I'<sub>aux</sub> be the pushforward of I<sub>aux</sub> by I<sub>rsp</sub><sup>(1)</sup>. // ϕ'<sub>aux</sub> : E<sub>rsp</sub><sup>odd</sup> → E'<sub>aux</sub>.
10: E'<sub>aux</sub>, (K<sub>aux,1</sub>, K<sub>aux,2</sub>) ← IdealTolsogeny(I<sub>com</sub> · I<sub>rsp</sub><sup>(0)</sup> · I'<sub>aux</sub>).
11: K<sub>1</sub> := ([2<sup>e−(e<sub>rsp</sub>−n+2)</sup> d']P<sub>com</sub>, [2<sup>e−(e<sub>rsp</sub>−n+2)</sup>]K<sub>aux,1</sub>).
12: K<sub>2</sub> := ([2<sup>e−(e<sub>rsp</sub>−n+2)</sup> d']Q<sub>com</sub>, [2<sup>e−(e<sub>rsp</sub>−n+2)</sup>]K<sub>aux,2</sub>).
13: eval-pts := [(P<sub>com</sub>, 0), (Q<sub>com</sub>, 0)].
14: E<sub>rsp</sub><sup>odd</sup>, E<sub>aux</sub>, eval-pts' ← IsogenyEval2-2(E<sub>com</sub>, E'<sub>aux</sub>, K<sub>1</sub>, K<sub>2</sub>, eval-pts).
15: Parse eval-pts' as [(R<sub>chl</sub>, R<sub>aux</sub>), (S<sub>chl</sub>, S<sub>aux</sub>)].
16: R<sub>chl</sub>, S<sub>chl</sub> := ϕ<sub>rsp</sub><sup>even</sup>(R<sub>chl</sub>), ϕ<sub>rsp</sub><sup>even</sup>(S<sub>chl</sub>).
17: Compute the non-backtracking part of the challenge isogeny ϕ'<sub>chl</sub> : E<sub>pk</sub> → E'<sub>chl</sub> with ker(ϕ'<sub>chl</sub>) = [2<sup>n<sub>bt</sub></sup>] ker(ϕ<sub>chl</sub>).
18: R<sub>chl</sub>, S<sub>chl</sub> := ι<sub>aux</sub>(R<sub>chl</sub>), ι<sub>aux</sub>(R<sub>chl</sub>), for an isomorphism ι<sub>chl</sub> : E<sub>rsp</sub><sup>even</sup> → E'<sub>chl</sub>.
19: A<sup>†</sup><sub>aux</sub> ← MontgomeryRandomize(A<sub>aux</sub>) and E<sup>†</sup><sub>aux</sub> := E<sup>†</sup><sub>A<sup>†</sup><sub>aux</sub></sub>. // E<sub>aux</sub> = E<sub>A<sup>†</sup><sub>aux</sub></sub>.
20: R<sub>aux</sub>, S<sub>aux</sub> := ι<sub>aux</sub>(R<sub>aux</sub>), ι<sub>aux</sub>(S<sub>aux</sub>), for an isomorphism ι<sub>aux</sub> : E<sub>aux</sub> → E<sup>†</sup><sub>aux</sub>.
21: P<sub>aux</sub>, Q<sub>aux</sub> := [2<sup>e−(e<sub>rsp</sub>−n<sub>bt</sub>+2)</sup>]. DeterministicBasis(E<sup>†</sup><sub>aux</sub>).
22: Compute a, b, c, d ∈ Z s.t. P<sub>aux</sub> = aR<sub>aux</sub> + bS<sub>aux</sub> and Q<sub>aux</sub> = cR<sub>aux</sub> + dS<sub>aux</sub>.
23: P<sub>chl</sub>, Q<sub>chl</sub> := (aR<sub>chl</sub> + bS<sub>chl</sub>, cR<sub>chl</sub> + dS<sub>chl</sub>).
24: if −P<sub>chl</sub> is lexicographically smaller than P<sub>chl</sub> then
25:     P<sub>chl</sub>, Q<sub>chl</sub> := −P<sub>chl</sub>, −Q<sub>chl</sub>
26:     return rsp := (n<sub>bt</sub>, r', A<sup>†</sup><sub>aux</sub>, P<sub>chl</sub>, Q<sub>chl</sub>).
**Algorithm 3: Verification**

**Input:** The statement $(\mathit{pp}, A_{\mathit{pk}})$. // $A_{\mathit{pk}}$ determines the public-key curve $E_{\mathit{pk}}$

**Input:** The transcript $(\mathit{com}, \mathit{chl}, \mathit{rsp})$ with rsp = $(n_{\mathit{bt}}, r', A_{\mathit{aux}}^{\dagger}, P_{\mathit{chl}}, Q_{\mathit{chl}})$.

1: $P_{\mathit{pk}}, Q_{\mathit{pk}} := \text{DeterministicBasis}(E_{\mathit{pk}})$.

2: Compute $E_{\mathit{pk}}, \varphi'_{\mathit{chl}}: E_0 \to E'_{\mathit{chl}}$ with $\ker(\varphi_{\mathit{chl}}) = \langle [2^{n_{\mathit{bt}}}] (P_{\mathit{pk}} + [\mathit{chl}]Q_{\mathit{pk}}) \rangle$.

3: Check that $E_{\mathit{pk}}, E_{\mathit{aux}}^{\dagger} \in \text{Supersingular}_p, r' + n_{\mathit{bt}} \le e_{\mathit{rsp}},$ and $P_{\mathit{chl}}, Q_{\mathit{chl}} \in E_{\mathit{chl}}^{\prime} [2^{e_{\mathit{rsp}}-n_{\mathit{bt}}+2}]$; otherwise, **return 0**.

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

5: &nbsp;&nbsp;&nbsp;&nbsp;**if** $[2^{e_{\mathit{rsp}}-n_{\mathit{bt}}+1}]P_{\mathit{chl}} \neq 0$ **then**

6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$R := [2^{(e_{\mathit{rsp}}-n_{\mathit{bt}}+2)-r'}]P_{\mathit{chl}}$.

7: &nbsp;&nbsp;&nbsp;&nbsp;**else if** $[2^{e_{\mathit{rsp}}-n_{\mathit{bt}}+1}]Q_{\mathit{chl}} \neq 0$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$R := [2^{(e_{\mathit{rsp}}-n_{\mathit{bt}}+2)-r'}]Q_{\mathit{chl}}$.

9: **else**

10: &nbsp;&nbsp;&nbsp;&nbsp;**return** 0.

11: Compute $\varphi: E'_{\mathit{chl}} \to E_{\mathit{rsp}}$ with $\ker(\varphi) = \langle R \rangle$.

12: $P_{\mathit{rsp}}, Q_{\mathit{rsp}} := \varphi(P_{\mathit{chl}}), \varphi(Q_{\mathit{chl}})$.

13: $P_{\mathit{aux}}, Q_{\mathit{aux}} := \text{DeterministicBasis}(E_{\mathit{aux}}^{\dagger})$.

14: $K_1 := (P_{\mathit{rsp}}, [2^{e-(e_{\mathit{rsp}}-n_{\mathit{bt}}-r'+2)}]P_{\mathit{aux}})$.

15: $K_2 := (Q_{\mathit{rsp}}, [2^{e-(e_{\mathit{rsp}}-n_{\mathit{bt}}-r'+2)}]Q_{\mathit{aux}})$.

16: $F_1, F_2, \dots \leftarrow \text{IsogenyEval2-2}(E_{\mathit{rsp}}, E_{\mathit{aux}}^{\dagger}, K_1, K_2, \dots)$.

17: **if** the computation of $\text{IsogenyEval2-2}$ fails or $j(F_1) \neq \text{com}$ **then**

18: &nbsp;&nbsp;&nbsp;&nbsp;**return** 0.

19: &nbsp;&nbsp;&nbsp;&nbsp;**return** 1.

# 3 EUF-CMA-security from hard relations with hints

## 3.1 Security properties

In this section, we define the properties we will need to prove the EUF-CMA-security of $\text{SIG}[\Sigma]$. To help the weak honest-verifier zero-knowledge (wHVZK) simulator, we will give it a hint sampled from a *hint distribution*.

**Definition 3.1 (Hint distribution).** Let $R \subseteq \mathcal{X} \times \mathcal{W}$ be a relation. A hint distribution $\mathcal{H}$ for $R$ is a collection of distributions $\mathcal{H} = \{\mathcal{H}_x\}_{x \in \mathcal{X}}$, where $\mathcal{H}_x := \text{HintSet}_x \to [0, 1]$ and the elements (i.e. the hints) of $\text{HintSet}_x$ are efficiently representable in $|x|$. The distribution $\mathcal{H}_x$ need not be efficiently sampleable.

We define wHVZK with hints as follows.

**Definition 3.2 (Hint-assisted wHVZK).** Let $\Sigma = (\mathcal{P}, \mathcal{V})$ be a $\Sigma$-protocol for a relation $R$ and let $\mathcal{H}$ be a hint distribution for $R$. We say that $\Sigma$ is $\mathcal{H}$-hint-assisted wHVZK if there exists a PPT algorithm, called the simulator $S$, such that for all $q = \text{poly}(\lambda)$ and all PPT algorithms $\mathcal{A}$

$$ \text{Adv}_{\Sigma, \mathcal{H}, S}^{\text{hint-wHVZK}}(\mathcal{A}, q) := \text{Adv}^{\text{dist}}[\text{Real}_{\Sigma}(1^{\lambda}, q), \text{HintSim}_{\Sigma}(1^{\lambda}, q, S)](\mathcal{A}) = \text{negl}(\lambda), $$

where $\text{Real}_{\Sigma}(1^{\lambda}, q)$ and $\text{HintSim}_{\Sigma}(1^{\lambda}, q, S)$ are the distributions defined in Experiment 2.

Without hints, we saw in Section 2.3 and 2.4 how to reduce the hardness of the relation $R$ to the EUF-CMA of $\text{SIG}[\Sigma]$. However, with only hint-assisted wHVZK, the reduction will yield an adversary against the relation that additionally needs hints as input. We therefore need $R$ to be a hard relation, even in the presence of hints.

**Definition 3.3 (Hard relation with hints).** Let $R$ be a hard relation and let $\mathcal{H}$ be a hint distribution for $R$. We call the pair $(R, \mathcal{H})$ a relation with hints. We say that it is a hard relation with hints if, in the following game, it holds for all PPT algorithms $\mathcal{A}$ and all $q = \text{poly}(\lambda)$ that

$$ \text{Adv}_{(R, \mathcal{H})}^{\text{hint-rel}}(\mathcal{A}, q) := \text{Pr} \left[ (x, w^*) \in R \left| \begin{array}{l} (x, w) \leftarrow \text{Gen}_R(1^{\lambda}), \\ h_1, \dots, h_q \leftarrow \mathcal{H}_x, \\ w^* \leftarrow \mathcal{A}(x, h_1, \dots, h_q) \end{array} \right. \right. = \text{negl}(\lambda). $$
Experiment 2: Hint-assisted wHVZK

Real$_{Σ}$(1$^{λ}$, q):

1: (x, w) ← Gen$_{R}$(1$^{λ}$)

2: for i = 1 to q do

3: (com$_{i}$, state$_{i}$) ← P$_{1}$ (x, w)

4: chl$_{i}$ ← $^{S}$

5: rsp$_{i}$ ← P$_{2}$ (state$_{i}$, chl$_{i}$)

6: π$_{i}$ := (com$_{i}$, chl$_{i}$, rsp$_{i}$)

7: return (x, π$_{1}$, ..., π$_{q}$)

HintSim$_{Σ}$(1$^{λ}$, q, S):

1: (x, w) ← Gen$_{R}$(1$^{λ}$)

2: for i = 1 to q do

3: h$_{i}$ ← H$_{x}$

4: π$_{i}$ ← S (x, h$_{i}$)

5: return (x, π$_{1}$, ..., π$_{q}$)

These are all the hint-based security properties we will need. In addition, we will also permit Σ to be
special-sound with respect to a different but related relation.

**Definition 3.4 (Soundness relation).** Let $\Sigma$ be a $\Sigma$-protocol for the relation $R$. Consider some relation $\tilde{R} \subseteq \tilde{X} \times \tilde{W}$. We say that $\tilde{R}$ is compatible with $R$ if $X = \tilde{X}$ and their instance generators sample statements with the same distribution.

We say that $\Sigma$ is special-sound with respect to a compatible relation $\tilde{R}$ if given a statement $x$ and two accepting transcripts $(\text{com}, \text{chl}, \text{rsp})$ and $(\text{com}, \text{chl}', \text{rsp}')$ with $\text{chl} \neq \text{chl}'$, we can compute a witness $w^*$ such that $(x, w^*) \in \tilde{R}$ in polynomial time in $|x|$. In this case, we say that $\tilde{R}$ is a soundness relation for $\Sigma$.

Observe that if $R$ and $\tilde{R}$ are compatible relations and $\mathcal{H}$ is a hint distribution for $R$, then it is also a hint distribution for $\tilde{R}$. Additionally, if $\Sigma$ is special-sound with respect to $\tilde{R}$, then we can always define an instance generator for $\tilde{R}$ so that it is compatible with $R$. It samples $(x, w) \leftarrow \text{Gen}_R(1^{\lambda})$ and then uses the special soundness of $\Sigma$ to compute a witness $w'$ such that $(x, w') \in \tilde{R}$.

3.2 Reducing the hard relations with hints to EUF-CMA

Let $(R, \mathcal{H})$ be a relation with hints and let $\Sigma$ be a $\Sigma$-protocol for $R$. In this section, we identify the following conditions for $\text{SIG}[\Sigma]$ to be EUF-CMA-secure:

1. $\Sigma$ has high commitment min-entropy.

2. $\Sigma$ is $\mathcal{H}$-hint-assisted wHVZK.

3. $\Sigma$ is special-sound with respect to a soundness relation $\tilde{R}$.

4. $\Sigma$ has a challenge space $\mathcal{C}$ of exponential size in $\lambda$.

5. $(\tilde{R}, \mathcal{H})$ is a hard relation with hints.

We prove this by a chain of reductions. The first step is standard: given that $\Sigma$ has high commitment min-entropy, we reduce the security against impersonation attacks (IMP-PA) of $\Sigma$ to the EUF-CMA security of $\text{SIG}[\Sigma]$ (for more details, see Lemma 2.2 in Section 2.4).

The next step will be to use the hint-assisted wHVZK. We will use it to simulate the transcript oracle OTrans in the IMP-PA game. For this purpose, we consider the intermediate game hint-IMP-PA in Definition 3.5. In this game, the adversary no longer has access to the transcript oracle OTrans. Instead, it is given hints from which it can simulate its own transcripts. Hence, we can view this game as a noninteractive variant of the IMP-PA game.

**Definition 3.5 (hint-IMP-PA).** Let $(R, \mathcal{H})$ be a relation with hints and let $\Sigma$ be a $\Sigma$-protocol for $R$. We say that $\Sigma$ is secure under $\mathcal{H}$-hint-assisted passive impersonation attacks ($\mathcal{H}$-hint-IMP-PA) if for all $q = \text{poly}(\lambda)$ and all PPT two-stage algorithms $\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2)$ it holds that

$$
\mathrm{Adv}_{\Sigma, \mathcal{H}}^{\text{hint-IMP-PA}}(\mathcal{A}, q) := \Pr[\mathcal{H}\text{-hint-IMP-PA}_{\Sigma}(\mathcal{A}, q) = 1] = \mathrm{negl}(\lambda),
$$

where $\mathcal{H}$-hint-IMP-PA$_{\Sigma}$ is the game presented in *Game 3*.

**Lemma 3.1.** Let $(R, \mathcal{H})$ be a relation with hints and let $\Sigma$ be a $\Sigma$-protocol for the relation $R$. Additionally, let $S$ be a $\mathcal{H}$-assisted simulator for $\Sigma$.
### Game 3: $\mathcal{H}$-hint-IMP-PA$_\Sigma(\mathcal{A}_1, \mathcal{A}_2, q)$

1. $(x, w) \leftarrow \text{Gen}_R(1^\lambda)$

2. $h_1, \dots, h_q \leftarrow \mathcal{H}_x$

3. $(\text{com}, \text{state}) \leftarrow \mathcal{A}_1(x, h_1, \dots, h_q)$

4. $\text{chl} \stackrel{\$}{\leftarrow} \mathcal{C}$

5. $\text{rsp} \leftarrow \mathcal{A}_2(\text{state}, \text{chl})$

6. $b := \text{Ver}_\Sigma(x, \text{com}, \text{chl}, \text{rsp}) = 1$

7. **return** $b$

For any two-stage PPT algorithm $\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2)$ against the IMP-PA of $\Sigma$, there exists a two-stage PPT algorithm $\mathcal{B}$ and a PPT algorithm $\mathcal{D}$ such that

$$ \text{Adv}_{\Sigma}^{\text{IMP-PA}}(\mathcal{A}) \le \text{Adv}_{\Sigma, \mathcal{H}}^{\text{hint-IMP-PA}}(\mathcal{B}, q) + \text{Adv}_{\Sigma, \mathcal{H}, \mathcal{S}}^{\text{hint-wHVZK}}(\mathcal{D}, q), $$

where $q$ is an upper-bound on the number of queries that $\mathcal{A}_1$ makes to OTrans.

*Proof.* We will use $\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2)$ and $\mathcal{S}$ to construct an adversary $\mathcal{B} = (\mathcal{B}_1, \mathcal{A}_2)$ for the hint-IMP-PA game. $\mathcal{B}$ has the same second stage algorithm as $\mathcal{A}$.

$\mathcal{B}_1$ takes as input a statement $x$ sampled from $\text{Gen}_R(1^\lambda)$ and $q$ hints $h_1, \dots, h_q \leftarrow \mathcal{H}_x$. It then runs $\mathcal{A}_1$ on input $x$. Whenever $\mathcal{A}_1$ makes a query to the transcript oracle OTrans, $\mathcal{B}_1$ responds using the simulator $\mathcal{S}$. For the $i$th query, $\mathcal{B}_1$ runs $(\text{com}_i, \text{chl}_i, \text{rsp}_i) \leftarrow \mathcal{S}(x, h_i)$ and responds with $(\text{com}_i, \text{chl}_i, \text{rsp}_i)$. When $\mathcal{A}_1$ outputs $(\text{com}^*, \text{state}^*)$, $\mathcal{B}_1$ outputs the same and terminates.

We use the hint-assisted wHVZK of $\Sigma$ to relate the advantage of $\mathcal{B}$ in the hint-IMP-PA game to the advantage of $\mathcal{A}$ in the IMP-PA game. If there is a difference in success probability, we can construct a distinguisher $\mathcal{D}$. On input $(x, \pi)$ with $\pi = (\pi_1, \dots, \pi_q)$, $\mathcal{D}$ runs the IMP-PA game for $\mathcal{A}$ and answers the $i$th query to OTrans with $\pi_i$. Finally, $\mathcal{D}$ outputs the same bit as the game. We have

$$ \begin{aligned} \text{Adv}_{\Sigma}^{\text{IMP-PA}}(\mathcal{A}) &= \Pr[1 \leftarrow \mathcal{D}(x, \pi) \mid (x, \pi) \leftarrow \text{Real}_{\Sigma}(1^{\lambda}, q)] \quad \text{and} \\ \text{Adv}_{\Sigma, \mathcal{H}}^{\text{hint-IMP-PA}}(\mathcal{B}, q) &= \Pr[1 \leftarrow \mathcal{D}(x, \pi) \mid (x, \pi) \leftarrow \text{HintSim}_{\Sigma}(1^{\lambda}, q)]. \end{aligned} $$

Hence,

$$ \text{Adv}_{\Sigma, \mathcal{H}, \mathcal{S}}^{\text{hint-wHVZK}}(\mathcal{A}, q) = |\text{Adv}_{\Sigma}^{\text{IMP-PA}}(\mathcal{A}) - \text{Adv}_{\Sigma, \mathcal{H}}^{\text{hint-IMP-PA}}(\mathcal{B}, q)|. \quad \square $$

Finally, we use the special soundness of $\Sigma$ to reduce the hardness of $(\tilde{R}, \mathcal{H})$ to the hint-IMP-PA-security of $\Sigma$.

**Lemma 3.2.** Let $(R, \mathcal{H})$ be a relation with hints and let $\Sigma$ be a $\Sigma$-protocol for the relation $R$ with challenge space $C$. Additionally, assume $\Sigma$ is special-sound with respect to the soundness relation $\tilde{R}$.

For any two-stage PPT algorithm $\mathcal{A} = (\mathcal{A}_1, \mathcal{A}_2)$ playing the hint-IMP-PA game for $\Sigma$ with $q$ hints from $\mathcal{H}$, there exists an expected polynomial time algorithm $\mathcal{B}$ playing the game for $(\tilde{R}, \mathcal{H})$ such that

$$ \text{Adv}_{\Sigma, \mathcal{H}}^{\text{hint-IMP-PA}}(\mathcal{A}, q) \le \text{Adv}_{(\tilde{R}, \mathcal{H})}^{\text{hint-rel}}(\mathcal{B}, q) + \frac{1}{|\mathcal{C}|}. $$

*Proof.* By Lemma 2.1, $\Sigma$ is knowledge-sound with respect to $\tilde{R}$, with knowledge error $1/|\mathcal{C}|$. Let $\mathcal{E}$ be the knowledge extractor.

We begin by describing the adversary $\mathcal{B}$ against the hard relation with hints $(\tilde{R}, \mathcal{H})$. It gets as input a statement $x$ generated by $\text{Gen}_{\tilde{R}}(1^\lambda)$ and hints $h_1, \dots, h_q \leftarrow \mathcal{H}$. This is exactly the same input distribution that $\mathcal{A}$ gets in its hint-IMP-PA game. $\mathcal{B}$ fixes the inputs of $\mathcal{A}$ to be $x, h_1, \dots, h_q$, then runs $\mathcal{E}$ on $\mathcal{A}$.

Let us analyze the success probability of $\mathcal{B}$. Let $X$ and $H$ be random variables distributed as the statement and the $q$ hints in the inputs to $\mathcal{A}$ and $\mathcal{B}$. Let $A(X, H)$ be the event that $\mathcal{A}$ succeeds in the hint-IMP-PA game on input an input from $X$ and $H$. Similarly, let $B(X, H)$ be the event that $\mathcal{B}$ succeeds in outputting a witness for $\tilde{R}$.

Fix a statement $x \in \mathcal{X}$ and hints $h = (h_1, \dots, h_q) \in \text{HintSet}_x^q$. By the knowledge soundness,

$$ \Pr[B(X, H) | X = x, H = h] \ge \Pr[A(X, H) | X = x, H = h] - \frac{1}{|\mathcal{C}|}. $$
Then by linearity,

$$
\begin{align*}
\mathrm{Adv}_{(\tilde{R}, \mathcal{H})}^{\mathrm{hint-rel}}(\mathcal{B}, q) &= \mathrm{Pr} [B(X, H)] \\
&= \sum_{x, \mathbf{h}} \mathrm{Pr} [X = x, H = \mathbf{h}] \mathrm{Pr} [B(X, H) | X = x, H = \mathbf{h}] \\
&\geq \sum_{x, \mathbf{h}} \mathrm{Pr} [X = x, H = \mathbf{h}] \left( \mathrm{Pr} [A(X, H) | X = x, H = \mathbf{h}] - \frac{1}{|C|} \right) \\
&= \mathrm{Pr} [A(X, H)] - \frac{1}{|C|} \\
&= \mathrm{Adv}_{\Sigma, \mathcal{H}}^{\mathrm{hint-IMP-PA}}(\mathcal{A}, q) - \frac{1}{|C|}.
\end{align*}
$$

Finally, the expected runtime of $\mathcal{B}$ is about the same as $\mathcal{E}$.

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

Note that the above is not quite a reduction from the hard relation with hints $(\tilde{R}, \mathcal{H})$ to the hint-IMP-PA-security of $\Sigma$. In particular, the definition of a hard relation with hints is only with respect to PPT algorithms. However, the algorithm constructed is just an *expected* polynomial time algorithm. To finish the reduction, we convert it to a PPT algorithm in a standard way.

**Lemma 3.3.** Let $\mathcal{A}$ be an algorithm that runs in expected time $t$ with success probability $\varepsilon$. Then there exists an algorithm $\mathcal{B}$ that runs in time at most $2t/\varepsilon$ and succeeds with probability at least $\varepsilon/2$. In particular, if $t$ and $\varepsilon^{-1}$ are polynomial in $\lambda$, then $\mathcal{B}$ runs in polynomial time in $\lambda$ and has non-negligible success probability.

*Proof.* $\mathcal{B}$ runs $\mathcal{A}$ but times out after $2t/\varepsilon - 1$ steps. Let $T$ be the random variable for the runtime of $\mathcal{A}$. By Markov's inequality,

$$ \mathrm{Pr} [T \geq 2t/\varepsilon] \leq \frac{E[T]}{2t/\varepsilon} = \frac{\varepsilon}{2}. $$

Let $S_{\mathcal{A}}$ and $S_{\mathcal{B}}$ be the events that $\mathcal{A}$ and $\mathcal{B}$ succeeds, respectively.

$$ \mathrm{Pr} [S_{\mathcal{B}}] = \mathrm{Pr} [S_{\mathcal{A}}, T < 2t/\varepsilon] \geq \mathrm{Pr} [S_{\mathcal{A}}] - \mathrm{Pr} [T \geq 2t/\varepsilon] \geq \varepsilon - \varepsilon/2 = \varepsilon/2. $$

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

In conclusion, we obtain a reduction from the hard relation with hints $(\tilde{R}, \mathcal{H})$ to the EUF-CMA security of $\mathrm{SIG}[\Sigma]$.

**Theorem 1 (hint-rel reduces to EUF-CMA).** Let $(R, \mathcal{H})$ be a relation with hints. Let $\Sigma$ be a $\Sigma$-protocol for the relation $R$ that has challenge space $C$ and is special-sound with respect to a soundness relation $\tilde{R}$. Additionally, let $S$ be a $\mathcal{H}$-hint-assisted simulator for $\Sigma$.

For any PPT algorithm $\mathcal{A}$ against the EUF-CMA of $\mathrm{SIG}[\Sigma]$, there exists a PPT algorithm $\mathcal{B}$ and an *expected* polynomial time algorithm $\mathcal{E}$ such that

$$
\begin{align*}
\mathrm{Adv}_{\mathrm{SIG}[\Sigma]}^{\mathrm{EUF-CMA}}(\mathcal{A}) &\le (q+1) \cdot \left( \mathrm{Adv}_{(\tilde{R}, \mathcal{H})}^{\mathrm{hint-rel}}(\mathcal{E}, s) + \mathrm{Adv}_{\Sigma, \mathcal{H}, \mathcal{S}}^{\mathrm{hint-wHVZK}}(\mathcal{B}, s) + \frac{1}{|C|} \right) \\
&\quad + (q+s+1)s \cdot \mathrm{MinEnt}(\Sigma),
\end{align*}
$$

where $q$ and $s$ are upper-bounds on the number of queries that $\mathcal{A}$ makes to $\mathrm{RO}$ and $\mathrm{OSign}$, respectively.

*Proof.* We simply combine the previous results.

$$
\begin{align*}
\mathrm{Adv}_{\mathrm{SIG}[\Sigma]}^{\mathrm{EUF-CMA}}(\mathcal{A}) &\le (q+1) \cdot \mathrm{Adv}_{\Sigma}^{\mathrm{IMP-PA}}(\mathcal{N}) + (q+s+1)s \cdot \mathrm{MinEnt}(\Sigma) \\
&\le (q+1) \cdot \left( \mathrm{Adv}_{\Sigma, \mathcal{H}}^{\mathrm{hint-IMP-PA}}(\mathcal{M}, s) + \mathrm{Adv}_{\Sigma, \mathcal{H}, \mathcal{S}}^{\mathrm{hint-wHVZK}}(\mathcal{B}, s) \right) \\
&\quad + (q+s+1)s \cdot \mathrm{MinEnt}(\Sigma) \\
&\le (q+1) \cdot \left( \left( \mathrm{Adv}_{(\tilde{R}, \mathcal{H})}^{\mathrm{hint-rel}}(\mathcal{E}, s) + \frac{1}{|C|} \right) + \mathrm{Adv}_{\Sigma, \mathcal{H}, \mathcal{S}}^{\mathrm{hint-wHVZK}}(\mathcal{B}, s) \right) \\
&\quad + (q+s+1)s \cdot \mathrm{MinEnt}(\Sigma),
\end{align*}
$$

where the first inequality uses Lemma 2.2, the second Lemma 3.1 and the third Lemma 3.2.

<figure><img src="image_6.png" /></figure>
# 4 Analyzing SQIsign in the Fiat-Shamir with hint framework

We now apply the framework introduced in the previous section to study the security of SQISIGN.

## 4.1 Commitment min-entropy

We begin by analyzing the distribution of the commitment $D_{com}$. For every supersingular curve $E$, we define $D_{E}^{\text{mix}}$ as the distribution on $j(\text{Supersingular}_p)$ obtained by taking the codomain of a uniformly random cyclic isogeny $\varphi: E \to E'$ of degree $N_{\text{mix}}$. The commitment distribution is $D_{com} = D_{E_0}^{\text{mix}}$ and $\Delta(D_{com}, S_j) \le 1/(2\sqrt{p})$ by Proposition 2.4. Next, we reduce the problem of distinguishing between $D_{com}$ and $S_j$ to the commitment min-entropy of $\Sigma_{\text{SQI}}$ (as defined in Definition 2.4).

**Lemma 4.1.** $\text{MinEnt}(\Sigma_{\text{SQI}}) \le p^{-1/2}$.

*Proof.* The commitment distribution $D_{com}$ is independent of the statement or witness. By the definition of statistical distance, $\text{MinEnt}(\Sigma_{\text{SQI}}) \le \Delta(D_{com}, S_j) + \text{Pr}[\text{com}' = \text{com} | \text{com}' \leftarrow S_j]$, for some commitment com. Then,

$$ \text{Pr}[\text{com}' = \text{com} | \text{com}' \leftarrow S_j] \le \frac{12}{p-1} \le \frac{1}{2\sqrt{p}}, $$

using first that $|\text{Aut}(E)| \ge 2$ for all $E \in \text{Supersingular}_p$ and second that $p \ge 578$. We conclude using $\Delta(D_{com}, S_j) \le 1/(2\sqrt{p})$. $\square$

## 4.2 Special soundness

While $\Sigma_{\text{SQI}}$ is not special-sound with respect to the original relation $R_{\text{SQI}}$, [BDD$^{+24}$] showed that it is special-sound with respect to a relation for the $\text{OneEnd}_p$ problem.

**Lemma 4.2 ([BDD$^{+24}$, Theorem 17]).** If $e_{\text{chl}} + e_{\text{rsp}} \le e$, then $\Sigma_{\text{SQI}}$ is special-sound with respect to the soundness relation

$$ R_{\text{OneEnd}} = \left\{ ((\text{pp}, A_{\text{pk}}), \alpha) \left| \begin{array}{l} \text{pp public parameters, } A_{\text{pk}} \in \mathbb{F}_{p^2}, \\ E_{\text{pk}} := E_{A_{\text{pk}}} \in \text{Supersingular}_p, \\ \alpha \in \text{End}(E) \setminus \mathbb{Z} \text{ in efficient representation,} \\ \deg(\alpha) \le p^4 \end{array} \right. \right\}. $$

For completeness, we include the proof from [BDD$^{+24}$]. It begins by proving two propositions.

**Proposition 4.1.** *From an accepting transcript (com, chl, rsp) for $\Sigma_{\text{SQI}}$, we can compute an efficient representation of an isogeny $\sigma: E_{\text{com}} \to E_{\text{chl}}$, where $E_{\text{com}}$ is a curve such that $j(E_{\text{com}}) = \text{com}$ and $\deg(\sigma) \le 2^{e_{\text{rsp}}}$.*

*Proof.* We extract the isogeny by inspecting the verification algorithm (Algorithm 3). Write the challenge isogeny as

$$ \varphi_{\text{chl}} : E_{\text{pk}} \xrightarrow{\varphi'_{\text{chl}}} E'_{\text{chl}} \xrightarrow{\tau} E_{\text{chl}} $$

where $\varphi'_{\text{chl}}$ is the non-backtracking challenge isogeny and $\tau$ is the last $n_{\text{bt}}$ steps. The verification algorithm first computes a $2^{r'}$-isogeny $\varphi: E'_{\text{chl}} \to E_{\text{rsp}}$ and then a $(2^{e_{\text{rsp}}-n_{\text{bt}}-r'}, 2^{e_{\text{rsp}}-n_{\text{bt}}-r'})$-isogeny

$$ \Phi : E_{\text{rsp}} \times E_{\text{aux}} \to F_1 \times F_2 $$

with $j(F_1) = \text{com}$. The latter is the efficient representation of an isogeny $\psi: E_{\text{rsp}} \to F_1$ of degree at most $2^{e_{\text{rsp}}-n_{\text{bt}}-r'}$. Let $E_{\text{com}} = F_1$. Then, we recover the isogeny $\sigma = \tau \circ \hat{\varphi} \circ \hat{\psi}: E_{\text{com}} \to E_{\text{chl}}$ of degree at most

$$ \deg(\tau) \deg(\varphi) \deg(\psi) \le 2^{n_{\text{bt}}} \cdot 2^{r'} \cdot 2^{e_{\text{rsp}}-n_{\text{bt}}-r'}. $$

$\square$

**Proposition 4.2.** Let $\varphi_{\text{chl},1}: E_{\text{pk}} \to E_{\text{chl},1}$ and $\varphi_{\text{chl},2}: E_{\text{pk}} \to E_{\text{chl},2}$ be two distinct challenge isogenies from the same public curve $E_{\text{pk}}$. Then the largest integer $m \in \mathbb{Z}$ such that $[m]$ divides $\varphi_{\text{chl},2} \circ \hat{\varphi}_{\text{chl},1}$ is strictly smaller than $2^{e_{\text{chl}}}$.
Proof. Let $\text{chl}_1, \text{chl}_2 \in \{0, \dots, 2^{e_{\text{chl}}}-1\}$ be the distinct challenges defining $\varphi_{\text{chl},1}$ and $\varphi_{\text{chl},2}$. Let $\psi$ be the backtracking component of $\widehat{\varphi}_{\text{chl},1}$ and $\varphi_{\text{chl},2}$ as in Lemma 2.3. This means that $\varphi_{\text{chl},1} = \varphi'_{\text{chl},1} \circ \psi$, $\varphi_{\text{chl},2} = \varphi'_{\text{chl},2} \circ \psi$ and $\varphi'_{\text{chl},2} \circ \widehat{\varphi'_{\text{chl},1}}$ is cyclic. Since $\varphi_{\text{chl},2} \circ \widehat{\varphi'_{\text{chl},1}} = [\deg \psi] \circ \varphi'_{\text{chl},2} \circ \widehat{\varphi'_{\text{chl},1}}$ and $\varphi'_{\text{chl},2} \circ \widehat{\varphi'_{\text{chl},1}}$ is cyclic, $\deg \psi$ is the largest integer dividing $\varphi_{\text{chl},2} \circ \widehat{\varphi'_{\text{chl},1}}$.

$\psi$ is cyclic, so its kernel is generated by some point $K \in E_{\text{pk}}$. Likewise, let $K_i = P_{\text{pk}} + [\text{chl}_i]Q_{\text{pk}}$ be the generator of $\ker(\varphi_{\text{chl},i})$ for $i = 1, 2$, where $(P_{\text{pk}}, Q_{\text{pk}})$ is the deterministic basis for $E_{\text{pk}}[2^e]$. $K \in \langle K_1 \rangle \cap \langle K_2 \rangle$ implies that there exists integers $c_1, c_2 \in \{0, \dots, 2^e-1\}$ such that $K = c_1 K_1 = c_2 K_2$. Then

$$[c_1 - c_2]P_{\text{pk}} + [c_1 \cdot \text{chl}_1 - c_2 \cdot \text{chl}_2]Q_{\text{pk}} = 0.$$

From the first coefficient, we get $c_1 = c_2 \mod 2^e$, meaning that $c_1 = c_2$. From the second, we get $c_1(\text{chl}_1 - \text{chl}_2) = 0 \mod 2^e$, meaning that $2^e | c_1 \cdot (\text{chl}_1 - \text{chl}_2)$. Because $\text{chl}_1 - \text{chl}_2 \neq 0$ and is bounded by $-2^{e_{\text{chl}}} < \text{chl}_1 - \text{chl}_2 < 2^{e_{\text{chl}}}$, we must have that $2^{e_{\text{chl}}+1}|c_1$. Then $K \in E_{\text{pk}}[2^{e_{\text{chl}}-1}]$ and $\deg(\psi) \le 2^{e_{\text{chl}}-1}$.

□

We are now finally ready to show that $\Sigma_{\text{SQI}}$ is special-sound with respect to $R_{\text{OneEnd}}$.

Proof. Let $(\text{com}, \text{chl}_1, \text{rsp}_1)$ and $(\text{com}, \text{chl}_2, \text{rsp}_2)$ be two accepting transcripts with $\text{chl}_1 \neq \text{chl}_2$. Let $\varphi_{\text{chl},1} : E_{\text{pk}} \to E_{\text{chl},1}$ and $\varphi_{\text{chl},2} : E_{\text{pk}} \to E_{\text{chl},2}$ be the challenge isogenies for $\text{chl}_1$ and $\text{chl}_2$. By Proposition 4.1 (and possibly by composing with an isomorphism), we obtain isogenies $\sigma_1 : E_{\text{com}} \to E_{\text{chl},1}$ and $\sigma_2 : E_{\text{com}} \to E_{\text{chl},2}$ such that $j(E_{\text{com}}) = \text{com}$ and each has degree at most $2^{e_{\text{rsp}}}$.

We obtain the endomorphism $\alpha = \widehat{\varphi_{\text{chl},2}} \circ \sigma_2 \circ \widehat{\sigma_1} \circ \varphi_{\text{chl},1} \in \text{End}(E_{\text{pk}})$. We have $\deg(\alpha) \le 2^{2e+2e_{\text{rsp}}} \le p^4$.

$$ \begin{aligned} [m] \circ \varphi_{\text{chl},2} \circ \widehat{\varphi_{\text{chl},1}} &= \varphi_{\text{chl},2} \circ [m] \circ \widehat{\varphi_{\text{chl},1}} \\ &= \varphi_{\text{chl},2} \circ (\widehat{\varphi_{\text{chl},2}} \circ \sigma_2 \circ \widehat{\sigma_1} \circ \varphi_{\text{chl},1}) \circ \widehat{\varphi_{\text{chl},1}} \\ &= [\deg(\varphi_{\text{chl},1}) \deg(\varphi_{\text{chl},2})] \circ \sigma_2 \circ \widehat{\sigma_1}. \end{aligned} \quad (1) $$

Write $\varphi_{\text{chl},2} \circ \widehat{\varphi_{\text{chl},1}} = [2^f]\tau_1$ and $\sigma_2 \circ \widehat{\sigma_1} = [d']\tau_2$, where $\tau_1$ and $\tau_2$ are cyclic isogenies. Then the largest integer dividing $(1)$ is $2^f m = d \deg(\varphi_{\text{chl},1}) \deg(\varphi_{\text{chl},2})$. Dividing, we obtain that $\tau_1 = \tau_2$.

Since $[2^f]$ divides $\varphi_{\text{chl},2} \circ \widehat{\varphi_{\text{chl},1}}$, by Proposition 4.2 we have $2^f < 2e_{\text{chl}}$. Using that $e_{\text{rsp}} + e_{\text{chl}} \le e$,

$$ \deg(\tau_1) = \frac{\deg(\varphi_{\text{chl},1}) \deg(\varphi_{\text{chl},2})}{2^{2f}} > 2^{2(e-e_{\text{chl}})} \ge 2^{2e_{\text{rsp}}} $$

At the same time, $\deg(\tau_2) \le \deg(\sigma_1) \deg(\sigma_2) \le 2^{2e_{\text{rsp}}}$. This is a contradiction, as $\tau_1 = \tau_2$. Hence, we have $((\text{pp}, A_{\text{pk}}), \alpha) \in R_{\text{OneEnd}}$. □

## 4.3 Hint-assisted wHVZK

We will prove that $\Sigma_{\text{SQI}}$ is hint-assisted wHVZK with respect to the hint distribution $\mathcal{H}^{\text{sim}}$ defined in Experiment 3. In essence, the hint provides the simulator with a response isogeny and auxiliary isogeny sampled from the correct distribution. Without knowledge of the endomorphism ring of $E_{\text{pk}}$, we only know how to efficiently sample random isogenies of smooth degree. Our $\mathcal{H}^{\text{sim}}$-hint-assisted simulator is defined in Algorithm 4.

To show that $\Sigma_{\text{SQI}}$ is $\mathcal{H}^{\text{sim}}$-assisted wHVZK, we begin by comparing the distribution of real and simulated transcripts. The commitment $j(E_{\text{com}})$ has the distribution $D_{\text{com}}$ in real transcripts and the stationary distribution $S_j$ in simulated transcripts. By Proposition 2.4, these distributions are statistically close. The challenge is also identically distributed in simulated and real transcripts. What remains is to compare the responses $\text{rsp} = (n_{\text{bt}}, r', A_{\text{aux}}^{\dagger}, P_{\text{chl}}, Q_{\text{chl}})$.

**Lemma 4.3.** Let $((\text{pp}, A_{\text{pk}}), I_{\text{sk}}) \in R_{\text{SQI}}$ and let $j_{\text{com}} \in j(\text{Supersingular}_p)$. Consider transcripts for the statement $(\text{pp}, A_{\text{pk}})$, $(j_{\text{com}}, \text{chl}, \text{rsp})$ with the commitment fixed to $j_{\text{com}}$. Then $\deg(\varphi_{\text{rsp}})$, $n_{\text{bt}}, r'$, $E'_{\text{chl}}$ and $E'_{\text{aux}}$ are identically distributed in real and simulated transcripts of this form.

Proof. In the response algorithm in Algorithm 2, the ideal $J$ is uniformly distributed among the equivalent ideals to $\overline{I}_{\text{com}} \cdot I_{\text{sk}} \cdot I_{\text{chl}}$ of norm $< 2^{e_{\text{rsp}}}$.

The simulator's response isogeny $\varphi_{\text{rsp}}$ is the cyclic component of a uniformly random isogeny $E_{\text{com}} \to E_{\text{chl}}$ of norm $< 2^{e_{\text{rsp}}}$.
Experiment 3: Hint distribution $\mathcal{H}^{\text{sim}}$ for SQISIGN

$D_{\text{Chall}}(E):$

1: $s \stackrel{\$}{\leftarrow} \{0, \dots, 2^{e_{\text{chl}}} - 1\}$.

2: $(P, Q) := \text{DeterministicBasis}(E)$.

3: Compute the isogeny $\varphi : E \to E'$ with $\ker(\varphi) = \langle P + [s]Q \rangle$ exactly as $\sum_{S \in \mathcal{S}_{\text{SQL}}} \text{ does for the challenge isogeny.}$

4: return $s, \varphi$.

$D_{\text{StatTarget}}(E):$

1: Sample an isogeny $\varphi : E \to E'$ such that

i. $E'$ is distributed according to the stationary distribution $S$ on $\text{Supersingular}_p$.

ii. The conditional distribution of $\varphi$ given $E'$ is uniform among isogenies $E \to E'$ of degree $< 2^{e_{\text{rsp}}}$.

2: Write $\varphi = [m] \circ \varphi'$ with $m \in \mathbb{Z}$ and $\varphi'$ cyclic.

3: return an efficient representation of $\varphi'$.

$D_{\text{Uniflsog}}(E, d):$

1: Sample an isogeny $\varphi : E \to E'$ uniformly among the cyclic isogenies from $E$ of degree $d$ to curves in $\text{Supersingular}_p$.

2: return an efficient representation of $\varphi$.

$\mathcal{H}_E^{\text{sim}}:$

1: $s, \varphi_1 \leftarrow D_{\text{Chall}}(E)$, where $\varphi_1 : E \to E_1$.

2: $\varphi_2 \leftarrow D_{\text{StatTarget}}(E_1)$, where $\varphi_2 : E_1 \to E_2$.

3: Write $\deg(\varphi_2) = 2^n d'$ with $d'$ odd.

4: $\varphi_3 \leftarrow D_{\text{Uniflsog}}(E_2, 2^{e_{\text{rsp}}-n} - d')$, where $\varphi_3 : E_2 \to E_3$.

5: return $h = (s, \varphi_2, \varphi_3)$.

$E_{\text{com}}$. Hence, the ideal has the same distribution as the prover's $I_{\text{rsp}}$. The values $\deg(\varphi_{\text{rsp}})$ $n_{\text{bt}}$ and $r'$ are uniquely determined by the response ideal and the challenge, so their simulated distributions are the same as the real ones.

Fix a choice of $\deg(\varphi_{\text{rsp}})$, $n_{\text{bt}}$ and $r'$ and write $\deg(\varphi_{\text{rsp}}) = 2^n d'$ with $d'$ odd. Given these values, the prover and simulator produce the same curve $E'_{\text{chl}}$, by computing $\varphi_{\text{chl}} : E_{\text{pk}} \to E'_{\text{chl}}$ with $\ker(\varphi'_{\text{chl}}) = \langle [2^{n_{\text{bt}}}] (P_{\text{pk}} + [\text{chl}] Q_{\text{pk}}) \rangle$.

Let $d_{\text{aux}} = 2^{e_{\text{rsp}}-n} - d'$. In line 7 of the response algorithm, $I''_{\text{aux}}$ is uniformly distributed among the primitive left $O_0$-ideals of norm $d_{\text{aux}}$. Since the norm of $I_{\text{com}}$ is coprime to $d_{\text{aux}}$, we can define the pushforward $I_{\text{aux}}$ of $I''_{\text{aux}}$ through $I_{\text{com}}$. It corresponds to the prover's auxiliary isogeny $\varphi_{\text{aux}} : E_{\text{com}} \to E_{\text{aux}}$. The pushforward by $I_{\text{com}}$ induces a bijection between the left $O_0$ ideals of norm $d_{\text{aux}}$ and the left $O_{\text{com}}$-ideals of norm $d_{\text{aux}}$. Hence, $I_{\text{aux}}$ is uniformly distributed among the primitive left-$\mathcal{O}_{\text{com}}$ ideals of norm $d_{\text{aux}}$. Given $I_{\text{aux}}$, the prover picks a uniformly random Montgomery A-invariant $A^\dagger_{\text{aux}}$ for the representative of the codomain.

On the other hand, the simulator's auxiliary isogeny $\varphi_{\text{aux}} : E_{\text{com}} \to E^\dagger_{\text{aux}}$ is uniformly distributed among the cyclic isogenies from $E_{\text{com}}$ of degree $d_{\text{aux}}$ to curves in $\text{Supersingular}_p$. Hence, the corresponding ideal has the same distribution as the prover's $I_{\text{aux}}$. Fix the $j$-invariant $j_{\text{aux}}$ of the codomain. The number of cyclic isogenies $E_{\text{com}} \to E_{\text{aux}}$ of degree $d_{\text{aux}}$ is the same for any representative $E_{\text{aux}}$ with $j(E_{\text{aux}}) = j_{\text{aux}}$. Hence, given $j_{\text{aux}}$, the simulator's $E^\dagger_{\text{aux}}$ is uniformly distributed among the representatives for $j_{\text{aux}}$. We conclude that the simulated distribution of $A^\dagger_{\text{aux}}$ is the same as the real one. $\square$

Finally, we compare the distribution of the points $P_{\text{chl}}$, $Q_{\text{chl}}$. It turns out that their distribution depends on the automorphism group of $E'_{\text{chl}}$.

**Lemma 4.4.** Let $((pp, A_{\text{pk}}), I_{\text{sk}}) \in \mathcal{R}_{\text{SQL}}$ and let $j_{\text{com}} \in j(\text{Supersingular}_p)$. Consider transcripts for the statement $(pp, A_{\text{pk}})$ with the commitment fixed to $j_{\text{com}}$ and $j(E'_{\text{chl}}) \notin \{0, 1728\}$. Then $P_{\text{chl}}$ and $Q_{\text{chl}}$ are identically distributed in real and simulated transcripts of this form.
**Algorithm 4:** The hint-assisted simulator $S_{\text{SQI}}(\text{pp}, A_{\text{pk}}, h)$

**Input:** The statement $(\text{pp}, A_{\text{pk}})$ and a hint $h = (s, \widehat{\varphi}_{\text{rsp}}, \varphi_{\text{aux}}) \in \text{HintSet}_{E_{\text{pk}}}^{\text{sim}}$ with $\widehat{\varphi}_{\text{rsp}} : E_{\text{chl}} \to E_{\text{com}}$ and
$\varphi_{\text{aux}} : E_{\text{com}} \to E_{\text{aux}}^{\dagger}$.

**Output:** Transcript of $\Sigma_{\text{SQI}}$.

1: $\text{com} := j(E_{\text{com}})$ and $\text{chl} := s$.

2: $(P_{\text{pk}}, Q_{\text{pk}}) := \text{DeterministicBasis}(E_{\text{pk}})$.

3: Compute $\varphi_{\text{chl}} : E_{\text{pk}} \to E_{\text{chl}}$ with $\ker(\varphi_{\text{chl}}) = \langle P_{\text{pk}} + [s]Q_{\text{pk}} \rangle$, exactly as $\Sigma_{\text{SQI}}$ does for the challenge isogeny.

4: Compute the backtracking component of $\varphi_{\text{chl}}$ and $\widehat{\varphi}_{\text{rsp}}$ with Lemma 2.3, obtaining $\psi_{\text{bt}}$ and $\widehat{\psi}_{\text{rsp}}$ such that

$$ \widehat{\varphi}_{\text{rsp}} : E_{\text{chl}} \xrightarrow{\psi_{\text{bt}}} F \xrightarrow{\widehat{\psi}_{\text{rsp}}} E_{\text{com}} \quad \text{and} \quad \ker(\psi_{\text{bt}}) = \ker(\widehat{\varphi}_{\text{chl}}) \cap \ker(\widehat{\varphi}_{\text{rsp}}). $$

5: Let $n_{\text{bt}} \in \mathbb{Z}$ be such that $\deg(\psi_{\text{bt}}) = 2^{n_{\text{bt}}}$.

6: Let $r'$ be the largest integer such that $2^{r'} | \deg(\psi_{\text{rsp}})$.

7: Use Lemma 2.3 to compute efficient representations of $\psi_{\text{rsp}}$ and $\widehat{\varphi}_{\text{aux}}$.

8: Compute $\varphi'_{\text{chl}} : E_{\text{pk}} \to E'_{\text{chl}}$ with $\ker(\varphi'_{\text{chl}}) = ([2^{n_{\text{bt}}}](P_{\text{pk}} + [s]Q_{\text{pk}}))$, as the verifier would.

9: Compute an isomorphism $\iota_{\text{chl}} : F \to E'_{\text{chl}}$.

10: $\varphi'_{\text{rsp}} := \iota_{\text{chl}} \circ \psi_{\text{rsp}} : E_{\text{com}} \to E'_{\text{chl}}$.

11: $(P_{\text{aux}}, Q_{\text{aux}}) := [2^{e-(e_{\text{rsp}}-n_{\text{bt}}+2)}] \cdot \text{DeterministicBasis}(E_{\text{aux}}^{\dagger})$.

12: $P_{\text{chl}} := [\deg(\varphi_{\text{aux}})^{-1}]\varphi'_{\text{rsp}} \circ \widehat{\varphi}_{\text{aux}}(P_{\text{aux}})$.

13: $Q_{\text{chl}} := [\deg(\varphi_{\text{aux}})^{-1}]\varphi'_{\text{rsp}} \circ \widehat{\varphi}_{\text{aux}}(Q_{\text{aux}})$.

14: **if** $-P_{\text{chl}}$ is lexicographically smaller than $P_{\text{chl}}$ **then**

15: $P_{\text{chl}}, Q_{\text{chl}} := -P_{\text{chl}}, -Q_{\text{chl}}$.

16: $\text{rsp} := (n_{\text{bt}}, r', E_{\text{aux}}^{\dagger}, P_{\text{chl}}, Q_{\text{chl}})$.

17: **return** $(\text{com}, \text{chl}, \text{rsp})$.

*Proof.* At line 20 in the response algorithm in Algorithm 2, we have

$$ R_{\text{chl}} = \iota_{\text{chl}} \circ \varphi_{\text{rsp}}^{\text{even}} \circ \varphi_{\text{rsp}}^{\text{odd}}(P_{\text{com}}), \quad R_{\text{aux}} = \iota_{\text{aux}} \circ \varphi_{\text{aux}}(P_{\text{com}}), $$

$$ S_{\text{chl}} = \iota_{\text{chl}} \circ \varphi_{\text{rsp}}^{\text{even}} \circ \varphi_{\text{rsp}}^{\text{odd}}(Q_{\text{com}}), \quad S_{\text{aux}} = \iota_{\text{aux}} \circ \varphi_{\text{aux}}(Q_{\text{com}}), $$

where $\iota_{\text{chl}} : E_{\text{rsp}}^{\text{odd}} \to E'_{\text{chl}}$ and $\iota_{\text{aux}} : E_{\text{aux}} \to E_{\text{aux}}^{\dagger}$ are the isomorphisms computed. Since $\deg(\varphi_{\text{aux}})$ is odd and $P_{\text{com}}, Q_{\text{com}} \in E_{\text{com}}[2^e]$, $(P_{\text{com}}, Q_{\text{com}})$ is the image of $(R_{\text{aux}}, S_{\text{aux}})$ through $[\deg(\varphi_{\text{aux}})^{-1}] \circ \widehat{\varphi}_{\text{aux}} \circ \widehat{\iota}_{\text{aux}}$. It follows that

$$ R_{\text{chl}} = [\deg(\varphi_{\text{aux}})^{-1}] \circ \iota_{\text{chl}} \circ \varphi_{\text{rsp}}^{\text{even}} \circ \varphi_{\text{rsp}}^{\text{odd}} \circ \widehat{\varphi}_{\text{aux}} \circ \widehat{\iota}_{\text{aux}}(R_{\text{aux}}) \text{ and} $$

$$ S_{\text{chl}} = [\deg(\varphi_{\text{aux}})^{-1}] \circ \iota_{\text{chl}} \circ \varphi_{\text{rsp}}^{\text{even}} \circ \varphi_{\text{rsp}}^{\text{odd}} \circ \widehat{\varphi}_{\text{aux}} \circ \widehat{\iota}_{\text{aux}}(S_{\text{aux}}). $$

After line 23 the same relationship holds for $(P_{\text{chl}}, Q_{\text{chl}})$ as the evaluation of $(P_{\text{aux}}, Q_{\text{aux}})$. Finally, the lines 24-25 makes a deterministic choice of sign for $P_{\text{chl}}$ and $Q_{\text{chl}}$. The simulator computes $P_{\text{chl}}, Q_{\text{chl}}$ in the same manner, by pushing $P_{\text{aux}}, Q_{\text{aux}}$ through $[\deg(\varphi_{\text{aux}})^{-1}] \circ \varphi'_{\text{rsp}} \circ \widehat{\varphi}_{\text{aux}}$ and then choosing the sign in the same way as the prover.

In the proof of Lemma 4.3, we saw that $E'_{\text{chl}}, E_{\text{aux}}^{\dagger}$ and the ideals corresponding to $\varphi_{\text{rsp}}, \varphi_{\text{aux}}$ and $\varphi_{\text{chl}}$ all have the same real and simulated distribution. These values determine the isogeny $E_{\text{aux}}^{\dagger} \to E'_{\text{chl}}$, up to post-composition with automorphisms. When $j(E'_{\text{chl}}) \notin \{0, 1728\}$, the only automorphisms of $E'_{\text{chl}}$ are $[\pm 1]$ [Sil86, Theorem III.10.1]. Then the automorphisms of $E'_{\text{chl}}$ only change the sign of the evaluation of the deterministic basis $(P_{\text{aux}}, Q_{\text{aux}})$. If the prover and simulator use isogenies $E_{\text{aux}}^{\dagger} \to E'_{\text{chl}}$ that agree up to post-composition with automorphisms, they compute the same $P_{\text{chl}}, Q_{\text{chl}}$, because they pick the same sign. So in this case, $P_{\text{chl}}$ and $Q_{\text{chl}}$ have the same real and simulated distribution. $\square$

The case when $j(E'_{\text{chl}})$ is 0 or 1728 must be handled separately. In this case, the real distribution of $P_{\text{chl}}, Q_{\text{chl}}$ might be distinguishable from the simulated distribution. However, we argue that this case will only happen with negligible probability under the assumption that the EndRing$_p$ problem is hard.

**Lemma 4.5.** Let $((\text{pp}, A_{\text{pk}}), I_{\text{sk}}) \in \mathcal{R}_{\text{SQI}}$. Let $J_{\text{chl}'}^{\text{real}}$ and $J_{\text{chl}'}^{\text{sim}}$ be random variables for the distribution of $j(E'_{\text{chl}})$ in real and simulated transcripts, respectively. There exists a PPT adversary $\mathcal{B}$ against the hard relation $\mathcal{R}_{\text{SQI}}$ such that

$$ \Pr[J_{\text{chl}'}^{\text{real}} \in \{0, 1728\}] \leq \text{Adv}_{\mathcal{R}_{\text{SQI}}}^{\text{rel}}(\mathcal{B}) \quad \text{and} \quad \Pr[J_{\text{chl}'}^{\text{sim}} \in \{0, 1728\}] \leq \text{Adv}_{\mathcal{R}_{\text{SQI}}}^{\text{rel}}(\mathcal{B}). $$
Proof. The curves with j-invariant 0 and 1728 have known endomorphism ring [McM14]. If the 2-isogeny walk of the challenge isogeny hits one of these curves with good probability, we can construct an efficient adversary B against $R_{\text{SQI}}$.

On input a statement (pp, $A_{pk}$) sampled from $\text{Gen}_{R_{\text{SQI}}}(1^{\lambda})$, B does the following:

1. Sample chl $\leftarrow \{0, \dots, 2^{e_{chl}} - 1\}$ and set $K = P_{pk} + [chl]Q_{pk}$, where $(P_{pk}, Q_{pk}) := \text{DeterministicBasis}(E_{pk})$.

2. Compute the 2-isogeny walk of the challenge isogeny with kernel generated by K,

$$ \varphi_{\text{chl}} : E_{\text{pk}} \xrightarrow{\varphi_1} E_1 \xrightarrow{\varphi_2} E_2 \xrightarrow{\varphi_3} \dots \xrightarrow{\varphi_n} E_n = E_{\text{chl}}. $$

3. If none of $E_1, \dots, E_n$ have j-invariant 0 or 1728, abort. Else, let $i$ be such that $j(E_i) \in \{0, 1728\}$.

4. Compute the generator $K'$ for the dual isogeny $\psi = \hat{\varphi}_1 \circ \dots \circ \hat{\varphi}_i : E_i \to E_{pk}$. This is done by pushing $[2^{e-i}]P_{pk}$ and $[2^{e-i}]Q_{pk}$ through $\varphi_i \circ \dots \circ \varphi_1$, and letting $K'$ be the evaluated point that has order $2^i$.

5. With $K'$ and a basis in efficient representation for $\text{End}(E_i) \cong \mathcal{O}_i$, use [DLRW24, Algorithm 9] to compute the ideal $I_{\psi}$ corresponding to $\psi$.

6. If $j(E_i) = 1728$, let $I := I_{\psi}$. Else, compute an ideal $I_0$ connecting $\mathcal{O}_0$ and $\mathcal{O}_i$ with [KV10, Algorithm 3.5], and let $I := I_0 \cdot I_{\psi}$.

7. Output $I$.

If B does not abort in step 3, it outputs a left $\mathcal{O}_0$-ideal $I$ with $\mathcal{O}_R(J) \cong \text{End}(E_{pk})$. Then $((\text{pp}, A_{pk}), J) \in R_{\text{SQI}}$.

The challenge isogeny $\varphi_{chl}$ has the same distribution in real and simulated transcripts. The probability that $j(E'_{chl}) \in \{0, 1728\}$ is at most the probability that some curve on the walk of $\varphi_{chl}$ has j-invariant 0 or 1728. The latter is exactly the probability that B succeeds. $\square$

We are now finally ready to prove that $\Sigma_{\text{SQI}}$ is $\mathcal{H}^{\text{sim}}$-hint-assisted wHVZK.

**Lemma 4.6 (Computational hint-assisted wHVZK).** Let $\mathcal{S}_{\text{SQI}}$ be the $\mathcal{H}^{\text{sim}}$-hint-assisted simulator defined in Algorithm 4. For any $q = \text{poly}(\lambda)$ and any PPT adversary A against the hint-assisted wHVZK of $\Sigma_{\text{SQI}}$ with $q$ hints, there exists a PPT algorithm B such that

$$ \text{Adv}_{\Sigma_{\text{SQI}}, \mathcal{H}^{\text{sim}}, \mathcal{S}_{\text{SQI}}}^{\text{hint-wHVZK}}(\mathcal{A}, q) \le \text{Adv}_{R_{\text{SQI}}}^{\text{rel}}(\mathcal{B}) + 2q \cdot \Delta(D_{\text{com}}, S_j). $$

*Proof.* Recall that A takes as input a statement (pp, $A_{pk}$) sampled from $\text{Gen}_R(1^{\lambda})$ and $q$ independently generated transcripts for this statement. The adversary tries to guess whether the transcripts come from the real or simulated distribution. The distinguishing advantage of A is

$$ \text{Adv}_{\Sigma_{\text{SQI}}, \mathcal{H}^{\text{sim}}, \mathcal{S}_{\text{SQI}}}^{\text{hint-wHVZK}}(\mathcal{A}) = |\text{Pr}[b^{\text{real}} = 1] - \text{Pr}[b^{\text{sim}} = 1]|, $$

where $b^{\text{real}} := \mathcal{A}(\text{Real}_{\Sigma_{\text{SQI}}}(1^{\lambda}, q))$ and $b^{\text{sim}} := \mathcal{A}(\text{HintSim}_{\Sigma_{\text{SQI}}}(1^{\lambda}, q, \mathcal{S}_{\text{SQI}}))$ are random variables.

We begin by considering the commitment. It is a j-invariant in $V := j(\text{Supersingular}_p)$, distributed as $D_{\text{com}}$ in real transcripts, and as $S_j$ in simulated transcripts. A is given $q$ independently sampled commitments from one of the distributions. When A gets real transcripts, let $J_{\text{com}}^{\text{real}} = (J_{\text{com},1}^{\text{real}}, \dots, J_{\text{com},q}^{\text{real}})$ be the random variable for the $q$ commitments. Similarly, when A gets simulated transcripts, let $J_{\text{com}}^{\text{sim}} = (J_{\text{com},1}^{\text{sim}}, \dots, J_{\text{com},q}^{\text{sim}})$ be the random variable for the $q$ commitments. For $j \in V^q$, we let $p_j^{\text{real}} = \text{Pr}[J_{\text{com}}^{\text{real}} = j]$ and $p_j^{\text{sim}} = \text{Pr}[J_{\text{com}}^{\text{sim}} = j]$. Using the statistical distance between $D_{\text{com}}$ and $S_j$,

$$
\begin{align}
\Pr[b^{\text{real}} = 1] &= \sum_{j \in V^q} p_j^{\text{real}} \Pr[b^{\text{real}} = 1 | J_{\text{com}}^{\text{real}} = j] \nonumber \\
&= \sum_{j \in V^q} (p_j^{\text{real}} - p_j^{\text{sim}} + p_j^{\text{sim}}) \cdot \Pr[b^{\text{real}} = 1 | J_{\text{com}}^{\text{real}} = j] \nonumber \\
&\le \sum_{j \in V^q} (|p_j^{\text{real}} - p_j^{\text{sim}}| + p_j^{\text{sim}}) \cdot \Pr[b^{\text{real}} = 1 | J_{\text{com}}^{\text{real}} = j] \nonumber \\
&\le \sum_{j \in V^q} |p_j^{\text{real}} - p_j^{\text{sim}}| + \sum_{j \in V^q} p_j^{\text{sim}} \Pr[b^{\text{real}} = 1 | J_{\text{com}}^{\text{real}} = j] \tag{2} \\
&= 2\Delta(J_{\text{com}}^{\text{real}}, J_{\text{com}}^{\text{sim}}) + \sum_{j \in V^q} p_j^{\text{sim}} \Pr[b^{\text{real}} = 1 | J_{\text{com}}^{\text{real}} = j] \nonumber \\
&\le 2q\Delta(D_{\text{com}}, S_j) + \sum_{j \in V^q} p_j^{\text{sim}} \Pr[b^{\text{real}} = 1 | J_{\text{com}}^{\text{real}} = j], \nonumber
\end{align}
$$
where the last step uses Proposition 2.2.

Next, we focus on $\Pr[b^{\text{real}} = 1 | \mathbf{J}_{\text{com}}^{\text{real}} = \mathbf{j}]$. It is the probability that $\mathcal{A}$ outputs 1 when it is given real transcripts with $\mathbf{j}$ as the commitments. When the commitments are fixed, we have seen in Lemma 4.3 and Lemma 4.4 that real and simulated transcripts are identically distributed, unless $j(E'_{\text{chl}}) \in \{0, 1728\}$.

When $\mathcal{A}$ is given real transcripts, let $G^{\text{real}}$ be the “good” event that all of the transcripts have $j(E'_{\text{chl}}) \notin \{0, 1728\}$. Let $G^{\text{sim}}$ be the corresponding event for the simulated transcripts. By Lemma 4.3, when the commitment is fixed, $j(E'_{\text{chl}})$ has the same distribution in real and simulated transcripts. Hence, for all $\mathbf{j} \in V^q$,

$$ \Pr[G^{\text{real}} | \mathbf{J}_{\text{com}}^{\text{real}} = \mathbf{j}] = \Pr[G^{\text{sim}} | \mathbf{J}_{\text{com}}^{\text{sim}} = \mathbf{j}]. $$

Furthermore, given that the good event has occurred, real and simulated transcripts are identically distributed, meaning that

$$ \Pr[b^{\text{real}} = 1 | \mathbf{J}_{\text{com}}^{\text{real}} = \mathbf{j}, G^{\text{real}}] = \Pr[b^{\text{sim}} = 1 | \mathbf{J}_{\text{com}}^{\text{sim}} = \mathbf{j}, G^{\text{sim}}]. $$

With these observations, we obtain that

$$ \begin{aligned} & \Pr[b^{\text{real}} = 1 | \mathbf{J}_{\text{com}}^{\text{real}} = \mathbf{j}] \\ &= \Pr[b^{\text{real}} = 1, G^{\text{real}} | \mathbf{J}_{\text{com}}^{\text{real}} = \mathbf{j}] + \Pr[b^{\text{real}} = 1, \neg G^{\text{real}} | \mathbf{J}_{\text{com}}^{\text{real}} = \mathbf{j}] \\ &\le \Pr[b^{\text{real}} = 1, G^{\text{real}} | \mathbf{J}_{\text{com}}^{\text{real}} = \mathbf{j}] + \Pr[\neg G^{\text{real}} | \mathbf{J}_{\text{com}}^{\text{real}} = \mathbf{j}] \\ &= \Pr[b^{\text{sim}} = 1, G^{\text{sim}} | \mathbf{J}_{\text{com}}^{\text{sim}} = \mathbf{j}] + \Pr[\neg G^{\text{sim}} | \mathbf{J}_{\text{com}}^{\text{sim}} = \mathbf{j}]. \end{aligned} $$

Combining this with (2), we get that

$$ \begin{aligned} \Pr[b^{\text{real}} = 1] &\le 2q\Delta(D_{\text{com}}, S_j) + \Pr[b^{\text{sim}} = 1, G^{\text{sim}}] + \Pr[\neg G^{\text{sim}}] \\ &\le 2q\Delta(D_{\text{com}}, S_j) + \Pr[b^{\text{sim}} = 1] + \Pr[\neg G^{\text{sim}}]. \end{aligned} $$

What remains is to upper bound the probability that $G^{\text{sim}}$ does not occur, i.e. the event that one of the $q$ simulated transcripts has $j(E'_{\text{chl}}) \in \{0, 1728\}$. For a single transcript, the probability can be upper bounded by the advantage of a PPT adversary $\mathcal{N}$ against the relation $R_{\text{SQI}}$, by Lemma 4.5. $\mathcal{N}$ first perfectly simulates the challenge isogeny, and then tries to use it to compute a witness for the statement. Consider the adversary $\mathcal{B}$ that runs $\mathcal{N}$ $q$ times with input $E_{\text{pk}}$, using a fresh random tape each time. Since $q = \text{poly}(\lambda)$, $\mathcal{B}$ is PPT. Furthermore,

$$ \Pr[\neg G^{\text{sim}}] \le \text{Adv}_{R_{\text{SQI}}}^{\text{rel}}(\mathcal{B}). $$

We conclude that

$$ \Pr[b^{\text{real}} = 1] - \Pr[b^{\text{sim}} = 1] \le 2q \cdot \Delta(D_{\text{com}}, S_j) + \text{Adv}_{R_{\text{SQI}}}^{\text{rel}}(\mathcal{B}). $$

By a symmetric argument, $\Pr[b^{\text{sim}} = 1] - \Pr[b^{\text{real}} = 1]$ has the same bound. $\square$

## 4.4 Applying the framework

We have shown that $\Sigma_{\text{SQI}}$ has the properties required to apply the framework of Section 3. It has high commitment min-entropy, is $\mathcal{H}^{\text{sim}}$-hint-assisted wHVZK, is special-sound with respect to the soundness relation $R_{\text{OneEnd}}$ and has an exponentially large challenge space in $\lambda$.10 By Theorem 1, we obtain a reduction from the relation $R_{\text{OneEnd}}$ with $\mathcal{H}^{\text{sim}}$-hints to the EUF-CMA of $\text{SIG}[\Sigma_{\text{SQI}}]$.

<footnote n="10">10 The challenge space in the round-2 SQISIGN submission to the NIST standardization process, is $2^{e_{\text{chl}}}$-large, which is a few bits short of being $2^{\lambda}$ large. This could be exploited by an attacker: given a valid signature $\sigma$ for a message $\text{msg}$, one can use a second preimage attack on the hash function used to generate a challenge to obtain a second message $\text{msg}'$. This leads to the exact same challenge in the SQISIGN identification protocol, so that $\sigma$ is also a valid signature for $\text{msg}'$. This would yield a forgery attack with complexity $O(2^{e_{\text{chl}}})$. To make up for the security gap, SQISIGN uses a hash function that consists of $2^{\lambda-e_{\text{chl}}}$ iterations of a standard hash function, SHAKE256. This technique, commonly known as “grinding” in the literature, brings the attack cost to the desired $O(2^{\lambda})$: finding a collision in the hash function requires $O(2^{e_{\text{chl}}})$ attempts, each of which consists of an evaluation of the hash function, which has a cost of at least $2^{\lambda-e_{\text{chl}}}$. Thus, the total attack cost is $O(2^{\lambda})$.</footnote>
**Algorithm 5: The pushable hint distribution**

$\mathcal{H}_E^{\text{unif}}$:

1: Sample an integer $d$ from a weighted distribution on the interval $[1, 2^{e_{\text{rsp}}}]$ where each integer $n$, with prime factorization $n = \prod_{i=1}^{t} p_i^{e_i}$, has weight $\prod_{i=1}^{t} (p_i + 1)^{e_i}$.

2: Sample an isogeny $\psi'_1 : E \to E'_1$ uniformly among the (possibly non-cyclic) isogenies from $E$ of degree $d$.

3: Write $\psi_1 : E \to E_1$ for the cyclic component of $\psi'_1$.

4: Write $\deg \psi_1 = 2^n d'$ with $d'$ odd.

5: Sample an isogeny $\psi_2 : E_1 \to E_2$ uniformly among the cyclic isogenies from $E_1$ of degree $2^{e_{\text{rsp}}-n} - d'$.

6: return $h = (\psi_1, \psi_2)$.

**Theorem 2.** For any PPT algorithm $\mathcal{A}$ against the EUF-CMA of SIG[$\Sigma_{\text{SQI}}$], there exists an expected polynomial time algorithm $\mathcal{E}$ with

$$ \mathrm{Adv}_{\mathrm{SIG}[\Sigma_{\mathrm{SQI}}]}^{\mathrm{EUF-CMA}}(\mathcal{A}) \le (q+1) \cdot \left( 2 \cdot \mathrm{Adv}_{(R_{\mathrm{OneEnd}}, \mathcal{H}^{\mathrm{sim}})}^{\mathrm{hint-rel}}(\mathcal{E}, s) + 2^{-e_{\mathrm{chl}}} \right) + \frac{(2q+s+2)s}{\sqrt{p}}, $$

where $q$ and $s$ are upper bounds on the number of queries that $\mathcal{A}$ makes to RO and OSign, respectively.

*Proof.* $\Sigma_{\text{SQI}}$ is special-sound w.r.t. the soundness relation $R_{\text{OneEnd}}$ and has the $\mathcal{H}^{\text{sim}}$-hint-assisted simulator $S_{\text{SQI}}$. By Theorem 1, there exists a PPT algorithm $\mathcal{N}$ and an expected polynomial time algorithm $\mathcal{E}_1$ such that

$$ \mathrm{Adv}_{\mathrm{SIG}[\Sigma_{\mathrm{SQI}}]}^{\mathrm{EUF-CMA}}(\mathcal{A}) \le (q+1) \cdot \left( \mathrm{Adv}_{(R_{\mathrm{OneEnd}}, \mathcal{H}^{\mathrm{sim}})}^{\mathrm{hint-rel}}(\mathcal{E}_1, s) + \mathrm{Adv}_{\Sigma_{\mathrm{SQI}}, \mathcal{H}^{\mathrm{sim}}, S_{\mathrm{SQI}}}^{\mathrm{hint-wHVZK}}(\mathcal{N}, s) \right) + \frac{q+1}{|\mathcal{C}|} + (q+s+1)s \cdot \mathrm{MinEnt}(\Sigma_{\mathrm{SQI}}). \quad (3) $$

We have $|\mathcal{C}| = 2^{e_{\mathrm{chl}}}$ . By Lemma 4.1, $\mathrm{MinEnt}(\Sigma_{\text{SQI}}) \le 1/\sqrt{p}$. For the hint-assisted wHVZK adversary $\mathcal{N}$, we use Lemma 4.6 to construct a PPT algorithm $\mathcal{M}$ such that by Proposition 2.4,

$$ \mathrm{Adv}_{\Sigma_{\mathrm{SQI}}, \mathcal{H}^{\mathrm{sim}}, S_{\mathrm{SQI}}}^{\mathrm{hint-wHVZK}}(\mathcal{N}, s) \le \mathrm{Adv}_{R_{\mathrm{SQI}}}^{\mathrm{rel}}(\mathcal{M}) + 2s \cdot \Delta(D_{\mathrm{com}}, S_j) \le \mathrm{Adv}_{R_{\mathrm{SQI}}}^{\mathrm{rel}}(\mathcal{M}) + \frac{s}{\sqrt{p}}. \quad (4) $$

Next, we use $\mathcal{M}$ to construct an algorithm $\mathcal{E}_2$ for the relation $R_{\text{OneEnd}}$ with hints. $\mathcal{E}_2$ does not use the hints, instead it runs $\mathcal{M}$ to compute $I_{\text{sk}}$, and if it succeeds, uses the special soundness to compute a witness for $R_{\text{OneEnd}}$. Let $\mathcal{E}$ be the algorithm with the maximal success probability out of $\mathcal{E}_1$ and $\mathcal{E}_2$, such that

$$ \mathrm{Adv}_{(R_{\text{OneEnd}}, \mathcal{H}^{\text{sim}})}^{\text{hint-rel}}(\mathcal{E}_1, s) + \mathrm{Adv}_{R_{\text{SQI}}}^{\text{rel}}(\mathcal{M}) \le 2 \cdot \mathrm{Adv}_{(R_{\text{OneEnd}}, \mathcal{H}^{\text{sim}})}^{\text{hint-rel}}(\mathcal{E}, s). \quad (5) $$

We conclude by plugging (4), (5) and $\mathrm{MinEnt}(\Sigma_{\text{SQI}}) \le 1/\sqrt{p}$ into (3). $\square$

# 5 Reducing hint-EndRing to the EUF-CMA of SQIsign

Without hints, [PW24] reduced the EndRing$_p$ problem to the OneEnd$_p$ problem. In this section, our goal is to provide a similar reduction with hints. For this, we introduce a new hint distribution $\mathcal{H}^{\text{unif}}$ for SQISIGN. $\mathcal{H}^{\text{unif}}$ is less structured and arguably more natural than $\mathcal{H}^{\text{sim}}$. Additionally, hints from $\mathcal{H}^{\text{unif}}$ are pushable. This means that given a $2^n$-isogeny $\sigma : E \to E'$ and a hint $h \leftarrow \mathcal{H}_E^{\text{unif}}$ for $E$, we can push it through $\sigma$ to get a hint for $E'$ distributed according to $\mathcal{H}_{E'}^{\text{unif}}$. With this property, the OneEnd$_p$ problem with $\mathcal{H}^{\text{unif}}$-hints is random self-reducible, and we obtain a reduction to it from the EndRing$_p$ problem with $\mathcal{H}^{\text{unif}}$-hints. To argue that this new hint-EndRing problem can be reduced to the EUF-CMA of SQISIGN, we introduce a new indistinguishability assumption.

## 5.1 The pushable hint distribution

We introduce a new hint distribution $\mathcal{H}^{\text{unif}}$: rather than sampling a random curve and generating a connecting isogeny, the new hint distribution $\mathcal{H}_E^{\text{unif}}$ samples random isogenies directly from $E$, as defined in Algorithm 5. The main property of the new distribution is that, unlike the previous hint distribution $\mathcal{H}^{\text{sim}}$, it is pushable. We push hints using Algorithm 6.
**Algorithm 6: PushHint(E, h, σ)**

**Input:** $E \in \text{Supersingular}_p$, $h = (\psi_1, \psi_2) \in \text{HintSet}_E^{\text{unif}}$ with $\psi_1: E \to E_1$ and $\psi_2: E_1 \to E_2$, cyclic $2^k$-isogeny $\sigma: E \to E'$ in efficient representation.
**Output:** $h' \in \text{HintSet}_E^{\text{unif}}$
1: Write $\psi$ for the composition $\psi = \psi_2 \circ \psi_1$.
2: Write $\deg(\psi) = 2^n d_{\text{odd}}$ with $d_{\text{odd}}$ odd.
3: Compute the pushforward $\psi'_{\text{odd}}: E' \to E_1$ of $\psi_{\text{odd}}$ by $\tau$.
4: Sample $\psi'_{2^n} : E_1' \to E_2'$ as a random cyclic $2^n$-isogeny from $E_1'$.
5: Let $\psi' = \psi'_{2^n} \circ \psi'_{\text{odd}}$.
6: Write $\psi'$ for the composition $\psi' = \psi'_2 \circ \psi'_1$ where $\deg \psi'_i = \deg \psi_i$ for $i \in \{1, 2\}$.
7: **return** $h' = (\psi'_1, \psi'_2)$.

1: Write $\psi$ for the composition $\psi = \psi_2 \circ \psi_1$.

2: Write $\deg(\psi) = 2^n d_{\text{odd}}$ with $d_{\text{odd}}$ odd.

3: Compute the pushforward $\psi'_{\text{odd}}: E' \to E_1$ of $\psi_{\text{odd}}$ by $\tau$.

4: Sample $\psi'_{2^n} : E_1' \to E_2'$ as a random cyclic $2^n$-isogeny from $E_1'$.

5: Let $\psi' = \psi'_{2^n} \circ \psi'_{\text{odd}}$.

6: Write $\psi'$ for the composition $\psi' = \psi'_2 \circ \psi'_1$ where $\deg \psi'_i = \deg \psi_i$ for $i \in \{1, 2\}$.

7: **return** $h' = (\psi'_1, \psi'_2)$.

**Lemma 5.1.** Let $E \in \text{Supersingular}_p$, let $k \in \mathbb{N}$ and let $\sigma: E \to E'$ be a cyclic $2^k$-isogeny in efficient representation. If $h \leftarrow \mathcal{H}_E^{\text{unif}}$, then PushHint(E, h, σ) is distributed according to $\mathcal{H}_{E'}^{\text{unif}}$.

*Proof.* Let $h = (\psi_1, \psi_2) \leftarrow \mathcal{H}_E^{\text{unif}}$ and $h' = (\psi'_1, \psi'_2) \leftarrow \text{PushHint}(E, h, \sigma)$. Write $\psi$ for the composition $\psi_2 \circ \psi_1$, and similarly $\psi' = \psi'_2 \circ \psi'_1$.

We start by noting that Lines 2 and 3 of Algorithm 5 (i.e., sampling of a possibly non-cyclic isogeny and extracting its cyclic component) affects the distribution of the degrees but not the distribution of the isogenies themselves, conditional on the degree. In other words, the isogeny $\psi_1$ is uniformly distributed among the cyclic isogenies of degree $\deg \psi_1$ from $E$. Since the PushHint algorithm preserves degrees, it is sufficient to show that $\psi'$ is uniformly distributed among the cyclic isogenies of degree $\deg \psi'$ from $E'$.

Then, we first consider the case where the degree $d := \deg(\psi)$ is odd. Then, the isogeny $\psi'$ is precisely the pushforward of $\psi$ by $\sigma$; similarly, the isogeny $\psi$ is the pullback of $\psi'$ by $\sigma$ (or, alternatively, the pushforward of $\psi'$ by $\hat{\sigma}$). Thus, the isogeny $\sigma$ induces a bijection between the isogenies from $E$ of degree $d$ and the isogenies from $E'$ of degree $d$ for any odd $d$. Since the supersingular graph is regular, the number of outgoing $d$-isogenies is the same for any curve in the graph. Hence, the distribution of $\psi'$ is uniform among the cyclic isogenies from $E'$ of degree $d$; that is, $\psi'$ is perfectly distributed as the composition of the hints produced by $\mathcal{H}_{E'}^{\text{unif}}$.

Lastly, we consider the case where $d = 2^n d_{\text{odd}}$ with $d_{\text{odd}}$ odd and $n > 0$. In this case, the isogeny $\psi'$ is the composition of a $d_{\text{odd}}$-isogeny and a random cyclic $2^n$-isogeny. The $d_{\text{odd}}$ component is uniformly distributed among the $d_{\text{odd}}$-isogenies originating from $E'$, by the previous argument; the $2^n$-component is also uniformly distributed, by construction. Hence, the isogeny $\psi'$ is perfectly distributed as the composition of the hints produced by $\mathcal{H}_{E'}^{\text{unif}}$. $\square$

By relying on the pushing algorithm (Algorithm 6), we can use a hint from $\mathcal{H}^{\text{unif}}$ to generate something that looks like a hint from $\mathcal{H}^{\text{sim}}$. Formally, we consider the problem of distinguishing between the two distributions in Experiment 4. For $q = \text{poly}(\lambda)$, we refer to this as the $q$-hint distinguishing problem (q-hint-dist). More formally, we have:

**Problem 3 (q-hint-dist).** Let $(E, h_1, \dots, h_q)$ be sampled with probability $1/2$ from $\text{RealHints}(1^\lambda, q)$ and with probability $1/2$ from $\text{PushHints}(1^\lambda, q)$, where $\text{RealHints}(1^\lambda, q)$ and $\text{PushHints}(1^\lambda, q)$ are defined in Experiment 4. Given $(E, h_1, \dots, h_q)$, distinguish between the two distributions.

For an algorithm $\mathcal{A}$, we let

$$ \text{Adv}^{\text{hint-dist}}(\mathcal{A}, q) := \text{Adv}^{\text{dist}}[\text{RealHints}(1^{\lambda}, q), \text{PushHints}(1^{\lambda}, q)](\mathcal{A}). $$

**Remark 5.1.** We expect the problem of distinguishing between the hint distributions $\text{RealHints}(1^\lambda, q)$ and $\text{PushHints}(1^\lambda, q)$ to be computationally hard, following a similar argument on the heuristical equivalence of two oracles in SQIsign2D-West [BDD$^+$24, Sec. 5.2]. The two hints distributions provide a representation of three isogenies $\varphi_1: E \to E_1$, $\varphi_2: E_1 \to E_2$, and $\varphi_3: E_2 \to E_3$. The first isogeny $\varphi_1$ is sampled according to the same distribution in both games, thus the curves $E, E_1$ and the isogeny $\varphi_1$ cannot provide any distinguishing information. The same is true for the third isogeny $\varphi_3$: fixed a starting curve $E_2$, the isogeny $\varphi_3$ is sampled according to the same distribution in both games. Thus, we focus on the second isogeny: in $\text{RealHints}(1^\lambda, q)$, the isogeny $\varphi_2$ is uniformly distributed among the isogenies between $E_1$ and $E_2$; by rejection sampling, the same is true in $\text{PushHints}(1^\lambda, q)$. Hence, the only distinguishing
Experiment 4: Hint distinguishing

Realhints(1^λ, q):

1: (E, I) ← Gen<sub>R<sub>SQI</sub></sub>(1<sup>λ</sup>)

2: for i = 1 to q do

3: h<sub>i</sub> ← H<sub>E</sub><sup>sim</sup>

4: return (E, h<sub>1</sub>, ..., h<sub>q</sub>)

Pushedhints(1^λ, q):

1: (E, I) ← Gen<sub>R<sub>SQI</sub></sub>(1<sup>λ</sup>)

2: for i = 1 to q do

3: (ψ<sub>1</sub>, ψ<sub>2</sub>) ← H<sub>E</sub><sup>unif</sup>

4: (s, φ) ← D<sub>Chall</sub>(E)

5: (ψ'<sub>1</sub>, ψ'<sub>2</sub>) ← PushHint(E, (ψ<sub>1</sub>, ψ<sub>2</sub>), φ)

6: h<sub>i</sub> := (s, ψ'<sub>1</sub>, ψ'<sub>2</sub>)

7: return (E, h<sub>1</sub>, ..., h<sub>q</sub>)

// see Experiment 3

factor is the distribution of the curve $E_2$: in Realhints(1^λ, q) it is distributed according to the stationary distribution, while in Pushedhints(1^λ, q) it is the codomain of a random isogeny $\varphi_2$ from $E_1$ of bounded degree. If the isogeny $\varphi_2$ was sufficiently long, the statistical distance between the curves $E_2$ produced by the two games would become negligible; in our case, the bound on the degree of $\varphi_2$ prevents $E_2$ from being close to stationary. However, since the bound on the degree is exponential in $\lambda$, we still expect the distinguishing problem to be computationally hard.

5.2 The reduction from hint-OneEnd

**Problem 4 (q-hint-OneEnd<sub>p</sub>).** Given a curve $E$ sampled from the stationary distribution $S$ on Supersingular<sub>p</sub> and $q$ hints $h_1, \dots, h_q \leftarrow \mathcal{H}_E^{\text{unif}}$, find an endomorphism in $\text{End}(E) \setminus \mathbb{Z}$ in efficient representation.

For an algorithm $\mathcal{A}$, we write $\text{Adv}^{\text{hint-OneEnd}_p}(\mathcal{A}, q)$ for the probability that it solves $q$-hint-OneEnd<sub>p</sub>. We obtain a reduction from $q$-hint-OneEnd<sub>p</sub> by replacing the hint distribution in Theorem 2 with $\mathcal{H}^{\text{unif}}$.

**Theorem 3.** For any PPT algorithm $\mathcal{A}$ against the EUF-CMA of SIG[$\Sigma_{\text{SQI}}$], there exist expected polynomial time algorithms $\mathcal{B}$ and $\mathcal{D}$ with

$$
\begin{align*}
\text{Adv}_{\text{SIG}[\Sigma_{\text{SQI}}]}^{\text{EUF-CMA}}(\mathcal{A}) \le (q+1) \cdot & \left( 2 \cdot \text{Adv}^{\text{hint-OneEnd}_p}(\mathcal{B}, s) + 2 \cdot \text{Adv}^{\text{hint-dist}}(\mathcal{D}, s) + 2^{-e_{\text{chl}}} \right) \\
& + \frac{2qs + s^2 + 2s + q + 1}{\sqrt{p}},
\end{align*}
$$

where $q$ and $s$ are upper bounds on the number of queries that $\mathcal{A}$ makes to RO and OSign, respectively.

*Proof.* By Theorem 2, there exists an expected polynomial time algorithm $\mathcal{E}$ such that

$$
\text{Adv}_{\text{SIG}[\Sigma_{\text{SQI}}]}^{\text{EUF-CMA}}(\mathcal{A}) \le (q+1) \cdot \left( 2 \cdot \text{Adv}^{\text{hint-rel}}_{(R_{\text{OneEnd}}, \mathcal{H}^{\text{sim}})}(\mathcal{E}, s) + 2^{-e_{\text{chl}}} \right) + \frac{(2q+s+2)s}{\sqrt{p}}. \quad (6)
$$

We construct $\mathcal{B}$ from $\mathcal{E}$ by simulating the hints of $\mathcal{H}^{\text{sim}}$ with the hints from $\mathcal{H}^{\text{unif}}$. $\mathcal{B}$ gets as input a curve $E_{pk}$ sampled from Gen<sub>R<sub>OneEnd</sub></sub>(1<sup>λ</sup>) and hints $h_1, \dots, h_s \leftarrow \mathcal{H}_{E_{pk}}^{\text{unif}}$. It then uses the $\mathcal{H}^{\text{unif}}$-hints to compute hints $h'_1, \dots, h'_s \in \text{HintSet}_{E_{pk}}^{\text{sim}}$ as in Pushedhints(1<sup>λ</sup>, s) of Experiment 4. Finally, it runs $\alpha \leftarrow \mathcal{E}(E_{pk}, h'_1, \dots, h'_s)$ and outputs $\alpha$.

Any difference in success probability between $\mathcal{E}$ and $\mathcal{B}$ can be used to construct an adversary $\mathcal{D}$ against $s$-hint-dist. On input $E$ and hints $h_1, \dots, h_s \in \text{HintSet}_E^{\text{sim}}$, $\mathcal{D}$ runs $\mathcal{E}(E, h_1, \dots, h_s)$. It outputs 1 if $\mathcal{E}$ outputs a witness $\alpha$ s.t. $(E, \alpha) \in R_{\text{OneEnd}}$, else it outputs 0. By construction,

$$
\text{Adv}^{\text{hint-dist}}(\mathcal{D}, s) = \left| \text{Adv}^{\text{hint-rel}}_{(R_{\text{OneEnd}}, \mathcal{H}^{\text{sim}})}(\mathcal{E}, s) - \text{Adv}^{\text{hint-rel}}_{(R_{\text{OneEnd}}, \mathcal{H}^{\text{unif}})}(\mathcal{B}, s) \right|,
$$

so in particular

$$
\text{Adv}^{\text{hint-rel}}_{(R_{\text{OneEnd}}, \mathcal{H}^{\text{sim}})}(\mathcal{E}, s) \le \text{Adv}^{\text{hint-rel}}_{(R_{\text{OneEnd}}, \mathcal{H}^{\text{unif}})}(\mathcal{B}, s) + \text{Adv}^{\text{hint-dist}}(\mathcal{D}, s). \quad (7)
$$

In the $q$-hint-OneEnd<sub>p</sub> problem, the curve is sampled from the stationary distribution $S$ on Supersingular<sub>p</sub>. By Proposition 2.3 and Proposition 2.4,

$$
\begin{align}
\text{Adv}^{\text{hint-rel}}_{(R_{\text{OneEnd}}, \mathcal{H}^{\text{unif}})}(\mathcal{B}, s) &\le \text{Adv}^{\text{hint-OneEnd}_p}(\mathcal{B}, s) + \Delta(E_{pk}, S) \nonumber \\
&\le \text{Adv}^{\text{hint-OneEnd}_p}(\mathcal{B}, s) + \frac{1}{2\sqrt{p}}. \tag{8}
\end{align}
$$
We conclude by plugging (7) and (8) into (6).

□

An important property of the $OneEnd_p$ problem is that it is a random self-reducible. Since $\mathcal{H}^{\text{unif}}$-hints are pushable, we can show that $q$-hint-$OneEnd_p$ retains this property.

**Lemma 5.2.** Let $\mathcal{A}$ be an algorithm for $q$-hint-$OneEnd_p$ with advantage $\varepsilon$ and outputs of degree at most $d$. Then we can construct an algorithm $\mathcal{A}'$ with the following properties.

1. For any curve $E \in \text{Supersingular}_p$, it solves $q$-hint-$OneEnd_p$ for $E$ with probability in $[\varepsilon - \frac{\log p}{p}, \varepsilon + \frac{\log p}{p}]$.

2. It runs $\mathcal{A}$ once. The rest of the algorithm runs in polynomial time in $\log p, \log d$ and $q$.

3. Its output has degree at most $2^{6[\log p]} \cdot d$.

*Proof.* $\mathcal{A}'$ gets as input $E \in \text{Supersingular}_p$ and $h_1, \dots, h_q \leftarrow \mathcal{H}_E^{\text{unif}}$, and does the following.

1. Sample $\sigma' : E \to E_A$ by a random non-backtracking 2-isogeny walk of length $3[\log p]$.

2. $\mathcal{A}' \leftarrow \text{MontgomeryRandomize}(\mathcal{A})$ and $E' := E_{\mathcal{A}'}$.

3. Compute an isomorphism $\iota : E_A \to E'$ and let $\sigma := \iota \circ \sigma' : E \to E'$.

4. $h'_i \leftarrow \text{PushHint}(E, h_i, \sigma)$ for $i = 1, \dots, q$.

5. Run $\mathcal{A}$ on input $E'$ and $h'_1, \dots, h'_q$.

6. When $\mathcal{A}$ outputs $\alpha$, abort if $\alpha \notin \text{EndRing}(E') \setminus \mathbb{Z}$.

7. Output $\hat{\sigma} \circ \alpha \circ \sigma$.

If $\hat{\varphi} \circ \alpha \circ \varphi = [m]$, then pre-composing with $\hat{\varphi}$ and post-composing with $\varphi$, we get that $[(\deg \varphi)^2] \circ \alpha = [\deg(\varphi)m]$, so that $\alpha = [m/(\deg(\varphi))]$. Hence, if $\alpha \in \text{End}(E') \setminus \mathbb{Z}$, then $\hat{\sigma} \circ \alpha \circ \sigma \in \text{End}(E) \setminus \mathbb{Z}$.

Let $D$ be the distribution of $E'$ and $D_j$ the distribution of $j(E')$. By Proposition 2.4,

$$ \Delta(D, S) = \Delta(D_j, S_j) \le \frac{3[\log p] + 1}{4p} \le \frac{\log p}{p}, $$

using $\log p \ge 4$ for the last inequality.

Any difference in success probability between $\mathcal{A}$ and $\mathcal{A}'$ can be used to construct a non-efficient distinguisher $\mathcal{D}$ between $D$ and $S$. It will not be efficient, as it needs to sample hints from $\mathcal{H}^{\text{unif}}$ itself. On input a curve $E$, $\mathcal{D}$ first computes a basis for $\text{End}(E)$. It then uses the basis to sample $q$ hints $h_1, \dots, h_q \leftarrow \mathcal{H}_E^{\text{unif}}$. Finally, it runs $\mathcal{A}$ on input $E$ and $h_1, \dots, h_q$, and outputs 1 if and only if $\mathcal{A}$ succeeds. By Proposition 2.3, $\text{Adv}^{\text{dist}}[D, S](\mathcal{D}) = |\varepsilon'(E) - \varepsilon| \le \Delta(D, S)$. □

## 5.3 The classical reduction from hint-EndRing

**Problem 5 (q-hint-EndRing$_p$).** Given a curve $E$ sampled from the stationary distribution $S$ on Supersingular$_p$ and $q$ hints $h_1, \dots, h_q \leftarrow \mathcal{H}_E^{\text{unif}}$, find four endomorphisms in efficient representation that form a basis of $\text{End}(E)$ as a lattice.

For an algorithm $\mathcal{A}$, we let $\text{Adv}^{\text{hint-EndRing}_p}(\mathcal{A}, q)$ denote the probability that $\mathcal{A}$ succeeds in solving $q$-hint-$\text{EndRing}_p$.

Without hints, [PW24] proved that an oracle for $\text{OneEnd}_p$ can be used to construct an efficient algorithm for $\text{EndRing}_p$. We recap their reduction in Section 6.1. Importantly, Corollary 6.1 shows that if the $\text{OneEnd}_p$ oracle has outputs of degree at most $d$, the algorithm for $\text{EndRing}_p$ runs in time $\text{poly}(\log p, \log d)$ times the number of calls it makes to the oracle. In expectation, the number of calls is

$$ t_{\text{OneEnd}}(\log p, \log d) < 2^{94} \cdot (\log(p) + \log(d)/30)^{13}. $$

We will show that with the pushable hint distribution $\mathcal{H}^{\text{unif}}$, we can reduce hint-$\text{EndRing}_p$ to hint-$\text{OneEnd}_p$ in the same way that [PW24] reduces $\text{EndRing}_p$ to $\text{OneEnd}_p$. We assume throughout that $q, \log d = \text{poly}(\log p)$. In the intermediate steps of our reduction, we consider several kinds of oracles.

- For each $E \in \text{Supersingular}_p$, $\text{OHint}_E$ is an oracle that when queried outputs a fresh hint sampled from $\mathcal{H}_E^{\text{unif}}$.
- For each $E \in \text{Supersingular}_p$, $\text{OEnd}_1 E, d$ is an oracle that, on input a $2^k$-isogeny $\sigma : E \to E'$ in efficient representation for some $k$ and $E' \in \text{Supersingular}_p$, outputs a non-scalar endomorphism of $E'$ of degree at most $d$.

- $\text{OEnd}_2 q, d, \varepsilon$ is an oracle which, on input a curve $E \in \text{Supersingular}_p$ and $q$ hints $h_1, \dots, h_q \leftarrow \mathcal{H}_E^{\text{unif}}$, outputs a non-scalar endomorphism of $E$ of degree at most $d$, with probability in $[\varepsilon - \frac{\log(p)}{p}, \varepsilon + \frac{\log(p)}{p}]$.

Our reduction proceeds in smaller steps, where the oracles are the parts we have not implemented yet. In the runtime analysis, each call to an oracle counts as a single step.

**Lemma 5.3.** There is an algorithm $\mathcal{A}$, which on input a curve $E \in \text{Supersingular}_p$ and given query access to the oracle $\text{OEnd}_1 E, d$, computes $\text{End}(E)$. Its runtime is $\text{poly}(\log p)$ times the number of calls it makes to $\text{OEnd}_1 E, d$. In expectation, the number of times it calls $\text{OEnd}_1 E, d$ is $t_{\text{OneEnd}}(\log p, \log d)$.

*Proof.* We follow the reduction from $\text{EndRing}_p$ to $\text{OneEnd}_p$ in [PW24]. We only need to implement their “rich oracle” $\text{RICH}^\mathcal{O}$ with parameter $k = \text{poly}(\log p)$ [PW24, Algorithm 1]. We implement it as follows.

1. Sample a $2^k$-isogeny $\sigma : E \to E'$ by a random non-backtracking walk.

2. $\alpha \leftarrow \text{OEnd}_1 E, d(\sigma)$.

3. (In the second stage of the reduction, reduce $\alpha$.)

4. Return $\hat{\sigma} \circ \alpha \circ \sigma$.

The expected number of calls to $\text{OEnd}_1 E, d$ is exactly the expected number of calls to the $\text{OneEnd}_p$ oracle in the reduction in [PW24]. The runtime follows by Corollary 6.1. $\square$

When $\varepsilon$ is large enough, we implement $\text{OEnd}_1 E, d$ using $\text{OHint}_E$ and $\text{OEnd}_2 q, d, \varepsilon$.

**Lemma 5.4.** Assume $\varepsilon \ge 2 \log(p)/p$. There is an algorithm $\mathcal{B}$, which on input a $2^k$-isogeny $\sigma : E \to E'$ with $E, E' \in \text{Supersingular}_p$, and given query-access to the oracles $\text{OEnd}_2 q, d, \varepsilon$ and $\text{OHint}_E$, has the following properties.

1. It outputs a non-scalar endomorphism of $E'$ of degree at most $d$.

2. Its runtime is $k \cdot \text{poly}(\log p)$ multiplied by the number of calls to $\text{OEnd}_2 q, d, \varepsilon$.

3. In expectation, it calls $\text{OEnd}_2 q, d, \varepsilon$ at most $2/\varepsilon$ times.

4. For every call to $\text{OEnd}_2 q, d, \varepsilon$, it makes $q$ calls to $\text{OHint}_E$.

*Proof.* On input $\sigma : E \to E'$, $\mathcal{B}$ follows these steps:

1. Sample $h_i \leftarrow \text{OHint}_E$ for $i = 1, \dots, q$.

2. $h'_i \leftarrow \text{PushHint}(E, h_i, \sigma)$ for $i = 1, \dots, q$.

3. $\alpha \leftarrow \text{OEnd}_2 q, d, \varepsilon(E', h'_1, \dots, h'_q)$.

4. If $\alpha \in \mathbb{Z}$, go back to step 1. Else, output $\alpha$.

Each iteration of the loop is an independent trial that succeeds with probability at least $\varepsilon - \log(p)/p \ge \varepsilon - \varepsilon/2 = \varepsilon/2$. Hence, the expected number of iterations is at most $2/\varepsilon$. $\square$

Combing the two previous results, we obtain the following.

**Corollary 5.1.** Assume $\varepsilon \ge 2 \log(p)/p$. There exists an algorithm $\mathcal{D}$, which on input a curve $E \in \text{Supersingular}_p$, and given query access to $\text{OHint}_E$ and $\text{OEnd}_2 q, d, \varepsilon$, computes $\text{End}(E)$. It has the following properties.

1. Its runtime is $\text{poly}(\log p)$ multiplied by the number of times it calls $\text{OEnd}_2 q, d, \varepsilon$.

2. In expectation, it calls $\text{OEnd}_2 q, d, \varepsilon$ at most $2t_{\text{OneEnd}}(\log p, \log d)/\varepsilon$ times.

3. For every call to $\text{OEnd}_2 q, d, \varepsilon$, it makes $q$ calls to $\text{OHint}_E$.

When we have an algorithm for $q$-hint-$\text{OneEnd}_p$ with non-negligible advantage, we can convert it to an algorithm for $s$-hint-$\text{EndRing}_p$, without any oracles.

**Lemma 5.5.** Let $\mathcal{A}$ be an expected polynomial time algorithm for $q$-hint-$\text{OneEnd}_p$ with advantage $\varepsilon \ge 2 \log(p)/p$ and with outputs of degree at most $d$. Let

$$s := 4q \cdot t_{\text{OneEnd}}(\log p, \log d + 6[\log p]) / \varepsilon.$$

Then there exists an algorithm $\mathcal{B}$ for $s$-hint-$\text{EndRing}_p$, running in expected time $s \cdot \text{poly}(\log p)$, with advantage at least $1/2$.
*Proof.* Let $\mathcal{D}$ be the oracle-algorithm from Corollary 5.1 with the degree bound $d' := 2^{6[\log p]} \cdot d$. We will first convert $\mathcal{D}$ to an algorithm with bounded worst-case running time and then instantiate its oracles.

Recall that $\mathcal{D}$ succeeds with probability 1 and has a runtime that is $\text{poly}(\log p)$ multiplied by the number of times it calls $\text{OEnd}_{2,q,d',\varepsilon}$. We will view the number of calls to this oracle as the runtime, and apply Lemma 3.3. In expectation, $\mathcal{D}$ makes $s/2$ calls to $\text{OEnd}_{2,q,d',\varepsilon}$. The corollary tells us that if we time out $\mathcal{D}$ after $s$ calls to $\text{OEnd}_{2,q,d',\varepsilon}$, it still succeeds with probability at least $1/2$. Denote the algorithm that times out by $\mathcal{N}$. Its runtime is at most $s \cdot \text{poly}(\log p)$.

Next, we instantiate the oracles of $\mathcal{N}$, to get an algorithm $\mathcal{B}$ for $s$-hint-EndRing$_p$. We implement the hint oracle $\text{OHint}_E$ simply by answering the $i$th query with the $i$th hint $h_i$. We implement $\text{OEnd}_{2,q,d',\varepsilon}$ using $\mathcal{A}'$, the algorithm we obtain from the worst-case to average-case reduction in Lemma 5.2 with $\mathcal{A}$. It runs in expected time $\text{poly}(\log p)$, with advantage in $[\varepsilon - \frac{\log p}{p}, \varepsilon + \frac{\log p}{p}]$. Its output has degree at most $d'$.

Composing the algorithm $\mathcal{A}'$ running in expected polynomial time with the oracle-algorithm $\mathcal{N}$ running in time $s \cdot \text{poly}(\log p)$, we get that $\mathcal{B}$ runs in expected time $s \cdot \text{poly}(\log p)$. Since $\mathcal{A}'$ always succeeds, $\mathcal{B}$ has the same advantage as $\mathcal{N}$. $\square$

We conclude that if $q$-hint-EndRing$_p$ and $q$-hint-dist are computationally hard problems, then $\text{SIG}[\Sigma_{\text{SQI}}]$ is EUF-CMA-secure in the ROM. Our reduction inherits the non-tightness from [PW24].

**Theorem 4.** For any PPT algorithm $\mathcal{A}$ against the EUF-CMA of $\text{SIG}[\Sigma_{\text{SQI}}]$, there are expected polynomial time algorithms $\mathcal{B}$ and $\mathcal{D}$ with

$$ \text{Adv}_{\text{SIG}[\Sigma_{\text{SQI}}]}^{\text{EUF-CMA}}(\mathcal{A}) \le (q+1) \cdot \left( 2 \cdot \text{Adv}^{\text{hint-OneEnd}_p}(\mathcal{B}, s) + 2 \cdot \text{Adv}^{\text{hint-dist}}(\mathcal{D}, s) + 2^{-e_{\text{chl}}} \right) \\ + \frac{2qs + s^2 + 2s + q + 1}{\sqrt{p}}, $$

where $q$ and $s$ are upper bounds on the number of queries that $\mathcal{A}$ makes to RO and OSign, respectively. Whenever $\mathcal{B}$ has advantage $\varepsilon_B \ge 2\log(p)/p$, there is an algorithm $\mathcal{E}$ for $t$-hint-EndRing$_p$ with

$$ t = 2^{102} [\log p]^{13} \cdot s / \varepsilon_B \quad \text{and} \quad \text{Adv}^{\text{hint-EndRing}_p}(\mathcal{E}, t) \ge 1/2, $$

running in expected time $\text{poly}(\log p)/\varepsilon_B$.

*Proof.* The first part is the same as Theorem 3. By the definition of the soundness relation $R_{\text{OneEnd}}$, when $\mathcal{B}$ succeeds, it outputs an endomorphism of degree at most $p^4$. Assume it has advantage $\varepsilon_B \ge 2\log(p)/p$. By Lemma 5.5, there exists an algorithm $\mathcal{E}$ for $t$-hint-EndRing$_p$ with

$$ t = 4 \cdot s \cdot t_{\text{OneEnd}}(\log p, 10[\log p]) / \varepsilon_B $$

hints, having expected time $\text{poly}(\log p) \cdot t = \text{poly}(\log p)/\varepsilon_B$ and advantage at least $1/2$. By Lemma 5.3

$$ \begin{aligned} t_{\text{OneEnd}}(\log p, 10[\log p]) &= 2^{94} \cdot (\log(p) + (10[\log p])/30)^{13} \\ &\le 2^{100}[\log p]^{13}. \end{aligned} $$

$\square$

## 5.4 The quantum reduction from hint-EndRing

We can obtain a much tighter quantum reduction from hint-EndRing$_p$ to hint-OneEnd$_p$. A serious source of complexity in the reduction of [PW24] arises from the possibility that a OneEnd$_p$ oracle might produce endomorphisms with hard-to-factor discriminants. Without this obstacle, several steps of the reduction become redundant. We prove the following theorem in Section 6.2.

**Theorem 5.** Let $\text{OEnd}$ be an oracle for the OneEnd$_p$ problem with outputs of degree at most $d$, and OFactor an oracle for integer factorization. Then there exists a three-stage algorithm for EndRing$_p$ which runs in expected polynomial time in $\log p$ and $\log d$. The first and third stage each call $\text{OEnd}$ in expectation 12 times. The second stage makes a single call to OFactor and runs in polynomial time.

With Shor's algorithm [Sho94], the second stage can be implemented by a quantum reduction. On the other hand, with a classical algorithm for hint-OneEnd$_p$, the first and third stage can remain classical in the reduction to hint-EndRing$_p$. Hence, we can apply our classical reduction separately for the first and third stage. We summarize the quantum reduction in the following theorem.
**Theorem 6.** For any PPT algorithm $\mathcal{A}$ against the EUF-CMA of SIG[$\Sigma_{\text{SQI}}$], there are expected polynomial time algorithms $\mathcal{B}$ and $\mathcal{D}$ with

$$ \mathrm{Adv}_{\mathrm{SIG}[\Sigma_{\mathrm{SQI}}]}^{\mathrm{EUF-CMA}}(\mathcal{A}) \le (q+1) \cdot \left( 2 \cdot \mathrm{Adv}^{\mathrm{hint-OneEnd}_p}(\mathcal{B}, s) + 2 \cdot \mathrm{Adv}^{\mathrm{hint-dist}}(\mathcal{D}, s) + 2^{-e_{\mathrm{chl}}} \right) \\ + \frac{2qs + s^2 + 2s + q + 1}{\sqrt{p}}, $$

where $q$ and $s$ are upper bounds on the number of queries that $\mathcal{A}$ makes to RO and OSign, respectively. Whenever $\mathcal{B}$ has advantage $\varepsilon_B \ge 2\log(p)/p$, there is a quantum algorithm $\mathcal{E}$ for $t$-hint-EndRing$_p$

$$ t = 96s/\varepsilon_B \quad \text{and} \quad \mathrm{Adv}^{\mathrm{hint-EndRing}_p}(\mathcal{E}, t) \ge 1/4, $$

running in expected time $\mathrm{poly}(\log(p))/\varepsilon_B$.

*Proof.* The first part is the same as Theorem 3. Assume $\mathcal{B}$ has advantage $\varepsilon_B \ge 2\log(p)/p$. Following the proof of Lemma 5.5 with $t_{\text{OneEnd}}(\log p, \log d') = 12$, we obtain a classical algorithm $\mathcal{E}_1$ for the first stage. It runs $\mathcal{B}$ at most $4 \cdot 12/\varepsilon_B = 48/\varepsilon_B$ times, and succeeds with probability at least $1/2$. In the same way, we obtain a classical algorithm $\mathcal{E}_3$ for the third stage, with the exact same properties. Let $\mathcal{E}_2$ the quantum algorithm that implements the second stage.

We let $\mathcal{E}$ be the three stage algorithm $(\mathcal{E}_1, \mathcal{E}_2, \mathcal{E}_3)$. If the first stage succeeds, the second stage always succeeds, and the third stage succeeds with probability at least $1/2$. Hence, $\mathcal{E}$ succeeds with probability at least $1/4$. $\square$

Under the assumption that $t$-hint-EndRing$_p$ is a hard problem for quantum algorithms, this is a meaningful result. By using the classical forger, the quantum reduction can efficiently recover a basis for $\mathrm{End}(\mathcal{E})$.

## 5.5 Expected hardness of the $q$-hint-EndRing$_p$ problem

In Theorem 4 and Theorem 6, we proved that SQISIGN is EUF-CMA-secure assuming the hardness of $q$-hint-EndRing$_p$ (Problem 5) and $q$-hint-dist (Problem 3). We also discussed the hardness of $q$-hint-dist in Remark 5.1. Here, we focus on why we expect the $q$-hint-EndRing$_p$ problem to be hard, or —in other words— why we do not expect the hints to make EndRing$_p$ easier.

Consider what the $\mathcal{H}_E^{\text{unif}}$ hint distribution does: it samples a degree $d$ according to a weighted distribution, and then it samples a random isogeny (if we consider the composition $\psi_2 \circ \psi_1$) of degree depending on $d$. In Section 5.6, we show that it is possible to sample from a distribution that is negligibly close to the distribution of $d$, in polynomial time. This means that the only non-trivial information that a hint sampled from $\mathcal{H}_E^{\text{unif}}$ provides to the simulator is the isogeny $\psi_2 \circ \psi_1$ itself.

To sample an isogeny according to $\mathcal{H}_E^{\text{unif}}$, the simulator could try the following:

- Factorize$^{11}$ the degree of $\psi_2 \circ \psi_1$ as $\deg \psi_2 \circ \psi_1 = \prod_i p_i^{e_i}$, and assume that $p_t$ is the largest prime dividing $\psi_2 \circ \psi_1$. The complexity of the factorization is polynomial in $p_t$.

- For every prime $p_i$:

* Sample a random point $K$ of $E[p_i]$, which is defined over an extension field of order $O(p_i)$. The complexity is polynomial in $p_i$.

* Compute an isogeny with kernel $\langle K \rangle$ with V\'eluSqrt formulas [BDFLS20]. The complexity is similarly polynomial in $p_i$.

* This yields an isogeny of degree $p_i$. Repeating the process $e_i$ times and concatenating the outputs, produces an isogeny of degree $p_i^{e_i}$.

- Finally, iterating over all $t$ possible $p_i$ and concatenating the outputs gives an uniformly random isogeny of the desired degree.

The complexity of the sampling procedure is polynomial in $p_t$. Hence, if the degree of $\psi_2 \circ \psi_1$ is sufficiently smooth (i.e., the smoothness bound $p_t$ is in $O(\mathrm{poly}(\lambda))$), the hint does not provide any additional information. Unfortunately, that happens with negligible probability.

In conclusion, the only information the hints provide to the adversary is the efficient representation of some isogenies of non-smooth degree. Informally, we do not expect these to provide any help in solving the EndRing$_p$ problem: non-smooth degree isogenies do not provide any additional information compared to smooth-degree isogenies.

<footnote>$^{11}$ It is possible to sample the degree $d$ together with its factorization [Bac88], but it is still necessary to factor the degree of $\psi_2$.</footnote>
## 5.6 Sampling a random degree

For any elliptic curve $E$ and integer $N$, let $A_N(E)$ be the set of isogenies from $E$ and of degree at most $N$ (up to post-composition with an isomorphism). Let $B_N(E) \subset A_N(E)$ be the subset of isogenies with cyclic kernel. We have

$$A_N(E) = \bigsqcup_{n<N} [n] \circ B_{\lfloor N/n \rfloor}(E).$$

Recall Dedekind's totient is the multiplicative function defined by $\psi(\ell^t) = (\ell+1)\ell^{t-1}$ for all primes $\ell$. For any $n \le N$, the number of isogenies of degree $n$ in $B_N(E)$ is equal to $\psi(n)$. In particular,

$$\#B_N(E) = \sum_{n \le N} \psi(n).$$

The asymptotic behavior of this sum is proven in [OEI25, Apo76, H¨16].

**Lemma 5.6.** $\#B_N(E) = \gamma \cdot N^2 + O(N \ln(N))$, where $\gamma = 15/2\pi^2$.

**Lemma 5.7.** There is an algorithm which, on input $N$, samples a random integer $d$ with the same distribution as $\deg(\varphi)$, where $\varphi$ is uniform in $B_N(E)$

*Proof.* The probability distribution of $\deg(\varphi)$ is $f(n) = \psi(n)/\#B_N(E)$. We have

$$\psi(n) = n \prod_{\substack{\ell \mid n \\ \ell \text{ prime}}} \left(1 + \frac{1}{\ell}\right) = n \prod_{\ell \mid n} \left(1 - \frac{\mu(\ell)}{\ell}\right) = n \sum_{d \mid n} \frac{\mu(d)^2}{d} \le n(\ln(n) + 2).$$

Let $g(n) = 1/N$ be the uniform distribution on $\{1, \dots, N\}$. Let $M = \frac{N^2(\ln(N)+2)}{\#B_N(E)}$. We then have

$$\frac{f(n)}{Mg(n)} = \frac{\psi(n)}{\#B_N(E)} \cdot \frac{N\#B_N(E)}{N^2(\ln(N)+2)} = \frac{\psi(n)}{N(\ln(N)+2)} \le 1.$$

We consider the following rejection sampling algorithm:

1. Sample $n \in \{1, \dots, N\}$ together with its factorization uniformly at random using [Bac88].

2. Compute $\psi(n)$ thanks to the factorization of $n$, and let $p = \frac{\psi(n)}{N(\ln(N)+2)}$.

3. With probability $p$, return $n$. Otherwise, restart.

The algorithm repeats an expected $M$ times, and from Lemma 5.6,

$$M = \frac{N^2(\ln(N) + 2)}{\#B_N(E)} = \frac{N^2(\ln(N) + 2)}{\gamma \cdot N^2 + O(N \log(N))} = O(\log N).$$

□

**Proposition 5.1.** There is an algorithm which, on input $N$, samples a random integer $d$ at statistical distance $O(\frac{(\log N)^2}{N})$ from the distribution of $\deg(\varphi)$, where $\varphi$ is uniform in $A_N(E)$.

*Proof.* Since

$$A_N(E) = \bigsqcup_{n<N} [n] \circ B_{\lfloor N/n \rfloor}(E),$$

and we can sample efficiently in each $B_{\lfloor N/n \rfloor}(E)$ (Lemma 5.7), it only remains to show that we can sample the cyclic part $n$. The distribution of $n$ for a uniformly random element in $A_N(E)$ is

$$f(n) = \frac{\#B_{\lfloor N/n \rfloor}(E)}{\#A_N(E)}.$$

Let $\alpha = \sum_{i=1}^N \frac{1}{i^2}$. Let us prove that the distribution $g(n) = \frac{1}{\alpha n^2}$ on $\{1, \dots, N\}$ is at the claimed statistical distance of $f$.

We have

$$\begin{aligned} \#A_N(E) &= \sum_{n \le N} \#B_{\lfloor N/n \rfloor}(E) = \sum_{n \le N} \left( \gamma \frac{N^2}{n^2} + O\left(\frac{N}{n} \log N\right) \right) \\ &= \alpha \gamma N^2 + O\left(N(\log N)^2\right) \end{aligned}$$
Now, to bound the statistical distance, we compute

$$
\begin{align*}
\#A_N(E)\|f-g\|_1 &= \#A_N(E) \sum_{n \le N} |f(n) - g(n)| \\
&= \sum_{n \le N} \left| \#B_{\lfloor N/n \rfloor}(E) - \frac{1}{\alpha n^2} \#A_N(E) \right| \\
&= \sum_{n \le N} \left| \gamma \frac{N^2}{n^2} + O\left(\frac{N}{n} \log N\right) - \gamma \frac{N^2}{n^2} + O\left(\frac{N}{n^2} (\log N)^2\right) \right| \\
&= O(N(\log N)^2).
\end{align*}
$$

Therefore, $\|f-g\|_1 = O\left(\frac{(\log N)^2}{N}\right)$, as claimed.

Finally, to sample from distribution g, one can sample an integer n for the zeta distribution with parameter 2 (e.g., with inverse transform sampling), and reject if n > N. □

# 6 Analyzing the EndRing to OneEnd reduction

This section collects our analysis on the EndRing$_p$ to OneEnd$_p$ reduction in [PW24]. In Section 6.1, we analyze the expected runtime of their reduction. Then in Section 6.2, we show how to make the reduction a lot tighter, given access to a factoring oracle.

## 6.1 A detailed analysis of the runtime loss

In [PW24], Page and Wesolowski proved that an efficient algorithm for OneEnd$_p$ can be used to construct an efficient algorithm for EndRing$_p$.

**Lemma 6.1 ([PW24]).** Let OEnd be an oracle for OneEnd$_p$, that when queried on a curve $E \in$ Supersingular$_p$ outputs an endomorphism $\alpha \in \mathrm{End}(E) \setminus \mathbb{Z}$ of degree at most $d$. Then there is an algorithm $\mathcal{A}$ that, on input $E \in$ Supersingular$_p$ and given query access to the oracle OEnd, outputs a basis for $\mathrm{End}(E)$ in efficient representation. $\mathcal{A}$ runs in expected polynomial time in $\log p$ and $d$, counting each call to OEnd as a single step.

By inspecting the proof in [PW24], we obtain that the runtime loss is polynomial in $\log p$, but concretely very large.

**Corollary 6.1.** Let definitions be as in Lemma 6.1. The runtime of $\mathcal{A}$ is poly($\log p, \log d$) times the number of calls it makes to OEnd. In expectation, the number of calls is

$$t_{\text{OneEnd}}(\log p, \log d) < 2^{94} \cdot (\log(p) + \log(d)/30)^{13}.$$

*Proof.* The EndRing algorithm $\mathcal{A}$ is described in [PW24, Algorithm 5]. We derive the bound $t$ by inspecting the proof of [PW24, Theorem 7.2]. We do not include their proof in full, but rather give pointers to the relevant parts.

The OneEnd oracle OEnd is called in the two loops of [PW24, Algorithm 5]. In the first loop (lines 3 to 6), each iteration calls OEnd once. Their proof says that the loop terminates after any 3 consecutive iterations with probability at least $1/16$. Thus, the loop succeeds in expectation after at most $3 \cdot 16 = 48$ iterations.

The second loop is more complicated. Each iteration queries OEnd three times. The loop termination condition is that $[\mathrm{End}(E) : R] = 1$. Note that [PW24] starts by bounding the degree of the endomorphisms produced by their algorithm Rich$^{OEnd}_{k_1}(E)$ by $2^{2k_1 \log(d)}$. While correct, the tighter bound $2^{2k_1+\log(d)}$ is satisfied by construction. Using the same techniques as [PW24], but starting from the bound $2^{2k_1+\log(d)}$ instead of $2^{2k_1 \log(d)}$, leads to

$$[\mathrm{End}(E) : R] \le 2^{3(k_1+\log(d)/2)+2}/p,$$

where

$$k_1 = \left\lfloor \frac{\log(12 \cdot 9 \cdot (1 + \sqrt{3}) \cdot \sqrt{p+13})}{\log(\frac{3}{2\sqrt{2}})} \right\rfloor.$$
When $p \ge 3146$,

$$
\begin{align*}
k_1 &\le 1 + \frac{\log(12 \cdot 9 \cdot (1 + \sqrt{3}) \cdot \sqrt{(1 + 1/242)} \cdot \sqrt{p})}{\log(\frac{3}{2\sqrt{2}})} \\
&\le 1 + \frac{\log(296) + \log(\sqrt{p})}{\log(\frac{3}{2\sqrt{2}})} \\
&= 1 + \frac{\log(12 \cdot 9 \cdot (1 + \sqrt{3}) \cdot \sqrt{2})}{\log(\frac{3}{2\sqrt{2}})} + \frac{\log(p)}{2 \log(\frac{3}{2\sqrt{2}})} \\
&\le 98 + \frac{\log(p)}{2 \log(\frac{3}{2\sqrt{2}})} \\
&\le 15 \log(p),
\end{align*}
$$

and

$$
\begin{align*}
\log[\mathrm{End}(E) : R] &\le 3(15 \cdot \log(p) + \log(d)/2) + 2 - \log p \\
&\le 45 \cdot \log(p) + 1.5 \cdot \log(d).
\end{align*}
$$

There are two cases where they say that an iteration of the second loop is a success. In the first case, a new factor of [End(E) : R] is discovered. This can happen at most log([End(E) : R]) - 1 times. In the second case, [End(E) : R] is divided by an integer that is at least 2. Likewise, [End(E) : R] can be divided by an integer that is at least 2 at most log([End(E) : R]) times. Hence, the second loop succeeds after at most 2 log([End(E) : R]) ≤ 90 · log(p) + 3 · log(d) successful iterations.

The probability that an iteration of the second loop succeeds is at least

$$
\frac{1}{2 \cdot 10^6 \cdot (\log N)^{12}}
$$

by [PW24, Proposition 5.11], where N is a variable in the loop that is always a factor of [End(E) : R].
Hence, the number of iterations needed for a success is in expectation at most

$$
\begin{align*}
2 \cdot 10^6 \cdot (\log N)^{12} \\
&\le 2 \cdot 10^6 \cdot (45 \cdot \log(p) + 1.5 \cdot \log(d))^{12} \\
&\le 2^{87} \cdot (\log(p) + \log(d)/30)^{12}.
\end{align*}
$$

In total, the number of calls to OEnd is in expectation at most

$$
\begin{align*}
48 &+ (90 \cdot \log(p) + 3 \cdot \log(d)) \cdot 2^{87} \cdot (\log(p) + \log(d)/30)^{12} \\
&= 48 + 90 (\log(p) + \log(d)/30) \cdot 2^{87} \cdot (\log(p) + \log(d)/30)^{12} \\
&< 2^{94} \cdot (\log(p) + \log(d)/30)^{13}.
\end{align*}
$$

□

6.2 A tighter reduction by factoring

In this section, we prove Theorem 5. Namely, let OEnd be an oracle for the OneEnd_p problem with outputs
of degree at most d, and OFactor an oracle for integer factorization. Then we will show that Algorithm 7
solves the EndRing_p problem in expected polynomial time in log p and log d, with a single call to OFactor
and in expectation at most 24 calls to OEnd.

To prove the theorem, let us start by reworking some of the preliminary results of [PW24]. In the
following, for any ring $R$, we write $M_2(R)$ for the ring of $2 \times 2$ matrices with coefficients in $R$, and $SL_2(R)$
for the multiplicative subgroup of matrices with determinant 1.

**Definition 6.1 ([PW24, Definition 5.9]).** Let $N$ be an integer, and $\varepsilon \ge 0$. Let $M$ be a ring with an isomorphism $\iota : M_2(\mathbb{Z}/N\mathbb{Z}) \to M$. The distribution of a random $\alpha \in M/\iota(\mathbb{Z}/N\mathbb{Z})$ is $\varepsilon$-close to $SL_2(\mathbb{Z}/N\mathbb{Z})$-invariant if, for every $g \in SL_2(\mathbb{Z}/N\mathbb{Z})$, the statistical distance between the distributions of $\alpha$ and $g^{-1}\alpha g$ is at most $\varepsilon$. When the distributions are the same (i.e., $\varepsilon = 0$), we say that the distribution is $SL_2(\mathbb{Z}/N\mathbb{Z})$-invariant.
We first refine a result of [PW24] for the case where $N = \ell$ is a prime.

**Lemma 6.2.** Let $\ell$ be an odd prime. Let $\alpha_1, \alpha_2, \alpha_3 \in M_2(\mathbb{F}_\ell)/\mathbb{F}_\ell$ be independent, non-zero, random elements from an $SL_2(\mathbb{F}_\ell)$-invariant distribution. Then, $(\alpha_1, \alpha_2, \alpha_3)$ is a basis of $M_2(\mathbb{F}_\ell)/\mathbb{F}_\ell$ with probability at least $(1 - \frac{4\ell}{\ell^2-1})^3$.

*Proof.* Note that almost the same statement is proved in [PW24, Lemma 5.3], but with bound 1/8 instead of $(1 - \frac{4\ell}{\ell^2-1})^3$. That bound is obtained as $1/8 \ge (1-p)^3$, where the $p \le 1/2$ is the bound computed in [PW24, Lemma 5.2]. However, this bound on $p$ in [PW24, Lemma 5.2] is obtained by proving that $p \le \frac{4\ell}{\ell^2-1}$, and applying the crude bound $\frac{4\ell}{\ell^2-1} \le 1/2$ (when $\ell \ge 11$). Using the finer bound $p \le \frac{4\ell}{\ell^2-1}$ in place of $p \le 1/2$ in the proof of [PW24, Lemma 5.3] yields the desired result. $\square$

**Definition 6.2 (ℓ-reduced).** For any prime $\ell$ and ring $R$, we say that $\alpha \in R$ is $\ell$-reduced if $\alpha \notin \mathbb{Z} + \ell R$.

**Proposition 6.1.** Let $N > 910$ be a squarefree odd integer such that its prime factors are all larger than some bound $B \ge 10 \cdot \log(N)$. Let $R = \mathbb{Z}/N\mathbb{Z}$, $M = \text{End}(E)/N\text{End}(E) \cong M_2(R)$ and $\bar{M} = M/R$. Consider a distribution $\nu$ on $\bar{M}$ that is $\varepsilon$-close to $SL_2(R)$-invariant, and supported on $\ell$-reduced elements for all prime factors $\ell$ of $N$.

1. Let $\alpha_1, \alpha_2, \alpha_3 \in \bar{M}$ independent random samples with distribution $\nu$. The triple $(\alpha_1, \alpha_2, \alpha_3)$ generates $\bar{M}$ with probability at least $1/2 - 3\varepsilon$.

2. Let $\alpha_1, \alpha_2, \alpha_3 \in \text{End}(E)$ independent random elements such that $\alpha_i \bmod (\mathbb{Z}+N\text{End}(E))$ follows distribution $\nu$. Let $\Lambda$ be the lattice generated by $(1, \alpha_1, \alpha_2, \alpha_3)$. Then, $\text{gcd}(N, [\text{End}(E) : \Lambda]) = 1$ with probability at least $1/2 - 3\varepsilon$.

*Proof.* Item 1, with $\varepsilon = 0$. Let $\ell$ be a prime factor of $N$. By the Chinese Remainder Theorem, conditional on $\alpha \bmod (N/\ell)$, the variable $\alpha \bmod \ell$ is $SL_2(\mathbb{F}_\ell)$-invariant. So $(\alpha_1, \alpha_2, \alpha_3)$ generates $\bar{M}/\ell\bar{M}$ with probability at least $(1 - \frac{4\ell}{\ell^2-1})^3$ (Lemma 6.2), and this bound applies independently on each prime factor of $N$, so $(\alpha_1, \alpha_2, \alpha_3)$ generates $\bar{M}$ with probability at least

$$ \prod_{\ell|N} \left(1 - \frac{4\ell}{\ell^2 - 1}\right)^3 \ge \left(1 - \frac{4B}{B^2 - 1}\right)^{3\omega(N)}. $$

By [Rob83], we have $\omega(N) \le 1.3841 \ln(N)/\ln\ln(N) = (1.3841/\log\ln(N))\log(N)$. We get that if $N \ge e^{2.13841 \cdot x}$, we have $\omega(N) \le \log(N)/x$. If furthermore $B \ge y \log(N) = z$, we get

$$ \prod_{\ell|N} \left(1 - \frac{4\ell}{\ell^2 - 1}\right)^3 \ge \left(1 - \frac{4y \log(N)}{y^2 \log(N)^2 - 1}\right)^{3 \log(N)/x} = f(y \log(N))^{\frac{3}{yx}}, $$

where $f: z \mapsto (1 - \frac{4z}{z^2-1})^z$. This function $f$ is increasing for $z \ge 2 + \sqrt{5}$, so for $z \ge 20$, we have $f(z) \ge f(20) \ge 0.011$.

So if $N \ge e^{2.13841 \cdot x}$, and $B \ge y \log(N) \ge 20$, we obtain

$$ \prod_{\ell|N} \left(1 - \frac{4\ell}{\ell^2 - 1}\right)^3 \ge 0.011 \frac{3}{yx}. $$

When $xy \ge 20$, we have $0.011 \frac{3}{yx} > 0.5$. We obtain the result by setting $x = 2$ and $y = 10$ (in particular, $e^{2.13841 \cdot x} \approx 909.2)$.

**Item 1, with $\varepsilon > 0$.** Applying the triangular inequality, the random triple $(\alpha_1, \alpha_2, \alpha_3)$ is at total variation distance at most $3\varepsilon$ from a triple of $SL_2(\mathbb{Z}/N\mathbb{Z})$-invariant random variables. We conclude from the case $\varepsilon = 0$ and the defining property of the total variation distance.

**Item 2.** This is a consequence of Item 1, [PW24, Proposition 5.6]. $\square$

Given an oracle $\text{OEnd}$ for the $\text{OneEnd}_p$ problem, the article [PW24, Algorithm 1] describes a procedure $\text{Rich}_k^{\text{OEnd}}$ which also solves $\text{OneEnd}_p$, but with the additional guarantee that its output is a random endomorphism, for a distribution which is $\varepsilon$-close to $SL_2$-invariant. Let us recall the formal result below.
**Proposition 6.2.** Let $p > 3$ be a prime, $N$ an odd integer, and $\varepsilon > 0$. Let

$$k = \left[ \frac{\log\left(\frac{1}{\varepsilon} \cdot \frac{1+\sqrt{3}}{4} \cdot N^2 \sqrt{p+13}\right)}{\log\left(\frac{3}{2\sqrt{2}}\right)} \right]$$

Let $OEnd$ be an oracle for the OneEnd$_p$ problem. Let $E/\mathbb{F}_{p^2}$ be a supersingular elliptic curve, and $\alpha$ be a random endomorphism produced by $\text{Rich}_k^{OEnd}(E)$. The distribution of $\alpha \bmod (\mathbb{Z}+N\text{End}(E))$ is $\varepsilon$-close to $\text{SL}_2(\mathbb{Z}/N\mathbb{Z})$-invariant.

*Proof.* This is a reformulation of [PW24, Theorem 4.2]. $\square$

With a procedure to generate endomorphisms which are $\varepsilon$-close to $\text{SL}_2$-invariant (Proposition 6.2), and a proof that such endomorphisms are likely to form (local) bases of the endomorphism ring (Proposition 6.1), we can now prove Theorem 5.

*Proof of Theorem 5.* Let us analyse Algorithm 7. The first loop terminates as soon as $\text{rank}_{\mathbb{Z}}(R) = 4$. By construction of the length of the walk $k_1$, Proposition 6.2 ensures that the conditions of Proposition 6.1 are satisfied for $\varepsilon = 1/12$ and $N = 911$ (the smallest prime larger than 910). In particular, at each iteration of the loop, the elements $(1, \alpha_1, \alpha_2, \alpha_3)$ are linearly independent with probability at least $1/2 - 3\varepsilon = 1/4$. Since each iteration calls $OEnd$ three times, this loop incurs an expected 12 calls to $OEnd$.

The loop of Line 13 ensures that, after that point, the squarefree part $N_R$ of $[\text{End}(E) : R]$ satisfies the condition for $N$ is Proposition 6.1. Now, the choice of $k_2$ following Proposition 6.2 ensures that the random endomorphisms $\alpha_i$ on Line 20 are $\varepsilon$-close to $\text{SL}_2(\mathbb{Z}/N\mathbb{Z})$-invariant (for $\varepsilon = 1/12$), and after the loop of Line 21, they are also reduced at every prime factor of $N_R$. In particular, all the conditions for Proposition 6.1, Item 2, are satisfied. Therefore, $\text{gcd}(N_R, [\text{End}(E) : \Lambda]) = 1$ with probability at least $1/2 - 3\varepsilon = 1/4$, where $\Lambda$ is the lattice generated by $(1, \alpha_1, \alpha_2, \alpha_3)$. When that happens, $\text{gcd}([\text{End}(E) : R], [\text{End}(E) : \Lambda]) = 1$, so $[\text{End}(E) : R + \Lambda] = 1$, and the loop terminates. This proves that the expected number if iterations of the loop of Line 16 is at most 4. Since each iteration calls $OEnd$ three times, this loop incurs an expected 12 additional calls to $OEnd$. $\square$

# 7 Discussion and future work

In this work, we provided a full proof of security of SQISIGN: we gave a reduction of the EUF-CMA security of SQISIGN in the ROM to the hardness of two non-interactive problems, the endomorphism ring problem with hints and the hint indistinguishability problem. Along the way, we developed several technical tools: the framework of Fiat-Shamir with hints, which captures all HD variants of SQIsign and possibly more; a significantly tighter quantum reduction between the Endomorphism Ring problem and the One Endomorphism problem, both with and without hints; several intermediate results, such as a proof EUF-CMA security that does not rely on the hint indistinguishability problem, or a polynomial-time algorithm to sample degrees of uniformly random isogenies of bounded degree. Overall, this work contributes to identify the precise assumptions needed for the security of SQISIGN and provide further evidence of its security.

**Remaining gaps and limitations.** The implementation of SQISIGN, in its round-2 submission to the NIST standardization process, differs slightly from the protocol analyzed so far: for efficiency reasons, the implementation relies on some algorithms that could fail instead of producing the desired output. These failure cases can be split into two categories: those that fail with negligible probability and therefore do not affect security, and those that fail with small but not negligible probability (approximately $2^{-64}$, according to [AAA+25]). This second category of failures has a more significant impact on security: while they are unlikely to be practically exploitable, they introduce a bias in the public keys and signatures that is not captured by our security analysis.

Furthermore, our result in Theorem 6 has a loss factor that is quadratic in the number of signing queries, which is then divided by $\sqrt{p}$. This implies that, for adversaries that make exponentially many signing queries (say, $2^{64}$ queries against a prime $p \approx 2^{256}$, for NIST security level I), the reduction becomes vacuous.
<caption>**Algorithm 7:** Reducing EndRing$_p$ to OneEnd$_p$ with a factoring oracle</caption>

**Input:** A supersingular elliptic curve $E \in \text{Supersingular}_p$, an oracle $\text{OEnd}$ for $\text{OneEnd}_p$, and an oracle $\text{OFactor}$ for factoring integers.
**Output:** The endomorphism ring $\text{End}(E)$.
1: $R := \mathbb{Z}$.
2: $N_1 := 911$.
3: $\varepsilon := 1/12$.
4: $k_1 := \left\lfloor \frac{\log\left(\frac{1+\sqrt{3}}{4} \cdot N_1^2 \sqrt{p+13}\right)}{\log\left(\frac{3}{2\sqrt{2}}\right)} \right\rfloor$.
5: **while** $\text{rank}_Z(R) \neq 4$ **do**
6: &nbsp;&nbsp;&nbsp;&nbsp; $\alpha_j \leftarrow \text{Rich}_{k_1}^{\text{OEnd}}(E)$, for $j \in \{1, 2, 3\}$, three random endomorphisms of $E$. // [PW24, Algorithm 1]
7: &nbsp;&nbsp;&nbsp;&nbsp; $\alpha_j := \text{Reduce}_{N_1}(\alpha_j)$, for $j \in \{1, 2, 3\}$. // [PW24, Algorithm 4]
8: &nbsp;&nbsp;&nbsp;&nbsp; $R := \text{the ring generated by } R, \alpha_1, \alpha_2, \alpha_3$.
9: &nbsp;&nbsp;&nbsp;&nbsp; $R := \text{Saturate}_2(R)$. // [PW24, Algorithm 2]
10: $R := \text{SaturateRam}(R)$. // [PW24, Algorithm 3]
11: $[\text{End}(E) : R] := \sqrt{\text{disc}(R)/p}$.
12: $\prod_{i=1}^t \ell_i^{e_i} := \text{OFactor}([\text{End}(E) : R])$.
13: **for** $i \in \{i \mid \ell_i \le \max(910, 10 \cdot \log([\text{End}(E) : R]))\}$ **do**
14: &nbsp;&nbsp;&nbsp;&nbsp; $R := \text{Saturate}_{\ell_i}(R)$. // [PW24, Algorithm 2]
15: Update $[\text{End}(E) : R] := \sqrt{\text{disc}(R)/p}$ and its factorisation $[\text{End}(E) : R] = \prod_{i=1}^t \ell_i^{e_i}$.
16: **while** $[\text{End}(E) : R] \neq 1$ **do**
17: &nbsp;&nbsp;&nbsp;&nbsp; $N_R := \text{squarefree part of } [\text{End}(E) : R]$.
18: &nbsp;&nbsp;&nbsp;&nbsp; $\varepsilon := 1/12$.
19: &nbsp;&nbsp;&nbsp;&nbsp; $k_2 := \left\lfloor \frac{\log\left(\frac{1+\sqrt{3}}{4} \cdot N_R^2 \sqrt{p+13}\right)}{\log\left(\frac{3}{2\sqrt{2}}\right)} \right\rfloor$.
20: $\alpha_j \leftarrow \text{Rich}_{k_2}^{\text{OEnd}}(E)$, for $j \in \{1, 2, 3\}$, three random endomorphisms of $E$. // [PW24, Algorithm 1]
21: **for** $i \in \{1, 2, \dots, t\}$, $j \in \{1, 2, 3\}$ **do**
22: &nbsp;&nbsp;&nbsp;&nbsp; $\alpha_j := \text{Reduce}_{\ell_i}(\alpha_j)$. // [PW24, Algorithm 4]
23: &nbsp;&nbsp;&nbsp;&nbsp; $R := \text{the ring generated by } R, \alpha_1, \alpha_2, \alpha_3$.
24: Update $[\text{End}(E) : R] := \sqrt{\text{disc}(R)/p}$ and its factorisation $[\text{End}(E) : R] = \prod_{i=1}^t \ell_i^{e_i}$.
25: **return** $R$.

**Takeaways and recommendations.** In light of the previous discussion, we invite the research community to further investigate the algorithmic building blocks of SQISIGN that currently have non-negligible failure probability. We expect that developing better algorithms that maintain the same efficiency while obtaining negligible failure probability is within reach. This would close the remaining gap between the theoretical analysis and the implemented version of SQISIGN.

Similarly, we suggest that future revisions of SQISIGN bring the commitment min-entropy to within $1/p$, rather than $1/\sqrt{p}$. This could be easily achieved at almost no cost by increasing $N_{\text{mix}}$ to $\approx 2^{8\lambda}$, but possibly even more efficient solutions exist. With a factor $1/p$, the statement of Theorem 6 would be meaningful even in the presence of attackers making $2^{64}$ queries or more.

**Future work.** Lastly, we leave the analysis of additional security properties for future work. This includes studying strong unforgeability (which, in its current formulation, SQISIGN is unlikely to achieve), the three BUFF properties [CDF+21], and a security proof in the quantum random oracle model. The current techniques for a QROM reduction do not seem to apply to SQISIGN, so further research is needed.

**Acknowledgments.** We thank the whole SQISIGN team for their help and support throughout this project. This work was funded by ERC grant No. 101116169 (AGATHA CRYPTOY); France 2030 program, grants No. ANR-22-PETQ-0008 (PQ-TLS) and ANR-22-PNCQ-0002 (HQI); Danish Independent Research Council, grant No. 1026-00350B (RENAIS); Swiss SNF Consolidator Grant No. 213766 (CryptonIs).

## References

AAA$^{+}$25. Marius A. Aardal, Gora Adj, Diego F. Aranha, Andrea Basso, Isaac Andrés Canales Martínez, Jorge Chávez-Saab, Maria Corte-Real Santos, Pierrick Dartois, Luca De Feo, Max Duparc, Jonathan Komada
Eriksen, Tako Boris Fouotsa, Décio Luiz Gazzoni Filho, Basil Hess, David Kohel, Antonin Leroux, Patrick Longa, Luciano Maino, Michael Meyer, Kohei Nakagawa, Hiroshi Onuki, Lorenz Panny, Sikhar Patranabis, Christophe Petit, Giacomo Pope, Krijn Reijnders, Damien Robert, Francisco Rodríguez Henríquez, Sina Schaeffler, and Benjamin Wesolowski. SQIsign - Version 2.0. Technical report, National Institute of Standards and Technology, 2025. available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-2-additional-signatures.

AABN02. Michel Abdalla, Jee Hea An, Mihir Bellare, and Chanathip Namprempre. From identification to signatures via the Fiat-Shamir transform: Minimizing assumptions for security and forward-security. In Lars R. Knudsen, editor, *EUROCRYPT 2002*, volume 2332 of LNCS, pages 418–433. Springer, Berlin, Heidelberg, April / May 2002. doi:10.1007/3-540-46035-7_28.

ACK21. Thomas Attema, Ronald Cramer, and Lisa Kohl. A compressed Σ-protocol theory for lattices. In Tal Malkin and Chris Peikert, editors, *CRYPTO 2021, Part II*, volume 12826 of LNCS, pages 549–579, Virtual Event, August 2021. Springer, Cham. doi:10.1007/978-3-030-84245-1_19.

Apo76. Tom M. Apostol. *Introduction to Analytic Number Theory*. Springer New York, 1976. doi:10.1007/978-1-4757-5579-4.

Bac88. Eric Bach. How to generate factored random numbers. *SIAM Journal on Computing*, 17(2):179–193, 1988. doi:10.1137/0217012.

BBSS18. Matilda Backendal, Mihir Bellare, Jessica Sorrell, and Jiahao Sun. The Fiat-Shamir zoo: Relating the security of different signature variants. In *NordSec*, volume 11252 of *Lecture Notes in Computer Science*, pages 154–170. Springer, 2018.

BCC<sup>+</sup>23. Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo, Tako Boris Fouotsa, Guido Maria Lido, Travis Morrison, Lorenz Panny, Sikhar Patranabis, and Benjamin Wesolowski. Supersingular curves you can trust. In Carmit Hazay and Martijn Stam, editors, *EUROCRYPT 2023, Part II*, volume 14005 of LNCS, pages 405–437. Springer, Cham, April 2023. doi:10.1007/978-3-031-30617-4_14.

BDD<sup>+</sup>24. Andrea Basso, Pierrick Dartois, Luca De Feo, Antonin Leroux, Luciano Maino, Giacomo Pope, Damien Robert, and Benjamin Wesolowski. SQIsign2D-west - the fast, the small, and the safer. In Kai-Min Chung and Yu Sasaki, editors, *ASIACRYPT 2024, Part III*, volume 15486 of LNCS, pages 339–370. Springer, Singapore, December 2024. doi:10.1007/978-981-96-0891-1_11.

BDFLS20. Daniel J Bernstein, Luca De Feo, Antonin Leroux, and Benjamin Smith. Faster computation of isogenies of large prime degree. *Open Book Series*, 4(1):39–55, 2020. doi:10.2140/obs.2020.4.39.

BLL25. Giacomo Borin, Yi-Fu Lai, and Antonin Leroux. Erebor and Durian: full anonymous ring signatures from quaternions and isogenies. *IACR Communications in Cryptology*, 1(4), 2025. doi:10.62056/ava3zivrzn.

CDF<sup>+</sup>21. Cas Cremers, Samed Düzlü, Rune Fiedler, Marc Fischlin, and Christian Janson. BUFFing signature schemes beyond unforgeability and the case of post-quantum signatures. In *2021 IEEE Symposium on Security and Privacy*, pages 1696–1714. IEEE Computer Society Press, May 2021. doi:10.1109/SP40001.2021.00093.

CSD<sup>+</sup>23. Jorge Chavez-Saab, Maria Corte-Real Santos, Luca De Feo, Jonathan Komada Eriksen, Basil Hess, David Kohel, Antonin Leroux, Patrick Longa, Michael Meyer, Lorenz Panny, Sikhar Patranabis, Christophe Petit, Francisco Rodríguez Henríquez, Sina Schaeffler, and Benjamin Wesolowski. SQIsign. Technical report, National Institute of Standards and Technology, 2023. available at https://csrc.nist.gov/Projects/pqc-dig-sig/round-1-additional-signatures.

DF24. Max Duparc and Tako Boris Fouotsa. SQIPrime: A dimension 2 variant of SQISignHD with non-smooth challenge isogenies. In Kai-Min Chung and Yu Sasaki, editors, *ASIACRYPT 2024, Part III*, volume 15486 of LNCS, pages 396–429. Springer, Singapore, December 2024. doi:10.1007/978-981-96-0891-1_13.

DKL<sup>+</sup>20. Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski. SQISign: Compact post-quantum signatures from quaternions and isogenies. In Shiho Moriai and Huaxiong Wang, editors, *ASIACRYPT 2020, Part I*, volume 12491 of LNCS, pages 64–93. Springer, Cham, December 2020. doi:10.1007/978-3-030-64837-4_3.

DLLW23. Luca De Feo, Antonin Leroux, Patrick Longa, and Benjamin Wesolowski. New algorithms for the deuring correspondence - towards practical and secure SQISign signatures. In Carmit Hazay and Martijn Stam, editors, *EUROCRYPT 2023, Part V*, volume 14008 of LNCS, pages 659–690. Springer, Cham, April 2023. doi:10.1007/978-3-031-30589-4_23.

DLRW24. Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin Wesolowski. SQISignHD: New dimensions in cryptography. In Marc Joye and Gregor Leander, editors, *EUROCRYPT 2024, Part I*, volume 14651 of LNCS, pages 3–32. Springer, Cham, May 2024. doi:10.1007/978-3-031-58716-0_1.

EHL<sup>+</sup>18. Kirsten Eisenträger, Sean Hallgren, Kristin E. Lauter, Travis Morrison, and Christophe Petit. Supersingular isogeny graphs and endomorphism rings: Reductions and solutions. In Jesper Buus Nielsen and Vincent Rijmen, editors, *EUROCRYPT 2018, Part III*, volume 10822 of LNCS, pages 329–368. Springer, Cham, April / May 2018. doi:10.1007/978-3-319-78372-7_11.

EHL<sup>+</sup>20. Kirsten Eisenträger, Sean Hallgren, Chris Leonardi, Travis Morrison, and Jennifer Park. Computing endomorphism rings of supersingular elliptic curves and connections to path-finding in isogeny graphs. *Open Book Series*, 4(1):215–232, 2020. doi:10.2140/obs.2020.4.215.
Hİ6. Werner Hürlimann. Dedekind's arithmetic function and primitive four squares counting functions. *Journal of Algebra, Number Theory: Advances and Applications*, 14(2):73-88, February 2016. doi: 10.18642/jantaa_7100121599.

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

KV10. Markus Kirschmer and John Voight. Algorithmic enumeration of ideal classes for quaternion orders. *SIAM Journal on Computing*, 39(5):1714-1747, 2010.

Ler22. Antonin Leroux. *Quaternion algebras and isogeny-based cryptography. (Algèbres de quaternions et cryptographie à base d'isogénies)*. PhD thesis, Polytechnic Institute of Paris, France, 2022.

McM14. Ken McMurdy. Explicit representation of the endomorphism rings of supersingular elliptic curves. https://pages.ramapo.edu/~kmcmurdy/research/McMurdy-ssEndoRings.pdf, 2014. Preprint.

NOC+24. Kohei Nakagawa, Hiroshi Onuki, Wouter Castryck, Mingjie Chen, Riccardo Invernizzi, Gioella Lorenzon, and Frederik Vercauteren. SQIsign2D-east: A new signature scheme using 2-dimensional isogenies. In Kai-Min Chung and Yu Sasaki, editors, *ASIACRYPT 2024, Part III*, volume 15486 of LNCS, pages 272-303. Springer, Singapore, December 2024. doi:10.1007/978-981-96-0891-1_9.

OEI25. OEIS Foundation Inc. Entry A173290 in The On-Line Encyclopedia of Integer Sequences, 2025. URL: https://oeis.org/A173290.

PS96. David Pointcheval and Jacques Stern. Security proofs for signature schemes. In Ueli M. Maurer, editor, *EUROCRYPT'96*, volume 1070 of LNCS, pages 387-398. Springer, Berlin, Heidelberg, May 1996. doi:10.1007/3-540-68339-9_33.

PW24. Aurel Page and Benjamin Wesolowski. The supersingular endomorphism ring and one endomorphism problems are equivalent. In Marc Joye and Gregor Leander, editors, *EUROCRYPT 2024, Part VI*, volume 14656 of LNCS, pages 388-417. Springer, Cham, May 2024. doi:10.1007/978-3-031-58751-1_14.

Rob83. Guy Robin. Estimation de la fonction de Tchebychef $\theta$ sur le k-ième nombre premier et grandes valeurs de la fonction $\omega(n)$ nombre de diviseurs premiers de n. *Acta Arithmetica*, 42(4):367-389, 1983.

Rob22. Damien Robert. Evaluating isogenies in polylogarithmic time. Cryptology ePrint Archive, Report 2022/1068, 2022. URL: https://eprint.iacr.org/2022/1068.

Rob24. Damien Robert. On the efficient representation of isogenies (a survey). Cryptology ePrint Archive, Report 2024/1071, 2024. URL: https://eprint.iacr.org/2024/1071.

Sho94. P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In *Proceedings 35th Annual Symposium on Foundations of Computer Science*, pages 124-134, 1994. doi:10.1109/SFCS.1994.365700.

Sil86. Joseph H. Silverman. *The Arithmetic of Elliptic curves*, volume 106 of *Graduate Texts in Mathematics*. Springer, 1986.

Wes22. Benjamin Wesolowski. The supersingular isogeny path and endomorphism ring problems are equivalent. In *62nd FOCS*, pages 1100-1111. IEEE Computer Society Press, February 2022. doi:10.1109/FOCS52979.2021.00109.