Antonin Leroux
email: antonin.leroux@polytechnique.org

Verifiable random function from the Deuring correspondence and higher dimensional isogenies

Introduction

A Verifiable Random Function (VRF) is a way to generate authenticated randomness in a verifiable manner. This notion was introduced in [START_REF] Micali | Verifiable random functions[END_REF] and have found several practical applications in the DNSSEC protocol [START_REF] Goldberg | Nsec5: provably preventing dnssec zone enumeration[END_REF] or in blockchain consensus [START_REF] Chen | Algorand agreement: Super fast and partition resilient byzantine agreement[END_REF][START_REF] Gilad | Algorand: Scaling byzantine agreements for cryptocurrencies[END_REF][START_REF] Ci | t. αi • (Ci + Diθ) ∈ K and gcd(Ci, Di, 2) = 1 using linear algebra[END_REF].

The most widely-used VRF constructions are based on pairings and elliptic curves such as [START_REF] Boneh | Aggregate and verifiably encrypted signatures from bilinear maps[END_REF] and are not resistant to an attacker that can access a quantum computer. Thus, it is an important problem to devise new schemes that are compact, efficient and resistant to quantum attackers.

In this work, we explore the possibilities offered by isogeny-based cryptography, one of the newest family of post-quantum candidates known for the compactness of its schemes. The main tools of isogeny-based cryptography are isogenies, that are maps between abelian varieties. Until very recently, only isogenies between elliptic curves, i.e. varieties of dimension 1, had been really studied. However, isogenies between abelian varieties of higher dimension (namely 2, 4 and 8) have recently found some surprising applications in the cryptanalysis of the SIDH key-exchange protocol [START_REF] Jao | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF]. A series of paper by Castryck and Decru [START_REF] Castryck | An efficient key recovery attack on sidh[END_REF], Maino, Martindale, Panny, Pope and Wesolowski [START_REF] Maino | A direct key recovery attack on sidh[END_REF], and Robert [START_REF] Robert | Breaking SIDH in polynomial time[END_REF] have shown how to use isogenies of higher dimension to break completely SIDH. This breakthrough has produced a small revolution in the field, first by breaking its most famous protocol, and more recently by finding several new constructive applications [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF]1,[START_REF] Decru | Towards a quantum-resistant weak verifiable delay function[END_REF].

In this article, we follow the example set in [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF] and explore the combinations of these new techniques with another sub-domain of the field related to the study of the Deuring correspondence, a link between quaternion algebras and isogenies between elliptic curves. As for isogenies of higher dimension, the Deuring correspondence was first explored for its cryptanalitic applications [START_REF] Kohel | On the quaternion ℓ-isogeny path problem[END_REF]18] before revealing its constructive potential in signature schemes [START_REF] Galbraith | Identification protocols and signature schemes based on supersingular isogeny problems[END_REF][START_REF] De Feo | Sqisign: compact postquantum signatures from quaternions and isogenies[END_REF]. These protocols rely on some complex algorithms to realize effectively the Deuring correspondence: i.e. the translation from isogenies to ideals (their quaternionic counterparts) and vice versa. These algorithms will also be crucial for our new VRF construction. In this work, we also tackle the important problem of improving their efficiency.

Related Works. There exists several other proposals of quantum-resistant VRF. Lattice-based constructions were the first to appear with [START_REF] Goyal | A generic approach to constructing and proving verifiable random functions[END_REF][START_REF] Yamada | Asymptotically compact adaptively secure lattice ibes and verifiable random functions via generalized partitioning techniques[END_REF]. These first constructions suffered from huge proof sizes and has been subsequently improved [START_REF] Yang | Efficient lattice-based zero-knowledge arguments with standard soundness: construction and applications[END_REF]22]. Among those, the recent proposal from [22] appears to be quite practical with reasonable key and proof sizes of around 10KB. We can also mention [START_REF] Esgin | Practical post-quantum few-time verifiable random function with applications to algorand[END_REF] that introduces a practical few-times construction.

There are other existing solutions relying on the security of symmetric primitives such as [4] that introduces several construction based on hash functions.

Finally, two proposals based on isogenies have been recently introduced in [START_REF] Lai | Capybara and tsubaki: Verifiable random functions from group actions and isogenies[END_REF]. The VRF protocol presented in [START_REF] Lai | Capybara and tsubaki: Verifiable random functions from group actions and isogenies[END_REF] are constructed from isogeny-based group actions and share almost nothing with our new VRF construction apart from the fact that isogenies are involved in both cases. Our construction uses a lot of different techniques and is much more compact. Conceptually, our Deuring-VRF y,z schemes is much closer to the recent weak VDF proposal of [START_REF] Decru | Towards a quantum-resistant weak verifiable delay function[END_REF] or the new SQIsignHD [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF] variant of the SQIsign signature scheme.

Contributions. Our contributions can be summarized in the following manner:

-A new family DeuringVRF y,z of VRF protocols based on the Deuring correspondence and isogenies between abelian varieties of high dimension. The security of the construction is based on a new hardness assumption in the random oracle model that is related to well-studied algorithmic problem of isogeny-based cryptographic. Every variant of DeuringVRF y,z is much more compact than all existing post-quantum constructions as exhibited in Table 1.

-A new algorithm for the effective Deuring correspondence to translate ideals to their corresponding isogenies using isogenies in dimension 2. This new algorithm relaxes the constraints of previous existing solutions and requires only "SIDH primes" of the form c2 f 3 e -1 for the characteristic of the underlying field. These primes are easy to find at any level of security unlike the "SQIsign primes" required by the algorithms used in [START_REF] De Feo | Sqisign: compact postquantum signatures from quaternions and isogenies[END_REF][START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF]. This new approach appears to be a promising direction to explore in order to improve the efficiency of the SQIsign [START_REF] De Feo | Sqisign: compact postquantum signatures from quaternions and isogenies[END_REF] signature scheme. -A new algorithm to evaluate an isogeny from its ideal representation with less torsion requirement than existing solutions.

In Table 1, we compare the concrete sizes we obtain for the example parameters that we will introduce in Section 5.2 with other existing constructions. We see that all our new protocols are much more compact than all existing solutions.

Public Key Proof No restrictions

Assumption Security (bytes) (bytes) level LB -VRF [START_REF] Esgin | Practical post-quantum few-time verifiable random function with applications to algorand[END_REF] 3.3K 4.9K ✗ MSIS/MLWE (Lattice) 128 X -VRF [4] 64 2.6K ✗ XMSS (Hash) 128 SL -VRF [4] 48 40K ✓ LowMC(Hash) 128 LaV [22] 8.81K 10.27K ✓ MSIS/MLWR (Lattices) 128 CAPYBARA [START_REF] Lai | Capybara and tsubaki: Verifiable random functions from group actions and isogenies[END_REF] 8.3K 39K ✓ DDH (Isogenies) 128 TSUBAKI [START_REF] Lai | Capybara and tsubaki: Verifiable random functions from group actions and isogenies[END_REF] 5 1. Comparison of the sizes of several post-quantum VRF schemes with our DeuringVRFy,z family for (y, z) ∈ {(2, 1), (2,2), (4, 1), (4, 2)} and the parameters of Section 5.2. ,

Technical overview

The high-level idea of our DeuringVRF y,z construction is the following: given a supersingular curve E (the public key), the DeuringVRF y,z function associates the curve E/G to the subgroup G of E. Computing E/G is difficult from the sole knowledge of E and G when the order of G is a big prime, but it can be done efficiently when one knows the endomorphism ring of E (and a few additional information) using the Deuring correspondence. The parameter z defines which dimension is going to be used to perform this computation.

The main feature of a VRF is the verifiability of the output. The correctness of the result can be proven by embedding the isogeny E → E/G in a y-dimensional isogeny using the techniques recently introduced to attack SIDH [START_REF] Castryck | An efficient key recovery attack on sidh[END_REF][START_REF] Maino | A direct key recovery attack on sidh[END_REF][START_REF] Robert | Breaking SIDH in polynomial time[END_REF].

At its heart, our construction exploits the difference between the different known ways of representing a cyclic isogeny.

First, there is the kernel representation made of one generator of the kernel. When the kernel is defined over a small field extension, this representation is quite easy to sample from the domain curve and it enables simple verification of the correctness of the computation by evaluating the isogeny on its kernel. However, there is no known efficient algorithm to compute or evaluate an isogeny from the kernel in the generic case. All those characteristics makes the kernel representation a perfect input to our random function.

Then, there is the ideal representation obtained from the Deuring correspondence. This representation is the most powerful one as it allows us to perform all the possible operations efficiently. However, as it also encodes the knowledge of the endomorphism ring of the domain, it essentially contains all the information there is to know about the isogeny, its domain and its codomain. This is why the ideal representation matches exactly the requirements of a secret key/trapdoor.

Finally, there is the y-dimensional isogeny representation (noted ydim hereafter) introduced recently by Robert [START_REF] Robert | Evaluating isogenies in polylogarithmic time[END_REF]. It allows us to evaluate efficiently the isogeny with the help of dimension y isogenies without revealing anything on the endomorphism ring. This is ideal for the proof as it provides verifiability when combined with the kernel representation while not leaking anything secret.

Below, we give a more precise description of the various mechanisms and parameters constituting our DeuringVRF y,z scheme. The notations introduced below are kept throughout the paper.

Evaluation Mechanism. On input x, the VRF evaluation is as follows: hash x into one element (a : b)

∈ P 1 (Z/N Z), compute R x = [a]P + [b]Q and compute E x = E/⟨R x ⟩. The output is then y = H(x || j(E x )
). The knowledge of I P and θ enables the efficient computation of the kernel ideal I x of ⟨R x ⟩. Then, the Deuring correspondence can be used to find the curve whose endomorphism ring is isomorphic to the right order of I x .

Proof and Verification Protocol. Proving the correctness of the computation can be done by revealing a representation of the isogeny φ x : E → E x . If the verifier can check the degree of this isogeny and evaluate it on R x , then the output must be correct. For that, we propose to use the representation of [START_REF] Robert | Evaluating isogenies in polylogarithmic time[END_REF] obtained by embedding φ x inside a 2 h -isogeny in dimension 2 or 4 (with h < 2f ).

In both cases, the crucial step to compute this high-dimensional representation is the evaluation of some isogenies on well-chosen torsion points. Using the secret key and the ideal I x , the prover will be able to evaluate these isogenies efficiently using the Deuring correspondence (with the IsogEval z id algorithm that we describe in Section 4.2). After that, the verification simply consists in checking that the isogeny representation is valid and has kernel R x . This last part can be done with an IsogEval ydim algorithm to evaluate the isogeny from its ydim representation.

New algorithm to evaluate an isogeny of big prime degree from its ideal. The algorithm IsogEval id that allows us to evaluate any isogeny from the Deuring correspondence plays an important role in our new construction. The principle of this algorithm is now pretty standard in isogeny-based cryptography (see [23,Algorithm 1] or [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF]Algorithm 4] for instance): first, compute with the Deuring correspondence an alternate isogeny of same domain and codomain and having smooth degree coprime to the order of the points to be evaluated with the IdealToIsogeny algorithm. Then, use this alternate isogeny to evaluate the first one. While this algorithm works pretty well in theory, in practice it requires a lot of available torsion (partly due to the IdealToIsogeny algorithm but also to the requirement that the degree of the alternate isogeny is coprime to the order of the points to be evaluated). When the order of the points to be evaluated is pretty big, the torsion requirement might simply be too big (this will be the case for our DeuringVRF y,1 constructions). In that case, it might be useful to remove the coprimality requirements. This is what we do with our new IsogEval-NonCoprime 1 id algorithm by reusing the ideas introduced for the IdealToIsogeny Eichler ℓ • algorithm in [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF] to "push" ℓ e torsion points through an isogeny of degree ℓ • .

New algorithms for the effective Deuring correspondence. As we explained above, the IsogEval z id algorithm that constitutes the main algorithmic building block of DeuringVRF y,z is based on a IdealToIsogeny z algorithm to translate ideals into their corresponding isogenies (of dimension 1) with the help of isogenies in dimension z. A relatively efficient algorithm to do so for z = 1 was introduced in [START_REF] De Feo | Sqisign: compact postquantum signatures from quaternions and isogenies[END_REF] and later improved in [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF]. We introduce a new algorithm to do the same thing with z = 2.

The motivation for this new algorithm is to overcome the obstacles of IdealTo-Isogeny 1 with the new possibilities offered by high-dimensional isogenies. More specifically, the bottleneck in IdealToIsogeny 1 is the computation of some endomorphisms. While the best solution in dimension 1 is to require that these endomorphisms have big smooth norm T 2 for some smooth integer T , we can remove this requirement by using embedding the endomorphisms in isogenies of dimension 2. This is roughly the same idea that led to the SQIsignHD variant [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF] of the SQIsign signature scheme. This idea simplifies a lot the choice of parameters by removing the need of so-called "SQIsign primes" (and replacing them by "SIDH primes") and could have interesting consequences on the efficiency of the ideal-to-isogeny algorithm. We discuss in more details the comparison between z = 1 and z = 2 at the end of this section.

Hard Problem and security. The security of our new VRF scheme essentially stems from the problem of computing the codomain of an isogeny from its kernel. The best known algorithm to solve this problem has polynomial complexity in the degree of the isogeny. Since the pseudo-randomness property of our scheme allows the adversary to evaluate the function on several inputs, the concrete security is based on the OMIP ydim , a variant of this problem, where the adversary has access to an oracle that computes the codomain and a ydim isogeny representation on given instances. The goal is then to find the answer for one instance that was not queried to this oracle. This problem has not been used anywhere in cryptography before, but the problem of computing the codomain of an isogeny from its kernel has been studied extensively due to its impact on the efficiency of several schemes in isogeny-based cryptography and has been recently considered for a proposal of weak post-quantum VDF [START_REF] Decru | Towards a quantum-resistant weak verifiable delay function[END_REF].

The formal description of our DeuringVRF y,z scheme can be found in Section 3.1. The concrete protocols include several additional steps to meet the requirements of a cryptographic VRF.

Comparison between the different variants. One might wonder why we introduce four different variants for (y, z) ∈ {(2, 1), (2, 2), (4, 1), (4, 2)} instead of choosing the best one and stick with it. The main reason is that there is currently no clear answer to the question: what is the best version of Deuring-VRF y,z ? Our parametrization is made of two variables y and z, and each of them have a different role that we try to explain below.

On y = 2 vs. y = 4. The 2 dim and 4 dim representations have quite different performance profiles. We refer the reader to Section 2.3 for a detailed description of these two representation. In both cases, the algorithm IsogEval ydim (used during the verification of our protocol) essentially consists in the evaluation of a 2 h -isogeny between abelian variety of dimension y. Thus, IsogEval 2 dim will be clearly faster than IsogEval 4 dim as any operation in dimension 2 will be faster than the corresponding operation in dimension 4 (the complexity is in fact exponential in the dimension y). However, the 2 dim representation in itself requires to compute strictly more things than the 4 dim representation. Thus, the computation of the isogeny representation (done during the evaluation algorithm of the VRF protocol) will be faster for the 4 dim and its size is essentially half the size of the 2 dim isogeny representation.

Hence, the choice between y = 2 and y = 4 will amount to a tradeoff between efficiency of the verification for y = 2, and compactness and efficiency of evaluation for y = 4.

On z = 1 vs. z = 2. The main advantage of z = 2 compared to z = 1 is the simplification of the parameter selection (and in particular the computation of the prime characteristic) that we already mention. There are two clear positive impacts:

1. A better asymptotic scaling for z = 2 due to the expected sub-exponential growth of the smoothness bound of the parameter T of the IdealToIsogeny 1 algorithm. 2. A better compactness of DeuringVRF y,2 due to the field of definition of the N -torsion points (more details on that in Section 5.1).

The only remaining open question is: at the lower levels of security, what value of z is more efficient? Unfortunately, it is still too early to give a definite answer to this question and it is out of the scope of this paper. It was demonstrated in [START_REF] De Feo | Sqisign: compact postquantum signatures from quaternions and isogenies[END_REF][START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF] that implementing the algorithm IdealToIsogeny 1 efficiently is a daunting task and finding the best way of implementing this algorithm remains an active research question.

The state of the algorithms to compute the dimension 2 isogenies required by our IdealToIsogeny 2 algorithm is even less stable. Some relatively efficient algorithms have been known for quite some time with the so-called Richelot correspondence [START_REF] Richelot | Ueber die integration eines merkwürdigen systems differentialgleichungen[END_REF] and new algorithms have been the focus of a lot of recent works [START_REF] Castryck | Hash functions from superspecial genus-2 curves using richelot isogenies[END_REF][START_REF] Kunzweiler | Efficient computation of (2ˆn, 2ˆn)-isogenies[END_REF][START_REF] Maino | A direct key recovery attack on sidh[END_REF][START_REF] Decru | Towards a quantum-resistant weak verifiable delay function[END_REF]1,[START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF][START_REF] Chi-Domínguez | Computing quotient groups of smooth order with applications to isogenies over higher-dimensional abelian varieties[END_REF]. Despite this uncertainty, the cost estimates for the computation of dimension 2 isogenies in the theta model provided in [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF] and recent progress toward the implementation of these algorithms [13] allow us to be quite optimistic that a careful implementation of our new IdealToIsogeny 2 algorithm might be competitive with the state of the art implementation of IdealToIsogeny 1 , even for the lower levels of security. This is particularly true in the context of our DeuringVRF y,z protocol where the value of p is even more constrained than for the SQIsign signature scheme (see Section 5). Our expectation is that IdealToIsogeny 2 will end up being more efficient than IdealToIsogeny 1 for all useful applications of the Deuring correspondence, but a careful implementation is required to confirm this. The rest of this paper is organized as follows. Section 2 introduces preliminaries on VRFs and the Deuring correspondence. Our VRF construction is introduced and analyzed in Section 3. In Section 4, we present all the algorithms required to instantiate the protocols. In Section 5.1, we look at parameters, size and efficiency for the proposed VRF construction.

Background material

We call negligible a function f : Z >0 → R >0 if it is asymptotically dominated by O(x -n ) for all n > 0. When a quantity a depending on some parameter x is negligible we will sometimes write a ≤ nelg(x).

Verifiable Random Function

A Verifiable Random Function (VRF) is a way to generate authenticated randomness that can be verified. It constist of the following protocols:

-SetUp(1 λ ), returns a set of public parameters pp.

-KeyGen(pp), returns a pair (pk, sk) of public key and secret key from the public parameters. -VRFEval(sk, x) = (v, π), takes the secret key sk and an input x ∈ {0, 1} n1 (λ) and computes the output v ∈ {0, 1} n2(λ) along with a proof π. -Verif(pk, π, x, v) takes the VRF public key, proof, input and output and returns 0 or 1.

In this article, we construct a VRF satisfying the following properties:

-Provability: The verification always returns 1 on correctly generated proof and output from a given input (see Definition 2). -Pseudo-randomness: With access to an oracle computing VRFEval(sk, x) for x ̸ = x 0 , an adversary cannot distinguish between VRFEval(sk, x 0 ) and a random value (see Definition 3). -Uniqueness: There does not exist a key and input and two pairs (v 1 , π 1 ) and (v 2 , π 2 ) with v 1 ̸ = v 2 both passing the verification (see Definition 5).

Elliptic curves, quaternion algebras and the Deuring correspondence

Below, we briefly expose the useful features and definitions of the Deuring correspondence. For a more complete treatment of supersingular elliptic curves and quaternion algebras and their link through the Deuring correspondence see [START_REF] Silverman | The Arithmetic of Elliptic Curves[END_REF][START_REF] Kohel | Endomorphism rings of elliptic curves over finite fields[END_REF][START_REF] Leroux | Quaternion Algebra and isogeny-based cryptography[END_REF][START_REF] Voight | Quaternion Algebras[END_REF]. The Deuring correspondence is an equivalence of categories between isogenies of supersingular elliptic curves and the left ideals over maximal order O of B p,∞ , inducing a bijection between conjugacy classes of supersingular jinvariants and maximal orders (up to equivalence) [START_REF] Kohel | Endomorphism rings of elliptic curves over finite fields[END_REF]. Moreover, this bijection is explicitly constructed as E → End(E). Hence, given a supersingular curve E 0 with endomorphism ring O 0 , the pair (E 1 , φ), where E 1 is another supersingular elliptic curve and φ : E 0 → E 1 is an isogeny, is sent to a left integral O 0 -ideal. The right order of this ideal is isomorphic to End(E 1 ). One way of realizing this correspondence is obtained through the kernel ideals defined in [START_REF] Waterhouse | Abelian varieties over finite fields[END_REF]. Given an integral left-O 0 -ideal I, we define the kernel of I as the subgroup E 0 [I] = {P ∈ E 0 (F p 2 ) : α(P ) = 0 for all α ∈ I}. To I, we associate the isogeny φ I : E 0 → E 0 /E 0 [I]. Conversely, given an isogeny φ, the corresponding kernel ideal is I φ = {α ∈ O 0 : α(P ) = 0 for all P ∈ ker(φ)}. Sometimes, when the kernel of φ is given as a group G generated by a point P , we also write I G or I P for this ideal. Two ideals I, J are said to be equivalent if I = Jβ for some β ∈ B × p,∞ and we write I ∼ J. The main properties of the Deuring correspondence are summarized in Table 2.

Supersingular j-invariants over F p 2 Maximal orders in Bp,∞ j(E) (up to Galois conjugacy) O ∼ = End(E) (up to isomorpshim) (E1, φ) with φ : E → E1 Iφ integral left O-ideal and right O1-ideal θ ∈ End(E0) Principal ideal Oθ deg(φ) n(Iφ) φ Iφ φ : E → E1, ψ : E → E1 Equivalent Ideals Iφ ∼ I ψ τ • ρ : E → E1 → E2 Iτ•ρ = Iρ • Iτ Table 2.
The Deuring correspondence, a summary from [START_REF] De Feo | Sqisign: compact postquantum signatures from quaternions and isogenies[END_REF].

On push-forward isogenies and ideals. Given two isogenies φ, ψ of coprime degree. We can define the push-forward of φ by ψ that we denote by [ψ] * φ as the isogeny of degree deg φ and kernel ψ(ker φ). The same can be done for the push-forward of φ by ψ. This way, we get the following commutative diagram.

E 3 [ψ] * φ / / E 4 E 1 ψ O O φ / / E 2 [φ] * ψ O O
Under the Deuring corresponding we can define the push-forward of an ideal I by another ideal J of coprime norm as the ideal [J] * I corresponding to the push-forward isogeny [φ J ] * φ I . Formulas to compute the push-forward ideals are given in [START_REF] De Feo | Sqisign: compact postquantum signatures from quaternions and isogenies[END_REF]Lemma 3].

In this work, we build upon several existing algorithms of the Deuring correspondence. We give precise references for all of them when they appear. Note that a description for all those algorithms can be found in [START_REF] Leroux | Quaternion Algebra and isogeny-based cryptography[END_REF]Chapters 3 and 4].

Isogeny Representation

The formal notion of isogeny representation is gaining more and more importance as the variety of existing method to build these representations is expanding. This definition appears at various places in the literature [START_REF] Leroux | A new isogeny representation and applications to cryptography[END_REF][START_REF] Leroux | Quaternion Algebra and isogeny-based cryptography[END_REF][START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF] with some small changes. The common and most important part is the existence of an algorithm to evaluate the isogeny from its representation. The representation is called efficient when the size of the representation and the complexity of the evaluation algorithm is polylogarithmic in the degree and field characteristic p.

Since, we are going to work with several family of representations, we will label each of those families with a tag xx. All the data and algorithms associated with the family xx will bear the same tag.

To avoid redundant computation we are going to divide the representation in two parts : one that is unique to the isogeny φ that we will write s φ xx (and that sometimes might be called the representation of φ), and one that is common to all isogenies of same domain E and degree N . This second part will be denoted by c N xx (E) and will be called the "common information". The distinction between s φ xx and c N xx (E) will be useful for an efficient instantiation (to avoid recomputing c N xx (E) for each new isogeny).

Definition 1. An efficient isogeny representation xx for an isogeny φ : E → E ′ of degree N defined over F q is in two parts: c N xx (E) (the same for all isogeny of degree N having domain E), and s φ xx . Both have size O (polylog(qN )), and there exists the following algorithm: IsogEval xx that takes E, s φ xx , c N xx (E) and a point P in E[F q k ] in input, and computes φ(P ) ∈ E ′ [F q k ] in time O polylog(q k N ) .

On existing isogeny representations. There exists several isogeny representation in the literature. A non-exhaustive list of them can be found in [36, chapter 4]. In this work, we will use two of the representations presented there: the kernel representation based on the Vélu formulas (which is one of the "historical" isogeny representation) and the ideal representation based on the Deuring correspondence.

For the kernel representation, we use the tag ker. The representation s φ ker is made of a generator of ker φ and c N ker (E) is trivial. This representation can be quite compact (O (polylog(p))) when the kernel points are defined over a small field extension. However, the complexity of IsogEval ker is polynomial in the biggest prime factor of the degree which makes it efficient only for smooth degree isogenies. Hence, it does not meet our definition of efficient isogeny (but this gap is actually desirable for our construction). The kernel representation has another advantage : it is quite efficient to "sample" when the kernel points of order N are defined over a small extension. By efficient to sample, we mean that, for a given supersingular curve E, it is easy to compute the kernel representation of a random isogeny of degree N (we can even sample uniformly at random from the set of N -isogenies starting from E).

For the ideal representation we use the tag id. The representation s φ id is made of a basis of the ideal I φ corresponding to φ under the Deuring correspondence.

As for the kernel representation, the common information c N id (E) is trivial. The ideal representation matches our definition of efficient, however it requires to know the endomorphism ring of the domain. When End(E) is known, we can also efficiently sample ideal representations of uniformly random N -isogenies.

The recent attacks against the scheme SIDH [START_REF] Castryck | An efficient key recovery attack on sidh[END_REF][START_REF] Maino | A direct key recovery attack on sidh[END_REF][START_REF] Robert | Breaking SIDH in polynomial time[END_REF] have introduced a new way to build an isogeny representation, as was noted by Robert in [START_REF] Robert | Evaluating isogenies in polylogarithmic time[END_REF], by evaluating φ on a basis of the T -torsion for T ≥ √ N . The evaluation can be performed by computing an isogeny between abelian varieties of dimension y > 1 that embeds the isogeny φ. There are different variants of this idea for different values of y. In this work, we will look at the version for y = 2 and y = 4. We will call dimension-y representation (with the tag ydim, the isogeny representation obtained from this principle. In most of this work, we are going to use these representations in a black box manner. We refer the reader to [START_REF] Castryck | An efficient key recovery attack on sidh[END_REF][START_REF] Maino | A direct key recovery attack on sidh[END_REF][START_REF] Robert | Breaking SIDH in polynomial time[END_REF][START_REF] Robert | Evaluating isogenies in polylogarithmic time[END_REF][START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF] to see how to instantiate the required algorithms. We give a brief summary below.

Embedding isogenies in higher dimension isogenies with Kani's lemma. The goal of this paragraph is to explain how one can embed isogenies in higher dimension using Kani's lemma. This result introduced in [START_REF] Kani | The number of curves of genus two with elliptic differentials[END_REF] describe how to build isogenies of dimension 2y from isogenies in dimension y.

Lemma 1 (Kani). Let us consider a commutative diagram of isogenies between principally polarized abelian varieties of dimension

g A ′ φ ′ / / B ′ A ψ O O φ / / B ψ ′ O O
where φ and φ ′ are a-isogenies and ψ and ψ ′ are b-isogenies for two integers a, b. The isogeny F : A × B ′ -→ B × A ′ given in matrix notation by

F := φ ψ ′ -ψ φ ′
is a d-isogeny between abelian varieties of dimension 2g with d = a + b, for the product polarisations.

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

ker(F ) = {( φ(x), ψ ′ (x)) | x ∈ B[d]}.
Similarly,

ker( F ) = {(φ(x), ψ(x)) | x ∈ A[d]}.
Remark 1. This lemma was first proven in [START_REF] Kani | The number of curves of genus two with elliptic differentials[END_REF]Theorem 2.3]. We are going to use it for g = 1 and g = 2 to obtain the 2 dim and 4 dim representations respectively. The idea is that the isogeny F provides a representation for the isogeny φ : A → B since φ can be recovered as

ρ 2 • F • ρ 1 where ρ 1 is any embedding morphism from A to A × B ′ and ρ 2 is the projection from B × A ′ to B.
Moreover, we are going to make good use of the trick presented in [12, Section 5.4] to cut the isogeny F in half to greatly lower the amount of torsion information required.

Indeed, when the isogeny F from Lemma 1 has degree d 1 d 2 , then it can be factored as F = F 2 • F 1 where each F i has degree d i . In that case, we get that

ker(F 1 ) = {( φ(x), ψ ′ (x)) | x ∈ B[d 1 ]} (1) ker( F 2 ) = {(φ(x), ψ(x)) | x ∈ A[d 2 ]}.
This means that we can use the d 1 -torsion and d 2 -torsion instead of the d 1 d 2torsion (the two situations are really different only if d 1 and d 2 are not coprime to eachother). This trick will prove to be necessary to obtain an efficient scheme in our case as we will take d 1 and d 2 as big powers of 2, which will essentially divide by 2 the torsion requirement by 2 (in bitsize).

More details on Kani's Lemma and the ways to compute isogenies in dimension g > 1 can be found in the appendices of [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF]. Below, we explain more concretely how Kani's Lemma can be applied to get our isogeny representations for an isogeny φ :

E 1 → E 2 .
The 2 dim isogeny representation. In dimension g = 1, Lemma 1 can be applied to embed φ in an isogeny of dimension 2 with A = E 1 and B = E 2 . The degree d is chosen to be 2 h for the smallest exponent h such that 2 h > N . In that case, the isogeny ψ is any isogeny of degree 2 h -N coprime to N of domain E 1 . This will define an isogeny diagram of the form

E 3 φ ′ / / E 4 E 1 ψ O O φ / / E 2 ψ ′ O O
The isogeny ψ can be the same for every isogeny φ of the same degree and codomain. Let f be an exponent such that 2f > h. The isogenies F 1 and F 2 are chosen to be of degree 2 h1 and 2 h2 for h = h 1 + h 2 and h i < f for i = 1, 2. Then, we can define the 2 dim isogeny representation as follows. Let P, Q be a basis of

E 1 [2 f ].
The common information c N 2 dim (E) is made of the curve E 3 and the points P, Q, ψ(P ), ψ(Q). Then, we define s φ 2 dim as E 2 , E 4 and the points φ(P

), φ(Q), ψ ′ • φ(P ), ψ ′ • φ(Q).
After the isogeny F 1 , F 2 have been computed, the full isogeny F can be recovered. Then, φ can be evaluated on any point as π • F • ι. This is how we get the algorithm IsogEval .

dim

The 4 dim isogeny representation. The 4 dim isogeny is a bit trickier to obtain. In fact, we will not provide a representation for φ directly, but for [α]φ for some integer α coprime to N . This scalar is unfortunately necessary because 2 h -α 2 N must be represantable as the sum of two squares (which might not always be true for α = 1). Let us now assume that we have chosen a scalar α such that 2 h -α 2 N = a 2 1 + a 2 2 for h the smallest exponent such that 2 h > α 2 N and two integers a 1 , a 2 . We will later explain in Section 3.2 a bit more concretely how this integer can be chosen as it will play a role in the efficiency of the verification of our DeuringVRF 4,z scheme.

In dimension g = 2, Kani's lemma is applied to the isogeny Diag([α]φ) :

E 2 1 × E 2 2 .
We abuse notation by denoting this diagonal isogeny as [α]φ as well. Then, we take

A = E 2 1 and B = E 2 2 . The degree d is 2 h where h is the smallest exponent such that the quadratic equation 2 h -[α] 2 N = a 2 1 + a 2 2 has a solution. Then, the isogeny ψ : E 2 1 → E 2
1 is defined as the matrix

ψ := [a 1 ] E1 [a 2 ] E2 -[a 2 ] E2 [a 1 ] E1
In that case, the parameters a 1 , a 2 , α can be considered as known constants (since they are common to all N -isogenies). Thus, the common data

c N 4 dim (E) is made of P, Q, a basis of E 1 [2 f ] (with 2f > h)
, and the data s φ 4 dim is constituted by the curve E 2 and the points φ(P ), φ(Q).

Similarly to the 2 dim representation, the isogeny F can be recovered from s φ 4 dim and the constants f, h, a 1 , a 2 , α and this allow us to instantiate a Isog-Eval 4 dim algorithm.

New post-quantum VRF from isogenies

In this section, we provide a generic description of our DeuringVRF y,z protocol. The protocoles are presented in Section 3.1. The security of the scheme is analyzed in Section 3.2.

Formal description

In this section, we give a formal description of the different protocols that composes our DeuringVRF x,y protocol for two integers y, z ∈ {(2, 1), (2, 2), (4, 1), (4, 2)}. We provide a common framework for all values of y, z to allow the reader to grasp the idea of the construction without wondering too much about the technical details. We postpone the detailed description of the most complicated building blocks to Sections 3.2 and 4. We also omit the parameter generation; it will be discussed later in Section 5.1.

Henceforth, let us assume that there are three distinct primes ℓ, p, N , and exponents e, f, k such that all the 2 f and ℓ e torsion points of supersingular curves can be defined over F p 2 , and the N -torsion can be defined over F p k .

There is also a curve E 0 over F p 2 of known endomorphism ring O 0 . The public parameters also include a basis (P 0 , Q 0 ) of E 0 [N ] and the related kernel ideal I P0 together with an endomorphism ι ∈ O 0 such that ι(P 0 ) = Q 0 . We write pp = (p, N, ℓ, E 0 , P 0 , Q 0 , I P0 , ι).

We write f in : {0, 1} n1(λ) → P 1 (Z/N Z) an injective function, and H out : {0, 1} * → {0, 1} n2(λ) a hash function, where n 1 (λ), n 2 (λ) are functions of the security parameter λ. The algorithms IsogEval ydim are used as blackbox and we do not give much details about them in this paper. There are, however, several tasks that needs more details in the algorithms we have outlined above. We list them below. These missing algorithms will be treated in Sections 3.2 and 4.

-The algorithm CommonIsogenyRepresentation 2,z to compute the common information c N 2 dim (E). We do not describe CommonIsogenyRepresentation 4,z which simply takes a basis of E[2 f ] and returns this basis.

-The algorithm IsogenyRepresentation y,z to compute the isogeny representation and the codomain. -The IsogVerif ydim algorithm to check that the high dimensional representation is correct.

Algorithm 3 Verify y,z (pk, π, x, v)

Input: A DeuringVRFy,z public key, an input x ∈ {0, 1} n 1 (λ) , a proof π and an output v ∈ {0, 1} n 2 (λ) . Output: A bit b.

1: Parse pk as E, P, Q, c N ydim (E). 2: Parse π as j, s φ ydim . 3: Compute (r :

s) = f in (x) and Rx = [r]P + [s]Q. 4: If IsogVerif ydim (s φ ydim , c N ydim (E), j) = 0, output 0. 5: If IsogEval ydim (π, s φ ydim , Rx) ̸ = OE x or Hout(x||j) ̸ = v, then output 0. 6: return 1.

Security Analysis

In this section, we study the security properties of our generic VRF scheme.

Provability. The first and most basic notions a VRF must satisfy is provability. This notion implies that a correctly generated proof for a given input and key will pass the verification. Definition 2. A VRF scheme is said to be provable if, for any x ∈ {0, 1} n1(λ) , (sk, pk) ← KeyGen y,z (pp) and (π, v) ← VRFEval y,z (sk, x), the following equality is satisfied:

Verify y,z (pk, π, x, v) = 1
Using results proven in Section 4, we are able to show that our DeuringVRF y,z scheme has provability.

Proposition 1. The DeuringVRF y,z scheme has provability for (y, z) ∈ {(2, 1), (2, 2), (4, 1), (4, 2)}.

Proof. In KeyGen y,z , the correctness of IdealToIsogeny z ℓ • , ensures that the isogeny φ I is the one corresponding to the ideal I. Then, with θ = φ I • ι • φI , we see that if Q 0 = ι(P 0 ) the definition of S = [ℓ e ]φ I (Q 0 ) ensures that θ(R) = S. After the change of basis is applied on R, S to get the basis P, Q, the value of θ is adjusted to ensure that θ(P ) = Q.

Next, we show that the ideal I P is the kernel ideal corresponding to the point P . The point P is equal to (a + bθ)φ I (P 0 ). By property of the Deuring correspoding, ideal multiplication corresponds to isogeny composition. Thus, the ideal I • (a + bθ) corresponds to the isogeny (a + bθ)φ I . Then, by definition of the push-forward ideals, the ideal [I(a+bθ)] * I P0 has kernel equal to (a+bθ)φ(ker I P0 ) and this is indeed the group generated by P .

The correctness of the computation of the DeuringVRF y,z keypair follows from the correctness of CommonIsogenyRepresentation y,z .

In VRFEval y,z , we can use the same reasoning as for I P to prove that I x is indeed the kernel ideal corresponding to the subgroup generated by [r]P + [s]θ (P ).

The correctness of the computation of s φ ydim follows from the correctness of IsogenyRepresentation y,z .

Since we have the equality [r]P + [s]θ(P ) = [r]P + [s]Q, the evaluation of the point R x in Verify y,z will be O Ex , and since c N ydim (E) and s φ ydim are honestly computed as a valid representation of an isogeny of degree N , the output of IsogVerif will be 1 by Proposition 3.

⊓ ⊔

Pseudo-randomness. This security notion implies that it is hard to distinguish the output from a random value without knowing the secret key.

Definition 3. Let A = (A 1 , A 2
) be an algorithm running in time t and playing the following experiment:

1. pp ← ParamGen(1 λ ) 2. (pk, sk) ← KeyGen y,z (pp). 3. (x ⋆ , st 1 ) ← A VRFEvaly,z(•),Hout(•) 1 (pk). 4. (v 0 , π 0 ) ← VRFEval y,z (sk, x ⋆ ). 5. v 1 $ ← -{0, 1} n2(λ) . 6. b $ ← -{0, 1}. 7. b ′ ← A VRFEvaly,z(•),Hout(•) 2 (v b , st).
where the query of VRFEval y,z on x ⋆ are implicitly forbidden. The pseudo-randomness advantage of A is defined as

Adv A PR (t) = Pr{b = b ′ } (2)
The advantage of the scheme is defined as

Adv PR (t) = max A Adv A PR (t) The VRF is pseudo-random if Adv PR (t) ≤ 1/2 + negl(λ) when t is in O (poly(λ)).
The pseudo-randomness property of our VRF is based on the hardness of Problem 1 that we introduce below. This problem is defined with respect of an isogeny representation with the tag xx. This problem uses an isogeny oracle in the fashion of the RADIO and RUGDIO introduced in [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF]. We call this new oracle a N -FIXDIO xx . xx (E), the goal is to compute the j-invariant of the codomain of an isogeny not given as the output of the N -FIXDIO xx .

We define Adv

OMIPxx (t) = max A Pr{A N -FIXDIOxx(•) (E, c N
xx (E)) solves Pb. 1} for A ranging over all algorithms running in time t.

The hardness of Problem 1 underlies the pseudo-randomness of our VRF as we prove in Proposition 2.

Proposition 2. In the random oracle model, the scheme DeuringVRF y,z satisfies

Adv PR (t) ≤ 1 2 + qAdv OMIP ydim (t ′ )
against any adversary A = A 1 , A 2 allowed less than q query to the random oracle H out for some time t ′ polynomial in t in the random oracle model.

Proof. Let G 0 be the pseudo-randomness game as given in Definition 3.

Let us define the game G 1 where the random oracle H out answers ⊥ on input x ⋆ , j(E x ⋆ ) (after the value x ⋆ has been defined). Let us call E ⋆ , the event "H out is queried on x ⋆ , j(E x ⋆ )". It is clear that the two games are identical when ¬E ⋆ . Hence, Pr{A wins G 0 |¬E ⋆ } = Pr{A wins G 1 |¬E ⋆ } and the conditional probability formula leads to

|Pr{A wins G 0 } -Pr{A wins G 1 }| ≤ Pr{E ⋆ }.
With the modifications defining G 1 , the output of H out is always independent of v 0 . In that case, given that v 0 and v 1 are distributed as uniformly random values, A has no way to distinguish between the two without making a forbidden evaluation query and so Pr{A wins

G 1 } = 1/2.
It now remains to bound Pr{E ⋆ }. For that, we will build an adversary C against the OMIP from A. This adversary proceed as follows :

1. C receives E, c N ydim (E). 2. C generates a random basis of E[N ] and transmits pk = (E, P, Q, c N ydim (E)) to A 1 . 3. C answers to any query to VRFEval y,z (x) by using the N -FIXDIO ydim on input R x = [r]P + [s]Q where (r : s) = f in (x) to compute E x and the proof π. Then, C computes v x = H out (x, j(E x )) and returns j(E x ), π, v x . 4. C answers to all queries to H out as a random oracle would. 5. C receives x ⋆ from A 1 , and aborts if VRFEval y,z has been queried on x ⋆ . 6. C generates the bit b and the values v 0 , v 1 as in the PR-experiment. 7. C transmits v b to A 2 and continues to simulate the evaluation oracle. 8. When A is done, C picks a random query to H out of the form x ⋆ , j and output the value j.

By definition of the N -FIXDIO ydim , C is able to simulate honestly all the requests to VRFEval y,z . Since the basis P, Q in KeyGen y,z is rerandomized by a random invertible matrix M , it behaves as a random basis of E[N ]. Moreover, until E ⋆ happens, all the queries to H out are also answered honestly. Thus, until E ⋆ happens C simulates perfectly the game G 1 for A. This means that the probability that E ⋆ happens during G 1 is exactly the probability that E ⋆ happens during the simulation by C. Moreover, it is clear that Pr{C solves Problem 1 |E ⋆ } ≥ 1/q. Thus, since Pr{C solves Problem 1} ≥ Pr{E ⋆ }Pr{C solves Problem 1 |E ⋆ }, we get

Pr{E ⋆ } ≤ qAdv OMIP ydim (t ′ )
where t ′ is the running time of C which is polynomial in t. This proves the desired result.

⊓ ⊔

Below, we analyze the complexity of the OMIP xx in the two cases relevant to our construction : xx ∈ {2 dim, 4 dim}. We start with the OMIP 4 dim which is simpler to analyze.

Analysis of the OMIP 4 dim . The most obvious way to attack the OMIP 4 dim is to try to compute directly any isogeny of domain E and degree N from its kernel. The best known method is the √ élu algorithm from [2]. This algorithm takes O( max d|N d) (ignoring logarithmic factors) operations over the field of definition of the kernel. Thus, even when E[N ] is defined over a small extension (which will be the case in our protocols), the complexity is exponential when N is a prime number. Another approach would be to try to compute the endomorphism ring End(E) (which would amount to key recovery in the context of our Deuring-VRF y,z protocols). As our protocols can run in polynomial-time, the knowledge of the endomorphism ring is obviously enough to break the OMIP 4 dim . However, the complexity to compute the endomorphism ring of a random supersingular curve is O( √ p) (see [19] for instance).

The two methods we described above are rather generic attacks that are not really using the fact that an access to the N -FIXDIO 4 dim is provided in the OMIP 4 dim . In particular, the attacker has access to several isogenies of degree N that he can evaluate. One might wonder if there could be a way to "tweak" one of the isogenies given by the N -FIXDIO 4 dim to obtain a new isogeny that would lead to a suitable solution to the OMIP 4 dim . However, there does not seem to be an obvious way to do so. The only way to "tweak" an isogeny seems to be to apply some kind of push-forward and realize a commutative diagram where two parallel arrows are isogenies of degree N , one that is the output of the N -FIXDIO and the other one that would be the "tweaked" isogeny. There is nothing to prevent this from happening, however the tweaked isogeny will not have E as domain with overwhelming probability. The only possibility to have E as the domain of the "tweaked" isogeny would be that one of the perpendicular arrows of the commutative diagram is an endomorphism of E. Computing one endomorphism of a random supersingular curve also has complexity O( √ p) and so this is not possible. Finally, one might wonder if the access to the N -FIXDIO might help finding endomorphisms. It was argued in [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF]Section 6.4] that the RADIO and RUGDIO oracles introduced there should not help to compute some endomorphisms of a given supersingular curve as we already know how to compute efficiently all isogenies of smooth degree. Given that our N -FIXDIO oracle is pretty similar to the RADIO and RUDGIO, the same reasoning applies in our case to justify that the N -FIXDIO should not be of any help.

Analysis of the OMIP 2 dim In dimension 2, both c N 2 dim (E) and s φ 2 dim contain more informations than their counterpart in dimension 4. However, there does not seem to be any relevant way to exploit this additional information. Indeed, the main difference between the dimension 2 and dimension 4 is that the dimension 2 embedding is constructed from two non-trivial isogenies (and the commutative diagram they generate) instead of one in dimension 4 (since one side of the commutative diagram in 4 dim is obtained from scalar multiplications isogenies that anyone can compute efficiently). However, since the additional isogenies revealed in dimension 2 do not satisfy any specific property, there does not seem to be a reason that they would make the OMIP 2 dim more vulnerable. We will see later with the CommonIsogenyRepresentation 2,z algorithm, that the isogeny ψ used in our 2 dim representation is distributed uniformly among all isogenies of the same degree and domain. This should prevent any weird behaviour that might leak some information on the endomorphism ring of E.

Comparison between the two problems. Note that in general the OMIP 2 dim and the OMIP 4 dim do not appear to be equivalent. Indeed, if the degree 2 h -N of the extra isogeny required in 2 dim is not smooth, then computing any isogeny of degree N -2 h from its domain E is believed to be hard (for the same reasons that we assume that the OMIP is hard) and so translating 4 dim representations to 2 dim representations should be hard. However, note that if N -2 h is powersmooth, then any isogeny of degree N -2 h can be computed from E in polynomial time and so the OMIP 2 dim and OMIP 4 dim are in fact equivalent. This fact might appear surprising, but in our opinion it is only one more reason to believe that the additional information revealed in the OMIP 2 dim should not make it easier than the OMIP 4 dim for any N .

Uniqueness. A VRF scheme satisfy unconditional full uniqueness when there cannot be two possible output for the same input. This is formalized in Definition 5 below. Definition 5. A VRF is said to satisfy unconditional full uniqueness when no values pk, v, v ′ , x, π, π ′ can satisfy Verify y,z (pk, π, x, v) = 1 and Verify y,z (pk,

π ′ , x, v ′ ) = 1 with v ̸ = v ′ .
To prove the uniqueness of our scheme, we need to give more details about the verification procedure. In particular, we need to details the IsogVerif ydim algorithms for y = 2, 4.

Verification in dimension 2. The verification in dimension 2 is pretty simple: we need to verify that the provided isogeny representation is well-formed. This means verifying that we can compute F , an isogeny of dimension 2 that represents an isogeny between E and a curve of the correct j-invariant. This part of the verification is handled by the IsogVerif 2 dim algorithm. For uniqueness, we also need to verify that the degree and kernel are correct. These two properties

Algorithm 4 IsogVerif 2 dim (E 1 , c N 2 dim (E), s φ 2 dim , j) Input: A curve E1, a 2 dim isogeny representation c N 2 dim (E), s φ 2 dim
, and a j-invariant j. Output: A bit b.

1: Parse c N 2 dim (E) as E3, P1, Q1, P3, Q3. 2: Parse s φ 2 dim as E2, E4, P2, Q2, P4, Q4. 3: if j(E2) ̸ = j then 4:

Return 0. 5:

end if 6: Compute G1 = [2 f -h 1 ]⟨([N ]P1, P4), ([N ]Q1, Q4)⟩ and G2 = [2 f -h 2 ]⟨(P2, P3), (Q2, Q3)⟩. 7: if Gi is not a kernel of a 2 h i -isogeny of dimension 2 for i = 1, 2 then 8:
Return 0. 9: end if 10: Compute F1 of kernel G1 and F2 of kernel G2. 11: if the codomain of F1, F2 do not agree. then 12:

Return 0. 13: end if 14: return 1.

will be verified during the check that φ(R x ) = 0 performed in Verify y,z (see the proof of Proposition 4 for the full reasonning that this is enough).

Note that, in the statement below, when the output IsogVerif is 1, there is no guarantee that the degree of the isogeny represented is N exactly.

Proposition 3. If IsogVerif 2 dim (E 1 , c N 2 dim (E), s φ 2 dim , j) = 1, then c N 2 dim (E), s φ 2 dim
constitute a valid 2 dim isogeny representation for an isogeny φ : E 1 → E 2 of degree smaller than 2 h where j(E 2 ) = j. Conversely, if c N 2 dim (E), s φ 2 dim is a valid 2 dim isogeny representation for an isogeny of degree

N from E 1 to E 2 , then IsogVerif 2 dim (E 1 , c N 2 dim (E), s φ 2 dim , j(E 2 )) = 1. Proof. When IsogVerif 2 dim (E 1 , c N 2 dim (E), s φ 2 dim , j) = 1
, then, since the codomain of F 2 and F 1 agree, there exists a 2 h -isogeny

F = F 2 • F 1 : E 1 × E 4 → E 2 × E 3
with 2 h1+h2 = 2 h and j(E 2 ) = j. Kani's Lemma imply that we have a valid 2 dim representation for the isogeny ρ 2 • F • ρ 1 : E 1 → E 2 where ρ 1 , ρ 2 are defined as in Remark 1, and that the degree of this isogeny must be smaller than 2 h . Conversely, when c N 2 dim (E), s φ 2 dim are a valid representation for an isogeny φ of degree N , then by definition, we must have

P 3 , Q 3 = ψ(P 1 , Q 1 ), P 2 , Q 2 = φ(P 1 , Q 1 ) and P 4 , Q 4 = ψ ′ • φ(P 1 , Q 1 ).
In the case, it can be verified that the two subgroup G 1 , G 2 agree exactly with the subgroups defined in Equation 1. Thus, G 1 and G 2 are correct kernels of dimension 2 isogenies and the codomains of F 1 and F 2 agree. Thus, the output of IsogVerif 2 dim is 1.

⊓ ⊔ Proposition 4. The scheme DeuringVRF 2,z satisfies unconditional full uniqueness.

Proof. Let us assume that we have a value v = H out (x||j(E ′ )) passing the verification for an input x, a public key pk and proof π. We want to prove that the only possibility is that j(E ′ ) = j(E/⟨R x ⟩). By Proposition 3, we know that a valid isogeny representation for an isogeny φ : E → E ′ can be extracted from pk and π. Since φ(R x ) = 0, we know that ⟨R x ⟩ ⊂ ker φ. This implies that N divides the degree of φ. But since φ has degree smaller than 2 h and we assumed that h was the smallest exponent such that 2 h > N then deg φ must be N . So ker φ = ⟨R x ⟩ and so E ′ must be isomorphic to E/⟨R x ⟩ which proves the result.

⊓ ⊔

Verification in dimension 4. The verification in dimension 2 is quite simple because the 2 dim isogeny representation embeds the isogeny φ directly. However, the situation is a bit more complicated in dimension 4 because the concrete isogeny that is represented is [α]φ as we explained in Section 2.3. Thus, checking the degree is slightly harder. In particular, checking that ρ 2 •F •ρ 1 (R x ) = 0 is not enough anymore as this only proves that ρ 2 •F •ρ 1 can be factored by φ. To ensure uniqueness, the verifier must be able to ensure that ρ 2 • F • ρ 1 = [α]φ. This is why IsogVerif 4 dim will include another step compared to IsogVerif 2 dim : check that

E[α] ⊂ ker ρ 2 •F •ρ 1 .
This is why the exact choice of α is important. To enable an efficient verification, we need that the α-torsion points are defined over a small field extension. That way, it can be easily checked that

ρ 2 • F • ρ 1 (E[α]) = 0
with IsogEval 4 dim . We will specify in Section 5.2 an example of parameters for which the α-torsion is defined over

F p 2 . Proposition 5. If IsogVerif 4 dim (E 1 , c N 4 dim (E), s φ 4 dim , j) = 1, then c N 4 dim (E), s φ 4 dim
constitute a valid 4 dim isogeny representation for an isogeny φ : E 1 → E 2 of degree smaller than 2 h /α 2 where j(E 2 ) = j. Conversely, if c N 4 dim (E), s φ 4 dim is a valid 4 dim isogeny representation for an isogeny φ :

E 1 → E 2 of degree N , then IsogVerif 4 dim (E, c N 4 dim (E), s φ 4 dim , j(E 2 )) = 1. Proof. When IsogVerif 4 dim (E 1 , c N 4 dim (E), s φ 4 dim , j) = 1
, then, since the codomain of F 2 and F 1 agree, there exists a 2 h -isogeny

F = F 2 • F 1 : E 2
1 → E 2 2 with 2 h1+h2 = 2 h and j(E 2 ) = j. Kani's Lemma, imply that we have a valid 4 dim representation for the isogeny ρ 2 • F • ρ 1 : E 1 → E 2 where ρ 1 , ρ 2 are defined as in Remark 1, and that the degree of this isogeny must be smaller than 2 h . Moreover, since

ρ 2 • F • ρ 1 (E 1 [α]) = 0, then ρ 2 • F • ρ 1 can be factored by [α]
and so the degree of the isogeny from E 1 to E 2 is smaller than 2 h /α 2 .

Conversely, when c N 4 dim (E), s φ 4 dim is a valid representation for an isogeny φ of degree N , then by definition, we must have P 2 , Q 2 = φ(P 1 , Q 1 ). In that case, it can be verified that the two subgroup G 1 , G 2 agree exactly with the subgroups defined in Equation 1. Thus, G 1 and G 2 are correct kernels of dimension 4 2 h1isogenies and 2 h2 -isogenies and the codomains of F 1 and F 2 agree. Finally, since the points have been multiplied by α in the definition of G 1 ,G 2 . The isogeny ρ 2 • F • ρ 1 can be factored by [α] and so the evaluation on the points of order α will be 0. Thus, the output of IsogVerif 4 dim is 1.

⊓ ⊔ Proposition 6. The scheme DeuringVRF 4,z satisfies unconditional full uniqueness.

Proof. Let us assume that we have a value v = H out (x||j(E ′ )) passing the verification for an input x, a public key pk and proof π. We want to prove that the only possibility is that j(E ′ ) = j(E/⟨R x ⟩). By Proposition 5, we know that a valid isogeny representation for an isogeny φ : E → E ′ can be extracted from pk and π. Since φ(R x ) = 0, we know that ⟨R x ⟩ ⊂ ker φ. This implies that N divides the degree of φ. But since φ has degree smaller than 2 h /α 2 and we assumed that h was the smallest exponent such that 2 h > N α 2 then deg φ must be N . So ker φ = ⟨R x ⟩ and so E ′ must be isomorphic to E/⟨R x ⟩ which proves the result.

⊓ ⊔

4 The algorithmic instantiation of DeuringVRF y,z .

In this section, we fill the blanks left in Section 3.1, and dive into the more complicated sub-algorithms of our VRF construction. Our goal is to be able to instantiate the DeuringVRF y,z family for (y, z) ∈ {(2, 1), (2, 2), (4, 1), (4, 2)}. Thus, this section will introduce the three following algorithms: IsogenyRepresentation 4,z , CommonIsogenyRepresentation 2,z and IsogenyRepresentation 2,z for z ∈ {1, 2}. The description of those algorithms can be found in Section 4.3, but several building blocks are required before that. The most crucial sub-algorithm is an algorithm to evaluate an isogeny from its ideal representation. This will be the focus of Section 4.2. This evaluation algorithm itself is built on top of another algorithm, which is our most basic build block : IdealToIsogeny z , an algorithm to realize the effective the Deuring correspondence by translating an ideal of smooth norm given in input to its corresponding isogeny. Here, the label z plays the same role as in DeuringVRF y,z , it indicates that the algorithm will make use of isogenies in dimension z. The algorithm IdealToIsogeny z is introduced in Section 4.1 with all the necessary building blocks to instantiate it with z = 1, 2.

We will provide in Section 5.3 a complete discussion on the various parameter constraints and choices to instantiate our DeuringVRF y,z family. In the rest of this section, we omit most efficiency considerations even when they underlie some of the design choices and focus on obtaining correct algorithms.

Algorithms for the effective Deuring correspondence

The goal of this section is to instantiate the algorithm IdealToIsogeny z ℓ • to translate an ideal of norm a power of ℓ into their corresponding isogeny for some small prime ℓ and z = 1, 2. The isogeny to be computed is always of dimension 1 (even when z > 1), but isogenies of dimension z will be used during the execution of IdealToIsogeny z ℓ • . For the rest of this section, we fix an exponent e such that the ℓ e torsion of supersingular curves can be defined over F p 2 . For simplicity, we will target the case where the norm of the input to IdealToIsogeny z ℓ • is exactly ℓ ne for some integer n. The generic case can be derived trivially from there.

In fact, our algorithm IdealToIsogeny z ℓ • is not new. It has been introduced as IdealToIsogenyEichler ℓ • for z = 1 in [16, Algorithm 5] in the context of the SQIsign signature scheme. When the input has norm ℓ ne , the algorithm IdealToIsogeny Eichler ℓ • consists in n sequential executions of a sub-algorithm IdealToIsogeny Eichler ℓ e ([16, Algorithm 4]) that performs the translation for inputs of norm ℓ e exactly.

For z = 2, we will keep the same structure as z = 1 for the high-level algorithm IdealToIsogeny 2 ℓ • . Thus, we give a common description (with z as a non-specified parameter) at the end of this section as Algorithm 8.

We introduce an algorithm IdealToIsogeny 2 ℓ e to replace IdealToIsogenyEichler ℓ e when z = 2. A detailed description of IdealToIsogenyEichler ℓ e (that we relabel as IdealToIsogeny 1 ℓ e ) can be found in Appendix A. We start with a brief summary of the ideas underlying IdealToIsogeny 1 ℓ e to provide some insights on how and why its dimension 2 counterpart was designed.

Translating ideal to isogenies with isogenies in dimension 1, a summary. The main subtlety in IdealToIsogeny 1 ℓ • is that each translation of length e "consumes" the ℓ e torsion points (those points are necessary to express the kernel of the ℓ eisogenies to be translated). This is why the algorithm IdealToIsogeny 1 ℓ e performs a "refresh" operation, necessary to all its subsequent executions inside Ideal-ToIsogeny 1 ℓ • . In IdealToIsogeny 1 ℓ e , this refresh is done by evaluating some wellchosen endomorphism θ of the domain curve on the ℓ e torsion. In dimension 1, there is only one way to ensure that this endomorphism θ can be efficiently evaluated: ensure that deg θ|T 2 where T is a smooth integer such that the Ttorsion points are defined over a small field extension. Endomorphisms satisfying these constraintes can be found using the SpecialEichlerNorm T algorithm [16, Algorithm 3]. But this algorithm only succeeds when the value of T is quite big (T ≈ p 5/4 ).

This constraint on the size of T is the main cause of the relative inefficiency of IdealToIsogeny 1 ℓ • , because having the T -torsion defined over a small field extension of F p 2 implies a very strong constraint on the two integers p and T . A suitable solution can be always be found, but the smoothness bound of T might not be very small. This smoothness bound in turn impacts the cost of the T -isogenies that must be computed in order to evaluate the endomorphism θ (the smoother the faster the computation will be). Moreover, we will see in Section 5.3 that, in the context of our DeuringVRF y,1 protocol, there are some additional constraints to take into account that complicate even more the search for a smooth T .

This limitation is the main motivation to introduce a variant with z = 2. The goal of this algorithm is to overcome the obstacle of the case z = 1 by exploiting the 2 dim isogeny representation.

Translating ideal to isogenies with isogenies in dimension 2, an overview. Our goal with the case z = 2 is to simplify the computation of the endomorpism θ. To overcome the obstacles encountered with the dimension 1 algorithm, we follow a reasoning that resembles the idea behind the recent SQIsignHD scheme [START_REF] Dartois | Sqisignhd: New dimensions in cryptography[END_REF]: by embedding θ in an 2 h -isogeny of higher dimension (for some exponent h), we can relax most of the constraints on its degree (and in particular the smoothness). This means that we can get rid of SpecialEichlerNorm T and simply look for θ among the endomorphism of small norm in End(E). The concrete requirements for IdealToIsogeny 2 ℓ e are in fact slightly more complex than that. In the next paragraph, we introduce an algorithm RandomGoodEndomorphism to find suitable endomorphisms.

Remark 2. Unlike SQIsignHD, where the dimension 4 is required, we will see that the dimension 2 is enough for our purpose because we can use endomorphisms to apply Kani's Lemma. This idea could not be applied to obtain a dimension 2 equivalent of SQIsignHD protocol because that would imply to reveal endomorphisms of the public key curve which would destroy the security of the scheme (since the endomorphism ring of the public key must remain secret). Also, note that it should probably be possible to devise IdealToIsogeny z ℓ e algorithms for z = 4 (or even z = 8) following the same ideas. However, there do not really seem to be a gain that would compensate for the efficiency loss induced by the cost of the higher dimension computations.

In the remaining of this section, we assume ℓ ̸ = 2, and we fix and exponent f such that the 2 f torsion of supersingular curves is defined over F p 2 .

Finding suitable endomorphisms for the dimension 2 representation. As explained in Section 2.3, the 2 dim representation for any isogeny φ of degree a requires a second isogeny β of degree b such that 2 h = a + b. In our case, the isogeny we want to represent is an endomorphism θ. Following an idea introduced in [8], we propose to choose β as an endomorphism of E as well. With the method described in [8] (see the algorithm OrientDiamondDim2), it is possible to find efficiently two endomorphisms θ, β in the same quadratic order satisfying the norm equation 2 h = n(θ) + n(β). Since θ, β are each defined by two coefficients, this is quaternary quadratic equation that can be solved using Cornacchia's algorithm [10] when 2 h is big enough compared to n. In Appendix B, we introduce an algorithm ExtendedOrientDiamondDim2 (which is a simple variant of [8, Algorithm 1]) to handle that task.

As in SpecialEichlerNorm, the endomorphism θ computed by RandomGood-Endomorphism must satisfy an additional constraint: it can not be contained in the Eichler order Z + K for some ideal K of norm ℓ given in input. This additional constraint is quite strong and it implies that RandomGoodEndomorphism will always fail for some maximal order O. Fortunately, it can be shown heuristically that this will only happen with very small probability when we consider a random supersingular curve, and this will be enough for our need. We provide some more insights on these potential failures later in this section.

Before proving the correctness and termination of our algorithm, we need to state a preliminary result. The following lemma, adapted from a result first

Algorithm 6 RandomGoodEndomorphism(O, K, h)

Input: A maximal order O, an O-ideal K of norm ℓ, and an integer h.

Output: θ, β ∈ O ∖ (2O ∪ Z + K) and 2 h = n(θ) + n(β), gcd(n(θ), n(β)) = 1.
1: Sample random element ω of norm smaller than 2 h in O ⊥ until ω is not contained in Z + K and Dω = tr(ω) 2 -4n(ω) is equal to 5 mod 8. 2: if no such elements ω can be found then 3:

Return ⊥ 4:

end if 5: if ExtendedOrientDiamondDim2(Dω, h) ̸ = ⊥ then 6: θ, β = ExtendedOrientDiamondDim2(D, h). 7:
Return θ, β. 8: end if 9: return Return ⊥.

mentioned by Elkies in [20] tells us that we can always find a non-trivial endomorphism ω of norm smaller than p 2/3 . We have also included a result by Boneh and Love regarding the number of curves having an endomorphism of norm smaller than some bound [START_REF] Love | Supersingular curves with small noninteger endomorphisms[END_REF]Proposition A.3].

Lemma 2. For any supersingular curve E, there exists a non-trivial endomorphism ω : E → E of degree smaller than 2p 2/3 . Moreover, given any B < p 2/3 , the number of curves having a non-trivial endomorphism of norm smaller than B is in O(B 3/2 ).

Proof. Let O be isomorphic to End(E). Let us consider the rank 3 lattice O/Z. Since the reduced discriminant of O is p, the determinant of O/Z is p 2 and, by Minkowski's theorem, it must contain an element θ of norm smaller than 2p 2/3 . The second result regaring the number of curves having a non-trivial endomorphism smaller than B was proven as [START_REF] Love | Supersingular curves with small noninteger endomorphisms[END_REF]Proposition A.3].

⊓ ⊔

The correctness and complexity of ExtendedOrientDiamondDim2 is stated in Proposition 10 of Appendix B. This proposition holds under Heuristic 1 which is a plausible heuristic assumption (adapted from [8,Heuristic 13]) regarding the distribution of numbers of the form 2 e +D(1+z 2 ) where D is the discriminant of a quadratic imaginary order equal to 1 mod 4. Thus, Proposition 7 holds under the same heuristic assumption. Proposition 7. Assuming Heuristic 1, for any κ > 0, there exists η = Θ(log log(p)+ κ) such that, if h > 2/3 log(p) + η, then RandomGoodEndomorphism will succeed with probability bigger than 1 -2 -κ on input O, K, h if the maximal order O is a uniformly random maximal order in B p,∞ , and K is a random O-ideal of norm ℓ.

Proof. For the algorithm to fail, either no suitable ω was found or Extended-OrientDiamondDim2 failed on input D ω , h.

Let us write α 1 , α 2 , α 3 for the three successive minimas of O ⊥ . First, note that if n(α 3 ) < 2 h , then there exists an endomorphism of norm smaller than 2 h that is not contained in Z + K. Indeed, if α 1 , α 2 , α 3 we cannot have all three elements α 1 , α 2 , α 3 contained in Z + K as O/ℓO ∼ = M 2 (Z/ℓZ) and so O ⊥ /ℓO ⊥ ∼ = M 2 (Z/ℓZ)/Z. Let us now take the smallest ω ∈ O ⊥ such that n(ω) < A and ω ̸ ∈ Z + K and D ω = 5 mod 8.

Then, by Proposition 10, the success probability of ExtendedOrientDiamondDim2 on input D ω , h is upper-bounded by

(1 -λ 0 /log(|D ω |)) √ 2 h /|Dω| .
For D ω and h big enough, this function will clearly increase as D ω increases. Thus, for any O such that n(ω) < A (which implies D ω < 4A) we can upperbound the failure probability of RandomGoodEndomorphism on input O by

(1 -λ 0 / log(4A)) √ 2 h+2 /A .
If we write p(A), the probability that a random O in B p,∞ is such that n(ω) < A, then the conditional probability formula associated to a trivial majoration of any probability by 1 gives us that the probability of failure of RandomGood-Endomorphism on a random input O is upper-bounded by

p(A) + (1 -λ 0 / log(4A)) √ 2 h+2 /A
We can now use Lemma 2 to upper-bound p(A).

By Minkowski's second theorem, we know that n(α 1 )n(α 2 )n(α 3 ) ≤ µ 0 p 2 for some constant µ 0 . Thus, if n(α 3 ) > A, then n(α 1 ) ≤ µ 1 p/ √ A for some constant µ 1 . By Lemma 2, this implies that the number of curves with n(α 3 ) < A is smaller than µ 2 p 3/2 /A 3/4 for some constant µ 2 .

It is sufficient that a constant number of (linearly-independent) endomorphisms in O ⊥ are smaller than A, to get an element ω that is not in Z + K and of discriminant equal to 5 mod 8. Since α 1 , α 2 , α 3 constitutes a basis of elements of norm smaller than A, we obtain enough elements to find ω with constant probability and so we get p(A) ≤ µ 3 √ p/A 3/4 for some constant µ 3 .

We derive the following upper-bound on the failure probability:

µ 3 √ p A 3/4 + 1 - λ 0 log(4A) √ 2 h /A (3)
Now, it is easily verified that for any κ > 0, there exists η = Θ(κ + log log(p)) such that if h > 2/3 log(p) + η, then there exists a = 2/3 log(p) + Θ(κ) smaller than h such that the upper-bound of the failure probability given in Equation 3is smaller than 2 -κ when A = 2 a . ⊓ ⊔ Potential failures of RandomGoodEndomorphism. We can extract easily the cases where RandomGoodEndomorphism will potentially fail: when the smallest endomorphism of O ⊥ is smaller than usual so all the endomorphisms of norm smaller than 2 h all lie in the same quadratic order that is either either contained in Z + K or does not have a discriminant equal to 5 mod 8. Depending on the value of p and h, this might happen for some maximal orders and values of K. In those cases, RandomGoodEndomorphism will simply fail. The results of Proposition 7 allow us to adjust the value of h to reduce the probability of this bad event as much as possible. Moreover, note that it can be shown that the third successive minima must be in Θ(p). Thus, when h > log(p) the proportion of failing maximal order will decrease very quickly to 0. In all of our applications of RandomGoodEndomorphism, it should not be too hard to rerandomize the choice of maximal order, thus these failures should not really be problematic as soon as we are careful to pick a value of h that is not too close to 2/3 log(p).

In particular, in our application to DeuringVRF y,2 , we need to take h ≈ log(p) and so we expect those failures to happen with negligible probability. We made some experiments by sampling random maximal orders as right orders of O 0ideals of norm 2 256 (for a prime p ≈ 2 256 ) and did not find a single example where the algorithm failed out of thousands of trials. The code is provided as supplementary material.

The full ideal-to-isogeny subroutine in dimension 2. As we explained above, we obtain IdealToIsogeny 2 by adapting IdealToIsogeny 1 to use RandomGoodEndomorphism instead of SpecialEichlerNorm and compute θ from a 2 dim isogeny representation rather than as a T -isogeny. This yields Algorithm 7. We remind the reader that we use in a black-box manner an algorithm IsogEval 2 dim to evaluate isogenies from their 2 dim-representation.

The algorithm IdealToIsogeny 2 ℓ e also assumes the knowledge of a curve E 0 with its endomorphism ring End(E 0 ). For this curve, it is known how to evaluate any endomorphism θ 0 ∈ End(E 0 ). Proposition 8. Let O, I, J, φ J , P be the input to IdealToIsogeny 2 ℓ e and let K = J + Oℓ. If RandomGoodEndomorphism(O, K, h) ̸ = ⊥, then IdealToIsogeny 2 ℓ e returns the correct output on input O, I, K, φ J , P .

Proof. By [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF]Lemma 8], if the point Q is equal to θ(P ), then the group ⟨[C]P + [D]Q⟩ is the kernel of the desired isogeny φ I . Thus, for our purpose, it suffices to show that Q is indeed equal to θ(P ). By the presumed correctness of IsogEval 2 dim , we need to show that the isogeny representation c n(θ) 2 dim (E), s θ 2 dim is correct. First, note that since θ, β are commutative endomorphisms, the commutative diagram they generate only involvde the curve E and we have θ ′ = θ and β ′ = β. Second, we need to verify that U, V = θ(R, S), W, X = β(R, S) and Y, Z = β • θ(R, S). Following the various computations, we see that

U, V = [t 2 ]φ J • θ 0 • φJ (R, S). By definition of θ 0 this is [t 2 ][deg φ 2 J ]θ(R, S) = θ(R, S)
. The same can be shown for W, X, and for Y, Z with

β 0 •θ 0 = [deg φ J ] φJ •β •θ •φ J .
This defines a correct 2 dim isogeny representation according to the formulas given in Section 2.3 and this concludes the proof.

⊓ ⊔

The generic ideal-to-isogeny algorithm. We are now ready to introduce the full algorithm IdealToIsogeny z algorithm. As we said at the beginning of this section, this is a simple generalization of [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF]Algorithm 5]. We refer the reader to [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF] for the proof of correctness.

Evaluating isogenies from the ideal representation

In this section, we introduce two algorithms to evaluate isogenies from their ideal representation. The first one is called IsogEval z id (see Algorithm 9 below) and works only when order of the point P is coprime to ℓ the small prime used in IdealToIsogeny z ℓ • . This algorithm is greatly inspired from [35, Algorithm 2] (or equivalently [23,Algorithm 1]). In our application ofIsogEval z id , we will need to evaluate points of order 2 f . This will not be problematic when z = 2 because we take ℓ ̸ = 2. However, with our choices of parameters when z = 1, only the translation of isogenies of degree 2 • will be efficient (more on that in Section 5.1). Thus, IsogEval 1 id will not be applicable efficiently and this is why we need to introduce a second algorithm called IsogEvalNonCoprime 1 id to handle the case where the order of the points is not coprime to ℓ.

When the order is coprime to ℓ. The high level idea is the following: find an ideal of norm ℓ • equivalent to the ideal in input with the KLPT algorithm from [START_REF] Kohel | On the quaternion ℓ-isogeny path problem[END_REF], compute the corresponding isogeny with IdealToIsogeny z ℓ • and use this isogeny to compute the final output. As we said above, this algorithm is now pretty standard. We refer the reader to [START_REF] Leroux | Quaternion Algebra and isogeny-based cryptography[END_REF]Section 4.2.4] for a more detailed description, correctness proof and complexity analysis, including the presentation of all the necessary building blocks. Proof. Let P i , Q i be the respective generators of G i , H i for i = 1, 2, 3. We know there exists λ i such that φ(

P i ) = [λ i ]Q i . By assumption that G 1 ∩ G 2 = {0}, the two points Q 1 , Q 2 form a basis of E[2 f ]. By solving a bidimensional discrete logarithm in E[2 f ], one can find µ 1 , µ 2 such that Q 3 = [µ 1 ]Q 1 +[µ 2 ]Q 2 .
Doing the same on E 0 , we obtain P 3 = [ν 1 ]P 1 + [ν 2 ]P 2 . Then, we get that λ 3 /λ i = ν i /µ i for i = 1, 2 (µ i ̸ = 0 since H 3 ∩H 1 = {0}, H 3 ∩H 2 = {0} because ψ has degree coprime to ℓ). Thus, the three values R i = λ 3 ψ(P i ) can be computed for i = 1, 2, 3.

Then, computing the discrete logarithm of e(P 1 , P 2 ) and e(R 1 , R 2 ), we get the scalar λ 2 3 N mod 2 f . Dividing by N and computing a squareroot s of the result mod 2 f , we get S i = s -1 R i = ±ψ(P i ). Then, to evaluate any point P ∈ E 0 [2 f ] is suffices to find a, b such that P = aP 1 + bP 2 and to output aS 1 + bS 2 .

It is clear that all the operations above can be performed in O (poly(log(p) + f )).

⊓ ⊔

The algorithm IsogEvalNonCoprime 1 id uses several building blocks of the Deuring correspondence based on isogenies in dimension 1. There is the SpecialEichler-Norm T 2 algorithm (see [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF]Algorithm 3]) to compute endomorphisms of norm dividing T 2 in any maximal order barred of an Eichler order of level ℓ, and the IdealToKernel D and IdealToIsogeny D algorithms to translate an ideal of norm D in the corresponding kernel and isogeny respectively (see [36, Proof. The heuristics involved in this proof are the same than in the proofs of correctness and termination of KLPT 2 • , IdealToKernel 2 f IdealToIsogeny 1 ℓ • and SpecialEichlerNorm T (see [START_REF] Leroux | Quaternion Algebra and isogeny-based cryptography[END_REF] and [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF] for statements and proofs regarding the termination and correctness of these algorithms).

The termination of IsogEvalNonCoprime 1 follows from the termination of all the building blocks. The condition on T and the constant success probability both come from [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF]Proposition 6].

Let us now prove correctness. After the ideal J and the isogeny φ J have been computed together with the point Q. The steps 5 to 15 are essentially the same that are performed in IdealToIsogeny 1 ℓ e (that we describe in Appendix A). We refer the reader to the proof of [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF]Proposition 6] for a proof that the subgroup ⟨Q i ⟩ is the kernel of the ideal [I] * I i for i = 1, 2, 3. This means that ⟨Q i ⟩ = φ I (⟨P i ⟩) for i = 1, 2, 3.

Steps 17 to 22 correspond to the algorithm described in the proof of Lemma 3. We refer the reader to this proof to show that S 1 , S 2 , S 3 = ±φ I (P 1 , P 2 , P

Parameters and Performances

In this section we discuss the choice of parameters to instantiate our Deuring-VRF y,z family as efficiently as possible at a given level of security λ. We propose concrete sets of parameters for λ = 128 presumably corresponding to the NIST-I level of security. Then, we assess the features of the different variants of our VRF family.

We remind that we target pairs y, z ∈ {(2, 1), (2, 2), (4, 1), (4, 2)}. We will see below that the value of z ∈ {1, 2} mostly determines our choice of prime p.

Parameter computation.

The main parameter we need to choose is the value of p. After that is done, all the other parameters can be deduced almost directly. Before diving into how to choose this prime concretely, let us give a brief reminder on the various constraints and requirements.

A summary of the constraints for security. The generic key recovery attack has complexity O( √ p). Thus, we need to take log(p) = 2λ. Similarly, the best Algorithm 13 IsogenyRepresentation 2,z (I, J, φI (P ), φI (Q))

Input: I an O0-ideal, J an OR(I)-ideal of norm N , the image φI (P, Q) of a basis known algorithm to compute N -isogenies has complexity O( √ N ). Thus, we need to target log(N ) = 2λ.

A summary of the constraints for efficiency. We need to take a prime N such that p k = 1 mod N for the smallest possible k to ensure that the N -torsion points are defined over F p k . We need that the 2 f torsion is defined over F p 2 for a value of f such that 2 2f > N . We also need to have other points of smooth order defined over F p 2 , but the exact requirement depends on the value of z.

When z = 1. In that case, we need to have the T -torsion defined over F p 2 where T is a smooth and odd number bigger than p 5/4 (this is a requirement of the IdealToIsogeny 1 2 e ) algorithm). In that case, the prime p that we need is a so-called "SQIsign prime" as in [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF]. The main difference between our setting and SQIsign's is that we have the additional constraints that the power of two exponent f must be of size ≈ log(p)/2 and that there must be a big prime divisor of p k -1 for a small value of k. The second is not too hard to satisfy for any given p if we allow the value of k to grow slightly (even though it might be hard to compute the value of N due to the cost of factorization). However, the first constraint on the size of f is quite restrictive and will be the main obstacle for an efficient instantiation of our scheme. Indeed, with such a big value of f , the smoothness bound of T is necessarily quite big.

We will give later an example of primes satisyfing almost all of our constraints. No extensive computation was involved to find this prime that we just use as a proof of concept. With more work, more efficient primes can certainly be found.

When z = 2. For our algorithms in the setting z = 2, the additional torsion requirement comes from IdealToIsogeny 2 ℓ • , that we will use for some small prime ℓ ̸ = 2. This algorithm makes calls to the sub-algorithm IdealToIsogeny 2 ℓ e for the value of e such that the ℓ e -torsion is defined over F p 2 . To reduce as much as possible the number of calls to this algorithm it is important to maximize the value of e. The best possible primes we can hope are the so-called "SIDH-primes" of the form p = c2 f ℓ e -1 with a value of c as small as possible. In our case, we also need that p + 1 has a big prime factor N . Fortunately this additional constraint is quite easy to satisfy. We can simply iterate over small values of c until a suitable candidate is found. Asymptotically, we can expect to find it after O(log(p) 2 ) attempts. With this choice of prime we will be able to define the 2 f , ℓ e -torsion and N -torsion on F p 2 (although not on the same curve) which is essentially the best we can hope for.

There is a bit of freedom regarding the choice of the exact value of f . Indeed, the minimal requirement is that 2 2f > N . However, the probability of success of the executions of the algorithm RandomGoodEndomorphism inside IdealTo-Isogeny 2 ℓ e is directly impacted by the value of f . Given Proposition 7, the requirement 2 2f > N , which implies that f is at least equal to 1/2 log(p), should be enough to ensure a negligible failure probability. Remark 3. It might be worth taking a value of f significantly bigger than this lower bound. Indeed, even though a bigger value of f implies a smaller value of e (which we want to maximize as we explained), if f go as far as 2/3 log(p), then we might be able to compute the 2 dim representation of the endomorphism θ directly (without having to cut it in half as we do now), which might allow us to use a faster IsogEval 2 dim algorithm. In the toy example that we provide, we take ℓ = 3 and 2 f ≈ 3 e ≈ √ p, but a careful implementation might prove that taking f ≈ 2/3 log(p) is better for effiency. We leave to future work the problem of answering to this interrogation.

Computation of remaining public parameters. Now that we have specified the choices of all the integral parameters, we need to explain how to compute the remaining public parameters of our scheme. In particular, we need to find a basis P 0 , Q 0 of E 0 [N ], an endomorphism ι such that ι(P 0 ) = Q 0 and the kernel ideal I P0 . This operation is not completely trivial as N is a large prime number, but it can be done as we explain next. Let us take as E 0 one of the curves of known endomorphism ring O 0 (for instance the curve of j-invariant 1728).

Our solution uses the fact that we can evaluate efficiently any endomorphisms of E 0 on points of E 0 . First, we can select R 0 as any point of order N . Then, we compute α ∈ End(E 0 ) of norm satisfying gcd(n(α), N 2 ) = N . Then, we can set P 0 = α(R 0 ). If P 0 = 0 we can try with another R 0 until we have P 0 of order N . When P 0 has order N , the ideal I P0 is equal to O 0 ⟨α, N ⟩. To finish the precomputation, we can take any endomorphism ι of norm coprime to N and we compute Q 0 = ι(P 0 ).

Example parameters for λ = 128

We now describe concrete parameters for λ = 128 that are estimated to reach the NIST-I security level. z = 1. We found the following prime p using the 2x n -1 method introduced in [START_REF] Costello | B-sidh: supersingular isogeny diffie-hellman using twisted torsion[END_REF]. Given the requirement to have a power of 2 of size ≈ √ p dividing p 2 -1, we found that method more efficient than the XGCD method introduced in [START_REF] De Feo | Sqisign: compact postquantum signatures from quaternions and isogenies[END_REF].

p + 1 = 2 • (2 32 • 3029820973) 4
The biggest prime factor of T |p 2 -1 is 106273. We found the following candidate value for N : 393726873534132384928444413735281749360848116391706711676559356809147 among the divisors of p 2 + p + 1. In that case, the points of order N can be defined over

F p 12 since #E(F p 12 ) = (p 6 -1) 2 = (p 3 + 1)(p 2 + p + 1)(p -1) 2 .
This N is only of 228 bits which is a bit short of the desired 256 bits. However, given that the algorithm from [2] requires also O( √ N ) memory and that we have omitted logarithmic factors in the complexity estimate, this value of N should already be enough the make the OMIP very hard to break. If needed, more secure parameters can be found.

For y = 4, we can take the parameter α to be equal to 87|p 2 -1. We have the equality

Sizes

In this section, we explain how to compute the sizes given in Table 1 for the parameters given in Section 5.2. We provide abstract formulas that are true for any security level λ.

On compression. To reduce the size of the public key and proof of our VRF family, we can use standard compression techniques for elliptic curves and their points (described for instance in [12, section 7.1]).

-Curves can be represented by their j-invariants which are always defined over F p 2 for supersingular curves. -Any point of smooth order T can be represented by two scalars mod T (as coefficients of this point in a prescribed basis). The image of a full basis of order T under an isogeny can be represented as 3 scalars mod T (the fourth one can be recovered with the Weil pairing). -A point of arbitrary order N defined over F p k can always be represented as one element over F p k and a bit.

Moreover, the points P, Q of order 2 f provided in c N ydim (E) for y = 2, 4 can be any basis of E[2 f ]. Thus they can be computed in a deterministic manner from the curve E and we can omit them from c N ydim (E).

Computation of key and proof sizes. Using the compressed representations that we described above for all the points and curves involved in our construction, we can deduce the size of keys and proofs of our DeuringVRF y,z family for all values of y, z from the security parameter λ. To comply with the security requirements, we take log(p) ≈ 2λ and f ≈ λ. We remind the reader that the integer k is such that F p k is the smallest field extension on which the points of order N are defined. The public key sizes will depend on this parameter. This parameter k is the only place where the value of z will impact the sizes which depend mostly on the value of y. When y = 2, the public key is made of 2 curves, 2 points of order N and a basis of order 2 f . This can be represented in 8λ + 4kλ + 3λ bits. The proof is made of two curves, and two images of a basis of order 2 f , so this is 8λ + 6λ.

When y = 4, the public key is simply made of one curve and two points of order N . This is 4λ + 4kλ bits. The proof is made of one curve and the image of one basis of order 2 f so this is 4λ + 3λ.

In both cases, since we need the function f in to be injective to avoid collisions, the input space cannot be bigger than N . Thus, we can take the input space has size n 1 (λ) = 2λ (of course this is an upper-bound, smaller values of n 1 (λ) can be considered). A value of n 2 (λ) = 2λ seems also to be reasonable.

These results are summarized in Table 3.

y Input (bits) Output (bits) Public Key (bits) Proof (bits) 2 2λ 2λ (4k + 11)λ 14λ 4 2λ 2λ (4k + 4)λ 7λ Table 3. Size of the inputs, outputs, keys and proofs of the DeuringVRFy,z schemes.

Prospects, open questions and future work

We have introduced a new family DeuringVRF y,z of VRF protocols based on isogenies between supersingular curves by making use of two important subfields of isogeny-based cryptography: the Deuring correspondence and isogenies between abelian varieties of high dimension. The security of our new problem stands upon a new security assumption in the random oracle model. Despite its novelty, this new assumption is related to various well-studied problem, and its hardness appears quite plausible. Interestingly, progress in the resolution of this progress could have very positive impacts on the efficiency of other areas of isogeny-based cryptography.

Our new scheme relies on various algorithmic block related to the Deuring correspondence that might be of independent interest. In particular, we have proposed an alternate method to perform the translation of ideal to their corresponding isogenies with the help of isogenies in dimension 2, that we believe could very well improve upon the state of the art algorithms.

Each variant of our new construction is more compact (by a good margin) than every other post-quantum VRF protocol and this is the main advantage of our new protocol.

On an implementation of our algorithms and protocols. The major remaining open question about our new protocol is its efficiency. While several related works have demonstrated that our construction will not be completely impractical, it is not easy to guess how fast it can concretely be. A part of the isogeny-community is currently dedicating significant efforts to implementing efficiently isogenies between abelian varieties of dimension 2 and 4 and the results are already very promising [13] with computation times on the order of tenths of seconds for dimension 2 isogenies and on the order of seconds for dimension 4 isogenies for a sage implementation. We plan to be able to provide an efficient implementation of our protocol in the near future. Other isogeny-based protocols such as the SQIsign signature scheme could benefit from this implementation if our new IdealToIsogeny 2 algorithm turns out to be as fast as we hope.

Algorithm 1 Algorithm 2

 12 KeyGen y,z (pp) Input: Public parameters pp. Output: A pair of DeuringVRFy,z keys sk, pk. 1: Take some e0 = 2λ and generate a random O0-ideal I of norm ℓ e 0 . 2: Compute φI = IdealToIsogeny z ℓ • (I). 3: Set θ = φI • ι0 • φI , R = φI (P0) and S = [ℓ e 0 ]φI (Q0). 4: Generate a random M = ( a b c d ) ∈ GL2(Z/N Z). 5: Set (P, Q) ← ([a]R + [b]S, [c]R + [d]S). 6: Compute IP = [I • (a + bθ)] * IP 0 . 7: Compute the scalars λ, µ such that (λ + µθ)(P ) = Q and set θ as λ + µθ. 8: Compute U, V , a basis of E[2 f ], and U0, V0 = φI (P, Q). 9: Compute c N ydim (E) = CommonIsogenyRepresentation y,z (I, U, V, U0, V0). 10: return (sk, pk) = (I, IP , θ, U0, V0), (E, P, Q, c N ydim (E)) . VRFEval y,z (sk, x) Input: A DeuringVRFy,z secret key, and an input x ∈ {0, 1} n 1 (λ) . Output: A proof π and the evaluation v of the DeuringVRFy,z function on input x. 1: Parse sk as I, IP , θ, U0, V0. 2: Compute (r : s) = f in (x). 3: Compute Ix = [O(r + sθ)] * IP . 4: Compute Ex and s φ ydim = IsogenyRepresentation y,z (I, Ix, U0, V0). 5: Set π as j(Ex), s φ ydim . 6: Compute v = Hout(x || j(Ex)). 7: return (π, v).

Definition 4 .

 4 Given two odd prime N ̸ = p, a FIXed Degree N -Isogeny Oracle (N -FIXDIO ) takes in input a supersingular elliptic curve E/F p 2 , some common information c N xx (E), and a point P ∈ E[N ] and outputs the j-invariant j(E/⟨P ⟩) and an isogeny representation s φ xx for the N -isogeny φ : E → E/⟨P ⟩. Problem 1. One-More Isogeny Problem (OMIP xx ) Given two odd primes N ̸ = p, let E be a supersingular elliptic curve and c N xx (E) the associated common information. Given access to the N -FIXDIO xx on input E, c N

Algorithm 7 1 J

 71 IdealToIsogeny 2 ℓ e (O, I, J, φ J , P )Input: I a left O-ideal of norm ℓ e , an (O0, O)-ideal J of norm in ℓ • and φJ : E0 → E the corresponding isogeny, the generatorP ∈ E[ℓ e ] of ker φK s.t φJ = φ K ′ • φK . Output: φI of degree ℓ e 1: Set K = J + Oℓ. 2: if RandomGoodEndomorphism(O, K, 2f ) = ⊥ then 3: Return ⊥. 4: end if 5: Compute θ, β = RandomGoodEndomorphism(O, K, h). 6: Select α ∈ I s.t. I = O⟨α, ℓ e ⟩. 7: Compute C, D s.t. α • (C + Dθ) ∈ K and gcd(C, D, ℓ) = 1 using linear algebra. 8: Compute R, S a basis of E[2 f ], t = deg φ -mod 2 f . 9: Compute W, X = φJ (R, S). 10: Set θ0 = φJ • θ • φJ ∈ End(E0) and compute U, V = θ0(W, X). 11: Set β0 = φJ • β • φJ ∈ End(E0) and compute W, X = β0(W, X) and Y, Z = β0(U, V ). 12: Compute U, V = [t 2 ]φJ (U, V ),W, X = [t 2 ]φJ (W, X),and Y, Z = [t 3 ]φJ (Y, Z). 13: Set s θ 2 dim = E, E, U, V, Y, Z, and c n(θ) 2 dim (E) = E, R, S, W, X. 14: Compute Q = IsogEval 2 dim (s θ 2 dim , c n(θ) 2 dim (E), P ) 15: Compute φI of kernel ⟨[C]P + [D]Q⟩. 16: return φI .

Algorithm 8 2 : 2 ( 4 :

 8224 IdealToIsogeny z ℓ • (I, J, φ J ) Input: I a left O-ideal of norm ℓ ne , an (O0, O)-ideal J of norm ℓ • and φJ : E0 → E the corresponding isogeny Output: φI of degree ℓ ne .1:Set Ji = J, Ii = I + ℓ f O, I ′ i = I -1 i I, Oi = O. 2: Set φi of degree ℓ f as the isogeny such that φJ = φ ′ • φi 3: Set φI = [1]E and Ei = E. 4: for i ∈ [1, n] do 5: Compute Pi ∈ Ei[ℓ f ] s.t ker φi = ⟨Pi⟩. 6:Compute φI i = IdealToIsogeny z ℓ e (Oi, Ii, Ji, φI • φJ , Pi).7:Set φi = φI i , φI = φI i • φI and Ei is the codomain of φI i . 8:Set Ji = Ji • Ii, Oi = OL(I ′ i ), Ii = I ′ i + ℓ f Oi and I ′ i = I -1 i I ′ i . 9:end for 10: return φI . Algorithm 9 IsogEval z id (I, E, P ) Input: I an ideal of Bp,∞, E an elliptic curve with End(E) ∼ = OL(I) and P ∈ E[2 f ] where ℓ is coprime to N = n(I). Output: φI (P ). 1: Compute J = KLPT ℓ • 2 (I) and set K = I • J. Set α ∈ End(E) as the endomorphism φK . Compute α(P ). 3: Compute φJ = IdealToIsogeny z ℓ • J) and compute Q = φJ (α(P )). Compute µ = n(J) -1 mod 2 f . 5: return [µ]Q.

  section 4.2.1]). The integer T is an implicit parameter of Algorithm 10.Proposition 9. (Heuristic) IsogEvalNonCoprime id1 is correct and terminates with constant probability when T > p 5/4 .

4 . 3

 43 3 ). Then, since P = [a]P 1 + [b]P 2 , we get [a]S 1 + [b]S 2 = ±φ I (P ). ⊓ ⊔ Computing high dimensional isogeny representation from the ideal representation. The goal of this section is to introduce the algorithms CommonIsogenyRepresentation y,z and IsogenyRepresentation y,z that are respectively building blocks of the Algorithm 10 IsogEvalNonCoprime 1 id (I, P ) Input: I an O0-ideal, J an OR(I)-ideal of norm N , the image φI (P, Q) of a basis P, Q of E[2 f ]. Output: s φ 4 dim for φ the isogeny corresponding to J 1: Compute the codomain E2 of J. 2: if z ̸ = 1 then 3: R = IsogEval z id (I • J, φI (P )) and S = IsogEval z id (I • J, φI (Q)). 4: else 5: R = IsogEvalNonCoprime z id (I • J, φI (P )) and S = IsogEvalNonCoprime z id (I • J, φI (Q)). 6: end if 7: return E2, R, S. Algorithm 12 CommonIsogenyRepresentation 2,z (I, P, Q, φI (P ), φI (Q))Input: I an O0-ideal, the points P, Q, φI (P ), φ(Q) whereP, Q is a basis of E[2 f ] for the codomain E of φI : E0 → E. Output: c N 2 dim (E) 1: Compute deterministically a random OR(I)-ideal J of norm 2 h -N . 2: if z =4then 3: R = IsogEval z id (I • J, φI (P )) and S = IsogEval z id (I • J, φI (Q)). 4: else if z=1 then 5: R = IsogEvalNonCoprime z id (I • J, φI (P )) and S = IsogEvalNonCoprime z id (I • J, φI (Q)). 6: end if 7: Set E3 the codomain of the isogeny corresponding to I • J. 8: return E3, P, Q, R, S.

2 2 + (574964126494597080514483051830733885074) 2

 22 258 = 87 2 • N + (364117604730757242963879384373328151625) For z = 2 and y = 2. We found the prime p p + 1 = 2 131 • 3 80 • 53 for which we have a value of N = (p -1)/2 equal to 10662908524884494611631258463500002312765285143871446016985384795473930849615871. For z = 2, y = 4. The case y = 4 is slightly harder to find, because we need to find the parameter α. To facilitate the search, we looked for primes p of the form 2 f • 3 e • c -1 for which 2 h -(α) 2 N is a prime equal to 1 mod 4 for some h < 2f and α|c. Using this idea, we found the prime p p + 1 = 2 131 • 3 71 • 41 • 293 for which we have a value of N = (p -1)/2 equal to 122789151551561527349552969205324705816674834267793279136622473322950205374463 and we have α = 1 and the following equality holds 2 258 = N + (538353225698644006063067721722936709209) 2 + (224844412377911053292857988960754557860) 2

Algorithm 14 3 : 2 : 10 :O 2 ,O 2 . 14 :

 1432102214 IdealToIsogeny 1 ℓ e (O, I, J, φ J , P ) Input: I a left O-ideal of norm ℓ f , an (O0, O)-ideal J of norm ℓ • and φJ : E0 → E the corresponding isogeny, a generator P of E[ℓ f ] ∩ ker( φJ ). Output: φI of degree ℓ f 1: Set K = J + Oℓ f . 2: Compute θ = SpecialEichlerNorm T (O, K + Oℓ) of norm dividing T 2 . Select α ∈ I s.t I = O⟨α, ℓ f ⟩. 4: Compute C, D s.t. α • (C + Dθ) ∈ K and gcd(C, D, ℓ) = 1 using linear algebra. 5: Take any n1|T and n2|T s.t n1n2 = n(θ). Compute H1 = O⟨θ, n1⟩ and H2 = O⟨θ, n2⟩. 6: Compute Li = [J] * Hi, and φi = [φJ ] * IdealToIsogeny n i (Li) for i ∈ {1, 2}. 7: Compute Q = φ2 • φ1(P ). 8: Compute φI of kernel ⟨[C]P + [D]Q⟩. 9: return φI . Heuristic 1. Let h, D O = 5 mod 8 be the inputs to Algorithm 15. If z are sampled as random integers then the integers 2 e+2 + D O (1 + z 2 ) behave like random odd integers of the same size that are either congruent to 1 modulo 4 or equal to 2 times an integer that is congruent to 1 modulo 4.Proposition 10. Assuming Heuristic 1, ExtendedOrientDiamondDim2 is correct, and there exists a constant λ 1 such that the computation will succeed with probability at least:1 -(1 -λ 0 / log(|D O |)) √ 2 h /|D O | .Algorithm 15 ExtendedOrientDiamondDim2(D O , h) Input: An imaginary quadratic order O with discriminant D O = 5 mod 8. Output: θ, β ∈ O such that n(θ) + n(β) is a 2-power and gcd(n(θ), n(β)) = 1. 1: Set x := 0, y := 0. for z ∈ ×[1, ⌊ 2 h+1 |D O | -1⌋] do 3: M := 2 h+2 + D O (z 2 + 1). 4: if M is a prime such that M ≡ 1 mod 4 or M = 2M ′ where M ′ is a prime such that M ′ ≡ 1 mod 4 then 5: Use Cornacchia's algorithm to find X, Y such that X 2 + Y 2 = M . 6: Set x = (X -D O )/2 and y = (Y -zD O )if x = 0 and y = 0 then 11: Return ⊥. 12: end if 13: θ := x + D O + √ D β := y + z D O + √ D return θ, β.

  Set E2 the codomain of the isogeny corresponding to I • J. 7: Compute deterministically a random OR(I)-idealJ ′ of norm 2 h -N . 8: Set K = I • J • [J] * J ′ .

					P, Q
		of E[2 f ].
	Output: s φ 2 dim
	1: if z =4 then
	2:	R2 = IsogEval z id (I • J, φI (P )) and S2 = IsogEval z id (I • J, φI (Q)).
	3: else if z=1 then
	4:	R2 = IsogEvalNonCoprime z id (I • J, φI (P )) and S2 = IsogEvalNonCoprime z id (I •
		J, φI (Q)).
	5: end if
	6: 9: if z =4 then
	10:	R4 = IsogEval z id (K, φI (P )) and S4 = IsogEval z id (K, φI (Q)).
	11: else if z=1 then
	12:	R4 IsogEvalNonCoprime z = id (K, φI (Q)). IsogEvalNonCoprime z id (K, φI (P ))	and	S4	=
	13: end if
	14: Set E4 the codomain of the isogeny corresponding to K.
	15: return E2, R2, S2, E4, R4, S4.

When the order is not coprime to ℓ. When we want to use IsogEval z id with ℓ = 2, the main problem we encounter is that n(J) is not invertible mod 2 f . Fortunately, there is a way to circumvent this issue by applying the following idea that underlies IdealToIsogenyEichler ℓ e : given an isogeny ψ : E 0 → E of arbitrary degree coprime to ℓ, another isogeny φ J : E 0 → E of degree ℓ • , an endomorphism θ of E of norm coprime to ℓ can be used to compute the image of any subgroup G ⊂ E 0 [G] efficiently, assuming a few conditions on θ.

Our algorithm IsogEvalNonCoprime 1 id is obtained by combining this idea with the algorithm introduced in the proof of Lemma 3 below to obtain the images of an isogeny on given points of smooth order from the images of this isogeny on subgroups of the same order. Lemma 3. Let N be an integer coprime to some small prime ℓ. Let E 0 , E be two elliptic curves connected by an isogeny ψ :

and computes ψ(P ) up to sign. KeyGen y,z and VRFEval y,z algorithms of our DeuringVRF y,z scheme. Given the pairs y, z that we target, we only need this function for y = 2, 4. These algorithms can be derived in a straightforward manner from the definition of the 2 dim and 4 dim representation. They mainly consists in applications of IsogEval id z and Isog-EvalNonCoprime id 1 . We start with the simpler case y = 4.

Constructing the 4 dim isogeny representation. The CommonIsogenyRepresentation 4,z algorithm is trivial, it simply outputs the points P, Q. We do not give a more detailed description than that. The IsogenyRepresentation 4,z algorithm simply consists in two executions of the isogeny evaluation algorithm. In our case, we use IsogEval z id when z ̸ = 1 and IsogEvalNonCoprime 1 id when z = 1.

Constructing the 2 dim isogeny representation. Similarly to the case y = 4, the two algorithms CommonIsogenyRepresentation 2,z and IsogenyRepresentation 2,z are mainly constitued of isogeny evaluations.

A Ideal to isogeny in dimension 1

We describe here the algorithm IdealToIsogeny 1 ℓ e (IdealToIsogenyEichler ℓ e in [16, Algorithm 4]). We refer the reader to the explanations in [START_REF] De Feo | New algorithms for the deuring correspondence: towards practical and secure sqisign signatures[END_REF] to obtain more details on the design, correctness and termination of this algorithm.

B On the ExtendedOrientDiamondDim2 algorithm.

In this section, we give some details on the ExtendedOrientDiamondDim2 algorithm and provide some statement on this algorithm. We remind the reader that this algorithm is almost identical to the OrientDiamondDim2 algorithm ([8, Algorithm 1]). The only real difference being that the exponent h is given in input.

We reuse the heuristic introduced in [8, Heuristic 13] as Heuristic 1 below. Assuming that heuristic, and following the proof provided of [8, Proposition 14], we can prove Proposition 10.