Supersingular Curves You Can Trust

Abstract

Generating a supersingular elliptic curve such that nobody knows its endomorphism ring is a notoriously hard task, despite several isogeny-based protocols relying on such an object. A trusted setup is often proposed as a workaround, but several aspects remain unclear. In this work, we develop the tools necessary to practically run such a distributed trusted-setup ceremony.

Our key contribution is the first statistically zero-knowledge proof of isogeny knowledge that is compatible with any base field. To prove statistical ZK, we introduce isogeny graphs with Borel level structure and prove they have the Ramanujan property. Then, we analyze the security of a distributed trusted-setup protocol based on our ZK proof in the simplified universal composability framework. Lastly, we develop an optimized implementation of the ZK proof, and we propose a strategy to concretely deploy the trusted-setup protocol.

Author list in alphabetical order; see https://ams.org/profession/leaders/CultureStatement04.pdf. This work began at the Banff International Research Station workshop “Supersingular Isogeny Graphs in Cryptography” (21w5229). This research was funded in part by the MIUR Excellence Department Project MatMod@TOV awarded to the Department of Mathematics, University of Rome Tor Vergata, the Commonwealth Cyber Initiative, the Academia Sinica Investigator Award AS-IA-109-M01, the Agence Nationale de la Recherche under grant ANR MELODIA (ANR-20-CE40-0013), and the France 2030 program under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

1 Introduction

Be it foundationally or for efficiency, most of isogeny-based cryptography is built upon supersingular elliptic curves [15, 17, 22, 27, 28, 37, 42]. At the heart of it, lies the supersingular isogeny graph: a graph whose vertices represent supersingular elliptic curves (up to isomorphism) and whose edges represent isogenies (up to isomorphism) of some fixed small prime degree between them. A foundational hard problem for isogeny-based cryptography is then: given two supersingular elliptic curves, find a path in the supersingular isogeny graph connecting them.

An endomorphism is an isogeny from a curve E to itself, and their collection forms the endomorphism ring $\textrm{End}(E)$. In recent years, the connection between finding isogeny paths and computing endomorphism rings of supersingular curves has become increasingly important [32, 35, 58, 59]. It is now established that, assuming the generalized Riemann hypothesis, there exists probabilistic polynomial time algorithms for these two problems:

• 1. Given supersingular elliptic curves $E_0,E_1$ along with descriptions of their endomorphism rings, compute an isogeny path $E_0\rightarrow E_1$;

• 2. Given a supersingular elliptic curve $E_0$ along with a description of its endomorphism ring, and given an isogeny path $E_0\rightarrow E_1$, compute a description of the endomorphism ring of $E_1$.

These algorithms—and variants—have successfully been used both constructively [22, 27, 37] and for cryptanalysis [28, 32, 34, 35, 49, 51].

Without the additional information above, computing the endomorphism ring of an arbitrary supersingular curve remains a hard problem, both for classical and quantum computers. Given the importance of this problem, it is natural to ask whether it is possible to sample supersingular curves such that computing their endomorphism ring is a hard problem, crucially, even for the party who does the sampling. We shall call these objects Supersingular Elliptic Curves of Unknown Endomorphism Ring, or Secuer¹ in short.

Applications. Generating a Secuer has turned out to be a delicate task, and no such curve has ever been generated. Yet, several isogeny-based schemes can only be instantiated with a Secuer. This is the case, for example, of isogeny-based verifiable delay functions [28] and delay encryption [12]. The so-called CGL hash function based on supersingular curves [17] has been shown to be broken by the knowledge of the endomorphism ring [32], and one possible fix is to instantiate it with a Secuer. Other protocols which require a Secuer include hash proof systems, dual mode PKE [1], oblivious transfer [44], OPRF [4], and commitment schemes [54].

Contributions. We analyze and put into practice a protocol for distributed generation of Secuers. Our main technical contribution is a key ingredient of the protocol: a new proof of isogeny knowledge (two curves $E_0$ and $E_1$ being public, a party wishes to prove that they know an isogeny $E_0 \rightarrow E_1$ without revealing it). Our proof is similar to the SIDH proof of knowledge [23, 25], but extends it in a way that makes it compatible with any base field, any walk length, and has provable statistical zero-knowledge (unlike any previous proof of isogeny knowledge). In particular, its statistical security makes it fully immune to the recent attacks [14, 46, 52].

To prove statistical security, we analyze supersingular $\ell$-isogeny graphs with level structure, a generalization of isogeny graphs that was recently considered in [3, 27]. We prove that these graphs, like classic isogeny graphs, possesses the Ramanujan property, a fact that is of independent interest. Using the property, we analyze the mixing behavior of random walks, which lets us give very precise parameters to instantiate the proof of knowledge at any given security level.

To show that the resulting protocol is practical, we implement it on top of Microsoft’s SIDH library² and benchmark it for each of the standard SIKE primes [41]. We must stress that SIDH-style primes are possibly the most favorable to our protocol, in terms of practical efficiency.

Finally, we sketch a roadmap to run the distributed generation protocol for the SIKE primes in a real world setting with hundreds of participants.

Limitations. We must point out that our new proof of knowledge is not well adapted to a secure distributed generation protocol in the case where one wants to generate a Secuer defined over a prime field $\mathbb {F}_p$, instead of $\mathbb {F}_{p^2}$, such as in [1, 44]. Different proofs of knowledge [8, 24] could be plugged in the distributed protocol for the $\mathbb {F}_p$ case, however their practical usability is dubious.

1.1 Generating a Secuer

The cornerstone of isogeny-based cryptography is the endomorphism ring problem: if it could be solved efficiently, then all of supersingular isogeny-based cryptography would be broken [32, 35, 58], leaving only ordinary isogeny-based cryptography [21, 26, 55] standing.

Definition 1

(Endomorphism ring problem). Given a supersingular curve $E/\mathbb {F}_{p^2}$, compute its endomorphism ring $\textrm{End}(E)$. That is, compute an integral basis for a maximal order $\mathcal {O}$ of the quaternion algebra ramified at p and $\infty$, as well as an explicit isomorphism $\mathcal {O}\simeq \textrm{End}(E)$.

For any p, there exists a polynomially sized subset of all supersingular curves for which the endomorphism ring can be computed in polynomial time [16, 45], but the problem is believed to be exponentially hard in general, even for quantum computers. A related problem, commonly encountered in isogeny protocols, is finding paths in supersingular isogeny graphs.

Definition 2

(Isogeny $\ell$-walk problem). Given two supersingular curves $E,E'/\mathbb {F}_{p^2}$ of the same order, and a small prime $\ell$, find a walk from E to $E'$ in the $\ell$-isogeny graph.

Such walks are always guaranteed to exist, as soon as they have length in $O(\log (p))$ [17, 43, 47, 50].

The two problems are known to be polynomial time equivalent, assuming GRH [59]. Indeed, given $\textrm{End}(E)$ and $\textrm{End}(E')$, it is easy to compute a path $E\rightarrow E'$. Reciprocally, given $\textrm{End}(E)$ and a path $E\rightarrow E'$, it is easy to compute $\textrm{End}(E')$; and, by random self-reducibility, we can always assume that one of $\textrm{End}(E)$ or $\textrm{End}(E')$ is known.

Our goal is to generate a Secuer: a curve for which the endomorphism ring problem is hard, and consequently one for which it is hard to find a path to any other given curve.

What Does Not Work. The supersingular elliptic curves over a finite field k of characteristic p are those such that $\# E(k) = 1 \bmod p$. Any supersingular curve is isomorphic to one defined over a field with $p^2$ elements, thus, without loss of generality, we are only interested in supersingular curves defined over $\mathbb {F}_{p^2}$. Among the $p^2$ isomorphism classes of elliptic curves over $\mathbb {F}_{p^2}$, only $\approx p/12$ of them correspond to supersingular curves.

The standard way to construct supersingular curves is to start from a curve with complex multiplication over a number field, and then reduce modulo p. Complex multiplication elliptic curves have supersingular reduction modulo $50\%$ of the primes, thus this technique quickly produces supersingular curves for almost all primes. For example, the curve $y^2 = x^3 + x$, which has complex multiplication by the ring $\mathbb {Z}[i]$ of Gaussian integers, is supersingular modulo p if and only if $p = 3 \bmod 4$. Most isogeny-based protocols are instantiated using precisely this curve as starting point. These curves are not Secuers, though, because from the information on complex multiplication one can compute the endomorphism ring in polynomial time [16, 45].

As p grows, the curves with computable³ complex multiplication form only a negligible fraction of all supersingular curves in characteristic p, so we may still hope to get a Secuer if we can sample a supersingular curve at random from the whole set. The natural way to do so is to start from a well known supersingular curve, e.g. $E_0:y^2 = x^3 + x$, take a random walk $E_0\rightarrow E_1$ in the isogeny graph, and then select the arrival curve $E_1$. But, by virtue of the reductions mentioned above, any $E_1$ constructed this way cannot be called a Secuer either.

Several other techniques have been considered for generating Secuers, however all attempts have failed so far [10, 48].

Distributed Generation of Secuers. An obvious solution that has been proposed for schemes that need a Secuer is to rely on a trusted party to start from a special curve $E_0$ and to perform an isogeny walk to a random curve $E_1$. Although $E_1$ is not a Secuer, if the trusted party keeps the walk $E_0\rightarrow E_1$ secret, no one else will be able to compute $\textrm{End}(E_1)$.

Of course, relying on a trusted third party is undesirable. The natural next step is to turn this idea into a distributed protocol with t parties generating a sequence of walks $E_0 \rightarrow E_1\rightarrow E_2 \rightarrow \cdots \rightarrow E_t$. First, suppose that the sequence was generated honestly: the i-th party indeed generated a random isogeny from the previous curve $E_{i-1}$ to a new curve $E_{i}$. Then it is sufficient for a single party to honestly discard their isogeny, for no path to be known by anyone from $E_0$ to $E_t$. Then, $E_t$ is a Secuer for all practical purposes.

To make this protocol secure against active adversaries, an additional ingredient is needed. As it is, the last party could cheat as follows: instead of generating an isogeny $E_{t-1} \rightarrow E_t$, they could reboot the chain by generating an isogeny $E_0 \rightarrow E_t$, and submitting that instead. They could then compute the endomorphism ring of $E_t$. If only the curves $E_i$ along the path are revealed, it is impossible to detect such misbehavior. To prevent this, each party needs to prove that they know their component of the walk: an isogeny $E_{i-1} \rightarrow E_i$ (as first discussed in [12]). To this end, we develop a statistically zero-knowledge proof of isogeny knowledge.

1.2 Proof of Isogeny Knowledge

State-of-the-Art. Protocols to prove knowledge of an isogeny have been mostly studied for signatures. The first such protocol is the SIDH-based proof of knowledge of [25]. Its security proof was found to be flawed and then fixed, either by changing the assumptions [38] or by changing the protocol [23]. However, these protocols are now fully broken by the recent polynomial time attacks on SIDH-like protocols [14, 46, 52]. These attacks can be avoided by relying on ternary challenges [9, 23].

CSIDH-based proofs of knowledge were first introduced in [24], and then improved in [8] for the parameter set CSIDH-512. These are limited to isogeny walks between curves defined over a prime field $\mathbb {F}_p$, and tend to be prohibitively slow outside of the specially prepared parameter set CSIDH-512.

Finally, De Feo and Burdges propose an efficient proof of knowledge tailored to finite fields used in delay protocols [12]. However the soundness of this protocol is only conjectural, and, being based on pairing assumptions, is broken by quantum computers.

In summary, no general purpose, quantum-safe, zero-knowledge proof of knowledge of an isogeny walk between supersingular curves defined over $\mathbb {F}_{p^2}$ exists in previous literature.

Overview of Our Method. Our main technical contribution is a new proof of knowledge that ticks all the boxes above: it is compatible with any base field, any walk length, it has provable statistical zero-knowledge, and is practical—as illustrated by our implementation. The idea is the following. Two elliptic curves $E_0$ and $E_1$ being public, some party, the prover, wishes to convince the verifier that they know an isogeny $\phi : E_0 \rightarrow E_1$ (of degree, say, $2^m$, large enough so it is guaranteed that such an isogeny exists). First, the prover secretly generates a random isogeny walk $\psi : E_0 \rightarrow E_2$ of degree, say, $3^n$. Defining $\phi '$ with kernel $\psi (\ker (\phi ))$, and $\psi '$ with kernel $\phi (\ker (\psi ))$, one obtains the following commutative diagram, known as “SIDH square” in the literature:

(1)

Now, the prover publishes a hiding and binding commitment to $E_2$ and $E_3$. The verifier may now ask the prover to reveal one of the three isogenies $\psi$, $\phi '$, or $\psi '$, by drawing a random $\textsf{chall}\in \{-1,0,1\}$ (and open the commitment(s) corresponding to the relevant endpoints). For the prover to succeed with overwhelming probability, they must know all three answers, so they must know an isogeny from $E_0$ to $E_1$: the composition $\psi ' \circ \phi ' \circ \psi : E_0 \rightarrow E_1$. This is the idea behind the soundness of the protocol.

So far, this protocol is more or less folklore and superficially similar to [23, §5.3]. But does it leak any information? Whereas previous protocols only achieved computational zero-knowledge, we provide a tweak that achieves statistical zero-knowledge: there is a simulator producing transcripts that are statistically indistinguishable from a valid run of the protocol. The simulator starts by choosing the challenge $\textsf{chall}$ first, then it generates an isogeny that is statistically indistinguishable from either $\psi$, $\phi '$, or $\psi '$, according to the value of $\textsf{chall}$. Simulating $\psi$ (or $\psi '$) is straightforward: generate a random isogeny walk $\tilde{\psi }$ (or $\tilde{\psi }'$) of degree $3^n$ from $E_0$ (or from $E_1$). The isogeny $\tilde{\psi }$ is a perfect simulation of $\psi$. Simulating $\phi '$ seems trickier. An obvious approach is to first generate a random $E_2$ (for instance, by simulating $\psi : E_0 \rightarrow E_2$), then generate a random walk isogeny $\tilde{\phi }' : E_2 \rightarrow E_3$ of degree $2^m$. While this may seem too naive, we in fact prove that when $\deg (\psi )$ is large enough, the distribution of $\tilde{\phi }'$ is statistically close to a honestly generated $\phi '$. The key is a proof that the isogeny graph enriched with so-called level structure has rapid mixing properties.

Isogeny Graphs with Level Structure. The isogeny $\phi '$ is essentially characterized by its source, $E_2$, and its kernel $\ker (\phi ')$, a (cyclic) subgroup of order $\deg (\phi ')$. We are thus interested in random variables of the form (E, C), where E is an elliptic curve, and C a cyclic subgroup of E, of order some integer d (not divisible by p). We call such a pair (E, C) a level d Borel structure.

The simulator proposed above essentially generates $\tilde{\phi }'$ as a uniformly random level $2^m$ Borel structure $(E,C) = (E_2,\ker (\tilde{\phi }'))$. On the other hand, a honestly generated $\phi '$ corresponds to a pair $(\psi (E_0), \psi (\ker \phi ))$, and $\psi$ is a uniformly random isogeny walk of degree $3^n$. This process corresponds to a random walk of length n in the 3-isogeny graph with level $2^m$ structure, with starting point $(E_0, \ker \phi )$. We prove the following result.

Theorem 3

Let $G = G(p,d,\ell )$ the supersingular $\ell$-isogeny graph with level d Borel structure. The adjacency matrix A of G is diagonalizable, with real eigenvalues, and has the Ramanujan property, i.e. the integer $\ell +1$ is an eigenvalue of A of multiplicity one, while all the other eigenvalues are contained in the Hasse interval $[-2\sqrt{\ell },2\sqrt{\ell }]$.

As a consequence, we prove that random walks quickly converge to the stationary distribution, so $\tilde{\phi }'$ and $\phi '$ are statistically indistinguishable.

Paper outline. We start in Sect. 2 with a few technical preliminaries on elliptic curves, isogenies, and proofs of knowledge. Section 3 is dedicated to the proof of Theorem 3. This section can be read independently from the rest. The reader only interested in applications, and willing to accept Theorem 3 (and its consequence on non-backtracking random walks, Theorem 11, page 14), can safely skip to the following section. This theoretical tool at hand, we then describe and analyse the new proof of isogeny knowledge in Sect. 4. We describe the protocol to generate a $\textsc {Secuer}$ in Sect. 5, and prove its security. Finally, we report on our implementation in Sect. 6.

2 Preliminaries

2.1 General Notations

We write $x\leftarrow \chi$ to represent that an element x is sampled at random from a set/distribution $\mathcal {X}$. The output x of a deterministic algorithm $\mathcal {A}$ is denoted by $x=\mathcal {A}$ and the output $x'$ of a randomized algorithm $\mathcal {A}'$ is denoted by $x'\leftarrow \mathcal {A}'$. For $a,b\in \mathbb {N}$ such that $a,b\ge 1$, we denote by [a, b] (resp. [a]) the set of integers lying between a and b, both inclusive (the set of integers lying between 1 and a, both inclusive). We refer to $\lambda \in \mathbb {N}$ as the security parameter, and denote by $\textsf{poly}(\lambda )$, $\textsf{polylog}(\lambda )$ and $\textsf{negl}(\lambda )$ any generic (unspecified) polynomial, poly-logarithmic or negligible function in $\lambda$, respectively.⁴ For probability distributions $\mathcal {X}$ and $\mathcal {Y}$, we write $\mathcal {X}\approx \mathcal {Y}$ if the statistical distance between $\mathcal {X}$ and $\mathcal {Y}$ is negligible.

2.2 Elliptic Curves, Isogenies and “SIDH Squares”

We assume the reader has some familiarity with elliptic curves and isogenies. Throughout the text, p shall be a prime number, $\mathbb {F}_p$ and $\mathbb {F}_{p^2}$ the finite fields with p and $p^2$ elements respectively. Unless specified otherwise, all elliptic curves will be supersingular and defined over $\mathbb {F}_{p^2}$. We write E[d] for the subgroup of d-torsion points of E over the algebraic closure.

Unless specified otherwise, all isogenies shall be separable. If G is a finite subgroup of E, we write $\phi :E\rightarrow E/G$ for the unique (up to post-composition with an isomorphism of E/G) separable isogeny with kernel G. If G is cyclic, we say the isogeny is cyclic. We denote by $\hat{\phi }$ the dual isogeny to $\phi$. Separable isogenies and their duals can be computed and/or evaluated in time $\textsf{poly}(\#G)$ using any of the algorithms in [7, 56], however in some cases, e.g. when $\#G$ only contains small factors, this cost may be lowered to as little as $\textsf{polylog}(\#G)$.

Given separable isogenies $\phi :E_0\rightarrow E_1$ and $\psi :E_0\rightarrow E_2$ of coprime degrees, we obtain the commutative diagram in (1) by defining $\phi ':E_2\rightarrow E_2/\psi (\ker (\phi ))$ and $\psi ':E_1\rightarrow E_1/\phi (\ker (\psi ))$. Again, $E_3$ is only defined up to isomorphism. In categorical parlance, this is the pushout of $\phi$ and $\psi$, but cryptographers may know it better through its use in the SIDH key exchange. We refer to these commutative diagrams as SIDH squares or SIDH ladders (see Sect. 4.2 for more details).

2.3 Proofs of Knowledge

Our main technical contribution is a $\varSigma$-protocol to prove knowledge of an isogeny of given degree between two supersingular elliptic curves. Recall a $\varSigma$-protocol for an NP-language $\mathcal {L}$ is a public-coin three-move interactive proof system consisting of two parties: a verifier and a prover. The prover is given a witness w for an element $x\in \mathcal {L}$, his goal is to convince the verifier that he knows w.

Definition 4

($\varSigma$-protocol). A $\varSigma$-protocol $\varPi _{\varSigma }$ for a family of relations $\{ \mathcal {R} \}_\lambda$ parameterized by security parameter $\lambda$ consists of PPT algorithms $(\textsf{P}_1, \textsf{P}_2, \textsf{V})$ where $\textsf{V}$ is deterministic and we assume $\textsf{P}_1, \textsf{P}_2$ share states. The protocol proceeds as follows:

• 1. The prover, on input $(x,w) \in \mathcal {R}$, returns a commitment $\textsf{com}\leftarrow \textsf{P}_1(x,w)$ which is sent to the verifier.

• 2. The verifier flips $\lambda$ coins and sends the result to the prover.

• 3. Call $\textsf{chall}$ the message received from the verifier, the prover runs $\textsf{resp}\leftarrow \textsf{P}_2(\textsf{chall})$ and returns $\textsf{resp}$ to the verifier.

• 4. The verifier runs $V(x, \textsf{com}, \textsf{chall}, \textsf{resp})$ and outputs a bit.

A transcript $(\textsf{com}, \textsf{chall}, \textsf{resp})$ is said to be valid, or accepting, if $V(x, \textsf{com},\textsf{chall},\textsf{resp})$ outputs 1. The main requirements of a $\varSigma$-protocol are:

Correctness: If the prover knows $(x,w) \in \mathcal {R}$ and behaves honestly, then the verifier outputs 1.

$\pmb {n}$-special soundness: There exists a polynomial-time extraction algorithm that, given a statement x and n valid transcripts

$$ (\textsf{com},\textsf{chall}_1,\textsf{resp}_1), \dots , (\textsf{com},\textsf{chall}_n,\textsf{resp}_n) $$

where $\textsf{chall}_i \ne \textsf{chall}_j$ for all $1 \le i < j \le n$, outputs a witness w such that $(x,w) \in \mathcal {R}$ with probability at least $1 - \varepsilon$ for soundness error $\varepsilon$.

A special sound $\varSigma$-protocol for $\mathcal {R}$ is also called a Proof of Knowledge (PoK) for $\mathcal {R}$. Our $\varSigma$-protocol will have the peculiar property that the relation used to prove correctness turns out to be a subset of the one used to prove soundness. This will require extra care when proving security in Sect. 5.

Special Honest Verifier Zero-Knowledge (SHVZK): There exists a polynomial-time simulator that, given a statement x and a challenge $\textsf{chall}$, outputs a valid transcript $(\textsf{com},\textsf{chall},\textsf{resp})$ that is indistinguishable from a real transcript.

Definition 5

A $\varSigma$-protocol $(\textsf{P}_1,\textsf{P}_2,\textsf{V})$ is computationally special honest verifier zero-knowledge if there exists a probabilistic polynomial time simulator $\textsf{Sim}$ such that for all probabilistic polynomial time stateful adversaries $\mathcal {A}$

$$\begin{aligned} \Pr \left[ \mathcal {A}(\textsf{com},\textsf{chall},\textsf{resp}) = 1 \ \left| \ \begin{array}{l} (x,w,\textsf{chall}) \leftarrow \mathcal {A}(1^\lambda );\\ \textsf{com}\leftarrow \textsf{P}_1(x,w); \\ \textsf{resp}= \textsf{P}_2(\textsf{chall}) \end{array}\right. \right] \\ \approx \Pr \left[ \mathcal {A}(\textsf{com},\textsf{chall},\textsf{resp}) = 1 \ \left| \ \begin{array}{l} (x,w,\textsf{chall}) \leftarrow \mathcal {A}(1^\lambda );\\ (\textsf{com},\textsf{resp}) \leftarrow \textsf{Sim}(x,\textsf{chall}) \end{array}\right. \right] . \end{aligned}$$

If the above indistinguishability holds statistically against all unbounded adversaries $\mathcal {A}$, the protocol is said to be statistically SHVZK.

2.4 Non-Interactive Zero-Knowledge Proofs

In this paper, we consider non-interactive zero-knowledge (NIZK) proofs in the random oracle model that satisfy correctness, computational extractability and statistical zero-knowledge.

Definition 6

(NIZK proofs.) Let $\mathcal {R}$ be a relation and let the language $\mathcal {L}$ be a set of statements $\{\textsf{st}\in \{0,1\}^n\}$ such that for each statement $\textsf{st}\in \mathcal {L}$, there exists a corresponding witness $\textsf{wit}$ such that $(\textsf{st},\textsf{wit})\in \mathcal {R}$. A non-interactive zero-knowledge (NIZK) proof system for $\mathcal {R}$ is a tuple of probabilistic polynomial-time (PPT) algorithms $\textsf{NIZK}=(\textsf{P}_{\textsf{NIZK}}, \textsf{V}_{\textsf{NIZK}})$ defined as follows (we assume that all algorithms in the description below have access to a common random oracle; we omit specifying it explicitly for ease of exposition):

• $\textsf{P}_{\textsf{NIZK}}(\textsf{st},\textsf{wit})$: A PPT algorithm that, given a statement $\textsf{st}\in \{0,1\}^n$ and a witness $\textsf{wit}$ such that $(\textsf{st},\textsf{wit})\in \mathcal {R}$, outputs a proof $\mathrm {\Pi }$.

• $\textsf{V}_{\textsf{NIZK}}(\textsf{st},\mathrm {\Pi })$: A deterministic algorithm that, given a statement $\textsf{st}\in \{0,1\}^n$ and a proof $\mathrm {\Pi }$, either outputs 1 (accept) or 0 (reject).

The following correctness and security properties should be satisfied:

Correctness. For any $(\textsf{st},\textsf{wit})\in \mathcal {R}$, letting $\mathrm {\Pi }=\textsf{P}_{\textsf{NIZK}}(\textsf{st},\textsf{wit})$, we must have $\textsf{V}_{\textsf{NIZK}}(\textsf{st},\mathrm {\Pi }) = 1$.

Computational Extractability. There exists an efficient PPT extractor $\textsf{Ext}_{\textsf{NIZK}}$ such that for any security parameter $\lambda \in \mathbb {N}$ and for any polynomially bounded cheating prover $P^*$ where: (i) $\textsf{Ext}_{\textsf{NIZK}}$ has rewinding access to $P^*$, and (ii) $\textsf{P}_{\textsf{NIZK}}$, $\textsf{Ext}_{\textsf{NIZK}}$ and $P^*$ all have access to a common random oracle, letting $(\textsf{st},\mathrm {\Pi })\leftarrow P^*(1^{\lambda })$ and $\textsf{wit}=\textsf{Ext}_{\textsf{NIZK}}(\textsf{st},\mathrm {\Pi })$, if $\textsf{V}_{\textsf{NIZK}}(\textsf{st},\mathrm {\Pi }) = 1$, we must have $\Pr [(\textsf{st},\textsf{wit})\in \mathcal {R}] > 1-\textsf{negl}(\lambda )$.

Statistical Zero-knowledge. There exists an efficient PPT simulator $\textsf{Sim}_{\textsf{NIZK}}$ such that for any security parameter $\lambda \in \mathbb {N}$ and for any non-uniform unbounded “cheating” verifier $V^* = (V^*_1,V^*_2)$ where $\textsf{P}_{\textsf{NIZK}}$, $V^*_1$ and $V^*_2$ all have access to a common random oracle, and such that $\textsf{Sim}_{\textsf{NIZK}}$ is allowed programming access to the same random oracle, we have

$$\begin{aligned} \left| \Pr \left[ V^*_2(\textsf{st},\mathrm {\Pi },\xi ) = 1 \wedge (\textsf{st}\in \mathcal {L})\right] - \Pr \left[ V^*_2(\textsf{st},\widehat{\mathrm {\Pi }},\xi ) = 1 \wedge (\textsf{st}\in \mathcal {L})\right] \right| \le \textsf{negl}(\lambda ), \end{aligned}$$

where $(\textsf{st},\textsf{wit},\xi )\leftarrow V^*_1(1^{\lambda })$, $\mathrm {\Pi }\leftarrow \textsf{P}_{\textsf{NIZK}}(\textsf{st},\textsf{wit})$, and $\widehat{\mathrm {\Pi }}\leftarrow \textsf{Sim}_{\textsf{NIZK}}(\textsf{st})$.

3 Isogeny Graphs and Expansion

Let p be a prime and d an integer not divisible by p. An elliptic curve with level d Borel structure is a pair (E, C), where E is an elliptic curve defined over a field of characteristic p and C is an order d cyclic subgroup of E[d]. We say that two such pairs $(E_1,C_1)$ and $(E_2,C_2)$ are isomorphic if there exists an isomorphism $\phi : E_1 \rightarrow E_2$ such that $\phi (C_1)=C_2$. An automorphism of (E, C) is an isomorphism $(E,C)\rightarrow (E,C)$. They form the group $\textrm{Aut}(E,C)$.

Let $\ell$ be a prime not dividing pd. The supersingular $\ell$-isogeny graph with level d structure $G = G(p,d,\ell )$ is defined as follows. The set of vertices of G is a complete set $V=V(p,d)=\{(E_i,C_i)\}$ of representatives of the set of isomorphism classes of supersingular elliptic curves with a level d Borel structure defined over $\mathbb {F}_{p^2}$. We note that each such class over $\overline{\mathbb {F}_{p^2}}$ admits a model defined over $\mathbb {F}_{p^2}$: Each isomorphism class of supersingular elliptic curves has a representative E such that $\#E(\mathbb {F}_{p^2})=(p+1)^2$ and thus the $p^2$-Frobenius acts as a scalar multiplication $[-p]$, so the kernel of any $\ell$-isogeny is $\text {Gal}(\overline{\mathbb {F}_{p^2}})$-invariant.

Now, the set of edges from (E, C) to $(E',C')$ in G is the set of degree $\ell$ isogenies from E to $E'$ which map C to $C'$, modulo the action of $\textrm{Aut}(E',C')$ (by postcomposition). The number of edges is independent of the representative of the isomorphism classes. When $d=1$, we recover the usual definition of the supersingular $\ell$-isogeny graph.

This graph is directed. The out-degree of each vertex is $\ell +1$, however the in-degree is not always $\ell +1$, hence the adjacency matrix of the graph is not always symmetric.

3.1 Generalities on the Graph and Its Adjacency Matrix

Let $V = \{(E_i,C_i)\}$ for $i =1,\ldots ,n$ be the vertex set of $G=G(p,d,\ell )$. On the complex vector space $\mathbb {C}^V$, we introduce the Hermitian form $Q((E_i,C_i),(E_j,C_j))=w_i\delta _{ij}$, where $\delta _{ij}$ is the Kronecker symbol and $w_i {:}{=}\tfrac{1}{2} |\textrm{Aut}(E_i,C_i)|$. Denote by $\Vert \cdot \Vert _Q$ the associated norm. We will compare $\Vert \cdot \Vert _Q$ with the $L^1$ and $L^2$ norms on $\mathbb {C}^V$. The set $\varOmega$ of probability distributions on V is the set of vectors with real positive entries and $L^1$ norm equal to 1. Consider also the vector $\mathcal {E}=\sum _{i=1}^n\frac{1}{w_i}(E_i,C_i)$, and s the probability distribution obtained normalizing $\mathcal {E}$. The following result contains a number of general facts about the adjacency matrix of G, which will be used later on.

Theorem 7

• 1. The adjacency matrix A of G is self-adjoint with respect to Q; in particular it is diagonalizable with real eigenvalues and eigenvectors;

• 2. The vector $\mathcal {E}$ is a left-eigenvector of eigenvalue $\ell +1$ of A;

• 3. The vector u with all entries equal to 1 is a right-eigenvector of A; in particular its orthogonal complement S with respect to the $L^2$ scalar product is preserved by right multiplication by A;

• 4. $K{:}{=}\inf \{\, \Vert v\Vert _Q \, : \, v \in \mathbb {C}^V \, \text { and } \, \Vert v\Vert _{L^1}=1\}= \Big ( \tfrac{(p-1)d}{12}\prod _{q} (1{+}\tfrac{1}{q})\Big )^{-1/2}$, where the product index q runs over the prime divisors of d;

• 5. $M{:}{=}\sup \{\, \Vert \pi -s\Vert _Q\, : \, \pi \in \varOmega \} \le \sqrt{3}$.

Proof

The proof is given in the full version [5].    $\square$

3.2 Proof of Theorem 3

We now prove that $G=G(p,d,\ell )$ has the Ramanujan property. This follows from the first three items of Theorem 7 combined with the following result, whose proof heavily relies on the theory of modular forms. An immediate consequence is that G is connected and not bipartite, a different proof of which can be found in [39, Theorem 5.3.3].

Theorem 8

Let $S \subset \mathbb {C}^V$ be the subspace of vectors $\sum _i v_i (E_i,C_i)$ such that $\sum _i v_i = 0$, as in Theorem 7. The eigenvalues of the action of A on S are all contained in the Hasse interval $[-2\sqrt{\ell },2\sqrt{\ell }]$.

To prove Theorem 8, we assume standard notations and results about quadratic forms and modular forms, such as the ones from [31, 40, 53]. Given two elliptic curves with level structure $(E_i,C_i)$ and $(E_j,C_j)$, we denote by $\varLambda _{ij}$ the lattice of isogenies $\phi :E_i\rightarrow E_j$ such that $\phi (C_i)\subset C_j$. The degree defines a quadratic form $\deg$ on $\varLambda _{ij}$. This quadratic module has rank four, level dp and determinant $d^2p^2$. We can thus define the theta series

$$ \varTheta _{ij}(\tau )=\frac{1}{|\textrm{Aut}(E_j,C_j)|}\sum _{\phi \in \varLambda _{ij}}q^{\deg (\phi )} \,, \quad \text {with }q = e^{2\pi i \tau }\,. $$

This function is in $M_2(\varGamma _0(dp))$, the space of modular forms of weight two for the modular group $\varGamma _0(dp)$, by [40, Theorem 4.2] (observe that in loc. cit. the exponential is one because Q(h) is an integer; moreover, we choose $P=1$) or [53, Chapter IX, Theorem 5, page 218]. The above construction extends to an Hermitian pairing

$$ \varTheta :\mathbb {C}^V \otimes \mathbb {C}^V \rightarrow M_2(\varGamma _0(dp)) : ((\alpha _i)_i \otimes (\beta _j)_j) \longmapsto \sum _{i,j}\alpha _i\beta _j\varTheta _{ij}. $$

We call this pairing the Brandt pairing, even though there is a little ambiguity⁵ in this set-up. The Brandt pairing is non-degenerate: let $v=\sum c_i (E_i,C_i)$, then the coefficient of q of $\varTheta (v,v)$ is the Hermitian norm of the vector of coefficients $(\dots , c_i , \dots )$. We will prove the following two key propositions.

Proposition 9

The Brandt pairing intertwines the adjacency matrix A of G and the Hecke operator $T_{\ell }$; in symbols $T_{\ell }\varTheta (w,v)=\varTheta (wA,v)$ for all $w,v \in \mathbb {C}^{V}$.

Proposition 10

For every three elliptic curves with level structure $(E_1,C_1)$, $(E_2,C_2)$ and $(E_3,C_3)$, we have a cusp form

$$\varTheta ((E_1,C_1),(E_3,C_3)) - \varTheta ((E_2,C_2),(E_3,C_3)).$$

The combination of these two results tells that the spectrum of the action of A restricted to S is contained into the spectrum of the action of the Hecke operator $T_{\ell }$ on the space of cusp modular forms of weight two for $\varGamma _0(dp)$. The Ramanujan Conjecture, proved by Eichler, predicts that this second spectrum is contained in the Hasse interval, and hence proves Theorem 8.

We refer to [30, Theorem 8.2] for a proof of the Ramanujan Conjecture. In loc. cit. this result is proven only for eigenvectors of $T_{\ell }$ which are new-forms. An eigenvector which is an old form will come from an embedding $\iota :S_2(\varGamma _0(m))\rightarrow S_2(\varGamma _0(dp))$ with m that divides dp. Since $\ell$ is coprime with dp, the map $\iota$ is $T_{\ell }$-equivariant (cf. [31, proof of Proposition 5.6.2]), so we can still deduce our result from [30, Theorem 8.2]. It is worth recalling that [30, Theorem 8.2] is stronger than what we need, as it applies to modular forms of every weight.

Proof of Proposition 9. We prove that both sides have the same q-expansions. For a power series $F\in \mathbb {C}[[q]]$, denote $a_n(F)$ the coefficient of $q^n$. By definition

$$ a_n(\varTheta ((E_i, C_i) ,(E_j, C_i))) = |\textrm{Aut}(E_j,C_j)|^{-1} \cdot |\textrm{Hom}^n((E_i, C_i),(E_j, C_j))|\,, $$

where $\textrm{Hom}^n((E_i, C_i),(E_j, C_j))$ is the set of degree n isogenies in $\varLambda _{ij}$. For $f \in M_2(\varGamma _0(dp))$, we have $a_n(T_\ell f) = a_{n\ell }(f) + \ell a_{n/\ell }(f)$ (see e.g. [31, Proposition 5.2.2]), where $a_{n/\ell }(f)$ is set to zero in the case $n/\ell \not \in \mathbb {Z}$. In particular,

$$\begin{aligned} \begin{aligned}&a_n(T_\ell \, \varTheta ((E_i,\! C_i),(E_j,\! C_j)) ) = \\ {}&= |\textrm{Aut}(E_j,C_j)|^{-1}\Big (|\textrm{Hom}^{n\ell }((E_i, C_i),(E_j, C_j))|+ \ell |\textrm{Hom}^{n/\ell }((E_i, C_i),(E_j, C_j)|\Big ) \end{aligned} \end{aligned}$$

(2)

On the other side,

$$\begin{aligned} \begin{aligned}&a_n(\varTheta ((E_i, C_i)A,(E_j, C_j))) = \sum _{C} a_n(\varTheta ((E_i/C, \pi _C(C_i) ), (E_j, C_j)) ) = \\&\quad = |\textrm{Aut}(E_j,C_j)|^{-1} \sum _{C} |\textrm{Hom}^n((E_i/C, \pi _C(C_i) ),(E_j, C_j))|\end{aligned} \end{aligned}$$

(3)

where C varies among the cyclic non-trivial subgroups of $E_i[\ell ]$ of cardinality $\ell$, and $\pi _C$ is the projection $E_i\rightarrow E_i/C$. For each C let

$$\begin{aligned} \begin{aligned} F_C:\textrm{Hom}^n((E_i/C, \pi _C(C_i) ),(E_j, C_j))&\longrightarrow \textrm{Hom}^{n\ell }((E_i, C_i),(E_j, C_j)) \\ f&\longmapsto f\circ \pi _C \,, \end{aligned} \end{aligned}$$

and let F be the disjoint union of the above maps. The map F is surjective: if $\alpha :(E_i, C_i) \rightarrow (E_j, C_j)$ has degree $n\ell$, then $\ker (\alpha )\cap E_i[\ell ] \ne \{0\}$, hence there exists a cyclic non-trivial $C\subset \ker (\alpha )\cap E_i[\ell ]$, and we can write $\alpha = f\circ \pi _C$. In particular, let us compute the cardinality of the fiber $F^{-1}(\alpha )$ for $\alpha$ in the codomain. Each $F_C$ is injective, hence $|F^{-1}(\alpha )|$ is equal to the number of subgroups C such that $F^{-1}_C(\alpha )$ is not empty, that is the number of subgroups C contained in $\ker (\alpha )\cap E_i[\ell ]$. Hence

$$ |F^{-1}(\alpha )|= {\left\{ \begin{array}{ll} \ell +1 \quad \text {if }\alpha = \ell \beta \text { for some } \beta \in \textrm{Hom}^{n/\ell }((E_i, C_i),(E_j, C_j)),\\ 1 \quad \text {otherwise } \end{array}\right. } $$

By (3), the domain of F has size exactly $|\textrm{Aut}(E_j, C_j)|\cdot a_n(\varTheta (A (E_i, C_i),(E_j, C_j)))$, hence the proposition follows from (2) together with the above formula summed over $\alpha$ in the codomain.    $\square$

Proof of Proposition 10. We have to show that, for any two pairs (E, C) and $(E',C')$ and any cusp of $X_0(dp)$, the residue r of $\varTheta ((E,C),(E',C'))d\tau$ does not depend on (E, C) and $(E',C')$ at the cusp but only on p, d and the cusp.

By the discussion in [31, Section 3.8, page 103] each cusp can be represented as $({\begin{matrix}a\\ c\end{matrix}})$ with c dividing dp, and r is equal to $a_0( \varTheta ((E,C),(E',C'))|_{M})$ for M any matrix in $\textrm{SL}_2(\mathbb {Z})$ of the form $({\begin{matrix}a&{}b\\ c&{}\delta \end{matrix}})$.

By [53, Chapter IX, Equation (21), page 213], we have

$$ \begin{aligned} r&= \frac{1}{c^2pd}\sum _{\nu ,\lambda \in \varLambda /c\varLambda } e\left( \frac{(a-1)\deg (\lambda )+\deg (\lambda +\nu )+(\delta -1)\deg (\nu )}{c}\right) \end{aligned} $$

where $e(z)=e^{2\pi iz}$, and $\varLambda$ is the lattice of isogenies from (E, C) to $(E',C')$ which map C into $C'$. The above formula tells us that r only depends on M and on the quadratic form $\deg :\varLambda /c\varLambda \rightarrow \mathbb {Z}/c\mathbb {Z}$. Writing $c = c_0 p^\epsilon$ with $c_0$ dividing N and $\epsilon =0,1$ and using the Chinese remainder theorem we can split the quadratic form in two parts

The quadratic module $(\varLambda /c_0\varLambda , \deg )$ is (non-canonically) isomorphic to a Borel subalgebra of the algebra $(\textrm{End}((\mathbb {Z}/c_0\mathbb {Z})^{\oplus 2}), \det )$. An isomorphism can be obtained mapping it to $\textrm{Hom}(E[c_0],E'[c_0])$, and then choosing a symplectic basis.

If $\epsilon =0$ we are done, otherwise $\epsilon =1$. Since $[\textrm{Hom}(E,E'):\varLambda ]=d$ is prime to p, we have $\varLambda /p = \textrm{Hom}(E,E')/p= (\textrm{Hom}(E,E')\otimes \mathbb {Z}_p)/p$, and the quadratic $\mathbb {Z}_p$-module $\textrm{Hom}(E,E')\otimes \mathbb {Z}_p$ does not depend on the pair because, by the Deuring correspondence (see [57, Theorem 42.3.2.]) and by [57, Lemma 19.6.6], it is isomorphic to $\lambda \mathcal {O}_p$ with the reduced norm, where $\mathcal {O}_p$ is the maximal order in the non-ramified quaternions over $\mathbb {Q}_p$, and $\lambda$ is an element of norm prime to p.    $\square$

3.3 Mixing Time of Non-backtracking Walks

We finally analyze the behavior of random walks in $G=G(p,d,\ell )$, which we will ultimately use to prove statistical indistinguishability of distribution arising from our proof of knowledge. First, observe that Theorem 7 item 2 shows that the probability distribution s introduced in Subsect. 3.1 is the stationary distribution on G. This is nearly the uniform distribution: all curves are equally likely, with the possible exception of the two curves with extra automorphisms, $j=1728$ and $j=0$, which are respectively twice and thrice less likely.

We are going to determine the speed at which random walks converge to the stationary distribution. We focus on non-backtracking walks, which are the most useful for cryptographic protocols, but, because the graph is directed, we need some care to define them. Edges of G are equivalence classes of isogenies, so we choose a representative for each class. For an edge $\alpha$ we define its dual edge as the chosen representative $\beta$ for the class $\textrm{Aut}(E,C)\hat{\alpha }$, so that $\beta \alpha = u\ell$ for $u\in \textrm{Aut}(E,C)$. Notice that the dual of $\beta$ (as an edge) might be different from $\alpha$, but this is not relevant for us. We say that a random walk on G is non-backtracking walk if an edge is never followed by its dual.

With this “duality”, we have that isogenies of degree a power of $\ell$ and with cyclic kernel (up to the equivalence $\alpha \sim \beta$ iff $\ker \alpha = \ker \beta$) correspond to non-backtracking walks.

Theorem 11

(Mixing time). Let $\pi$ be a probability distribution on G, and $\pi ^{(k)}$ the distribution obtained after a non-backtracking random walk of length k. Then we have

$$ d_{TV}(\pi ^{(k)},s)\le \frac{1}{2} K^{-1}M \frac{(\ell +1)(k+1)-2}{(\ell +1)\sqrt{\ell ^k}}\,, $$

where K and M are as in Theorem 7 and $d_{TV}$ denotes the total variation distance.

Proof

This follows from [2] for the case of undirected graphs. In the full version [5] we adapt the proof to the graph $G(p,d,\ell )$.    $\square$

4 Proof of Knowledge

Our goal is to provide a PoK of an isogeny walk $\phi : E_0\rightarrow E_1$ between two supersingular curves defined over $\mathbb {F}_{p^2}$ that can be seamlessly plugged in a distributed Secuer generation protocol. For this, we need the following properties:

• 1. Compatible with any pair of curves $(E_0,E_1)$; this rules out [36, 37], which is restricted to a special starting curve $E_0$, and [24] and derivatives, which are restricted to curves defined over $\mathbb {F}_p$.

• 2. Statistically ZK, so that the security of the final Secuer does not hinge on computational assumptions brought in by the PoK; this rules out all other isogeny-based PoKs in the literature.

• 3. Post-quantum secure, possibly relying on as few additional assumptions as possible; this rules out many generic ZK proof systems.

• 4. Possibly compatible with any walk length and any base field $\mathbb {F}_{p^2}$.

• 5. Usable in practice for cryptographically sized finite fields.

Our new PoK inherits from the SIDH-based $\varSigma$-protocol of De Feo, Jao and Plût [25], and from the recent developments of De Feo, Dobson, Galbraith and Zobernig [23]. The common theme to all of them is to construct random SIDH squares (see (1)) on top of the secret isogeny $\phi : E_0 \rightarrow E_1$ and to reveal some, but not all of the edges $\psi ,\psi ',\phi '$ in response to a challenge. The reason these protocols are not statistically ZK is that the side $\phi '$ is strongly correlated to the parallel side $\phi$ (often unique given $E_2$) and can thus easily be distinguished by an unbounded adversary.

Our first idea is to make the walk $\psi$ long enough that the distribution of $(E_2,\phi ')$ becomes statistically close to the uniform distribution on supersingular curves with isogenies of degree $\deg (\phi )$. To prove it, we will use the properties of isogeny graphs with level structure analyzed in Sect. 3.

But making $\psi$ longer is easier said than done. SIDH-based protocols are constrained in the lengths of $\phi$ and $\psi$ by the form of the prime p: typically, $p+1=2^a3^b$ and then $\deg (\phi ) = 2^a$ and $\deg (\psi ) = 3^b$. Our second idea is to glue several SIDH squares together to make longer walks (see Fig. 2). We call these larger diagrams SIDH ladders.

A valuable side-effect of gluing SIDH squares together is that we can free ourselves from the constraints on p. All we need is that isogenies of a small prime degree $\ell$ coprime to $\deg (\phi )$ can be computed efficiently, then we stack vertically sufficiently many SIDH squares to make $\deg (\psi ) = \ell ^n$ as large as we need. In practice, we will take $\deg (\phi ) = 2^m$, $\deg (\psi ) = 3^n$, and the protocol will be most efficient for SIDH primes, but in full generality our protocol works for any base field and any isogeny degree.

4.1 Protocol Description and Analysis

Let $E_0,E_1$ be supersingular curves defined over a finite field $\mathbb {F}_{p^2}$, and let $\phi : E_0 \rightarrow E_1$ be a cyclic separable isogeny of smooth degree d. Let $\ell$ be a small prime not dividing pd. Let $\textsf{C}(m;r)$ be a statistically hiding and computationally binding commitment scheme. Our $\varSigma$-protocol is described in Fig. 1; it depends on a parameter n, controlling the length of the $\ell$-isogeny walks, that we will determine in Definition 15. The prover consists of two stateful algorithms $(\textsf{P}_1,\textsf{P}_2)$: the former is randomized and produces a commitment $(\textsf{com}_2,\textsf{com}_3)$, the latter receives a ternary challenge $\textsf{chall}\in \{-1,0,1\}$ and produces a deterministic response $\textsf{resp}$. The verifier is a deterministic algorithm that receives $\bigl ((\textsf{com}_2,\textsf{com}_3),\textsf{chall},\textsf{resp}\bigr )$ and outputs a bit indicating whether or not the proof is accepted.

Fig. 1.

Interactive proof of knowledge of a cyclic isogeny $\phi :E_0\rightarrow E_1$ of degree d.

Proposition 12

The $\varSigma$-protocol in Fig. 1 is correct for the relation

$$\begin{aligned} \mathcal {R}_d= \{ ((E_0,E_1), \phi ) \;\vert \; \phi :E_0\rightarrow E_1 \text { is a cyclic }d\text {-isogeny} \}. \end{aligned}$$

Assuming the commitment $\textsf{C}$ is computationally binding, it is 3-special sound for the relation

$$\begin{aligned} \mathcal {R}^\star = \{ ((E_0, E_1), \chi ) \;\vert \; \chi :E_0\rightarrow E_1 \text { is a cyclic }\ell ^{2i}d\text {-isogeny for some }0\le i \le n\}. \end{aligned}$$

More precisely, there is a probabilistic polynomial time algorithm that, given three successful transcripts of the protocol with same commitments and distinct challenges, either recovers a witness $\chi : E_0 \rightarrow E_1$, or opens one of the commitments $\textsf{C}(E_i;r_i)$ to two distinct values (breaking the binding property).

Proof

Correctness. Suppose that the prover $\textsf{P}= (\textsf{P}_1, \textsf{P}_2)$ and the verifier $\textsf{V}$ follow the protocol. First note that, since the degree d of $\phi$ is smooth, the SIDH ladder in $\textsf{P}_1$ can be constructed as described in Sect. 4.2. Then it is clear that the commitments open successfully, and the verifier accepts the transcript for any challenge.

3-Special Soundness. Given three accepting transcripts $(\textsf{com}, -1, \textsf{resp}_{-1})$, $(\textsf{com}, 0,\textsf{resp}_{0})$ and $(\textsf{com}, 1, \textsf{resp}_{1})$, recover $(\phi ',E_2,r_2,E_3,r_3) = \textsf{resp}_0$ where $\phi ':~E_2~\rightarrow ~E_3$ is an isogeny. If the curves in $\textsf{resp}_{-1}$ and $\textsf{resp}_{1}$ are not equal to $E_2$ and $E_3$ respectively, then we can open one of the commitments $\textsf{C}(E_2;r_2)$ or $\textsf{C}(E_3;r_3)$ to two distinct outputs. Otherwise, we have $\textsf{resp}_{-1} = (\psi ,E_2,r_2)$ and $\textsf{resp}_{1} = (\psi ',E_3,r_3)$ where $\psi : E_0 \rightarrow E_2$ and $\psi ': E_1 \rightarrow E_3$ are isogenies. Therefore $\chi ' = \widehat{\psi '} \circ \phi ' \circ \psi$ is an isogeny from $E_0$ to $E_1$ of degree $\ell ^{2n}d$. Factoring out the non-cyclic part of $\chi '$, we extract a cyclic isogeny $\chi :E_0\rightarrow E_1$ of degree $\ell ^{2i}d$ such that $\chi ' = [\ell ^{2(n-i)}]\circ \chi$ for some $0\le i \le n$; however, like in the original SIDH PoK [23, 38], we cannot guarantee that $i=0$.    $\square$

We are now going to define the simulator for proving ZK. Simulating $\textsf{chall}= \pm 1$ is easy, however how well we can simulate the case $\textsf{chall}= 0$ depends on the parameter n given to $\textsf{P}_1$. The opening $(E_2, \phi ':E_2\rightarrow E_3)$ can be equivalently viewed as the curve with level d Borel structure $(E_2, \ker (\phi '))$. Our goal is to have this opening distributed like a “random” vertex in the graph $G=G(p,d,\ell )$. To this effect, we define two sequences $D_1(k)$ and $D_2(k)$ of probability distributions on G, and we show that they converge as k grows.

Definition 13

Let $\phi :E_0 \rightarrow E_1$ be a cyclic separable isogeny of degree d. Define

$$\begin{aligned} \begin{array}{l l l} \mathcal {D}_1(k) &{}= \big \{ (E_0/K, \tau (\ker (\phi )) &{}\;\big \vert \; K\leftarrow \mathcal {C}_E(\ell ^k),\, \tau :E_0\rightarrow E_0/K \big \},\\ \mathcal {D}_2(k) &{}= \big \{ (E_0/K, C) &{}\;\big \vert \; K\leftarrow \mathcal {C}_E(\ell ^k),\, C\leftarrow \mathcal {C}_{E_0/K}(d) \big \}, \end{array} \end{aligned}$$

(4)

where $\mathcal {C}_E(f)$ is the uniform distribution on the cyclic subgroups of order f of E, up to $\textrm{Aut}(E)$.

Lemma 14

Keep notations as above, fix a positive real number $\varepsilon$, and let k be a positive integer such that

$$ \tau (p,d,\ell ,k) = \tfrac{1}{4}(p-1)^{1/2}\Big (1+\sqrt{d}\prod _{\begin{array}{c} q\mid d\\ q \text { prime} \end{array}} (1{+}\tfrac{1}{q})^{1/2}\Big )\cdot \Big (k + \tfrac{\ell -1}{\ell +1}\Big ) \cdot \ell ^{-k/2}\le \varepsilon \,, $$

then $d_{TV}\left( \mathcal {D}_1(k) , \mathcal {D}_2(k)\right) \le \varepsilon$, where $d_{TV}$ is the total variation distance between the two distributions, also known as statistical distance.

Proof

We bound the statistical distance of each of $\mathcal {D}_1(k)$ and $\mathcal {D}_2(k)$ from the stationary distribution of $G(p,d,\ell )$, as determined in Theorem 7, then we conclude with the triangle inequality. For $\mathcal {D}_1(k)$, we can directly apply Theorem 11. The argument for $\mathcal {D}_2(k)$ is slightly more involved and is presented in the full version [5].    $\square$

Definition 15

Given p,  d,  $\ell$ and m, define

$$ n(p,d,\ell ,m) = \min \left\{ k \in \mathbb {Z} \ | \ \tau (p,d,\ell ,k) \le 2^{-m} \right\} .$$

Proposition 16

Let $\lambda$ be a security parameter and let $n = n(p,d,\ell ,\lambda )$. The $\varSigma$-protocol of Fig. 1 is statistically SHVZK for the relation $\mathcal {R}_d$ defined in Proposition 12, assuming the commitment $\textsf{C}$ is statistically hiding.

Proof

We simulate the honest prover for each of the three challenges as follows.

$\textsf{chall}= -1$. Sample a random isogeny $\psi :E_0\rightarrow E_2$ of degree $\ell ^n$, and random strings $r_2,r_3$. Set $\textsf{com}_2 = \textsf{C}(E_2;r_2)$ and set $\textsf{com}_3 = \textsf{C}(\bot ;r_3)$. Return $(\textsf{com}_2, \textsf{com}_3), \textsf{chall}, (\psi , E_2, r_2)$.

The isogeny $\psi$ is distributed exactly like in the real protocol, thus this transcript is valid. Because $\textsf{C}$ is statistically hiding, an adversary cannot distinguish $\textsf{com}_3$ from a real commitment.

$\textsf{chall}= 1$. This is nearly identical to the above. The simulator samples $\psi ' : E_1\rightarrow E_3$ of degree $\ell ^n$ and random strings $r_2,r_3$. It sets $\textsf{com}_2 = \textsf{C}(\bot ;r_2)$ and $\textsf{com}_3 = \textsf{C}(E_3;r_3)$, and returns $(\textsf{com}_2, \textsf{com}_3)$, $\textsf{chall}$, $(\psi ', E_3, r_3)$.

Because $\ell$ is coprime to d, if $\psi$ is uniformly distributed so is $\psi '$. Then, the transcript is indistinguishable from a real one as before.

$\textsf{chall}= 0$. Sample a random isogeny $\psi :E_0\rightarrow E_2$ of degree $\ell ^n$, and then a random isogeny $\rho :E_2\rightarrow E_3$ of degree d. Sample random strings $r_2,r_3$ and set $\textsf{com}_2 = \textsf{C}(E_2;r_2)$ and $\textsf{com}_3 = \textsf{C}(E_3;r_3)$. Return $(\textsf{com}_2, \textsf{com}_3), \textsf{chall}, (\rho , E_2, r_2, E_3, r_3)$.

Thanks to Lemma 14, the statistical distance between the simulated $(E_2, \ker (\rho ))$ and $(E_2, \psi (\ker (\phi )))$ is negligible. Because $\rho$ is uniquely determined from $\ker (\rho )$, and the real response $\phi '$ by $\psi (\ker (\phi ))$, an adversary has negligible probability of distinguishing the transcript output by the simulator.    $\square$

4.2 Executing the Protocol

The protocol we just described crucially depends on the ability to construct a commutative square with sides of degrees d and $\ell ^n$. The SIDH setting has $p+1 = d\cdot \ell ^n$ so that the square can be constructed by simply pushing a single kernel point for $\psi$ through $\phi$ and vice versa. We refer to such a square as an SIDH square. For more general choices of $\ell ^n$ and d, the kernels are typically generated by points defined over very large extension fields, requiring superpolynomial space. We efficiently construct such “larger” squares by gluing together several SIDH squares in what we call SIDH ladders, as depicted in Fig. 2.

For simplicity, we shall present the case $d = (2^a)^w$ and $\ell ^n=(3^b)^h$, where $2^a$ and $3^b$ are the side lengths of an SIDH square, and w and h are positive integers defining the width and height of the ladders in units of SIDH squares. However, the technique generalizes easily to any coprime d and $\ell ^n$, as long as isogenies of degrees d and $\ell$ can be efficiently computed.

First, notice that there always exist some choice of a and b such that points (and hence kernel subgroups) of orders $2^a$ and $3^b$ can be represented efficiently. This is clear if the prime p is a SIDH prime where $2^a3^b \mid (p+1)$, but for a generic prime p, one can set $a = b = 1$: Points of order 2 and 3 are defined over a small extension field and can thus be efficiently represented. Moreover, any isogeny of degree $(3^b)^h$ is the composition of h isogenies of degree $3^b$ each, which can be stored as a sequence of h kernel generators which are efficiently representable.

This means that the prover can generate the isogeny $\psi : E_0 \rightarrow E_2$ in step 2 of $\textsf{P}_1$ by generating a random kernel $K_{1,0}$ on $E_0$, computing the isogeny $\psi _{1,0}: E_0 \rightarrow E_0 / K_{1,0} =: E_{1,0}$, generating a random kernel $K_{2,0}$ on $E_{1,0}$ such that $K_{2,0} \cap \ker \widehat{\psi _{1,0}} = \{ 0\}$ to prevent backtracking, and repeating the process h times to obtain a chain of h isogenies $\psi _{i,0} : E_{i-1,0} \rightarrow E_{i,0}$. The curve $E_2$ is the codomain of the last isogeny $\psi _{h,0}$, i.e., $E_2 = E_{h,0}$.

If the width w of the ladder is one, the prover can now recursively push the kernel G of the isogeny $\phi = \phi _{0,1}$ through the isogenies $\psi _{i,0}$ to obtain its image $G_i$ on each curve $E_{i,0}$. Each horizontal isogeny $\phi _{0,i}$ has kernel $G_i$, and the prover can compute the kernel of the right-side vertical isogeny $\psi '_{i,0}$ as the image of the kernel of $\psi _{i,0}$ under the isogeny $\phi _{i-1,1}$. Since each square composed of $(E_{i,0}, E_{i+1,0}, E'_{i,0}, E'_{i+1,0})$ is a commutative diagram, so is the larger square $(E_0, E_1, E_2, E_3)$. In the general case where $w > 1$, the prover can use a similar approach for the horizontal isogeny $\phi$ as used for the vertical isogeny $\psi$: The isogeny $\phi$ can be written as the composition of w isogenies $\phi _{0,w} \circ \ldots \circ \phi _{0,1}$ of degree $2^a$ and their kernels can be mapped through the vertical isogenies. In other words, the prover can glue horizontally w compatible ladders, one for each factor $\phi _{0,i}$ of $\phi$. The right descending isogenies of each ladder are used as the left descending isogenies of the next one. This allows the prover to compute $w \times h$ SIDH squares in such a way that the curves $(E_0, E_1, E_2, E_3)$ and the isogenies between them form a commutative diagram. This is illustrated in Fig. 2. For the challenges $\textsf{chall}= \pm 1$, the prover reveals the isogenies $\psi _{i,0}$ of the leftmost squares, or the isogenies $\psi _{i,w}$ of the rightmost squares. For the challenge $\textsf{chall}= 0$, the prover responds with the isogenies $\phi _{h,i}$ of the bottom squares.

Fig. 2.

An SIDH ladder.

Verification consists of evaluating (depending on the challenge) either w or h isogenies of degree $2^a$ or $3^b$, which can be done efficiently. Generating the proof is slower, as the prover needs to fill in all the $w\times h$ SIDH squares that make up the ladder. The proving complexity is thus quadratic in w and h, while the verification complexity is linear in w and h. However, the complexity of computing an SIDH square with degrees $2^a$ or $3^b$ is only quasilinear in a and b using sparse strategies [25]; thus, maximizing the size of SIDH squares improves performance, which explains why SIDH primes are the most efficient scenario for this proof. If the degree of the isogenies and the size of the underlying field are kept constant, in the SIDH setting we have that $2^a3^b \mid (p+1)$ for large values of a and b (in the order of several hundreds), and thus w and h can be small. For a generic prime, the prover might need to set $a = b = 1$ and work with large values of w and h, incurring a quadratic cost, besides possibly having to compute points over an extension field of degree bounded by a small constant.

Remark 17

Above, we assumed that the degree of the witness $\phi$ was $d= (2^a)^w$. As mentioned before, this can be generalized to any witness $\phi$ of smooth degree $d = d_1 \dots d_w$ as far as the $d_i$-torsion groups are accessible (ideally, one should have $E_0[d_i] \subseteq E_0(\mathbb {F}_{p^2})$). In this case, one factors $\phi$ as $\phi = \phi _{0,w} \circ \ldots \circ \phi _{0,1}$ where each isogeny $\phi _{0,i}$ has degree $d_i$, and constructs compatible ladders for each $\phi _{0,i}$.

5 Distributed $\textsc {Secuer}$ Setup and Its Security

In this section, we formally describe the distributed $\textsc {Secuer}$ setup protocol and prove its security under a security definition using the simplified universal composability (SUC) framework due to Canetti, Cohen, and Lindell [13] in the real/ideal world paradigm. Our security definitions consider a dishonest majority corruption model, wherein the adversary can corrupt up to $t-1$ of the t participating parties in the distributed $\textsc {Secuer}$ setup protocol. The protocol uses a non-interactive version of the $\varSigma$-protocol described in Sect. 4. We begin by formally describing this non-interactive zero-knowledge (NIZK) PoK protocol.

5.1 The NIZK Protocol

We transform the $\varSigma$-protocol of Sect. 4 into a NIZK using the standard Fiat-Shamir heuristic [33] for transforming interactive PoK protocols into NIZK proofs, albeit with the difference that soundness and zero-knowledge hold for slightly different languages.

The NIZK Construction. Let $E_0,E_1$ be supersingular curves defined over a finite field $\mathbb {F}_{p^2}$, let $\phi : E_0 \rightarrow E_1$ be a separable isogeny of smooth degree d and let $\textsf{C}(m;r)$ be a statistically hiding and computationally binding commitment scheme. Additionally, let $\varSigma = (\textsf{P}_1,\textsf{P}_2,\textsf{V})$ be the interactive PoK protocol described in Sect. 4, let $\lambda \in \mathbb {N}$ be the security parameter, let $\ell$ be a small prime not dividing dp, let $n = n(p,d,\ell ,\lambda )$, and let $N=\textsf{poly}(\lambda )$ be a fixed polynomial. Finally, let $H:\{0,1\}^*\rightarrow \{-1,0,1\}^N$ be a random oracle. The NIZK proof system consists of a pair of algorithms $\textsf{NIZK}=(\textsf{P}_{\textsf{NIZK}},\textsf{V}_{\textsf{NIZK}})$ as described in Fig. 3. The prover algorithm $\textsf{P}_{\textsf{NIZK}}$ is randomized and produces a proof $\mathrm {\Pi }$. The verifier algorithm $\textsf{V}_{\textsf{NIZK}}$ is deterministic; it receives the proof $\mathrm {\Pi }$ and outputs a bit $b\in \{0,1\}$ indicating whether or not the proof is accepted.

Fig. 3.

The NIZK.

Correctness, Extractability and ZK. Correctness follows immediately from the correctness of the underlying $\varSigma$-protocol. We state and prove the following propositions for extractability and ZK.

Proposition 18

Assuming that $\varSigma = (\textsf{P}_1,\textsf{P}_2,\textsf{V})$ satisfies 3-special soundness with respect to the relation $\mathcal {R}^\star$ (described in Proposition 12) and that H is a random oracle, the NIZK $\textsf{NIZK}= (\textsf{P}_{\textsf{NIZK}},\textsf{V}_{\textsf{NIZK}})$ satisfies extractability (and hence soundness) with respect to the relation $\mathcal {R}^\star$.

Proof

We provide an informal proof overview. We begin by noting that $\varSigma$ is a public-coin protocol, and that there exists a probabilistic polynomial-time algorithm that extracts a witness from 3 accepting transcripts corresponding to N parallel executions of $\varSigma$ w.r.t. the same statement. Consequently, we can invoke the generalized forking lemma of [11] to argue the existence of a probabilistic polynomial-time witness-extraction algorithm for $\textsf{NIZK}$. This completes the proof of extractability (and hence, soundness) for $\textsf{NIZK}$.    $\square$

Proposition 19

Assuming that $\varSigma = (\textsf{P}_1,\textsf{P}_2,\textsf{V})$ is statistically SHVZK for the relation $R_d$ (described in Proposition 16) and that H is a random oracle, the NIZK $\textsf{NIZK}= (\textsf{P}_{\textsf{NIZK}},\textsf{V}_{\textsf{NIZK}})$ is statistically ZK for the relation $R_d$.

Proof

We again provide an informal proof overview. Let $\textsf{Sim}_{\varSigma }$ be a ZK simulator that simulates an accepting transcript for the underlying $\varSigma$-protocol (as described in the proof of ZK for $\varSigma$). We construct a ZK simulator $\textsf{Sim}_{\textsf{NIZK}}$ that simulates an accepting proof as follows:

• 1. $\textsf{Sim}_{\textsf{NIZK}}$ simulates the random oracle H as follows: it maintains a local table consisting of tuples of the form $(x,y)\in \{0,1\}^*\times \{-1,0,1\}^N$. On receiving a query $x\in \{0,1\}^*$ from the adversary $\mathcal {A}$, it looks up this table to check if an entry of the from (x, y) exists. If yes, it responds with y. Otherwise, it responds with a uniformly sampled $y\leftarrow \{-1,0,1\}^N$, and programs the random oracle as $H(x):=y$ by adding the entry (x, y) to the table.

• 2. For each $i\in [N]$, $\textsf{Sim}_{\textsf{NIZK}}$ internally invokes the simulator $\textsf{Sim}_{\varSigma }$ for the underlying $\varSigma$-protocol to obtain the i-th accepting transcript of the form

  $$\begin{aligned} \left( (\textsf{com}_{2,i}, \textsf{com}_{3,i}), \textsf{chall}_i, \textsf{resp}_i\right) . \end{aligned}$$

• 3. At this point, $\textsf{Sim}_{\textsf{NIZK}}$ aborts if the adversary $\mathcal {A}$ has already issued a random oracle query on the input $x = \bigl ((\textsf{com}_{2,1},\textsf{com}_{3,1}),\ldots ,(\textsf{com}_{2,N},\textsf{com}_{3,N})\bigr )$.

• 4. Otherwise, $\textsf{Sim}_{\textsf{NIZK}}$ programs the random oracle as

  $$\begin{aligned} H\bigl ((\textsf{com}_{2,1},\textsf{com}_{3,1}),\ldots ,(\textsf{com}_{2,N},\textsf{com}_{3,N})\bigr ):= (\textsf{chall}_1,\ldots ,\textsf{chall}_N), \end{aligned}$$

  and outputs the simulated proof as $\mathrm {\Pi }= \left( \lbrace (\textsf{com}_{2,i},\textsf{com}_{3,i},\textsf{resp}_i) \rbrace _{i\in [N]}\right)$.

We note that $\textsf{Sim}_{\textsf{NIZK}}$ runs in polynomial time as long as $\textsf{Sim}_{\varSigma }$ runs in polynomial time. Additionally, if $\textsf{Sim}_{\textsf{NIZK}}$ does not abort, it outputs a simulated proof that is distributed in a statistically indistinguishable manner from the distribution of a real proof, assuming that $\textsf{Sim}_{\varSigma }$ outputs a simulated accepting transcript with distribution statistically indistinguishable from a real accepting transcript for $\varSigma$. Finally, $\textsf{Sim}_{\textsf{NIZK}}$ aborts with only negligible probability, since the adversary $\mathcal {A}$ guesses $((\textsf{com}_{2,i}, \textsf{com}_{3,i}), \textsf{chall}_i, \textsf{resp}_i)$ for each $i\in [n]$ with at most negligible probability. This completes the proof of statistical ZK for $\textsf{NIZK}$.    $\square$

5.2 Our Distributed Secuer setup protocol

We now move to the distributed $\textsc {Secuer}$ setup protocol. Let $P_1,\ldots ,P_t$ be a set of t participating parties and let $E_0$ be some fixed starting curve. In a nutshell, the idea is to have the parties act sequentially: each $P_i$ at its own turn performs a secret random walk $E_{i-1}\rightarrow E_i$ and broadcasts $E_i$ and a NIZK PoK of the secret walk. We claim that, as long as one party is honest, the final curve $E_t$ is a Secuer.

To get any security guarantee, we need to carefully set the parameters of the random walk $E_{i-1}\rightarrow E_i$. The natural choice is to fix some small prime q, not dividing $\ell p$, and to take a random walk long enough that the distribution of $E_i$ is negligibly far from the stationary distribution on the q-isogeny graph G(p, 1, q). For example we may set $q=2$ and $\ell =3$, then Theorem 11 provides a precise bound to set the length $\delta =n(p,1,q,\lambda )$ of the q-walk as a function of the security parameter, and ultimately the parameter $n(p,q^\delta ,\ell ,\lambda )$ of the PoK.

Remark 20

For increased efficiency, we may choose to perform shorter q-walks $E_{i-1}\rightarrow E_i$ of length $\log _q(p)$. This length approximates the diameter of the supersingular q-isogeny graph; hence, it ensures that the secret isogeny can reach almost any curve in the graph.

Under mild assumptions, this choice would still yield a secure protocol, but it would also make the security proof somewhat more involved. For this reason, we shall stick here to the more conservative choice of walking long enough to ensure nearly stationary distribution of $E_i$.

We formally describe the protocol (referred to as $\varGamma _{\textsc {Secuer}}$ henceforth). Assume that $E_0$ is known to all the parties at the start. Let $\textsf{NIZK}= (\textsf{P}_{\textsf{NIZK}},\textsf{V}_{\textsf{NIZK}})$ be the non-interactive proof as described above. The protocol $\varGamma _{\textsc {Secuer}}$ proceeds in t rounds while only using broadcast channels of communication, where round-i for each $i\in [t]$ is as follows:

• Party $P_i$ performs a q-isogeny walk starting at curve $E_{i-1}$ and ending at curve $E_i$ (where $E_{i-1}$ and $E_i$ are both supersingular curves defined over $\mathbb {F}_{p^2}$), such that party $P_i$ knows a separable isogeny $\phi _i : E_{i-1} \rightarrow E_{i}$ of degree $q^\delta$, where $\delta = n(p,1,q,\lambda )$.

• Party $P_i$ generates $\mathrm {\Pi }_i \leftarrow \textsf{P}_{\textsf{NIZK}}(E_{i-1},E_{i},\phi _i,n,N)$, where $n = n(p,q^\delta ,\ell ,\lambda )$, and broadcasts $(E_i,\mathrm {\Pi }_i)$ to all other parties.

• Each party $P_j$ for $j\in [t]\setminus \{i\}$ verifies the NIZK proof $\mathrm {\Pi }_i$ by computing $b_{i} = \textsf{V}_{\textsf{NIZK}}(E_{i-1},E_i,\mathrm {\Pi }_i,N)$. If $b_i = 0$ (i.e., the proof is invalid), $P_j$ aborts.

At the end of round-t, all parties output $E_t$ to be the final output curve.

Correctness. Correctness of $\varGamma _{\textsc {Secuer}}$ follows immediately from the correctness guarantees of the NIZK.

5.3 Proof of Security for $\varGamma _{\textsc {Secuer}}$

We now present the proof of security for $\varGamma _{\textsc {Secuer}}$ using the simplified universal composability (SUC) framework [13] in the real/ideal world paradigm. We consider a dishonest majority corruption model, wherein the adversary can corrupt up to $(t-1)$ of the t participating parties.

The Ideal Functionality. Intuitively, the ideal functionality for distributed $\textsc {Secuer}$ setup should simply take as input the initial curve $E_0$ and output a Secuer $E_t$. It is however not obvious how to model the property of being a Secuer in the plain SUC model: a game based definition, stating that an adversary who can compute $\textrm{End}(E_t)$ can be used to break some other assumption, appears to be more appropriate.

Thus, we prove security in two steps. First, we prove that $\varGamma _{\textsc {Secuer}}$ securely emulates a less-than-ideal functionality $\mathcal {F}^{*}_{\textsc {Secuer}}$ (described in Fig. 4) that enforces that: (a) for each $i\in [t]$, if a corrupt party $P_i$ outputs a curve $E_i$, it must know a valid isogeny $\phi _i:E_{i-1}\rightarrow E_i$, and (b) for each $i\in [t]$, if an honest party $P_i$ outputs a curve $E_i$, then the corresponding isogeny $\phi _i:E_{i-1}\rightarrow E_i$ is hidden from the adversary. This step relies on the extractability and ZK properties of the NIZK protocol described above. Next, we prove that, assuming the hardness of the endomorphism ring problem in the $\mathcal {F}^{*}_{\textsc {Secuer}}$-hybrid model, the output curve $E_t$ is a $\textsc {Secuer}$, i.e. that the (malicious) adversary cannot compute $\textrm{End}(E_t)$.

Theorem 21

Assuming that $\textsf{NIZK}= (\textsf{P}_{\textsf{NIZK}},\textsf{V}_{\textsf{NIZK}})$ satisfies extractability and zero-knowledge, and assuming the hardness of the endomorphism ring problem (Definition 1) and GRH, the output $E_t$ of the protocol $\varGamma _{\textsc {Secuer}}$ is a $\textsc {Secuer}$ if at least one party $P_{i^*}$ for some $i^*\in [t]$ is honest.

Fig. 4.

The Ideal functionality $\mathcal {F}^{*}_{\textsc {Secuer}}$

Secure Emulation of . We now prove that $\varGamma _{\textsc {Secuer}}$ securely emulates the less-than-ideal functionality $\mathcal {F}^{*}_{\textsc {Secuer}}$. Our proof is in the real/ideal world paradigm defined formally as follows.

The Real World. The following entities engage in the real protocol $\varGamma _{\textsc {Secuer}}$: (i) a set $\mathcal {H}\subseteq [t]$ of honest parties, (ii) a real-world adversary $\mathcal {A}$ controlling a set $\mathcal {C}\subset [t]$ of corrupt parties, and (iii) the environment $\mathcal {E}$ that provides $E_0$ to each party, interacts with the real-world adversary $\mathcal {A}$, receives the final output curve $E_t$ from the honest parties, and eventually outputs a bit $b\in \{0,1\}$.

The Ideal World. The following entities interact with the functionality $\mathcal {F}^{*}_{\textsc {Secuer}}$: (i) A set $\mathcal {H}\subseteq [t]$ of honest parties, where for each $i\in \mathcal {H}$, party $P_i$ directly forwards its secret isogeny to $\mathcal {F}^{*}_{\textsc {Secuer}}$, (ii) an ideal-world simulator $\textsf{Sim}$ that sends inputs to $\mathcal {F}^{*}_{\textsc {Secuer}}$ on behalf of a set $\mathcal {C}\subset [t]$ of corrupt parties, and (iii) the environment $\mathcal {E}$ that provides each party with the starting curve $E_0$, interacts with the simulator $\textsf{Sim}$, receives the final output curve $E_t$ from the functionality, and eventually outputs a bit $b\in \{0,1\}$.

For any t-party $\textsc {Secuer}$ setup protocol $\varGamma _{\textsc {Secuer}}$, any adversary $\mathcal {A}$, any simulator $\textsf{Sim}$, and any environment $\mathcal {E}$, we define the following random variables:

• $\textsf{real}_{\varGamma _{\textsc {Secuer}},\mathcal {A},\mathcal {E}}$: denotes the output of the environment $\mathcal {E}$ after interacting with the adversary $\mathcal {A}$ during a real-world execution of $\varGamma _{\textsc {Secuer}}$.

• $\textsf{ideal}_{\mathcal {F}^{*}_{\textsc {Secuer}},\textsf{Sim},\mathcal {E}}$: denotes the output of the environment $\mathcal {E}$ after interacting with the simulator $\textsf{Sim}$ in the ideal world.

Theorem 22

Assuming that $\textsf{NIZK}= (\textsf{P}_{\textsf{NIZK}},\textsf{V}_{\textsf{NIZK}})$ satisfies extractability and zero-knowledge, for any security parameter $\lambda \in \mathbb {N}$ and any probabilistic polynomial time (PPT) adversary $\mathcal {A}$, there exists a PPT simulator $\textsf{Sim}$ such that, for any PPT environment $\mathcal {E}$, we have

$$\begin{aligned} \left| \Pr \left[ \textsf{real}_{\varGamma _{\textsc {Secuer}},\mathcal {A},\mathcal {E}} = 1\right] - \Pr \left[ \textsf{ideal}_{\mathcal {F}^{*}_{\textsc {Secuer}},\textsf{Sim},\mathcal {E}} = 1\right] \right| \le \textsf{negl}(\lambda ). \end{aligned}$$

Proof

We prove this theorem by constructing a PPT simulator $\textsf{Sim}$ that simulates the view of the environment $\mathcal {E}$ in the ideal world. Details are given in the full version [5].    $\square$

Analyzing $E_t$ in -hybrid Model. Based on the above secure emulation guarantee, we now analyze the output $E_t$ of $\varGamma _{\textsc {Secuer}}$ in the $\mathcal {F}^{*}_{\textsc {Secuer}}$-hybrid model. Concretely, we state and prove the following theorem.

Theorem 23

Assuming the hardness of the endomorphism ring problem and GRH, the output $E_t$ of $\mathcal {F}^{*}_{\textsc {Secuer}}(E_0,t)$ is a $\textsc {Secuer}$ if at least one party is honest.

To prove this theorem, we first prove the following lemma.

Lemma 24

Assuming the hardness of the endomorphism ring problem, the output $E_i$ of $\mathcal {F}^{*}_{\textsc {Secuer}}(E_0,i)$ for $i\in [t]$ is a $\textsc {Secuer}$ whenever $P_i$ is honest.

Proof

Suppose that there exists an adversary $\mathcal {A}$ corrupting a dishonest majority of the parties that efficiently computes the endomorphism ring of $E_i$ with non-negligible probability. Also assume that $\mathcal {A}$ corrupts all of $P_1,\ldots ,P_{i-1}$. We can use $\mathcal {A}$ to construct an algorithm $\mathcal {B}$ that solves the endomorphism ring problem. The algorithm $\mathcal {B}$ receives as input a uniformly random curve $E^*/\mathbb {F}_{p^2}$, internally runs the adversary $\mathcal {A}$ to emulate the outputs of the corrupt parties $P_1,\ldots ,P_{i-1}$, and finally feeds $\mathcal {A}$ with $E_i:=E^*$. The view of the adversary $\mathcal {A}$ is properly simulated by $\mathcal {B}$, since $E_i$ output by $\mathcal {F}^{*}_{\textsc {Secuer}}$ and $E^*$ provisioned by $\mathcal {B}$ are statistically indistinguishable (here we use Theorem 11, which crucially follows from the honest party taking a q-walk of length $n(p,1,q,\lambda )$). Finally, $\mathcal {B}$ uses $\mathcal {A}$ to recover the endomorphism ring of $E^*$ with non-negligible probability. This concludes the proof of Lemma 24.    $\square$

We now prove Theorem 23. We break the proof into two cases: (i) when $P_t$ is honest, and (ii) when $P_t$ is corrupt. The proof for case (i) is immediate from Lemma 24. Hence, we focus on case (ii). Let $\mathcal {H}\subseteq [t]$ be the set of honest parties, and let $i^* = \max \left( \{i:P_i \in \mathcal {H}\}\right)$. By Lemma 24, $E_{i^*}$ must be a $\textsc {Secuer}$. Now, suppose that $E_t$ is not a $\textsc {Secuer}$, i.e., there exists an adversary $\mathcal {A}$ corrupting dishonest majority of the parties that efficiently computes the endomorphism ring of $E_t$ with non-negligible probability. Since all of $P_{i^*+1},\ldots ,P_t$ are corrupt, $\mathcal {A}$ knows a walk from $E_{i^*}$ to $E_t$ in the $\ell$-isogeny graph. However, since $E_t$ is not a $\textsc {Secuer}$, $\mathcal {A}$ can use the reduction [59] (assuming GRH) to recover $\textrm{End}(E_{i^*})$, thereby violating Lemma 24. This completes the proof of Theorem 23.    $\square$

Finally, the proof of Theorem 21 follows immediately from the proofs of Theorem 22 and Theorem 23, which completes the proof of security for our distributed $\textsc {Secuer}$ setup protocol $\varGamma _{\textsc {Secuer}}$.

6 Implementation and Results

In this section, we report on our proof-of-concept implementation of our proof of knowledge (Sect. 4), including a discussion of proof sizes and running times. Moreover, we lay out concretely how one may deploy the trusted setup protocol from Sect. 5 in the real world.

Parameter Selection. The base-field primes p in our proof-of-knowledge implementation are taken from the four SIKE parameter sets p434, p503, p610, and p751. As discussed in Sect. 4.2, our proof of knowledge achieves its optimal efficiency for SIDH-style primes. Moreover, those primes have been featured extensively in the literature, and thus appear to be the obvious choice to demonstrate our proof of knowledge. That said, we stress once more that our techniques are generic and can be applied in any choice of characteristic.

We use the degree $q=2$ for the random walks $E_i\rightarrow E_{i-1}$, and $\ell = 3$ for the random walks of the $\varSigma$-protocol of Fig. 1. Like Sect. 5, we set $\delta = n(p,1,2,\lambda )$ for the length of the 2-walks, and $n = n(p,2^\delta ,3,\lambda )$ for the 3-walks. Lastly, the $\varSigma$-protocol needs to be repeated several times to achieve a negligible soundness error. Since one repetition has soundness error 2/3, the protocol needs to be repeated $-\lambda /{\log (2/3)}$ times to achieve $2^{-\lambda }$ soundness error. We target the same security levels as the corresponding SIKE parameter sets, i.e., $\lambda = 128$ for p434 and p503, $\lambda = 192$ for p610, and $\lambda = 256$ for p751. The resulting conservative parameters are summarized in Table 1.

Table 1. Parameters and corresponding secret/proof size for each of the four SIKE finite fields.

Implementation. We developed an optimized implementation⁶ of our proof of knowledge (Sect. 4.1) for the trusted-setup application (Sect. 5) based on version 3.5.1 of Microsoft’s SIDH library⁷. Our implementation inherits and benefits from all lower-level optimizations contained in that library, and it supports a wide range of platforms with optimized code for a variety of Intel and ARM processors. Compiling our software produces two command-line tools prove and verify, which use a simple ASCII-based interface to communicate the data contributed to the trusted setup.

The implementation closely follows the strategy outlined in Sect. 4.2. This includes the choices $d=(2^a)^w$ and $\ell ^n=(3^b)^h$; thus, both the witness and the commitment isogenies are uniformly random cyclic isogenies of degree d and $\ell ^n$ respectively. To reduce latency, we additionally exploit parallelism: Recall that the proof of knowledge is repeated many times to achieve a low soundness error; indeed most of the computations are independent between those repetitions and can thus easily be performed at the same time on a multi-core system. This is confirmed by experimental results, where our implementation is observed to parallelize almost perfectly when run on an eight-core processor.

Sampling purely random large-degree isogenies with code from SIDH comes with two caveats: First, the sampling of “small” squares must avoid backtracking between the individual squares being glued to ensure that the composition is cyclic in the end; in both cases this is done by keeping track of the kernel of the dual of the last prime-degree step of the previous square and avoiding points lying above this “forbidden” kernel when choosing the next square. Besides that, the specific isogeny formulas used in SIDH fail for the 2-torsion point (0, 0), which can be resolved by changing to a different Montgomery model each time this kernel point is encountered. For curves revealed in the proof, the choice of Montgomery model should be randomized to avoid leakage. Similarly, the kernel generators of the horizontal isogeny $\phi '$ also need to be randomized, as Lemma 14 only distinguishes cyclic subgroups and revealing specific generators may leak.

Our software sacrifices some performance for simplicity, which aids auditability and hence helps increase trust in the results of a trusted-setup ceremony. Some unused optimizations: Two-isogenies are faster to compute than three-isogenies, and since the SIDH ladder is taller than wider, swapping the role of two- and three-isogenies in the trusted-setup application could somewhat improve the resulting performance. For simplicity, our implementation also only uses full SIDH squares, and thus all isogeny degrees are rounded up to the closest multiple of an SIDH square; shortening the sides of some of the squares can save time. We also did not apply all optimizations to reduce the proof size. This includes applying SIDH-style compression techniques [20] to the points contained in the proof, cutting their size approximately in half. Moreover, applying a slight bias when sampling the challenges $\textsf{chall}_i$ means smaller responses can appear more often, at the expense of requiring slightly more repetitions; we investigated this tradeoff and determined that the potential improvement is essentially void.

Results. We benchmarked the three algorithms (instance generation, proving, and verification) that make up the zero-knowledge proof of knowledge. We run our tests on an ARM Apple M1 Pro with eight cores, and we averaged the running times of 100 iterations for the parallel implementation and the running times of 50 iterations of the single-core version. The resulting timings are shown in Table 2. They demonstrate that the algorithm is highly practical and can realistically be used within a trusted setup protocol: Generating proofs of knowledge for all four base fields takes less than five core-minutes on a modern CPU. Note that these algorithms need to be run only once per contributor.

Table 2. Benchmarks for instance generation, proving, and verification of our proof of isogeny knowledge for each of the four SIKE finite fields.

Real-World Deployment. We briefly discuss how we intend to deploy the trusted setup protocol proposed in Sect. 5. The goals of such a deployment include include a transparent setup that allows parties to trust the process, a low bar of entry to participate in the protocol, and a secure system that can withstand Sybil and Denial-of-Service (DoS) attacks.

Firstly, we are releasing at https://github.com/trusted-isogenies/ a set of tools that participants can download and run to generate a valid addition to the trusted setup, and for ceremony orchestrators to validate protocol submissions on the server-side. To increase user trust, we also provide higher-level versions (e.g., in SageMath) of some components. Moreover, the proof format is made public, so that any party can—if they choose to—re-implement the algorithms and generate a compatible proof.

Then, we propose leveraging the existing infrastructure of git and GitHub to host our distributed protocol. Thus, each party $E_i$ can generate a random walk from the latest curve $E_{i-1}$ to a new curve $E_{i}$, generate a PoK of their secret isogeny walk, and submit the new curve and the PoK to the server as a pull request (PR). The server is a separate git repository and execution environment maintaining the sequence of curves and the proofs, with checks that are run automatically against submissions from parties. The repository automation verifies that the submitted PoK of the isogeny between the current curve $E_{i-1}$ at the end of the walk (the ‘tip’ curve) and the new proposed curve $E_{i}$ is valid, and that the PR does not rewrite any previous history. If the checks pass, the PR is rebased on top of the main branch, adding the new PoK of the latest hop, and updating the tip curve to $E_i$. New parties in the protocol will generate isogeny walks starting from the new tip curve.

If the chain of isogenies diverges, i.e. if some party submits a new curve and PoK starting from a curve other than the tip, the new submission is rejected. This may happen when several parties try to contribute at the same time. To minimize the amount of wasted prover work, we parallelize verification and reject invalid proofs as early as possible.

The configuration for the continuous integration checks is maintained in a separate repository to prevent modification from protocol parties. Hosting the protocol on GitHub raises the bar to Sybil attacks, as it requires all parties to have a GitHub account with a verified email address. Using our tool requires generation of a GitHub personal access token to authenticate when generating the submission, which further complicates automation/collusion.

The end result of the protocol is a public git repository whose final commit contains a sequence of curves and valid PoKs of isogenies between them, the last of which is the final Secuer $E_{t}$, a curve with unknown endomorphism ring, in a parsable hex encoding. Anyone can pull down this artifact and verify the sequence of curves and proofs independently if they wish.

7 Conclusion

In this work, we analyzed a distributed Secuer generation protocol, and proposed a concrete instantiation with strong security guarantees based on a novel proof of isogeny knowledge. To demonstrate the practical feasibility of our protocol, we are going to run a distributed Secuer generation ceremony, scaling to hundreds of participants, using the technology outlined in Sect. 6.

Our new PoK is especially well-suited for SIDH-like base fields, but can be used reasonably well with fields $\mathbb {F}_{p^2}$ of any characteristic. Generic ZK proof systems, such as the SumCheck protocol used in [18], would be an alternative to our PoK. After this work was published, Cong, Lai and Levin [19] designed an R1CS encoding of 2-isogeny walks that they fed to various generic proof systems. Their results show that Aurora [6], in particular, can be quite competitive, giving a measurable speed boost at the cost of a moderate increase in proof size. Currently, the question of which proof system to use appears to be context-dependent.

None of the currently known techniques are particularly well suited for proving knowledge of an isogeny walk over $\mathbb {F}_p$: our PoK and generic proof systems are much more efficient when the walks consist of isogenies of small degree such as 2 or 3, which is not possible over $\mathbb {F}_p$. SeaSign-like techniques [24, 29] are at least one order of magnitude slower than our PoK, and scale much worse. CSI-FiSh [8] is reasonably efficient, but limited to the base field of CSIDH-512. We think generating Secuers over $\mathbb {F}_p$ efficiently is an interesting open problem.

To show the security of the proof of knowledge, we developed the theory of supersingular isogeny graphs with level structure, in particular proving that they possess the Ramanujan property. In this work we only focused on the so-called Borel level structure, however similar properties can be proven for more general level structures. In a follow-up work, we will develop the general theory of these graphs, prove bounds on their eigenvalues, and discuss consequences for isogeny-based cryptography.