1 Introduction↩︎

Onion routing is a privacy-enhancing network protocol whose primary goal is anonymity. Beyond transport security, it uses layered encryption so no single relay can link sender to destination. Onion routing anonymises network traffic by wrapping it in multiple layers of encryption and sending it through a short chain of relays (guard \(\rightarrow\) middle \(\rightarrow\) exit). Each relay peels one layer and knows only the next hop, so no single node can link source and destination. If sufficient network traffic is present, this ensures that an outside observer can only link the sender of a message to the guard server and the receiver to the exit server, but tracking the communication through the network is difficult. Thus, onion routing not only keeps the message hidden but also hides who is communicating with whom.

A quantum analogue of onion-routing encounters challenges intrinsic to quantum computing. First and foremost, the fact that every quantum operation is unitary implies that any operation performed on a state is reversible with relative ease. Thus, any cryptographic setup in which the message is encoded as a state and the encryption works as a function (determined by the key) on the message state is necessarily a symmetric encryption scheme. Public key encryption in a quantum computing setting therefore (up to further complications) has the key as a state and the message defining the operation performed, or has a fixed state and both key and message define the operation. The decryption process then relies on identifying which operation was performed by the sender and reconstructing the message from that information. Although theoretically possible, such an asymmetric encryption scheme cannot easily be layered, if the message is a genuine quantum state (as opposed to a bit-state encoded in qubits).

The main goal of this paper is to overcome these problems, and design a quantum onion routing through layered symmetric quantum encryption. We achieve this by basing each layer on the ideal class group action from Number Theory, and specifically from the Theory of Complex Multiplication. The associated group-action inversion (vectorization) problem remains hard even for quantum adversaries, and underpins post-quantum schemes such as CSIDH [1]. “Local session keys” are generated via Diffie-Hellman key exchange for neighboring nodes in the chain of communication. Furthermore, we propose a method of communicating a “global session key” chosen by the sender to the receiver that allows for the final decryption step.

Of course, many of the individual components of the proposed quantum onion routing scheme can be replaced with quantum encryption schemes that serve a similar role. E.g., local session keys can be established using quantum key distribution and the global session key encryption layer can be replaced with a quantum public key encryption layer. However, it is advantageous to base the entire scheme on a single underlying problem, such as for ease of implementation. This means that all encryption layers need to use compatible schemes. The isogeny-based post-quantum cryptography scheme chosen allows for exactly that while it is also possible to use the same scheme for classical encryption problems. Thus, the here proposed quantum onion routing scheme is also more easily compatible with larger systems requiring both classical and quantum cryptographic schemes.

Incidentally, this also allows us to further develop the intersection of post-quantum cryptography with quantum computing. A secondary goal of this paper is therefore to implement an isogeny-based post-quantum cryptographic scheme within a quantum-computing-based protocol and execution routine.

The paper is structured as follows. In Section 2 we provide a brief account of the main facts and definitions from the Theory of Complex Multiplication necessary to understand the rational behind our quantum onion routing construction (QOR). Section 3 lifts the problem to the path-finding problem on isogeny graphs and discusses security assumptions. Section 4 connects isogeny graphs to association schemes and their Bose–Mesner algebra, yielding two implementation paths for QOR. The first uses a universal quantum oracle that evaluates the class group action with polynomially many quantum resources. We also outline a second, more intrinsically quantum route based on continuous-time quantum walks (CTQWs) [2], [3]; this line is developed in a companion work and not pursued further here. Section 5 presents a fully worked Qiskit example—deliberately small and exponential in resources—whose purpose is to make the mechanics of QOR explicit. Finally, Section 6 briefly discusses certain security considerations in classical vs.quantum settings.

2 The Ideal Class Group Action↩︎

For any given fundamental discriminant \(\Delta < 0\), we denote by \(K_{\Delta} = \mathbb{Q}(\sqrt{\Delta})\) the corresponding imaginary quadratic number field, and by \(Cl(\mathcal{O}_{\Delta})\) the ideal class group of the maximal order \(\mathcal{O}_{\Delta}\). We write \(h(\Delta) = |Cl(\mathcal{O}_{\Delta})|\) for the class number. Associated to \(Cl(\mathcal{O}_{\Delta})\) is the maximal abelian unramified extension \(H_{\Delta}\) of \(K_{\Delta}\), known as the Hilbert Class Field of \(K_{\Delta}\).

Fundamental results from Class Field Theory and the Theory of Complex Multiplication yield the following important result:

The action of the fractional ideals on the roots of \(H_{\Delta}\) defined in the Theorem 1 above, is what is referred to in cryptography as the class group action. Together with Deuring’s Theorems (e.g., [5] and [4]), which enable the transition from characteristic zero to characteristic \(p\) and vice-versa, are the key ingredients that make isogeny-based cryptography built on the ideal class group action, possible. In the ordinary case in particular, where \(H_{\Delta}\) splits completely in \(h(\Delta)\)-many distinct roots over \(\mathbb{F}_{q}\), an elliptic curve in characteristic zero with \(j\)-invariant a root of \(H_{\Delta}\) and an elliptic curve in characteristic \(p\) with \(j\)-invariant a root of \(H_{\Delta}\bmod q\) have isomorphic endomorphism rings. Furthermore, the class group action in characteristic zero respects this isomorphism, and we observe the same class group action on the roots of \(H_{\Delta}\) modulo \(q\).

Even in the supersingular case, if instead of the full ring of endomorphisms, which is non-commutative, we consider the subring of \(\mathbb{F}_p\)-rational endomorphisms, this subring is again an order in an imaginary quadratic field and the ideal class group action applies as above. The advantage is that now the supersingular elliptic curves \(E/\mathbb{F}_p\) have known trace \(t=0\) and known number of points \(|E(\mathbb{F}_p)| = p+1\). Hence, with the right choice of a prime \(p\) we can have \(\mathbb{F}_p\)-rational isogenies of desired degree \(\ell\), as long as \(\ell | p+1\). That is why the existing cryptographic schemes based on the ideal class group action, such as CSIDH [1] and SCURF [6], employ supersingular curves.

The one-to-one correspondence between the classes \([\mathfrak{a}]\) of the ideal class group \(Cl(\mathcal{O}_{\Delta})\) and the homothety classes of lattices \([\Lambda_{\mathfrak{a}}] \cong [\langle 1 , \tau_{\mathfrak{a}} \rangle]\) with \(\mathcal{O}_{\Delta}\) as their full ring of complex multiplication [7] was employed by the authors of [8] in order to show that the isogeny graph \(G_{\Delta,S,q}(J_{\Delta},E_{S})\) is isomorphic to the Cayley graph \(\mathcal{G}(Cl(\mathcal{O}_{\Delta}),S)\), for some set \(S\) that does not contain the identity element and is closed under inversion. The set of vertices \(J_{\Delta} = \{j_1 , ... , j_{h(\Delta)}\} \subseteq \mathbb{F}_{q}\) contains the \(h(\Delta)\)-many distinct roots of \(H_{\Delta}\) modulo \(q\). Every edge \((j_1,j_2) \in E_{S}\) corresponds to an isogeny between elliptic curves \(E_{1}, E_{2}\) with corresponding \(j\)-invariants \(j_1, j_2 \in J_{\Delta}\). The degree of any such isogeny equals some positive integer \(b\) such that \(b=\text{Norm}_{K_{\Delta}/\mathbb{Q}}(\mathfrak{b})\) for some ideal \(\mathfrak{b} \in S\). When we include in \(S\) all ideals of prime norm less than some fixed bound \(M \geq (\log |\Delta|)^{B}\), for some absolute constant \(B > 2\) then, assuming GRH, the isogeny graph \(G_{\Delta,S,q}\) becomes an expander graph [8].

3 Walks on Isogeny Graphs↩︎

3.1 The Cayley Graph of the Ideal Class Group↩︎

As the ideal class group of a number field is a finite abelian group and the isogeny graphs are isomorphic to Cayley graphs of the underlying ideal class group, we focus our attention on Cayley graphs of finite abelian groups. For the basic facts and definitions that we quote in the following, we follow mainly [9] and [10].

Let us denote by \(\Gamma\) any finite abelian group written multiplicatively, and with identity element \(1_{\Gamma}\). Let \(1_\Gamma \notin S \subseteq \Gamma\) be any subset that is closed under taking inverses. Then the Cayley Graph \(\mathcal{G}(\Gamma,S)\) is the graph with vertex set \(V(\mathcal{G}) = \Gamma\) and edge set \[E(\mathcal{G}) = E(\mathcal{G}(\Gamma,S)) = \{gh \;| \;hg^{-1} \in S\}.\]

A subgraph \(\mathcal{G}'\) of \(\mathcal{G}\) is a graph with \(V(\mathcal{G}') \subseteq V(\mathcal{G})\) and \(E(\mathcal{G}') \subseteq E(\mathcal{G})\). In the case where \(V(\mathcal{G}') = V(\mathcal{G})\), \(\mathcal{G}'\) is called a spanning subgraph of \(\mathcal{G}\).

The graph \(\mathcal{G}(\Gamma,S)\) is an undirected graph with no loops. It is, as expected, vertex-transitive. Recall from above that \(G_{\Delta,S,q}(J_{\Delta},E_{\Delta}) \cong \mathcal{G}(Cl(\mathcal{O}_{\Delta}),S)\) and the ideal class group action on \(J_{\Delta} \equiv V(\mathcal{G}(Cl(\mathcal{O}_{\Delta}),S))\) is free and transitive. Vertex-transitive graphs are regular; i.e. each vertex has the same number of edges \(k \leq |S|\). This integer \(k\) is called the degree. When we choose \(S\) to be a generating set for \(\Gamma\), then the graph is connected.

The Adjacency matrix \(A(\mathcal{G})\) of the connected undirected regular graph \(\mathcal{G}(\Gamma,S)\) is the \(n\times n\) real symmetric matrix, with entries \(a_{i,j} = 1\) if \((v_i,v_j) \in E(\mathcal{G})\) and \(a_{i,j} = 0\) if \((v_i,v_j) \notin E(\mathcal{G})\). As a real symmetric matrix, \(A(\mathcal{G})\) has real eigenvalues \(\lambda_n \leq \cdots \leq \lambda_1 = k\), where as above, \(k\) is the degree. Each eigenvalue of \(A\) can be given in the form \[\lambda_{\chi} = \sum_{s \in S} \chi(s), \;\chi \in \hat{\Gamma},\] where as customary \(\hat{\Gamma}\) denotes the character group of the finite abelian group \(\Gamma\), which is isomorphic (non-canonically) to \(\Gamma\) and hence it is of the same cardinality \(n = |\Gamma| = |\hat{\Gamma}|\). Thus, the spectrum of \(\mathcal{G}(\Gamma,S)\) consists of character sums ranging over the generating set \(S\).

3.2 Random Walks↩︎

As we mentioned in Section 2, in the case of isogeny graphs \(\mathcal{G}_{\Delta,S,q}\) and for an appropriate set \(S\), the result of [8] guarantees that these graphs become expander graphs. In terms of the eigenvalues, what this result yields is a bound on the spectral gap. More specifically, the absolute value of every eigenvalue \(\lambda \neq \lambda_1\) should be of the order \(|\lambda| = O((\lambda_1\log \lambda_1)^{1/2+1/B})\) for some absolute constant \(B > 2\), and \(M \geq (\log |\Delta|)^{B}\) is such that \(S = S_{M} = S_{M}^{-1}\) contains the ideals of prime norm up to \(M\). With such a choice of \(S\), there exists a constant \(C>0\) such that any walk on \(\mathcal{G}_{\Delta,S,q}\) of length \[\label{eqn:WalkLength} t \;\ge\; C\,\frac{\log |Cl(O_{\Delta})|}{\log\log q}\tag{1}\] is well mixed.

Assume for simplicity that \(Cl(O_{\Delta}) \cong \mathbb{Z}/r\mathbb{Z}\) is cyclic of odd prime order \(r\). In implementation terms, for a walk of length \(t\) on the associated isogeny graph, choose some generator \(g \in Cl(O)\) and also choose uniformly at random \(k = C\lceil \log r \rceil\) exponents \(c_1,\ldots,c_k \in (\mathbb{Z}/r\mathbb{Z})^{\times}\), sample a random word \(w=(c_{s_1},\ldots,c_{s_m})\) with \(s_\ell \in \{1,\ldots,k\}\), and form the class-group element \[\label{eqn:RandomElement} g^{\,e}, \qquad e \equiv \sum_{\ell=1}^{m} c_{s_\ell} \pmod r.\tag{2}\] This random element \(g^e\) is then used for the class group action on the given \(j\)-invariant, say \(j_0\), to yield the end-point \(g^e * j_0 = j_1\) of the walk.

We rely on the vectorization (group-action inversion) problem for the ideal class group action, which is believed to remain hard even for quantum adversaries. Concretely: given a pair of \(j\)-invariants \((j_0,j_1)\), it is not possible in quantum polynomial time to recover the secret \(g^e\in \mathrm{Cl}(\mathcal{O}_\Delta)\) such that \(g^e * j_0 = j_1\). Equivalently, one cannot efficiently reconstruct a path (walk) on the underlying isogeny graph \(\mathcal{G}_{\Delta,S,q}\) connecting \(j_0\) to \(j_1\).

In Section 4.2 we describe these isogeny graphs via association schemes and their Bose–Mesner algebra, with emphasis on the cyclic, prime-order case; in this setting the graph is a disjoint union of undirected \(r\)-cycles. This perspective both places the path-finding problem in an algebraic–spectral context and sets the stage for a parallel line of work in which we exploit this structure to implement our quantum onion routing via CTQWs.

4 Quantum Onion Routing based on the ideal class group action↩︎

The main goal of this paper is to construct a quantum onion routing scheme based on the ideal class group action. Without loss of generality, we present our construction in the ordinary case and, as we already discussed in Section 2, the same ideas readily extend to the supersingular setting, in the same way as CSIDH and CSURF extended the original CRS in the Diffie–Hellman context.

Given \(\Delta\), \(p\) and \(a >0\), the ideal class group \(Cl(\mathcal{O}_{\Delta})\) can be computed in quantum-polynomial time [11]. We choose \(\Delta\) so as \(Cl(\mathcal{O}_{\Delta})\) has a large-enough, for security reasons, cyclic part. Such discriminants are not hard to find since, according to the Cohen-Lenstra Heuristics [12], the odd part of the class group of imaginary quadratic number fields is cyclic with probability \(\sim 97.7575\ldots \%\).

In order to simplify our scheme and notation, from now on we will assume further that \(Cl(\mathcal{O}) \cong \mathbb{Z}/r\mathbb{Z}\), for \(r\) a large prime of exponential size, and that \(a=1\); i.e. \(q=p\). The set \[J = \{j_i : 0 \leq i \leq r-1\} \subset F_p\] contains the \(r = |Cl(\mathcal{O})|\)-many \(j\)-invariants. The corresponding isogeny graph is isomorphic to the Cayley graph \(\mathcal{G}_r \mathrel{\vcenter{:}}= \mathcal{G}(Cl(O_{\Delta}),S) \cong \mathcal{G}(\mathbb{Z}/r\mathbb{Z},S)\), for a spanning set \(S \subset Cl(O_{\Delta})\); i.e. we include in \(S\) all ideals of prime norm less than some fixed bound \(M \geq (\log |\Delta|)^{B}\), for some absolute constant \(B > 2\), as we discussed in the end of Section 2.

In this prime-order case, every non-trivial subgraph is a spanning subgraph of \(\mathcal{G}_r\), and a random element \(g^e\), as in Equation 2 , is a walk on such a graph comprised of \(O(\log r)\)-many \(r\)-cycles. As the ideal class group action is commutative 2 and injective (see, e.g. [13]), layered encryptions are possible also in the quantum setting, as reversibility is guaranteed.

A naive sketch of the protocol, with only three users present for simplicity, is outlined below in Procedure 1. These three users will be called Alice (sender), Bob (intermediary), and Carol (receiver).

In terms of implementation, there are two fundamental issues. Firstly, we need to specify how to apply the class group action \(*\) and how to deal with the exponentially large isogeny graph. Secondly, we need to specify where and how to hide Alice’s message. The subsequent sections are devoted to answering these questions.

4.1 The Message Encryption↩︎

Let \(|m\rangle\in\mathcal{M}\) be the quantum message in the message space \(\mathcal{M}\) of dimension \(2^N\). To each \(j\)-invariant \(j \in J_{\Delta} \subseteq \mathbb{F}_p\), which can be represented by \(\log p\)-many qubits, we can associate a quantum circuit \(C(j)\) on \(N\)-qubits as follows: \[\label{Circuit}C(j)=\bigotimes_{k=0}^{N-1}R_X(\vartheta_{k}(j)).\tag{3}\] For the angles \(\vartheta_{k}(j)\), we take a fixed \(N\)-dimensional (scrambled) Sobol’ sequence \(S\), choose Sobol’ point \(S_{2^{K}+j}\), and \(\vartheta_k(j)\) is \(2\pi\) times the \(k\)-th coordinate of the Sobol’ point. Since the Sobol’ points are more uniform, the potential rotation angles are uniformly distributed in the parameter space. To make this as uniform as possible, we want the band \([2^K,2^K+p]\) to be as close to \([2^K,2^{K'}]\) as possible; i.e., \(p\approx 2^K\) gives the band \([2^K,2^{K+1}]\), which is the case for our cryptographic construction since \(p\) needs to be of exponential size.

Going back to step (4) of the naive Procedure 1 above, Alice could send to Bob \[(j_{ABC},\mathcal{C}(j_A)|m\rangle),\] where \(|m\rangle \in \mathcal{M}\) is her secret message. Bob can undo his encryption and send \[(j_{AC},\mathcal{C}(j_A)|m\rangle)\] to Carol, and once Carol obtains \(j_A\), then she can read Alice’s message by using the inverse circuit, i.e. \[C(j_A)^{-1}C(j_A)|m\rangle.\] We notice however that the hidden message \(\mathcal{C}(j_A)|m\rangle\) remains the same throughout the channel. Even though quantum data cannot be cloned nor observed without tampering, one can still make imperfect copies of this message and, in case they obtain a big overlap, then the communications channel will be reveled. To address this issue, we propose the following variant that makes use of an additional Diffie–Hellman setup.

Every user in the network has an established shared secret key with their neighbor (either via quantum or classical computation). The secret shared key is another \(j\)-invariant derived through Diffie–Hellman using the class group action. In this scenario, the exchange can proceed as shown in Procedure 2:

In the next section we will define Association schemes with respect to isogeny graphs - a viewpoint that clarifies and streamlines the implementation of the ‘quantum’ class group action.

4.2 Cyclic Association Schemes and their Bose-Mesner Algebra↩︎

In this section we collect basic facts and definitions for cyclic association schemes and their Bose-Mesner Algebra, noting that many of these facts may still hold for association schemes in general. For more details the interested reader may refer to [14], or to [3] for a more concise account.

For any integer \(n \geq 3\) we denote by \(\mathcal{C}_{n}\) the cycle-graph of length \(n\). It is a Cayley graph over \(\mathbb{Z}/n\mathbb{Z}\) with generating set \(\{1,n-1\}\) (modulo \(n\)). We let \(d = \lfloor \frac{n}{2} \rfloor\) and for \(0 \leq r \leq d\) we consider the following adjacency matrices \(A_{r}\), where the indices of the matrices are computed modulo \(n\): \[(A_{r})_{j,k} = \begin{cases} 1; \;\text{if} \;j-k \in \{r,-r\} \\ 0; \;\text{o.w.} \end{cases}.\] For any matrix \(M\) we denote by \(M^{t}\) its transpose. We denote by \(A_{0}\) the \(n\times n\) identity matrix and by \(J = J_{n}\) the all-ones matrix. We notice that \(A_{1}\) is the adjacency matrix of \(C_{n}\). The set of matrices \[\mathcal{A}_{n} = \{A_{0},\ldots,A_{d}\}\] can be proven to form a special type of a symmetric \(d\)-class association scheme (e.g. [3]), known as the cyclic association scheme of order \(n\).

Cyclic symmetric association schemes in particular, enjoy further properties, which we summarize in the following remark.

Given a symmetric association scheme \(\mathcal{A}\), Definition 4 implies that the algebra \(\mathbb{C}[\mathcal{A}]\), known as the Bose-Mesner algebra of \(\mathcal{A}\), is a commutative algebra of dimension \(d+1\). It is a known result that all matrices of \(\mathcal{A}_d\) are simultaneously diagonalizable (see, e.g. [14]), hence every \(A \in \mathcal{A}_d\) can be written as \[\label{eqn:decompn} A= \sum_{1\leq s \leq d} \theta_s E_s \;\in \mathcal{A}_d,\tag{4}\] where the set \(\{E_0, E_1, \ldots, E_d\}\) is the set of spectral idempotents of the association scheme. In the special case of a cyclic symmetric association scheme, each \(E_s\) is is given by \[E_s = \begin{cases} \frac{1}{n}\sum_{k=0}^{n-1} (\omega^{kr} + \omega^{-kr}) \mathcal{C}^k; \;1 \leq s \leq \lfloor n/2 \rfloor \\[0.3cm] \frac{1}{n} \sum_{k=0}^{n-1} \omega^{kr} \mathcal{C}^{k}; \;s \in \{0, n/2\}. \end{cases}\]

An isogeny graph \(\mathcal{G}_r=\mathcal{G}_{\Delta,S,q}\) with ideal class group \(\mathrm{Cl}(\mathcal{O}_\Delta)\cong \mathbb{Z}/r\mathbb{Z}\) (with \(r\) an odd prime) can be written as the edge–disjoint union of \(|S|/2\) undirected \(r\)-cycles. In particular, if \(|S|=\Theta(\log r)\), the graph is a union of \(\Theta(\log r)\)-many \(r\)-cycles \(A_s \in \mathcal{A}_d\). A walk on \(\mathcal{G}_r\) corresponding to the element \(g^e\) of 2 is a sequence of \(m\)-many steps \(c_s\), each one of them carried along one of these \(r\)-cycles.

In the next section we analyze these isogeny graphs through the lens of association schemes and their Bose–Mesner algebra, and we discuss isogeny graphs with respect to a purely quantum form of computing, namely that of continuous-time quantum walks (CTQW), before we continue to the implementation of our QOR via a universal quantum oracle, which we define in Section 4.5.

4.3 Isogeny Graphs and Unitaries↩︎

Let us fix a fundamental discriminant \(\Delta\) and a good prime \(p\) that splits the Hilbert Class polynomial completely into \(h(\Delta)\)-many distinct roots over \(\mathbb{F}_{q}\), \(q = p^a\) for some \(a \in \mathbb{N}\). Any subgraph of \(\mathcal{G}\equiv \mathcal{G}(Cl(\mathcal{O}_{\Delta}),S)\) has an associated adjacency matrix \(A\), which forms the Hamiltonian of the quantum system determined by the unitary operator \[U_{A}(t) = e^{-itA},\] also known as the time evolution operator. The time evolution is described by \[|\psi(t)\rangle = e^{-itA}|\psi(0)\rangle,\] where we follow the physicists’ notation and write column vectors \(\psi \in \mathbb{C}^{n\times1}\) as kets \(|\psi\rangle\).

The unitary \(U_A(t)\) corresponds to a walk on the graph with adjacency \(A\), for time \(t\). In isogeny-based schemes this would correspond to the secret walk of a user on the isogeny graph with adjacency \(A\). As the underlying ideal class group action is commutative 2, the walks are also expected to commute and hence the unitaries are expected to commute. This claim can also be verified rigorously, since one can show that the unitaries lie in the commutative Bose-Mesner Algebra.

One can now express the walk on the isogeny graph induced by the action of the element \(g^e, \;e \equiv \sum_{\ell=1}^{m} c_{s_\ell} \pmod r\) of Equation 2 , in terms of unitaries, as follows: \[\label{eqn:AdjacencyElement} g^e * j_0 \equiv \prod_{\ell = 1}^{m}U_{c_{s_{\ell}}}(t_{s_{\ell}}) |j_0\rangle.\tag{6}\]

Further study of the isogeny walk via a CTQW is being carried out in a parallel project. In the next section we assume the existence of a universal oracle for the class group action and describe in detail how the QOR protocol runs under this assumption, leaving the discussion for the quantum oracle in the last subsection, Section 4.5.

4.4 Isogeny graphs in superposition↩︎

As above, we assume for simplicity that \(Cl(\mathcal{O}) \cong \mathbb{Z}/r\mathbb{Z}\), for \(r\) a large prime of exponential size. The set \[J = \{j_i : 0 \leq i \leq r-1\} \subseteq \mathbb{F}_p\] contains the \(r\)-many \(j\)-invariants associated with \(Cl(\mathcal{O})\), and \(j_{0} \in J\) is a fixed public \(j\)-invariant. The corresponding cyclic association scheme \(\mathcal{A}_{d}\), is of order \(d = \frac{r-1}{2}\), also of exponential size.

When Bob notifies Carol that somebody wants to send her a message,

1. Carol chooses and keeps secret a random element \(\mathfrak{c} = g_C^{e_C} \in \mathrm{Cl}(\mathcal{O})\), constructed as discussed above. The associated isogeny graph corresponding to the action of \(\mathfrak{c}\) on the \(j\)-invariants of the set \(J\) is represented by an adjacency matrix, which we denote by \(C\), and \(C \in \mathcal{A}_d\).

2. Carol furthermore chooses two secret values \(\omega,\Omega\in\mathbb{Z}/r\mathbb{Z}\) satisfying \(0\le\omega<r\) and \(0\le\Omega<r-\omega\). Here we assume both \(\omega\) and \(\Omega\) to be of polynomial size, although this restriction can be lifted relative to a “global mapper oracle”, cf. Section 4.5. Carol prepares a uniform superposition over \(i \in \mathbb{Z}/\Omega\mathbb{Z}\) \[\frac{1}{\sqrt{\Omega}} \sum_{i=0}^{\Omega-1} |i\rangle.\]

3. She then loads \(\left|{j_0}\right\rangle\) into another register and applies her unitary operator \(U_C\), which we can interpret as a quantum oracle \(f_C\), that computes in quantum parallelism the class group action, \(*\), and gives the resulting \(j\)-invariant \[|i\rangle\otimes|j_0\rangle \mapsto |i\rangle\otimes|f_C(j_0)\rangle = |i\rangle\otimes|\mathfrak{c}^1 * j_0\rangle = |i\rangle\otimes|j_1\rangle.\] Applying the oracle \(\omega\) times, yields the resulting state \[\frac{1}{\sqrt{\Omega}} \sum_{i=0}^{\Omega-1} |i\rangle\otimes|j_\omega\rangle.\]

4. Finally, Carol applies a “mapper oracle” as shown in Figure 3. This mapper oracle¹ applies her oracle \(i\) many times if the control register is in the state \(\left|{i}\right\rangle\). The resulting state is \[\frac{1}{\sqrt{\Omega}} \sum_{i=0}^{\Omega-1} |i\rangle\otimes|j_{i+\omega}\rangle.\]

   If possible in practical implementations, Carol should retain the index-register (containing the \(\left|{i}\right\rangle\) factor) at all times. However, the communication scheme remains secure if both the index- and \(j\)-register qubits are sent during the protocol. For simplicity, we will assume that Carol retains the index-register.

5. Carol sends the quantum state \[|\psi_0\rangle = \frac{1}{\sqrt{\Omega}}\sum_{i=0}^{\Omega-1}|j_{i+\omega}\rangle,\] which corresponds to a part of the isogeny-cycle in superposition produced by the element \(\mathfrak{c} \in Cl(O_{\Delta})\) acting on the set \(J\), to Bob.

6. In the same way, Bob chooses \(\mathfrak{b} = g_B^{e_B} \in Cl(O_{\Delta})\), which corresponds to his adjacency \(B \in \mathcal{A}_d\). His associated quantum oracle \(f_B\) computes the class group action, i.e. \[f_B(j) = \mathfrak{b}*j,\] and Bob computes and sends to Alice the following state \[|\psi_1\rangle = \frac{1}{\sqrt{\Omega}} \sum_{i=0}^{\Omega-1} |f_B(j_{i+\omega})\rangle.\]

7. Similarly, Alice chooses her secret \(\mathfrak{a} = g_A^{e_A} \in Cl(O_{\Delta})\), corresponding to some adjacency matrix \(A \in \mathcal{A}_d\), and with her quantum oracle \(f_A\) computes her class group action. She also attaches the message \(|m\rangle\) which is encrypted with the circuit \(C(j_A)\), \(j_A = \mathfrak{a} * j_0\), (preventing Bob from reading the message) and the transport encryption layer \(C(j_{ab})\) (preventing tracking of the message). Thus, she sends the following state \[|\psi_2\rangle = \frac{1}{\sqrt{\Omega}} \sum_{i=0}^{\Omega-1} |f_A(f_B(j_{i+\omega}))\rangle \otimes C(j_{ab})C(j_A)|m\rangle\] back to Bob.

8. Bob undoes his oracle \(f_B\) on the \(j\)-invariants register, modifies the message as discussed in Section 4.1, and obtains \[|\psi_3\rangle = \frac{1}{\sqrt{\Omega}} \sum_{i=0}^{\Omega-1} |f_A(j_{i+\omega})\rangle \otimes C(j_{bc})C(j_A)|m\rangle\] which he sends on to Carol.

9. Carol removes the transport encryption layer \(C(j_{bc})\) from the message and splits the message register off. Combining the \(j\)-invariants register with the index-register again, she obtains two separate quantum states; the still encrypted message \(C(j_A)|m\rangle\) and the key information state \[|\psi_4\rangle=\frac{1}{\sqrt{\Omega}} \sum_{i=0}^{\Omega-1} |i\rangle\otimes|f_A(j_{i+\omega})\rangle.\]

10. Carol now measures the key information state \(|\psi_4\rangle\) and obtains a random state \(|i\rangle\otimes|f_A(j_{i+\omega})\rangle\). From this, she can compute \(j_A=\mathfrak{c}^{-i-\omega}f_A(j_{i+\omega})\) either classically or using her oracles (as we will in Section 5).²

11. Finally, Carol can now apply \(C(j_A)^{-1}\) to the message register and retrieve Alice’s secret message \(|m\rangle\).

4.5 A Universal Quantum Oracle↩︎

The ideal class group \(Cl(O_{\Delta})\) of an imaginary quadratic number field is isomorphic to the so-called form class group of primitive positive definite binary quadratic forms of discriminant \(\Delta\) (see, e.g. [7]). The explicit isomorphism allows for a straightforward transition between the elements of the two groups. As a result, one can work in the form class group instead, which yields a very efficient arithmetic in the group, when considered as composition of forms. An algorithm of Schönhage [15] gives the time for reduction as well as composition of forms to be \[\label{eqn:time1}O(m(|\Delta|) \log |\Delta|) \sim O(\mathrm{poly} \log |\Delta|),\tag{7}\] where \(m(|\Delta|) \leq \log(|\Delta|)^2\) denotes the time for multiplication of two integers of size \(\sim |\Delta|\).

As above, we assume that the class group \(G\) is cyclic of prime order \(r\). Given any \(g \in G\) and \(1\leq s \leq r\), we can perform exponentiation \(g^s\) by repeated squaring (see the Circuit in Figure 4), and together with equation 7 above, yield the total time \[\label{eqn:time2} O(\log s \;\mathrm{poly} \log |D|) \sim O(\mathrm{poly} \log r).\tag{8}\]

Denote by \(U(g,j)\) the global oracle \[U: Cl(O_{\Delta}) \times J_\Delta\rightarrow J_\Delta\] \[(g,j) \mapsto g*j,\] which is injective in each argument given the properties of the class group action, but of course it is not jointly injective.

Each user computes their random element, which is of the form \(g^e\) as in Equation 2 , and applies this global oracle accordingly. As the exponent \(e\) is of size \(O(\log r)\), we need \(O(\log r)\)-many controlled \(U(g^{2^k},-)\) gates, and the total time for this global oracle, given Equations 7  & 8 , remains at \(O(\mathrm{poly} \log r)\). Like everywhere else in the paper, we do not analyze the runtime of the class-group action per se (or isogeny computation), as implementations are an active research area with steadily improving results.

Now, given such a global oracle, the restrictions on \(\omega\) and \(\Omega\) to be of polynomial size can be lifted, and arbitrary sub-intervals of the entire cycle corresponding to the chosen element \(g^e\) can put in superposition, including the entire cycle itself. With the entire cycle in superposition, the protocol can be formed as shown in Procedure 5.

5 An Example Implementation with \(5\) actors↩︎

In this section we present a fully worked, minimal Qiskit example with five actors A, B, C, D, and E. Here, A wants to send a message to E with B, C, and D acting as intermediaries similar to the classical TOR protocol. For simplicity, we will only cover the key information part of the protocol as the message part is equivalent to classical Diffie-Hellman exchanges and applying simple circuitry for scrambling. We also remove the classical communication overheads of setting up communications channels between actors.

For simplicity, we will implement the class group action oracles by classically pre-computing the corresponding cycles and implementing the corresponding shift operators. The direct implementation of these oracle gates is beyond the scope of this implementation as we want to focus on the communication part of the protocol.

For this example, we choose the ideal class group of the imaginary quadratic number field \(\mathbb{Q}(\sqrt{-167})\), which is of order \(11\). The corresponding Hilbert Class Polynomial has very large coefficients but it splits completely into eleven linear factors over the finite field \(\mathbb{F}_{311}\). The set of \(j\)-invariants containing its roots is \[J = \{307, 248, 236, 223, 213, 209, 193, 182, 116, 12, 1\} \subset \mathbb{F}_{311}.\]

This example has five, \(\frac{11-1}{2}\), non-trivial undirected cycles, as shown in Figure 6, and we attribute a different one as the secret choice made by each actor. The publicly known \(j_0\) is chosen as \(1\). These computations were performed in PARI/GP [16] and SageMath [17].

For this implementation, we will use Qiskit and load the following libraries.

    import numpy as np
    import copy
    
    from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister, transpile
    from qiskit.circuit.library import PhaseGate, UnitaryGate
    from qiskit_aer import AerSimulator
    from qiskit.visualization import plot_histogram
    
    from <private_library> import basic_comparator

The final library loading basic_comparator is not publicly available at the time of writing this paper. It supplies the comparator \(i<\Omega\) which is required for the oracle in an optional Grover step to filter for only the indices \(i<\Omega\). If \(\Omega\) is chosen as a power of \(2\), this basic_comparator is not required. Its general implementation has been used previously, cf. e.g. in [18], [19].

We may then define the \(5\) cycles and give one to each actor. All cycles are represented to start with the public \(j\)-invariant \(j_0=1\). In an actual implementation using oracles implementing the class group action, explicit knowledge of these cycles is not required.

    aj = [1,213,193,236,209,248,12,182,307,116,223]
    bj = [1,12,213,182,193,307,236,116,209,223,248]
    cj = [1,116,182,248,236,213,223,307,12,209,193]
    dj = [1,236,12,116,213,209,182,223,193,248,307]
    ej = [1,209,307,213,248,116,193,12,223,236,182]

This means that the secret key that A needs to communicate to E is \(j_A=\mathfrak{a}*j_0\) or aj[1]=213.

We choose \(\omega=2\) and \(\Omega=5\) which implies that we require \(Q=\lceil\log_2\Omega\rceil=3\) many qubits for the index register. Similarly, since the field is \(F_{311}\), we require \(N=\lceil\log_2311\rceil=9\) many qubits to represent the \(j\)-invariants. Using the cycles defined above, we can define the oracles that shift one element to the right and act as the identity on non-\(j\)-invariants for all actors and their inverses (the left shifts) for all but A (A’s inverse is not required).

    # defining constants and oracle matrices
    omega = 2 # arbitrarily chosen
    Omega = 5 # < number of j-invariants minus omega, chosen arbitrarily
    N = int(np.ceil(np.log2(max(ej))))
    Q = int(np.ceil(np.log2(Omega)))

    A = np.zeros((2**N,2**N))
    B = np.zeros((2**N,2**N))
    C = np.zeros((2**N,2**N))
    D = np.zeros((2**N,2**N))
    E = np.zeros((2**N,2**N))
    
    for j in range(2**N):
        if j in ej:
            A[aj[(aj.index(j)+1)            B[bj[(bj.index(j)+1)            C[cj[(cj.index(j)+1)            D[dj[(dj.index(j)+1)            E[ej[(ej.index(j)+1)        else:
            A[j,j] = 1
            B[j,j] = 1
            C[j,j] = 1
            D[j,j] = 1
            E[j,j] = 1

    # define qiskit gates from matrices
    UA = UnitaryGate(A)
    UB = UnitaryGate(B)
    UBinv = UnitaryGate(B.transpose())
    UC = UnitaryGate(C)
    UCinv = UnitaryGate(C.transpose())
    UD = UnitaryGate(D)
    UDinv = UnitaryGate(D.transpose())
    UE = UnitaryGate(E)
    UEinv = UnitaryGate(E.transpose())

We also need to implement the mapper oracle for E. However, the relatively large value of \(N\) and the fact that we do not have “real” circuitry for the oracles UE and UEinv, render the construction of the mapper – as described in Figures 3 or 4 – computationally heavy. Instead, we will implement a mapper \(\left|{i}\right\rangle\mapsto \left|{j_i}\right\rangle\) according to E’s cycle. Thus, rather than loading \(\left|{j_0}\right\rangle\) into the \(j\)-register and entangling it with the index register via the mapper, we will create entanglement by producing the state \(\left|{i}\right\rangle\otimes \left|{i}\right\rangle\) and then using the “fake” mapper implementation to obtain \(\left|{i}\right\rangle\otimes \left|{j_i}\right\rangle\). This “fake” mapper necessarily has super-polynomial complexity as otherwise it could be used to break the cryptosystem.

    # mapper implementation not efficient but chosen because turning UE and UEinv into controlled gates is very resource intensive
    ejextended = copy.copy(ej)
    for j in range(2**N):
        if j not in ej:
            ejextended.append(j)
    
    mapper = np.zeros((2**N,2**N))
    for j in range(len(ejextended)):
        mapper[ejextended[j],j] = 1
    
    UM = UnitaryGate(mapper)
    UMinv = UnitaryGate(mapper.transpose())

We can now set up the quantum circuit in Qiskit.

    i_register = QuantumRegister(Q, "i")     # index register
    anc_register = QuantumRegister(1, "anc") # ancilla register for Grover (to make sure indices smaller than Omega)
    j_register = QuantumRegister(N, "j")     # j-invariant register
    
    # corresponding classical registers
    cl_i_register = ClassicalRegister(len(i_register), "cl_i")
    cl_anc_register = ClassicalRegister(len(anc_register), "cl_anc")
    cl_j_register = ClassicalRegister(len(j_register), "cl_j")
    
    # initialize quantum circuit
    qc = QuantumCircuit(
        i_register, anc_register, j_register, 
        cl_i_register,cl_anc_register, cl_j_register
    )
    
    # Step 1: Apply Hadamard to all qubits
    qc.h(i_register)
    qc.barrier()

All of this is executed by E upon being told that they are to receive a message via the quantum onion routing protocol. It should be noted that the ancilla register is only required for values of \(\Omega\) that are not powers of \(2\).

At this point, the current quantum state (ignoring the ancilla qubit) is \(\frac{1}{\sqrt{8}}\sum_{i=0}^{7}|i\rangle\otimes|0\rangle\). In other words, we have an equal superposition of all computational basis states in the index register, and the \(|0\rangle\) state in the \(j\)-invariants register. We now add the optional Grover step to filter for only the states \(i<\Omega=5\).

    # Optional gover circuit if Omega is not a power of 2 
    if Omega<2**Q:
        # Filter out numbers larger than Omega-1. (Marking)
        qc.append(basic_comparator(Q, Omega), list(i_register) + list(anc_register))
        # We clearly now have over 50        
        # So we can use Grover's exact rotation to remove any non-solutions.
        # We know the angle will be:
        theta = np.arccos(1 - (2**Q / (2*Omega)))
        qc.append(PhaseGate(theta), [anc_register[0]])
        
        qc.append(basic_comparator(Q, Omega, reverse=True), list(i_register) + list(anc_register))
        
        # Apply Grover operator
        qc.h(list(i_register))
        qc.x(list(i_register))
        qc.mcp(theta,list(i_register[:-1]), i_register[-1])
        qc.x(list(i_register))
        qc.h(list(i_register))
    
        qc.barrier()

With this Grover step, the current quantum state is now \(\frac{1}{\sqrt{\Omega}}\sum_{i=0}^{\Omega-1}|i\rangle\otimes|0\rangle\) (ignoring the ancilla qubit). As the ancilla is no longer required for any calculations, we will forget about its existence going forward.

Next, E needs to prepare the corresponding \(|j_i\rangle\) for each \(|i\rangle\) in the \(j\)-invariants register. This is done in two steps. First copy \(|i\rangle\) into the \(j\)-register and then apply the “fake” mapper oracle \(|i\rangle\mapsto|j_i\rangle\) to the \(j\)-invariants register. Using the correct mapper as described in Figures 3 or 4, we would need to load \(\left|{j_0}\right\rangle\) into the \(j\)-register and apply the correct mapper to both index- and \(j\)-register to create \(|i\rangle\mapsto|j_i\rangle\).

E also applies the shift with respect to \(\omega\) to produce \(|i\rangle\mapsto|j_{i+\omega}\rangle\).

    # generate equal superposition of all |i,j_(i+omega)> states
    for j in range(len(i_register)):
        qc.cx(i_register[j],j_register[j])
    qc.unitary(UM,j_register,label="UM")
    for _ in range(omega):
        qc.unitary(UE,j_register,label="UE")
    
    qc.barrier()

Thus, E has now created the state \(\frac{1}{\sqrt{\Omega}}\sum_{i=0}^{\Omega-1}|i\rangle\otimes|j_{i+\omega}\rangle\). E should retain the index register and send the \(j\)-register to D who applies their shift.

    # E sends j-register to D, D applies UD    
    qc.unitary(UD,j_register,label="UD")

This creates the state \(\frac{1}{\sqrt{\Omega}}\sum_{i=0}^{\Omega-1}|i\rangle\otimes|f_D(j_{i+\omega})\rangle\) where the left register is retained by E and D has the \(j\)-register. D further sends the \(j\)-register up the chain eventually reaching A via C and B who all execute their respective shift oracles.

    # D sends j-register to C, C applies UC    
    qc.unitary(UC,j_register,label="UC")
    # C sends j-register to B, B applies UB
    qc.unitary(UB,j_register,label="UB")
    # B sends j-register to A, A applies UA    
    qc.unitary(UA,j_register,label="UA")

At this point, the current quantum state is \(\frac{1}{\sqrt{\Omega}}\sum_{i=0}^{\Omega-1}|i\rangle\otimes|f_A(f_B(f_C(f_D(j_{i+\omega}))))\rangle\) where the index register is retained by E and the \(j\)-register is held by A. A also attaches the encrypted message at this point, but we will ignore that for simplicity.

A now sends the registers back to E via B, C, and D who each use their inverse oracles on the \(j\)-register as well as their respective scrambling operations for the Diffie-Hellman layer on the message.

    # A sends state to B, B applies UBinv
    qc.unitary(UBinv,j_register,label="UBinv")
    # B sends state to C, C applies UCinv
    qc.unitary(UCinv,j_register,label="UCinv")
    # C sends state to D, D applies UDinv
    qc.unitary(UDinv,j_register,label="UDinv")

Since the group action is commutative, the oracles commute; i.e., \(f_{X^{-1}}\circ f_A\circ f_X=f_A\circ f_{X^{-1}}\circ f_X=f_A\) hold for \(X\in\{B,C,D\}\), and we obtain that the final quantum state sent from D to E is \(\frac{1}{\sqrt{\Omega}}\sum_{i=0}^{\Omega-1}|i\rangle\otimes|f_A(j_{i+\omega})\rangle\).

Upon receipt of this final transmission, all further operations are performed by E. First, E measures the state.

    # E adds measurements
    qc.barrier()
    qc.measure(i_register,cl_i_register)
    qc.measure(anc_register,cl_anc_register)
    qc.measure(j_register,cl_j_register)
    
    # Transpile for simulator
    simulator = AerSimulator()
    qct = transpile(qc, simulator)
    
    # Run and get counts
    result = simulator.run(qct,shots=1).result()
    counts = result.get_counts(qct)
    key_raw = list(counts.keys())[0]

This collapses the state into a single \(|i\rangle\otimes|f_A(j_{i+\omega})\rangle\) which is uniformly selected from all \(r\) possible values. As shown in Figure 7, repeating the experiment \(10000\) times yields each state \(|i\rangle\otimes|f_A(j_{i+\omega})\rangle\) roughly \(\frac{10000}{\Omega}\approx2000\) times.

In reality, E will measure only once and obtain, for example, the measurement outcome key_raw = "011101100 0 100", which corresponds to \(i=4\) and \(f_A(j_{i+\omega})=236\). E now needs to uncompute their shift. They can do this by applying their inverse oracle UEinv \(i+\omega\) times, or by applying the “true” inverse mapper oracle once and the inverse oracle UEinv \(\omega\) times. Since we don’t have the “true” mapper implemented, we will use UEinv \(i+\omega\) times. E immediately measures the \(j\)-register afterwards again.

    # set up j-register as it is post measurement
    qc2 = QuantumCircuit(
        j_register,
        cl_j_register
    )
    
    key_split = key_raw.split(" ")
    for j in range(len(key_split[0])):
        if key_split[0][len(key_split[0])-j-1] == "1":
            qc2.x(j_register[j])
    
    qc2.barrier()

    # get index shift i 
    def bin2dec(s):
        n = 0
        for j in range(len(s)):
            n += int(s[len(s)-j-1])*2**j
        return n
    
    i = bin2dec(key_split[-1])
        
    # reverse shift i+omega
    for _ in range(i+omega):
        qc2.unitary(UEinv,j_register,label="UEinv")
        
    # and measure
    qc2.measure(j_register,cl_j_register)

Letting E’s cycle generator be denoted as \(\mathfrak{e}\) and A’s as \(\mathfrak{a}\), this last operation executes \[\begin{align} \left|{\mathfrak{e}^{-i-\omega}*f_A(j_{i+\omega}}\right\rangle=\left|{\mathfrak{e}^{-i-\omega}*\mathfrak{a}*\mathfrak{e}^{i+\omega}*j_0}\right\rangle=\left|{\mathfrak{a}*j_0}\right\rangle=\left|{j_A}\right\rangle. \end{align}\] Thus, the final measurement lets E read out \(j_A\).

In the example where key_raw = "011101100 0 100", E measures "011010101" in the \(j\)-register which is binary for \(j_A=\mathfrak{a}*j_0=213\) as it should be since aj[1]=213. Hence, we have successfully communicated the secret key from A to E via B, C, and D.

6 Security Considerations and Final Remarks↩︎

For security reasons, we require the class number \(h(\Delta)\) to be exponential in the security parameter. Since \(h(\Delta)\) “grows like” \(\sqrt{|\Delta|}\) [20], \(\Delta\), and hence the choice of \(p\), should be set accordingly. Regarding the security of the class group action, there is ongoing work on appropriate parameter sets; the most up-to-date analysis is given by Campos et al.(2024) [21], which incorporates the best known quantum attacks based on Kuperberg’s hidden-shift algorithm running in subexponential time \(2^{O(\sqrt{\log h(\Delta)})}\). As implementation techniques for evaluating the action continue to improve (e.g., [22]), recommended parameters may be revised; a full treatment lies beyond the scope of this paper.

It is worth noting a distinction between a fully quantum setting such as ours and the classical group-action protocols (as used in post-quantum cryptography but analyzed against quantum adversaries). Classically, a public transcript may reveal a start point \(j_0\) and an endpoint \(j_k\), and the core hardness assumption is the vectorization problem: find \(a\in G\) such that \(a * j_0 = j_k\), for which the best known quantum algorithms are subexponential at best. In a quantum construction such as the QOR however, no intermediate \(j\)-invariants are accessible unless a measurement is performed (which yields a random \(j\)-invariant); only the public \(j_0\) is visible. Moreover, by protocol design only the receiver performs the final measurement.

Our second remark on security addresses the properties of uniform mixing and periodicity of the underlying isogeny graph. The property of uniform mixing is desirable since a sufficiently long walk on the isogeny graph becomes indistinguishable from a random walk. In particular, supersingular \(\ell\)-isogeny graphs are Ramanujan. Their nontrivial eigenvalues are bounded by \(2\sqrt{\ell}\), so the classical walk mixes in \(O(\log |V|)\) steps, \(|V|\) being the number of vertices (see, e.g. [23]). For ordinary isogeny graphs Jao–Miller–Venkatesan (under GRH) prove in [8] that a walk of length \[t \;\ge\; C\,\frac{\log |V|}{\log\log q}\] is already near-uniform from any start. Here \(C\) is a positive constant and, in the elliptic curve scenario of [8], \(|V| \sim \sqrt{q}\).

In the quantum setting on the other hand, uniform mixing is known only for a narrow family of graphs, so one can instead work with the relaxed notion of \(\varepsilon\)-uniform mixing. It is known that for every \(p \geq 5\), every \(p\)-cycle \(C_p\) exhibits \(\varepsilon\)-uniform mixing [3]. Consequently, for appropriately chosen walk lengths (or evolution times), the walkers’ paths appear \(\varepsilon\)-random to any observer. Moreover, combining [24] and [3], one obtains the known result that no \(n\)-cycle \(C_n\) is periodic unless \(n \in \{1, 2, 3, 4, 6\}\). Finally, [25] ensures that other than the complete graph \(K_p\), no other circulant graph \(G(p;S)\) on \(p\)-many vertices and generating set \(S\) of cardinality \(|S| < p-1\) is periodic. It therefore appears that \(p\)-cycles are good candidates for quantum cryptographic scenarios as the one considered in this paper. In the extremal case where the class group is cyclic of large prime order, the resulting isogeny graph, after \(d\)-many encryptions, is the disjoint union of \(d\)-many \(p\)-cyles \(C_p\). Even when the class group is not of prime order, one can restrict to a large enough prime-order subgroup and the corresponding isogeny cycles to obtain the same effect.

Our final remark turns to implementation considerations. These primarily concern the quantum oracles. If we are in the CSIDH/CSURF setting discussed in Section 2, i.e. we work with supersingular elliptic curves over \(\mathbb{F}_p\), then efficient classical computation of the action \(*\) by arbitrary class group elements is becoming increasingly feasible, owing to advances such as PEGASIS [22]. This remains an active research area, and we do not pursue further details here as this is not in the scope of the paper. Alternatively, as already discussed in the paper, the class group action can be interpreted as continuous-time quantum walk on the underlying isogeny graph, hence on the underlying Hamiltonian. Currently, in a parallel project, we are developing this viewpoint theoretically, and we are considering possible implementations on actual hardware.

References↩︎