A Post-Quantum Oblivious PRF from Isogenies Andrea Basso University of Birmingham, United Kingdom University of Bristol, United Kingdom andrea.basso@bristol.ac.uk Abstract. An oblivious pseudorandom function, or OPRF, is an im- portant primitive that is used to build many advanced cryptographic protocols. Despite its relevance, very few post-quantum solutions exist. In this work, we propose a novel OPRF protocol that is post-quantum, verifiable, round-optimal, and moderately compact. Our protocol is based on a previous SIDH-based construction by Boneh, Kogan, and Woo, which was later shown to be insecure due to an attack on its one-more unpredictability. We first propose an efficient countermeasure against this attack by re- defining the PRF function to use irrational isogenies. This prevents a malicious user from independently evaluating the PRF. The SIDH-based construction by Boneh, Kogan, and Woo is also vulnerable to the recent attacks on SIDH. We thus demonstrate how to efficiently incorporate the countermeasures against such attacks to obtain a secure OPRF protocol. To achieve this, we also propose the first proof of isogeny knowledge that is compatible with masked torsion points, which may be of independent interest. Lastly, we design a novel non-interactive proof of knowledge of parallel isogenies, which reduces the number of communication rounds of the OPRF to the theoretically-optimal two. Putting everything together, we obtain the most compact post-quantum verifiable OPRF protocol. Keywords: Oblivious Pseudorandom Functions · Isogenies · SIDH 1 Introduction An oblivious pseudorandom function (OPRF) is a two-party protocol between a user and a server. The two parties obliviously evaluate a PRF on a user-controlled input with a secret key held by the server. After engaging in the protocol, the user learns only the output of the PRF on their chosen input, while the server does not learn anything, neither the user’s input nor the output of the function. Oblivious PRFs can also satisfy a stronger property called verifiability: in a verifiable OPRF (vOPRF), the server initially commits to its secret key, and during the execution of the protocol it provides a proof that it has behaved honestly and it has used the previously committed secret key. 2 Andrea Basso Oblivious PRFs have widespread applications in privacy-preserving construc- tions. For instance, the web browser Microsoft Edge uses an OPRF-based proto- col to detect compromised passwords. Another practical use case of OPRFs is the privacy-preserving authorisation mechanism known as Privacy Pass [11]. OPRFs are also used within OPAQUE [22], a strong asymmetric password-authenticated key exchange. Overall, OPRFs are a fundamental tool for developing privacy- preserving solutions. It is possible to build an OPRF using generic multi-party computation tech- niques, but such solutions can be inefficient, and they require more rounds of communication than what an ad-hoc construction can achieve. Indeed, highly- efficient and round-optimal (i.e., with two rounds) constructions exist based on Diffie-Hellman [20] or RSA blind signatures [9]. All such constructions are vulner- able to quantum attacks, and very few quantum-resistant OPRFs are reported in the literature. The first quantum-secure verifiable OPRF was proposed by Albrecht, Davidson, Deo and Smart [1]. The protocol is based on the learning- with-errors problem and the short-integer-solution problem in one dimension, and it only requires two rounds of communication. However, the construction can be characterized as a feasibility result, as a single OPRF execution requires communicating hundreds of gigabytes of data. The only other post-quantum so- lutions were proposed by Boneh, Kogan, and Woo [5]. The authors proposed two moderately-compact OPRFs based on isogenies, one relying on SIDH and one on CSIDH. The protocol based on CSIDH is a non-verifiable, three-round OPRF, which is obtained by combining a Naor-Reingold PRF [27] with a CSIDH-based oblivious transfer protocol [24] to make the PRF evaluation oblivious. The OPRF based on SIDH is verifiable, but requires an even higher number of communi- cation rounds, since the verifiability proof is highly interactive. A later work by Basso, Kutas, Merz, Petit and Sanso [4] cryptanalyzed the SIDH-based OPRF by demonstrating two attacks against the one-more unpredictability of the protocol, i.e. it showed that a malicious user can recover sufficient information to indepen- dently evaluate the PRF on any input. The first attack is polynomial-time, but it can be easily prevented with a simple countermeasure; the second attack is subexponential but still practical, and the authors argue that there is no simple countermeasure against it. More recently, a series of works [7,25,28] developed an efficient attack on SIDH that also extends to the SIDH-based OPRF. Contributions. In this work, we propose an OPRF protocol that is post- quantum secure, verifiable, round-optimal, and moderately compact (≈9 MB per execution), with a security proof in the UC framework [6] in the random- oracle model. To do so, we follow the same high-level approach as the SIDH-based OPRF by Boneh, Kogan, Woo [5], but with the following changes: – We propose an efficient countermeasure against the one-more unpredictabil- ity attack by Basso, Kutas, Merz, Petit, and Sanso [4]. We modify the PRF definition, and in particular we use irrational isogenies to map the user’s input to an elliptic curve. In this way, the information that allowed an at- tacker to independently evaluate the PRF is no longer defined over a field of A Post-Quantum Oblivious PRF from Isogenies 3 small extension. A malicious user may still attempt to carry out the attack from [4], but this would now require the attacker to work with points with exponentially many coordinates over the base field, which makes the attack infeasible. Besides preventing the attack, this change results in a smaller prime and a more compact protocol. – We discuss how to integrate MSIDH, a recently-proposed countermeasure [15] against the SIDH attacks that relies on masked torsion, into the OPRF pro- tocol. This requires using longer isogenies and a larger prime, but a series of optimizations allow us to maintain a reasonable communication cost. To integrate MSIDH, we also propose the first zero-knowledge proof of knowl- edge that can guarantee the correctness of an MSIDH public key, which may be of independent interest. The proof relies on splitting the masking value into three multiplicative shares: this enables the prover to build a commu- tative SIDH square and reveal a single edge, together with the torsion point images, without leaking any information about the witness. Repeating the process multiple times yields a proof with negligible soundness error. – We propose a novel proof of knowledge that can guarantee that two isogenies are parallel, i.e. they are computed by applying the same secret key to two starting curves and torsion points. The protocol is obtained by evaluating two proofs of isogeny knowledge in parallel with correlated randomness. The proof can be proved zero-knowledge under a new yet mild assumption. Such a proof can be used by the server to show that it has used a previously committed secret key, which is the key ingredient to make the OPRF verifiable. Since the proof is a proof of knowledge, it can be made non-interactive through standard transformations; this makes the proposed OPRF the first isogeny- based OPRF to be round-optimal. Paper organization. In Section 2, we introduce the main constructions needed for the rest of the paper. In Section 3, we present the OPRF ideal functionality, together with the security notions and assumptions needed to implement it. Section 4 presents novel countermeasures against the one-more unpredictability attack by Basso, Kutas, Merz, Petit and Sanso, while Section 5 discusses how to prevent the SIDH attacks, and Section 6 presents the new proof of parallel isogeny used to achieve verifiability. In Section 7, we put everything together to obtain the new OPRF protocol, estimate its communication complexity, and compare it with the existing solutions. 2 Preliminaries 2.1 SIDH The Supersingular Isogeny Diffie-Hellman (SIDH) [19] is a key-exchange pro- tocol based on isogenies between supersingular elliptic curves. For informa- tion on elliptic curves and isogenies, we refer the reader to [29]. The proto- col parameters include a prime p of the form p = ABf − 1, where A and B 4 Andrea Basso are smooth coprime integers and f a small cofactor, a supersingular curve E0 defined over Fp2 , and the basis PA , QA and PB , QB that span, respectively, $ E0 [A] and E0 [B]. One party samples a secret key a ← − ZA , computes the isogeny ϕA : E0 → EA := E0 /⟨PA + [a]QA ⟩, and publishes pkA = (EA , RA = ϕA (PB ), SA = ϕA (QB )). The second party, proceeds similarly by sampling a se- $ cret key b ←− ZB , computing ϕB : E0 → EB := E0 /⟨PB + [b]QB ⟩, and revealing pkB = (EB , RB = ϕB (PA ), SB = ϕB (QA )). Then, both parties can agree on a shared secret by translating their secret isogeny to the starting curve in the other party’s public key using the revealed torsion information. In other words, the first party computes ϕ′A : EB → EAB := EB /⟨RB + [a]SB ⟩, and the second party computes ϕ′B : EA → EBA := EA /⟨RA + [b]SA ⟩. The codomain curves EAB and EBA are isomorphic, and thus their j-invariant is the same and pro- vides the shared secret of the key exchange. Note that it is possible to represent the points in the public keys more compactly than two x-coordinates, which re- quires 4 log p bits. If the points are expressed in terms of a canonical basis , i.e. a basis deterministically computed from the curve, their coefficients only require 4 log A or 4 log B bits [10]. In the rest of the paper, we write P, Q = BN (E) for a canonical basis of order N on E. We also refer to the setup described above as the SIDH square (E0 , EA , EB , EAB ) with edges (ϕA , ϕB , ϕ′A , ϕ′B ). The Weil pairing between points P, Q ∈ E[N ], for some curve E and integer N , is denoted by eN (P, Q), and it satisfies the property eN (ϕ(P ), ϕ(Q)) = eN (P, Q)deg ϕ . The SIDH attacks. The security of the SIDH protocol hinges on the hardness of recomputing the secret isogenies given the public key. While the problem of finding an isogeny between two curves is believed to be hard, the presence of torsion point images in SIDH makes it easier since more information is revealed about the secret isogeny. In a series of works by Castryck and Decru [7], Maino, Martindale, Panny, Pope, and Wesolowski [25], and Robert [28], the authors propose a polynomial-time algorithm that can compute an isogeny of smooth degree d given the domain and codomain √ curves, the degree d, and the image of a torsion basis of order at least d. This fully breaks the SIDH key exchange and all protocols based on it. Some countermeasures have been proposed [15], based on either secret-degree isogenies or on masked torsion images. We discuss these approaches in the context of the OPRF protocol in Section 5. 2.2 The OPRF construction by Boneh, Kogan, Woo Boneh, Kogan, and Woo [5] introduced a verifiable OPRF protocol based on SIDH, which uses a prime p of the form p = NM NB NK N1 N2 f − 1, where the values Ni are coprime smooth integers and f is a small cofactor. Initially, the server commits to its key k by publishing the curve EC obtained as the codomain of the NK -isogeny starting from Ẽ with kernel ⟨P̃ + [k]Q̃⟩, where the values Ẽ, P̃ , Q̃ are protocol parameters. The commitment also includes a zero- knowledge proof πC of the correctness of the computation. Then, to evaluate the PRF on input m ∈ M, where M defines the input space, the user computes an A Post-Quantum Oblivious PRF from Isogenies 5 isogeny ϕm of degree NM by hashing the input with a function H and computing ϕm : E0 → Em := E0 /⟨P + [H(m)]Q⟩, where the curve E0 and the points P, Q are also protocol parameters. Then, the user blinds the curve Em by computing a second isogeny ϕb : Em → Emb of degree NB . The user sends the curve Emb and the torsion images RK = ϕb ◦ ϕm (PK ), SK = ϕb ◦ ϕm (QK ) to the server, where the points PK , QK are also protocol parameters of order NK . The user also provides a non-interactive zero-knowledge proof that torsion information was honestly computed. The server validates the proof, computes the isogeny ϕk : Emb → Embk := Emb /⟨RK + [k]SK ⟩ based on its secret key k, and sends the curve Emrk , the image ϕk (Emb [NB ]), and a non-interactive zero-knowledge proof of correctness to the user. Then, the server and the user engage in an in- teractive protocol where the server proves that the isogeny ϕk has used the same key k as the committed value. If the user is convinced, they use the provided torsion information to undo the blinding isogeny, i.e. to compute the translation of the dual of the blinding isogeny, to obtain the curve Emk . The output of the OPRF is then the hash H m, j(Emk ), (EC , πC ) . The main exchange, without the commitments and the proofs, is represented in Fig. 1. ϕm E0 Em ϕb ϕ′k Emb ϕ′m Ek Emk ϕk ϕ̂′b Embk Fig. 1: The OPRF construction by Boneh, Kogan, and Woo. The protocol, without the relevant zero-knowledge proofs, is represented by the solid lines: the isogenies −→ (ϕm , ϕb , ϕ̂′b ) are computed by the client, while the isogeny −→ (ϕk ) is computed by the server. The isogenies ⇝ represent the PRF evaluation, and the isogenies 99K are relevant to the attack presented in [4]. The figure is based on Fig. 1 of [4]. 2.3 The BKMPS attacks Basso, Kutas, Merz, Petit, and Sanso [4] proposed two attacks against the one- more unpredictability of the OPRF protocol by Boneh, Kogan, Woo [5] OPRF. In the first attack, an attacker who acts as a malicious user engages in the OPRF with a message isogeny ϕm with kernel generator a point M , of order ℓe . The attacker repeats the process with message isogenies with kernel generators [ℓ]M, [ℓ2 ]M, . . . , [ℓe ]M . The outputs of the PRF are the curves that lie on the isogeny path of ϕ′m : Ek → Emk (see Fig. 1), which allows the attacker to compute a generator of the kernel of such isogeny. The recomputed generator is 6 Andrea Basso a scalar multiple ϕ′k (M ), where ϕ′k is the isogeny parallel to the server’s secret isogeny, i.e. its kernel is generated by Pk + [k]Qk . By repeating this process three times with points M1 , M2 and M3 := M1 + M2 (where M1 and M2 are linearly independent), the attacker obtains R := [α]ϕ′k (M0 ), S := [β]ϕ′k (M1 ), T := [γ]ϕ′k (M3 ) = [γ/α]R + [γ/β]S, for some unknown values α, β, γ. By expressing T in terms of R and S, the at- tacker obtains the values γ/α and γ/β and the points R′ := [γ/α]R = [γ]ϕ′k (M0 ) and S ′ := [γ/β]S = [γ]ϕ′k (M1 ). Finally, the attacker can evaluate the PRF on any input m by computing EK /⟨R′ + [H(m)]S ′ ⟩. The attack runs in polynomial time, but it crucially relies on using message isogenies ϕm of varying degree. The attack can be thwarted by server checking the order of the isogeny ϕm , which is possible because of the proof of knowledge provided by user. The authors of [4] also propose a second attack that cannot be easily pre- vented. The attack proceeds in a similar way to the previous one, but the ma- licious user uses only isogenies of full degree. To obtain the curves on the path of ϕm , the attacker needs to find the middle curve between two PRF outputs. This introduces a trade-off between the complexity of the attack and the number of queries. Minimizing both yields a subexponential yet practical attack on the one-more unpredictability of the protocol. 3 Oblivious pseudorandom functions The security properties of an OPRF can be hard to define. Oblivious pseudoran- dom functions were originally proposed by Naor and Reingold [27], who defined an OPRF via an ideal functionality. Subsequent work [16,23] defined OPRFs in terms of the two-party computation (k, x) 7→ (⊥, f (k, x)), but such a def- inition has several drawbacks. On one side, it is hard to build protocols that satisfy such a definition, because the security proof would require extracting the user’s input, while at the same the definition is not secure enough, because it does not guarantee any security under composability. Since OPRFs are mainly used as building blocks in larger protocols, such a security guarantee is highly needed. For these reasons, Jarecki et al. [20,22] proposed new definitions in the UC framework [6]. To avoid extracting the user’s input, the ideal functionality introduces a ticketing system that increases a counter when the PRF is evaluated and decreases the counter when the user receives the PRF output. This captures the idea that a malicious user should learn only the PRF output for one input for each interaction. This results in the definition of Fig. 2, which is based on the definitions by Jarecki et al. [20,21,22]. 3.1 Security assumptions To prove that the OPRF protocol we propose implements the functionality of Fig. 2, we will make use of the properties listed in this section. Since our protocol A Post-Quantum Oblivious PRF from Isogenies 7 Parameters: The PRF output ℓ, polynomial in the security parameter λ. Convention: For every identifier S, the counter tx[S] is initially set to zero. For every value π ∈ {0, 1}∗ and x ∈ {0, 1}∗ , the value F (π, x) is initially undefined, and whenever such a value is referenced, the functionality assigns a random ℓ-bit $ − {0, 1}ℓ . string F (π, x) ← Initialization – On message init from party S, forward (init, S) to the adversary A. – On message (Param, S, π) from adversary A, and if param[S] is undefined, then set param[S] = π. Evaluation – On message (Eval, S, x) from P ∈ {U, A}, record ⟨P, x⟩ and forward the message (Eval, P, S) to A. – On message ServerComplete from server S, send (ServerComplete, S) to A and increment tx[S]. – On message (UserComplete, P, π) from A, retrieve the record ⟨P, x⟩, delete it from the list of records, and decrement tx[S] if there exists an honest server S such that param[S] = π; abort if no such record exists or if tx[S] = 0. Then, send (Eval, π, F (π, x)) to P . Fig. 2: The FvOPRF functionality. and security proof follows the same high-level structure as that of the OPRF protocol by Boneh, Kogan, and Woo [5], these properties are also based on those of the augmentable commitment framework proposed in [5]. Unlike [5], we avoid the abstraction of augmentable commitments due to its restrictiveness (the counteremasures of Section 4 would not be possible within that framework), and we prefer an explicit description throughout this work. Correctness. Firstly, we require the OPRF to be correct, i.e. the output of the protocol is the output of function that deterministically depends only on the user’s input and the server’s secret key. In other words, we want that the blinding process that guarantees the obliviousness of the user’s input does not affect the final output. In the context of our protocol, we want that the unblinding isogeny undoes the effect of the blinding isogeny. This is contained in the following lemma, whose proof follows from the correctness of the SIDH protocol [19]. Lemma 1 (Correctness). Let p be a prime of the form p = NB NK f − 1, where NB , NK , f are smooth coprime integers. Let E0 be a supersingular elliptic curve defined over Fp2 and let PB , QB and PK , QK be respectively a basis of E0 [NB ] and E0 [NK ]. Let also b and k be two values in ZNB and ZNK . Then, consider the 8 Andrea Basso isogenies ϕB : E0 → EB := E0 /⟨PB + [b]QB ⟩, ϕK : E0 → EK := E0 /⟨PK + [k]QK ⟩, ϕ′k : EB → EBK := EB /⟨ϕB (PK ) + [k]ϕB (QK )⟩. If RB , SB is a basis of EB [NB ] and the values b0 , b1 satisfy ker ϕ̂B = ⟨[b0 ]RB + [b1 ]SB ⟩, then we have j (EBK /⟨[b0 ]ϕ′k (RB ) + [b1 ]ϕ′k (SB )⟩) = j(EK ). Input hiding. To ensure that the OPRF is oblivious, we want that the server does not learn the user’s input. That holds in the strongest sense, i.e. the server should not learn the user’s input even when the input is randomly chosen between two inputs chosen by the server. In other words, the user must apply a blinding step that fully hides the chosen input. In the context of isogenies, we want the following problem to be hard. Problem 1. Let p be a prime of the form p = NB NK f − 1, where NB NK , f are smooth coprime integers. Let E0 and E1 be two supersingular elliptic curves defined over Fp2 and chosen by the adversary, and let P0 , Q0 and P1 , Q1 be a basis of E0 [NK ] and E1 [NK ], respectively, such that eNK (P0 , Q0 ) = eNK (P1 , Q1 ). $ Let i be a random bit, i.e. i ← − {0, 1}, and B a random point in Ei [NB ], and write ϕ : Ei → E ′ := Ei /⟨B⟩. Output i given E ′ and faux (ϕ(Pi ), ϕ(Qi )), where the latter is some auxiliary torsion information. The hardness of the problem clearly depends on the function faux ; if the tor- sion images were directly revealed, Problem 1 would be easy due to the SIDH attacks. We thus delay describing the function faux until Section 5, where we dis- cuss the SIDH countermeasures and choose faux to reveal the values ϕ(Pi ), ϕ(Qi ), both scaled by the same unknown value. In the section, we also state the variant of the Decisional Isogeny problem that Problem 1 reduces to. One-more unpredictability. A key property of an OPRF is that the user learns the output of the PRF only on its input of choice. That means that a malicious user should not learn the output on more inputs than the number of OPRF executions. The BKMPS attack [4] on the OPRF by Boneh, Kogan, and Woo [5] targets the one-more unpredictability, since it shows that a malicious user can extract enough information to independently evaluate the OPRF on any input of their choice. We propose an efficient countermeasure against the one-more unpredictability attack in the next section; we thus delay until then a formalization of the isogeny-related assumption (see Problem 4) we need to guarantee the one-more unpredictability of the OPRF protocol. A Post-Quantum Oblivious PRF from Isogenies 9 Commitment binding. At the beginning of the OPRF protocol, the server commits to a secret key k, so that during each OPRF execution it can prove that the same key was used. To guarantee verifiability, we want a commitment scheme with an associated proof of input reuse. We propose to commit to a key k by fixing a special curve Ẽ with a basis P̃ , Q̃ of Ẽ[NK ] and revealing j(Ẽ/⟨P̃ + [k]Q̃⟩). The proof of input reuse, which in the context of isogenies becomes a proof of parallel isogenies, is presented in Section 5.2. To guarantee that the commitment is binding, we want that the following problem to be hard. Problem 2 (Collision finding problem). Let E0 be a supersingular elliptic curve of unknown endomorphism ring. Find two distinct isogenies ϕ0 : E0 → E and ϕ1 : E0 → E ′ such that j(E0 ) = j(E1 ). Problem 2 has been studied in the context of the CGL hash function [8], and it has been shown to be heuristically equivalent to the following problem, which underpins every isogeny-based protocol [13]. Problem 3 (Endomorphism Ring problem). Let E be a supersingular elliptic curve. Find its endomorphism ring End(E). 4 Countermeasures against the one-more unpredictability attack The original protocol by Boneh, Kogan and Woo starts by mapping an input m to an isogeny ϕm . If we denote with NM the torsion space dedicated to the message, the protocol fixes a basis P, Q of E0 [NM ] and computes the isogeny ϕm given by ϕm : E0 → E0 /⟨P + [H(m)]Q⟩ =: Em , (1) where H(·) maps the message m onto an element of ZNM . The subexponential attack [4] recovers the image Pk , Qk of the torsion basis P, Q, up to scalar multiplication, under the secret isogeny ϕ′k : E0 → Ek . With such information, the attacker can evaluate the PRF on any input of their choice. The output curve of the PRF is the curve computed as Ek /⟨Pk + [H(m)]k ⟩. The attack is subexponential, and it is possible to obtain λ bits of security if the 2 isogeny ϕm has degree 2λ (this can be reduced if we limit the number of queries the attacker can make). This would require using very long isogenies (the degree would be 216,384 for λ = 128) and very large primes. Instead, in this section we propose a novel and efficient countermeasure that sidesteps these issues. Our main idea is to accept that an attacker may recover the curve Ek and points Pk , Qk on it, but to prevent those points from being sufficient to evaluate the desired isogeny. To do so, we require that the isogeny ϕm has an irrational kernel, i.e. its kernel is defined over a sufficiently-large extension field. Such an isogeny can be efficiently computed as a composition of rational isogenies. More formally, assume that NM = ℓe , and e is the highest power of ℓ that divides p + 1. Then, given an input m ∈ M, we compute the isogeny ϕm in the following way: 10 Andrea Basso 1. We first map the message m to two elements in Zℓe through two hash func- tions H0 , H1 that are collision resistant. We thus have m0 = H0 (m) and m1 = H1 (m). 2. Given the starting curve E0 and two points P0 , Q0 spanning E0 [ℓe ], we com- pute the isogeny ϕ0 : E0 → E1 := E0 /⟨P0 + [m0 ]Q0 ⟩. 3. We determine a canonical basis P1 , Q1 of E1 [ℓe ] and compute the isogeny ϕ1 : E1 → Em := E1 /⟨P1 + [m1 ]Q1 ⟩, 4. The isogeny ϕm : E0 → Em is the composition ϕ1 ◦ ϕ0 . An attacker may still try to apply the one-more unpredictability attack. In the original case, the attacker recovers three isogenies from Ek to Emk and they combine their kernel generators to obtain the image points Pk , Qk . In the proposed construction, the attacker can still recover three (or more) isogenies from Ek to Emk . However, the kernel generators of these isogenies are points of order ℓ2e , and thus they are defined only over the extension field Fp2ℓe . This is an exponentially large field, and even just representing such a point—let alone doing any computation—would be exponential in the security parameter. To guarantee security, it is important that the degree of ϕm is a prime power. If the degree were a product of prime powers, it is possible to represent a large extension by working over several smaller extensions because of the Chinese Remainder Theorem. This can reduce the complexity of working over a large extension and thus reduce the security of the proposed countermeasures. ϕ0 ϕ1 E0 E1 Em Ek ϕm0 Em0 k ϕm 1 Emk Fig. 3: Summary of the proposed countermeasure (this does not depict the blind- ing/unblinding phase). Isogenies in red are known or can be computed by the attacker, isogenies in black are unknown to the attacker, and the dotted isogeny represents the missing isogeny that the attacker needs to compute to succeed in the attack. The attacker can work with the kernel generators of only the first half of the isogenies and obtain a basis Pk , Qk of order ℓe (see Fig. 3). This allows them to evaluate the first isogeny ϕm0 to obtain the curve Em0 k for any message m. However, the attacker has no way of computing the remaining isogeny ϕm1 . To do so, the attacker would need to map the canonical basis on E1 to Em0 k , which does not seem to be possible without knowing the server secret key. Alternatively, the attacker could map the points P, Q and Pk , Qk under the isogenies ϕ0 and ϕ′k . At least one of the image points on each curve has full order, and the point of full order on Em0 k is the image of the point of full order on E1 . This suggest such A Post-Quantum Oblivious PRF from Isogenies 11 an approach could be used to find a basis, but the second point on each curve is always a scalar multiple of the first point1 . Hence, guessing the remaining point has exponential complexity ℓe . Lastly, the attacker cannot use a similar strategy as the one-more unpredictability attack to recover a basis on Em0 k because the curve Em0 k depends on the message m. It thus changes at every interaction, and it is hard for an attacker to find two messages that have the same first curve E1 and Em0 k since we assume that the hash function H0 is collision-resistant. Note that we require H0 and H1 to be collision-resistant, but we conjecture that only H0 needs to be. Overall, the knowledge of Em0 k does not help the attacker learn any information on the curve Emk , which successfully prevents the the one-more unpredictability attack. Optimizations. We can extend this approach to obtain a more compact pro- tocol. Rather than limiting ourselves to two isogenies, we can extend this to an arbitrary number I. We obtain the optimal case when I is maximal, i.e. when deg ϕm = ℓI . Let Hi be I distinct random oracles for every i ∈ {1, . . . , I}. Then, given an input m and a starting curve E0 , the isogeny ϕm and the curve Em by computing an isogeny ϕi determined by Hi (m), generating a canonical basis on the codomain curve, and repeating the process I times (see Algorithm 1). We refer to this hashing as HI (x), and in the rest of the paper, we write (ϕm , Em ) = HI (x) to refer to the function in Algorithm 1; we also write [P0 , P1 , . . . , PI−1 ]E,N to denote a list points of order N where the point P0 belongs to E, and the point Pi belongs to Ei := Ei1 /⟨Pi−1 ⟩. We refer to this as a sequence, whose associated isogeny is the composition of the isogenies Ei → Ei /⟨Pi ⟩. Algorithm 1 Function HI mapping the input m to the curve Em 1: for i ← 0 to I − 1 do 2: Set mi = Hi (m) and Pi , Qi = BM (E); 3: Compute ϕi : Ei → Ei+1 := Ei /⟨Pi + [mi ]Qi ⟩; 4: Set ϕm = ϕI−1 ◦ . . . ◦ ϕ0 and Em = EI−1 ; 5: return ϕm , Em ; This technique to compute message isogenies results in a more compact OPRF protocol because only the shorter isogenies ϕi need to be defined over Fp2 ; thus, using more isogenies can result in a smaller prime p while maintaining the same degree of the isogeny ϕm . However, this approach has also a security advantage: an attacker can use the BKMPS attack to recover the image of basis on Ek , which could potentially be used to recover the isogeny between E0 and Ek using the SIDH attacks. While this could be avoided by picking a sufficiently long isogeny ϕk , choosing I = e, i.e. setting parameters such that only isogenies 1 If ker ϕ = ⟨P + αQ⟩, it follows that ϕ(P ) = −αϕ(Q). 12 Andrea Basso of degree ℓ have a kernel defined over Fp2 , ensures that an attacker obtains only a basis of very small order, which prevents the attack altogether. A new assumption. We proposed a modified protocol that prevents the ex- isting one-more unpredictability attacks. As in the original construction, the one-more unpredictability of the resulting protocol relies on the hardness of a novel problem, which is the following. Problem 4 (One-more unpredictability). Let p be a prime of the form p = NM NK f − 1, where NM and NK are smooth coprime integers, and f a cofactor. Let HI be a function as in Algorithm 1. Let E0 be a supersingular curve defined over Fp2 , and let K be a point on E0 of order NK . Write ϕK for the isogeny ϕK : E0 → EK := E0 /⟨K⟩. Given the curves E0 , EK and an oracle that responds to the following queries: – challenge: returns a random sequence [M0 , . . . , MI−1 ]E0 ,NM , – solve([V0 , . . . , VI−1 ]E0 ,NM ): returns j(EV /⟨ϕV (K)⟩), where ϕV is the isogeny associated to the input sequence, – decide(i, j): returns true if j is equal to the output of a solve query with input the response of the i-th challenge query, and false otherwise, For any value n, produce n pairs (i, j) such that decide(i, j) = true with less than n solve queries. The problem is based on Game 12 of [5], but compared to it, this game involves multiple points during the challenge and solve query to abstract the behavior described in the previous section. Moreover, the problem includes the countermeasures against the polynomial time attack of [4], i.e. the attacker can only query points of the correct order. This can be replicated in the OPRF set- ting by checking the order of the isogenies in the proof of isogeny knowledge. We included these countermeasures to prevent possible attacks since they are inexpensive. However, we conjecture that the problem remains hard even if the adversary is allowed to submit solve queries with points of arbitrary order. Fur- thermore, the problem remains hard after the SIDH attacks since it does not involve exchanging any torsion points. Countermeasure costs. We briefly discuss the impact of the proposed coun- termeasures on the performance of the OPRF protocol. Firstly, we need to de- termine the parameters ℓ, e, and I. Keeping in mind the possible SIDH attacks based on the recovered torsion on Ek , we choose I to be maximal. We require that the degree of the message isogeny is about ≈ 25/2λ to prevent the attack proposed in [26]. Hence, we set e = 1 and I = logℓ (25/2λ ). The message component NM can then be chosen to be ℓ, to ensure that isogenies of degree ℓ have kernel in Fp2 , or one, if torsion points of order ℓ are defined over a small extension field. In the latter case, the prime p does not need A Post-Quantum Oblivious PRF from Isogenies 13 to change to allow computations of the message isogeny. In both cases, not only do the proposed countermeasures protect against existing attacks, but also they reduce the prime size leading to a more compact and efficient protocol. 5 Countermeasures against the SIDH attacks The recent series of attacks by Castryck and Decru [7], Maino, Martindale, Panny, Pope, and Wesolowski [25], and Robert [28] exploits torsion-point infor- mation to break SIDH. These attacks trivially translate to the OPRF, where any third party can recover both the user’s hashed input (which breaks oblivi- ousness) and the server’s secret key. In this section, we discuss how to adapt the existing SIDH countermeasures to work in the OPRF setting. After modifying the main exchange, we propose a novel proof of isogeny knowledge that works together with the countermeasures, which may be of independent interest since it is the first proof to prove the correctness of torsion point images in the SIDH- with-countermeasure setting. This proof can be used together with the patched SIDH to obtain a post-quantum non-interactive key-exchange. Combining the countermeasures together with the novel proof of torsion point correctness, we obtain an SIDH-based OPRF that is resistant against the SIDH attacks. While the countermeasures impose larger parameters, the resulting pro- tocol remains the most compact post-quantum vOPRF. 5.1 Protecting the exchange Thus, to guarantee the security of the SIDH-based OPRF we need to rely on the masked-torsion countermeasure, as in masked SIDH (MSIDH) [15]. Con- sider an isogeny ϕ : E → E ′ of degree d, with a basis P, Q of E[n], for some n coprime with d. Given the images P ′ = ϕ(P ), Q′ = ϕ(Q), a second party can compute the pushforward of an isogeny with kernel ⟨P + [x]Q⟩ as the isogeny with kernel ⟨P ′ + [x]Q′ ⟩. Thus, it is possible to reveal [α]P ′ , [α]Q′ , for some random α coprime with the torsion order n, without affecting the correct- ness of the protocol. However, this leaks the value α2 from the Weil pairing, 2 since en ([α]P ′ , [α]Q′ ) = en (P, Q)α deg ϕ . To ensure that the attacker cannot re- cover the value α, MSIDH requires that any value has at least 2λ square roots modulo n, hence n needs to be the product of at least λ prime powers. This, however, is not enough to guarantee security, as an attacker can guess the correct square root modulo some n′ | n with n′ > d1/2 in less than O(2λ ) guesses. It is thus also needed that d > n′ , where n′ is the product of the powers of the λ largest primes dividing n. From now on, we write n = fMSIDH (λ, d) to denote the smallest value n that can guarantee λ bits of security when used in MSIDH with an isogeny of degree d. Lastly, the countermeasure analysis in [15] shows that MSIDH may be vulnerable when the starting curve has a small endomorphism. In our case, such an attack does not apply even if the OPRF starting curve E0 has a known endomorphism ring with a small endomorphism ι. That is because the attack would need a small endomorphism on Em x, but the composition of 14 Andrea Basso the message and blinding isogeny ϕx ◦ ϕm is sufficiently long that the attack does not apply. Even considering the attack on the starting curve Em (remem- ber that in the security game the attacker can control the messages), does not help: if the attacker can guess the input message, the smallest endomorphism known on Em is ϕ̂m ◦ ι ◦ ϕm , which is too large for the attack to apply. Moreover, the server computes its isogeny starting from a curve Emx that is sent by the user, which generally could be an avenue for attack since MSIDH is insecure for special starting curves. However, the user also submits a proof of knowledge of an isogeny of long degree between E0 and Emx : this guarantees that the small- est known endomorphism is again sufficiently large, which similarly prevents the attack against the server’s isogeny. We can now formulate the following problem, on whose hardness the input hiding property of the OPRF is based. Problem 5 (Decisional MSIDH isogeny problem). Let E0 be a supersingular el- liptic curve, with a basis P, Q be of E0 [n]. Distinguish between the following distributions: – (E1 , R, S), where E1 is the codomain of a d-isogeny ϕ : E0 → E1 , where d is coprime with n, and the points R, S are the masked images of P, Q, i.e. $ R = [α]ϕ(P ) and S = [α]ϕ(Q) for some α ← − Z∗n ; – (E1 , R, S), where E1 is a random supersingular elliptic curve and the points 2 R, S are a random basis of E1 [n] such that e(R, S) = e(P, Q)α d , for some value α. The hardness of the problem clearly depends on the choices of n and d; the problem (conjecturally) requires O(2λ ) operations to solve when n > fMSIDH√(λ, d), i.e. the product of the λ largest prime powers dividing n is smaller than d. Concrete cost. We have shown it is possible to protect the OPRF protocol from the SIDH attacks. Unfortunately, the proposed countermeasure do come at a significant cost. The degrees of the blinding isogeny and the server’s isogeny are the same as in SIDH with the same countermeasures. At security level λ = 128, that corresponds to isogenies of degree ≈ 22956 . More generally, we see experimentally that the degree of the isogenies scales log-linearly in the security parameter with a constant of ≈ 6.7. We thus have that the degree of the blinding isogeny and the server’s isogeny must be ≈ 26.7λ log λ to guarantee the security of the protocol. 5.2 Adapting the proof of isogeny knowledge In the previous section, we showed how it is possible to protect the OPRF against the SIDH attacks using masked torsion points. However, in the OPRF protocol both parties need to prove the correctness of their torsion images to prevent adaptive attacks and guarantee the verifiability of the execution. Thus, both A Post-Quantum Oblivious PRF from Isogenies 15 parties want to prove that their revealed torsion points were honestly generated, i.e. the two points are both scaled by the same value. In this section, we propose a zero-knowledge proof of isogeny knowledge that can guarantee the correctness of torsion points up to a scalar, i.e. a proof for the following relation:    ϕ : E0 → E1 is a cyclic d-isogeny,  Riso = ((E0 , P0 , Q0 , E1 , P1 , Q1 ), (ϕ, α)) P1 = [α]ϕ(P0 ), . Q1 = [α]ϕ(Q0 ).   In the literature, we can find two proofs of isogeny knowledge that also guar- antee the correctness of torsion point images. The first proof constructs an SIDH square and explicitly maps the torsion images through all the sides of the square. This proof was proposed by Boneh, Kogan, and Woo [5] for the OPRF protocol, based on a previous idea by Galbraith [17]. The second proof [12], instead, is an extension of the simpler proof of isogeny knowledge by De Feo and Jao [19]. The first proof requires a larger prime, but the torsion images are explicitly mapped, which makes it well-suited to support masked torsion. We thus propose a new proof based on the same approach as [5] and [17], although with some notable differences. Building a more compact proof based on the second approach [12] remains an open problem. The main idea is that the masking constant α can be split into three shares α = α1 α2 α3 . The prover can mask the torsion points with αi when computing the i-th side of the SIDH square, so that the composition of the three isoge- nies, together with their masking values, forms a commutative diagram with the isogeny ϕ with masking value α. The proof remains zero-knowledge because each single value αi is independent of α. More formally, let E0 and E1 be supersingular elliptic curves with points P0 , Q0 ∈ E0 [n] and P1 , Q1 ∈ E1 [n]. The prover wants to prove knowledge of a d-isogeny ϕ : E0 → E1 and a value α ∈ Zn such that P1 = [α]ϕ(P0 ) and Q1 = [α]ϕ(Q0 ). Let us assume n = fMSIDH (λ, d), so that the isogeny ϕ is hard to extract from public information. The prover generates a random isogeny ψ : E0 → E2 of degree s, where s ≈ n is a smooth number coprime with both n and d, and generates the SIDH square (E0 , E1 , E2 , E3 ) with edges (ϕ, ψ, ϕ′ , ψ ′ ). To guarantee soundness, the prover needs to show that ψ and ψ ′ are parallel: the prover thus generates a s-basis R2 , S2 on E2 , maps it to E3 to obtain R3 , S3 , and expresses the kernels of ψ̂ and ψ̂ ′ in terms of R2 , S2 and R3 , S3 with the same linear coefficients. The prover also splits α in three shares α = α1 α2 α3 and maps the points P0 , Q0 through ψ and ϕ′ with masking values α1 and α2 to obtain the points P2 = [α1 ]ψ(P0 ), Q2 = [α1 ]ψ(Q0 ), P3 = [α2 ]ϕ′ (P2 ), Q3 = [α2 ]ϕ′ (Q2 ), which implies that P3 and Q3 also satisfy the relation [α3 ]P3 = ψ ′ (P1 ), [α3 ]Q3 = ψ ′ (Q1 ). 16 Andrea Basso Hence, the SIDH square commutes with respect to the points Pi , Qi , i.e. if we restrict ourselves to the n-torsion, we have [α][s]ϕ = [α3 ]ψ̂ ′ ◦ [α2 ]ϕ′ ◦ [α1 ]ψ. Thus, the witness can be split into three components, and hence we obtain a proof with ternary challenges. The prover initially commits to the curves E2 , E3 and the relevant points on them with a commitment scheme C(·). Then, depend- ing on the challenge, the prover responds with one edge of the SIDH square, the relevant curves and points, and the corresponding commitment openings. The proof is described in Fig. 4. Since each iteration has soundness error 2/3, the proof must be repeated −λ log2/3 (2) ≈ 1.71 times to achieve a soundness error of 2−λ . Remark 1. If the kernel of the isogeny ϕ is not defined over a small extension field, as in the case of the message isogeny, the proof can be computed by gluing together multiple SIDH squares, as shown in [3]. P1 ((E0 , P0 , Q0 ), (E1 , P1 , Q1 ), ϕ, α): 1: Sample a random cyclic isogeny ψ : E0 → E2 of degree s; 2: Construct the SIDH square (E0 , E1 , E2 , E3 , ϕ′ , ψ ′ ) on (ϕ, ψ); 3: Sample random units α1 , α2 mod n and set a3 := α/α1 α2 ; 4: Set P2 , Q2 := [α1 ]ψ(P1 ), [α1 ]ψ(Q1 ), and P3 , Q3 := [α2 ]ϕ′ (P2 ), [α2 ]ϕ′ (Q2 ); 5: Let R2 , S2 be a basis of E2 [d] and set R3 , S3 := ϕ′ (R2 ), ϕ′ (S2 ); 6: Write K = [a]R2 + [b]S2 for K a random generator of ker ψ̂ 7: Sample random strings r1 , . . . , r7 ; 8: return st, C(E2 , R2 , S2 , P2 , Q2 ; r1 ), C(E3 , R3 , S3 , P3 , Q3 ; r2 ),  C(a, b; r3 ), C(ϕ′ ; r4 ), C(α1 ; r5 ), C(α2 ; r6 ), C(α3 ; r7 ) . P2 (st, chall): 1: if chall == −1 then 2: return ((E2 , R2 , S2 , P2 , Q2 , r1 ), (a, b, r3 ), (α1 , r5 )); 3: else if chall == 0 then 4: return ((E2 , R2 , S2 , P2 , Q2 , r1 ), (E3 , R3 , S3 , P3 , Q3 , r2 ), (ϕ′ , r4 ), (α2 , r6 )); 5: else if chall == 1 then 6: return ((E3 , R3 , S3 , P3 , Q3 , r2 ), (a, b, r3 ), (α3 , r7 )); V((E0 , P0 , Q0 ), (E1 , P1 , Q1 ), (com1 , . . . , com9 ), chall, resp): 1: if chall == −1 then 2: ((E2 , R2 , S2 , P2 , Q2 , r1 ), (a, b, r3 ), (α1 , r5 )) = resp; 3: Check com1 = C(E2 , R2 , S2 , P2 , Q2 ; r1 ), com3 = C(a, b; r3 ), com5 = C(α1 ; r5 ); 4: Let ψ̂ be the isogeny with kernel ⟨[a]R2 + [b]S2 ⟩; 5: Check ψ̂ is an s-isogeny from E2 to E0 ; 6: Check [α1 s]P0 = ψ̂(P2 ) and [α1 s]Q0 = ψ̂(Q2 ); 7: else if chall == 0 then 8: ((E2 , R2 , S2 , P2 , Q2 , r1 ), (E3 , R3 , S3 , P3 , Q3 , r2 ), (ϕ′ , r4 ), (α2 , r6 )) = resp; A Post-Quantum Oblivious PRF from Isogenies 17 9: Check com1 = C(E2 , R2 , S2 , P2 , Q2 ; r1 ), com2 = C(E3 , R3 , S3 , P3 , Q3 ; r2 ), com4 = C(ϕ′ ; r4 ), com6 = C(α2 ; r6 ); 10: Check ϕ′ is a d-isogeny from E1 to E2 ; 11: Check R3 , S3 = ϕ′ (R2 ), ϕ′ (R3 ); 12: Check P3 , Q3 = [α2 ]ϕ′ (P2 ), [α2 ]ϕ′ (Q2 ); 13: else if chall == 1 then 14: ((E3 , R3 , S3 , P3 , Q3 , r2 ), (a, b, r3 ), (α3 , r7 )) = resp; 15: Check com2 = C(E3 , R3 , S3 , P3 , Q3 ; r2 ), com3 = C(a, b; r3 ), com7 = C(α3 ; r7 ); 16: Check ⟨R3 , S3 ⟩ = E3 [s]; 17: Let ψ̂ ′ be the isogeny with kernel ⟨[a]R3 + [b]S3 ⟩; 18: Check ψ̂ is an s-isogeny from E3 to E1 ; 19: Check [α3 s]P1 = ψ̂ ′ (P3 ) and [α3 s]Q1 = ψ̂ ′ (Q3 ); Fig. 4: Interactive proof of knowledge for the relation Riso . We now sketch the proofs of correctness, three-special soundness and zero- knowledge. Given the similarity of the zero-knowledge proof with those in [5], the proofs also follow a similar approach. Correctness. A honest prover always generates proofs that are accepted by the verifier. The verifier recomputes the same operations as the prover and checks that the outputs match. The only difference is in the chall = ±1 cases, where the verifier computes the dual of ψ and ψ ′ , which then introduces a factor s in the point equality check. Three-special soundness. The protocol is three-special sound because there exists an extractor that extracts the witness given three accepting transcripts with the same commitments and different challenges. The isogeny ϕ can be computed by mapping the kernel of ϕ′ (from chall = 0) under the isogeny ψ̂ (from chall = −1). Since the isogenies ψ and ψ ′ are parallel (from all the challenges combined), this guarantees that ϕ is a d-isogeny from E0 to E1 . The masking value α can be recomputed as the product of α1 , α2 , and α3 . Zero-knowledge. We sketch a simulator that given a statement (E0 , P0 , Q0 , E1 , P1 , Q1 ) and a challenge chall can simulate a valid transcript without knowl- edge of the witness. For the case chall = −1, the simulator behaves like an honest prover. For chall = +1, the situation is similar: the simulator can compute a d- isogeny ψ ′ , pick a random basis R3 , S3 of E3 [d] and a random value α3 ∈ Z∗n , and compute the values a, b and points P3 , Q3 that pass verification. Note that the points R3 , S3 are uniformly random among the bases of E3 [d], and the value α3 is uniformly random and independent of α; the simulated values are thus distributed as the honestly-generated ones. The case of chall = 0 is more com- plicated: the simulator can sample a random curve E2 , generate a random basis 18 Andrea Basso 2 P2 , Q2 of E2 [n] that satisfies e(P2 , Q2 ) = e(P0 , Q0 )x s for some random x, pick a random d-isogeny ϕ′ : E2 → E3 , and compute the image points on E3 . In this case, the indistinguishability of the simulator’s output is only computational. It is thus based on the conjectured hardness of the following problem, which is a modified version of the Decisional Supersingular Product (DSSP) problem introduced in [19]. Problem 6 (DSSP with Torsion (DSSPwT) problem). Given an isogeny ϕ : E0 → E1 and points P0 , Q0 ∈ E0 [n], where n = fMSIDH (λ, d), distinguish be- tween the following distributions: – D0 = {(E2 , P2 , Q2 , E3 , ϕ′ )}, where E2 is the codomain of an s-isogeny ψ : E0 → E2 , the points P2 , Q2 satisfy P2 = [α]ψ(P0 ), Q2 = [α]ψ(Q0 ) for some α ∈ Z∗n , and ϕ′ : E2 → E3 is a d-isogeny with kernel ker ϕ′ = ψ(ker ϕ). – D1 = {(E2 , P2 , Q2 , E3 , ϕ′ )}, where E2 is a random supersingular curve with the same cardinality as E0 , P2 and Q2 are two random points of order n such that e(P2 , Q2 ) = e(P0 , Q0 )s , and the isogeny ϕ′ is a d-isogeny between E2 and E3 . Note that [5] argues that a similar proof can only reveal one torsion point (either Pi or Qi ) at a time to prevent a distinguishing attack on the simulator. The attack they present relies on computing the Weil pairing between two points of coprime order, and thus their pairing is always one. The attack thus does not apply, and the simulated transcript remains indistinguishable under Weil pairing checks because the sampled points P2 , Q2 are guaranteed to have the same pairing as the honestly-generated points. By revealing both points Pi and Qi we obtain a significantly more efficient proof, since it has 1/3 soundness rather than 1/6. Optimizations. For simplicity, the proof in Fig. 4 contains a schematic descrip- tion of the protocol, but the proof can be made more efficient through a series of optimizations. In the commitment phase, the value α2 is only revealed together with the isogeny ϕ′ , and thus they can be committed together. Note that we have the prover commit to ϕ′ to make the proof online-extractable without recursion, which is necessary to achieve a proof in the UC model. For applications of this proof outside of the OPRF context, the prover can avoid committing to ϕ′ . The masking values α1 and α3 are independent of α, even when considered together, because α2 is uniformly random. They can then be committed together and re- vealed both in the response to challenges chall = ±1. Since the commitment for a, b is also revealed when chall = ±1, the values a, b, α1 , α3 can all be committed together. When chall = −1, the curve E3 and the points P3 , Q3 are not revealed, and thus learning α3 does not provide any information. The same applies to α1 when chall = +1. This allow us to reduce the number of commitments to four. To further reduce the communication between prover and verifier, the basis R2 , S2 on E2 can be chosen canonically, so that it can be recomputed from E2 . Moreover, for the challenge chall = −1, the prover can avoid revealing the A Post-Quantum Oblivious PRF from Isogenies 19 curve E2 , the points P2 , Q2 and the coefficients a, b by revealing instead a kernel generator of ψ. The prover can recompute E2 , P2 , Q2 and obtain a, b by writing a kernel generator of ψ̂ in terms of the canonical basis R2 , S2 . Normally, the recomputed a, b would not be the same as those computed by the verifier since they are not unique. The problem can be avoided by fixing a canonical way to compute the coefficients, such as prescribing that one of the two coefficients must be one, and that a must be one if both coefficients are invertible mod s. The same approach holds for chall = +1, except that the points R3 , S3 have to be revealed by the prover. In the case of the horizontal isogeny, the prover can avoid revealing E3 and the points R3 , S3 and P3 , Q3 . They can all be recomputed from the remaining values. Concrete cost. Each repetition of the proof requires two commitments, which are 2λ-bit long and use a λ-bit long opener. When chall = −1, the prover reveals one s-isogeny, a masking value, and two commitment openers, which requires log n + log s + 2λ bits. When chall = +1, the prover also reveals two torsion points of order s: if they are compressed as in [2], the response requires 5 log s + log n + 2λ bits. Lastly, for chall = 0, the prover reveals a curve, a d-isogeny, two points of order n, a masking value, and three openers; thus, the answer requires 2 log p + log d + 5 log n + 3λ bits.√ Hence, if we assume d ≈ n ≈ s ≈ 3 n, an average proof where the three challenges appear equally requires ≈ 1.71λ(20/9 log p + 7/3λ) bits, while a worst-case proof, with only chall = 0 challenges, requires ≈ 1.71λ(4 log p + 3λ) bits. 6 Verifiability Oblivious PRFs can satisfy a stronger security property called verifiability. In- formally, this guarantees that the server behaves honestly and always uses the same long-term static key. This is needed to guarantee the privacy of the user in those instances where the user may later reveal the output of the OPRF. A malicious server may behave “honestly” while also using different secret keys on different interactions. After learning the OPRF output of the user, the server can then test which secret key was used to produce that specific output and thus link the user to a specific user-server interaction. The OPRF protocol by Boneh, Kogan, and Woo achieves verifiability by intro- ducing three components. First, the server initially commits to a secret key k. The commitment is in the form of an elliptic curve EC := E/⟨P + [k]Q⟩, where the curve E and the points P, Q are fixed parameters. Second, during the OPRF execution, the server provides a zero-knowledge proof that its computations used the same key as the one in the commitment. We refer to this proof as a proof of parallel isogeny (PoPI). Lastly, the server also provides two proofs of isogeny knowledge (PoIKs) that guarantee the correctness of the computations during both the commitment stage and the OPRF execution. The proof of parallel isogeny proposed by Boneh, Kogan, and Woo relies on the user and the server engaging in an SIDH exchange, where one of the sides is either the commitment 20 Andrea Basso isogeny or the the secret server isogeny in the OPRF protocol. However, this proof is inherently interactive, and it requires five rounds of interaction. More- over, the proof relies on multiple SIDH exchanges, and it is thus broken by the attacks on SIDH [7,25,28]. We avoid these issues by introducing a novel public-coin proof protocol of parallel isogeny. Since the proof does not rely on private randomness, we obtain a proof of knowledge that can be made non-interactive via the Fiat-Shamir transform [14] or the Unruh transform [30]. In the OPRF setting, we will rely on the latter to achieve the online-extractability without rewinding needed to get a proof in the UC model. Our main approach relies on executing two proofs of isogeny knowledge in parallel with correlated randomness. Since part of the randomness used is shared, we can obtain a proof of parallelness without needing additional computations. Firstly, we formalize the notion of parallelness. We say that two d-isogenies ϕ : E0 → E1 and ϕ̃ : Ẽ0 → Ẽ1 are parallel with respect to the bases T0 , V0 ∈ E0 [d] and T̃0 , Ṽ0 ∈ E0′ [d] if there exists coefficients a, b ∈ Zd such that ker ϕ = ⟨[a]T0 + [b]V0 ⟩ and ker ϕ̃ = ⟨[a]T̃0 + [b]Ṽ0 ⟩. This suggests that the parallelness relation that we are proving is the following: E0 /⟨[k0 ]T0 + [k1 ]V0 ⟩ ∼   = E1 , Rpar = ((E0 , T0 , V0 , E1 , Ẽ0 , T̃0 , Ṽ0 , Ẽ1 ), (k0 , k1 )) Ẽ0 /⟨[k0 ]T̃0 + [k1 ]Ṽ0 ⟩ ∼ = Ẽ1 However, as discussed before, we are combining several proofs together to ob- tain a larger proof that simultaneously proves knowledge of two isogenies and guarantees the two isogenies are parallel. We thus obtain a proof for the follow- ing relation, where we consider the case of a secret key with two coefficients for completeness. For practical reasons, the OPRF will fix k0 = 1 without any loss of security.   ker ϕ = ⟨[k0 ]T0 + [k1 ]V0 ⟩,   0 0 0 0 0 1 1 1 ((E , T , V , P , Q , E , P , Q , ′   ker ϕ = ⟨[k ]T̃ + [k ] Ṽ ⟩,  ∗ 0 0 1 0 Rpar = Ẽ0 , T̃0 , Ṽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ), (E0 , P0 , Q0 , E1 , P1 , Q1 ), (ϕ, α) ∈ Riso ,  (k0 , k1 , α, α′ ))    (Ẽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ), (ϕ′ , α′ ) ∈ Riso   Now, let the curve Ẽ0 with a d-basis T̃0 , Ṽ0 be fixed protocol parameters. Using the same notation as before, assume that server has committed to its key (k0 , k1 ) by publishing the codomain of the d-isogeny ϕ̃ that has kernel ⟨[k0 ]T̃0 + [k1 ]Ṽ0 ⟩. The server may also reveal some torsion information in its commitment, but as we will discuss later, this is not strictly needed. During the OPRF execution, the server receives a curve E0 with a d-basis T0 , V0 on it, and it computes ϕ : E0 → E1 := E0 /⟨[k0 ]T0 + [k1 ]V0 ⟩. The server then wants to prove that it knows the isogenies ϕ and ϕ̃ and that they are parallel. If the server simply ran two instances of the PoIK from Fig. 4 in parallel, there would be no way to convince the prover that the isogenies are indeed parallel. If the proofs share the same challenges, i.e. the verifier sends the same challenges to both proofs, the server would respond with both ϕ′ and ϕ̃′ when chall = 0. How- ever, the isogenies ϕ′ and ϕ̃′ are parallel with respect to the bases ψ(T0 ), ψ(V0 ) A Post-Quantum Oblivious PRF from Isogenies 21 and ψ̃(T̃0 ), ψ̃(Ṽ0 ) (where ψ is the vertical isogeny used in the proof of knowl- edge), which are not revealed in the proof. If we were to reveal them, the proof would not be zero-knowledge, because when chall = 0, the verifier could recom- pute the secret isogeny ψ and ψ̃ through the SIDH attacks. Instead, we want to modify the proof to reveal different bases T2 , V2 ∈ E2 [d] and T̃2 , Ṽ2 ∈ Ẽ2 [d] such that ϕ′ and ϕ̃′ are parallel with regards to them, but also such that they do not reveal much information about ψ and ψ̃. We thus propose that the prover generates four random coefficients w, x, y, z ∈ Zd such that wz − xy ̸= 0 mod d, and computes T2 and V2 as the solution of ψ(T0 ) = [w]T2 + [x]S2 , ψ(V0 ) = [y]T2 + [z]V2 , and similarly for T̃2 and Ṽ2 . This is then secure, because the basis T2 , V2 is uniformly random. Thus, for a single proof, this change only does not affect the security of the proof since no additional information is revealed. The rest of the proof needs to be modified to ensure that the process is followed correctly, i.e. we want the prover to reveal the values w, x, y, z together with ψ so that the verifier can verify the correctness of T2 and V2 . The modified proof is denoted ∗ by Piso , and it is represented explicitly in Fig. 5.   P∗1  (E0 , T0 , V0 , P0 , Q0 ), (E1 , P1 , Q1 ), ϕ, α , (w, x, y, z) : 1-4: Same as P1 in Fig. 4. 5: Set T2 , V2 to satisfy ψ(T0 ) = [w]T2 + [x]S2 , ψ(V0 ) = [y]T2 + [z]V2 ; 6-8: Same as P1 in Fig. 4. P∗2 (st, chall): 1: if chall == −1 then 2: return ((E2 , T2 , V2 , P2 , Q2 , r1 ), (a, b, r3 ), (α1 , r5 ), (w, x, y, z)); 3: else if chall == 0 then 4: return ((E2 , T2 , V2 ,R2 , S2 , P2 , Q2 , r1 ), (E3 , R3 , S3 , P3 , Q3 , r2 ), (ϕ′ , r4 ), (α2 , r6 )); 5: else if chall == 1 then 6: Same as P2 in Fig. 4.   V∗ ( (E0 , T0 , V0 , P0 , Q0 ), (E1 , P1 , Q1 ), ϕ, α , com, chall, resp :  1: if chall == −1 then 2: ((E2 , R2 , S2 , P2 , Q2 , r1 ), (a, b, r3 ), (α1 , r5 ), (w, x, y, z)) = resp; 3-6: Same as V in Fig. 4. 7: Check ψ(T0 ) = [w]T2 + [x]S2 , ψ(V0 ) = [y]T2 + [z]V2 ; 8: else 9: Same as V in Fig. 4. Fig. 5: Modified proof of knowledge for the relation Riso where the basis ran- domness is explicit. The expressions in magenta denote the changes from Fig. 4. 22 Andrea Basso Now, if the prover executes the modified proof of isogeny knowledge for ϕ and ϕ̃ in parallel, with the same challenges, and with the same values x, w, y, z, the isogenies ϕ′ , ϕ̃′ revealed when chall = 0 are parallel when the isogenies ϕ, ϕ̃ are also parallel, as shown in the following lemma. Lemma 2. Let notation be as above. The isogenies ϕ, ϕ̃ are parallel if and only if the isogenies ϕ′ , ϕ̃′ are also parallel. Proof. Assume the isogeny ϕ has kernel ⟨[k0 ]T0 + [k1 ]V0 ⟩ and the isogeny ϕ̃ has kernel ⟨[k̃0 ]T̃0 + [k̃1 ]Ṽ0 ⟩. The kernel of ϕ′ is the image of the kernel of ϕ under ψ, i.e. ker ϕ′ = ψ(ker ϕ). Since ker ϕ = ⟨[k0 ]T0 + [k1 ]V0 ⟩, it follows that ker ϕ′ = ⟨[k0 ]ψ(T0 ) + [k1 ]ψ(V0 )⟩ = ⟨[wk0 + yk1 ]T2 + [xk0 + zk1 ]V2 ⟩. Similarly, we obtain ker ϕ̃′ = ⟨[wk̃0 + y k̃1 ]T̃2 + [xk̃0 + z k̃1 ]Ṽ2 ⟩. Since the coefficients w, x, y, z were chosen such that the matrix ( wy xz ) is invert- ible, we obtain that (k0 = k̃0 ) ∧ (k1 = k̃1 ) ⇐⇒ (wk0 + yk1 = wk̃0 + y k̃1 ) ∧ (xk0 + zk1 = xk̃0 + z k̃1 ). ∗ We can now use the proof Piso from Fig. 5 to construct our proof of parallel isogeny knowledge. The prover runs two such proofs in parallel, with the same randomness (w, x, y, z), and responds to the verifier’s challenges with the re- sponses of the individual proofs. The resulting proof is represented explicitly in Fig. 6. The security proofs follow closely those of the PoIK Piso in Section 5.2: correctness of Piso implies correctness of Ppar , while the soundness of Ppar follows from the soundness of Piso and Lemma 2. The argument for zero-knowledge is also similar, but it is based on the hardness of the following problem, which takes into consideration that the two parallel instance partially share the same randomness. Problem 7 (Double DSSP with Torsion (DDSSPwT) problem). Let D0 and D1 be as in Problem 6. Given: 1. two d-isogenies ϕ : E0 → E1 , ϕ̃ : Ẽ0 → Ẽ1 , 2. the points T0 , V0 ∈ E0 [d] and T̃0 , Ṽ0 ∈ Ẽ0 [d], 3. the points P0 , Q0 ∈ E0 [n] and P̃0 , Q̃0 ∈ Ẽ0 [n], where n = fMSIDH (λ, d), distinguish between the following distributions: (E2 , T2 , V2 , P2 , Q2 , E3 , ϕ′ ),   ∗ – D0 = , where the curves and the n-torsion (Ẽ2 , T̃2 , Ṽ2 , P̃2 , Q̃2 , Ẽ3 , ϕ̃′ ) points follow the D0 -distribution, i.e. we have (E2 , P2 , Q2 , E3 , ϕ′ ) ← D0 , and (Ẽ2 , P̃2 , Q̃2 , Ẽ3 , ϕ̃′ ) ← D0 , and moreover         T2 ψ(T0 ) T̃2 ψ̃(T̃0 ) =B , and =B , V2 ψ(V0 ) Ṽ2 ψ̃(Ṽ0 ) A Post-Quantum Oblivious PRF from Isogenies 23 P1 ((E0 , T0 , V0 , P0 , Q0 , E1 , P1 , Q1 ), (Ẽ0 , T̃0 , Ṽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ), k0 , k1 , α, α′ ): 1: Sample random coefficients w, x, y, z such that wz − xy ̸= 0 mod d; 2: Compute ϕ : E0 → E0 /⟨[k0 ]T0 + [k1 ]V0 ⟩ ∼ = E1 3: Compute ϕ′ : Ẽ0 → Ẽ0 /⟨[k0 ]T̃0 + [k1 ]Ṽ0 ⟩ ∼ = Ẽ1 4: Run P∗1 ((E0 , P0 , Q0 , E1 , P1 , Q1 ), ϕ, α, (w, x, y, z)) to get st, com; 5: Run P∗1 ((Ẽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 ,Q̃1 ), ϕ̃′ , α̃′ , (w, x, y, z)) to get st, ˜ com;˜ 6: return (st, st), ˜ (com, com) ˜ ; ˜ chall): P2 ((st, st), 1: return (P∗2 (st, chall), P∗2 (st, ˜ chall)); V((E0 , T0 , V0 , P0 , Q0 , E1 , P1 , Q1 ), (Ẽ0 , T̃0 , Ṽ0 , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ), ˜ chall, (resp, resp)): (com, com), ˜ 1: Set v := V∗ ((E0 , R, S, P0 , Q0 , E1 , P1 , Q1 ), com, chall, resp); 2: Set ṽ := V∗ ((Ẽ0 , T̃ , Ṽ , P̃0 , Q̃0 , Ẽ1 , P̃1 , Q̃1 ), com, ˜ chall, resp); ˜ 3: if chall == 0 and ϕ′ , ϕ̃′ are not parallel wrt T2 , V2 and T̃2 , Ṽ 2 then 4: return ⊥; 5: return v ∧ ṽ; Fig. 6: Interactive proof of knowledge for the relation R∗par . for some B ∈ GL2 (Zn ), and ψ and ψ̃ being respectively the s-isogenies between E0 and E2 and Ẽ0 and Ẽ2 that are guaranteed to exist because of the D0 distribution; (E2 , T2 , V2 , P2 , Q2 , E3 , ϕ′ ),   ∗ – D1 = , where the curves and the n-torsion (Ẽ2 , T̃2 , Ṽ2 , P̃2 , Q̃2 , Ẽ3 , ϕ̃′ ) points follow the D1 -distribution, i.e. we have (E2 , P2 , Q2 , E3 , ϕ′ ) ← D1 , and (Ẽ2 , P̃2 , Q̃2 , Ẽ3 , ϕ̃′ ) ← D1 , and moreover the points T2 , V2 and T̃2 , Ṽ2 form a random basis of E2 [d] and Ẽ2 [d], respectively. The proof Ppar is a proof of knowledge, and it can be made non-interactive with standards transformations, such as the Fiat-Shamir [14] or the Unruh [30] transform. This is the first non-interactive proof of parallelness. Optimizations. For simplicity, the presentation of the proof R∗par preferred a schematic description, but it is possible to improve the protocol to make it more compact. Besides the optimizations applicable to the proof Piso described in Section 5.2, we remark that parallelness is independent of torsion images. Thus, the proofs of isogeny knowledge do not need to guarantee the correctness of torsion images to prove parallelness. However, in the OPRF context, the correctness of the torsion images revealed by the server is needed to guarantee verifiability: a malicious server might otherwise reveal incorrect torsion points to different users and use that information to match OPRF outputs to specific 24 Andrea Basso interactions. Hence, the proof can be made more efficient by avoiding proving the correctness of torsion images for the commitment isogeny. Concrete cost. The proof described in Fig. 5 adds the communication of the values w, x, y, z when chall = −1. In that case, the prover’s response requires log n + log s + 4 log d + 2λ bits; when chall = 0, the response is also larger because the points R2 , S2 need to be communicated explicitly. The answers to the other challenge remains unchanged. The same proof, when used for the commitment isogeny, can avoid proving cor- rectness of the torsion images, resulting in a smaller proof. In particular, no masking values are ever revealed, and when chall = 0 the√response does not con- tain the points P2 , Q2 on E2 . Setting d ≈ n ≈ s ≈ 3 n, we obtain that an average proof Ppar requires ≈ 1.71λ(49/9 log p + 14/3λ) bits, while a worst-case proof would require ≈ 1.71λ(9 log p + 6λ) bits. 7 A new OPRF protocol In this section, we combine the countermeasures presented in Section 4, the SIDH countermeasures and the novel proof of isogeny knowledge discussed in Section 5, and the non-interactive proof of parallel isogeny introduced in Section 6 to obtain a verifiable OPRF protocol that is post-quantum secure, round-optimal, and moderately compact. The OPRF protocol is a two-party protocol between a user U and a server S. Let NM , NB , NK be coprime numbers representing the degrees of the message isogeny, the blinding isogeny, and the server’s isogeny, respectively. Let p be a prime of the form p = NM NB NK f − 1, for some cofactor f , and let E0 , Ẽ be two supersingular elliptic curves defined over Fp2 . Moreover, let P, Q be a fixed basis of E0 [NM ] and let P̃ , Q̃ be a fixed basis of Ẽ[NK ]. The first curve is used to compute the PRF, while the second is used within the server’s commitment. At a high-level, to evaluate the OPRF on an input x, the user maps the input to a curve Em according to Algorithm 1 and computes a blinding isogeny ϕb : Em → Emb . The user then sends the codomain curve, together with torsion images and a proof of their correctness, to the server, which computes a second isogeny ϕk : Emb → Embk . The torsion information is appropriately masked to avoid the SIDH attacks. The server then responds with the curve Embk , some torsion information, a proof of their correctness, and a proof that it has used the previously-committed secret key. The user then concludes by using the torsion information provided by the server to undo the blinding isogeny and compute the curve Emk . Its j-invariant is then hashed together with the input and the server’s public key to form the PRF output. The protocol is described in Fig. 7, and it realizes the OPRF ideal functionality of Fig. 2, which allows us to state the following theorem. Theorem 1. The protocol described in Fig. 7 realizes the ideal functionality FvOPRF of Fig. 2 in the random oracle model. A Post-Quantum Oblivious PRF from Isogenies 25 The proof follows the same line as the security proof of the OPRF protocol by Boneh, Kogan, and Woo [5, Theorem 20], since the hardness assumption of Problem 4 and the proof Piso are a drop-in replacement for the Auxiliary One-More SIDH assumption and the NIZKPK proof used in [5], respectively. At a high level, the case of an honest user and malicious server in the proof is simple because the server only interacts with the user through their first query, and in that case the user’s security corresponds to the input hiding property, guaranteed by the hardness of Problem 1. The case of a malicious user is more complicated, because the user has output. The server can be simulated as a honest server, but to ensure that the malicious user output is indistinguishable from the ideal-world, the random oracle H̄ can be programmed to output the ideal-world output. This would create a problem with the ticketing system of the ideal functionality if the adversary could produce more OPRF outputs than the number of interactions, but the one-more unpredictability property prevents that. The main difference between this proof and that of [5] is the use of a non- interactive proof of parallel isogeny, which results in a simpler proof since the proof of knowledge can be simulated. Note that the proof in [5] is written in terms of the augmentable commitment abstraction, which we preferred avoiding; since the same security properties can be directly expressed in terms of the OPRF protocol, as shown in Section 3, the difference is purely syntactical. Parameters. A prime p of the form p = NM NB NK f − 1, where NM , NB , NK are smooth coprime integers and f a smooth cofactor. E0 and Ẽ are supersingular elliptic curves defined over Fp2 , where End Ẽ is unknown, and P, Q ∈ E0 [NM ] and P̃ , Q̃ ∈ E[NK ] are fixed bases. The protocol also relies on the following functions: – Hi : {0, 1}∗ → ZM for i ∈ {1, . . . , I}, where I is such that NM I > 24λ ∗ λ – H̄ : {0, 1} → {0, 1} , to hash the final PRF output, and two non-interactive proofs of knowledge: Piso , for the user to prove correctness of torsion images, and Ppar , for the server to prove it computed honestly with the committed key. Initialization. On input init from the environment, the server S: – sample k ← ZK and stores it, – computes the curve ẼC = Ẽ/⟨P̃ + [k]Q̃⟩, – stores pk = (j(EC )) and outputs (init, pk). Evaluation. On input init from the environment, the server S: – On input (Eval, S, x), the user U proceeds as follows: 1. Sample α ← Z∗N and b ← ZB , 2. Compute (ϕm , Em ) = HI (x); 3. Compute ϕb : Em → Emb := Em /⟨Pm + [b]Qm ⟩, where Pm , Qm = BB (Em ), 4. Set ϕmb = ϕb ◦ ϕ1 ◦ ϕ0 , R = [α]ϕmb (P ), S = [α]ϕmb (Q), 5. Compute πc ← Piso (E0 , P, Q, Emb , R, S, ϕmb , α), 26 Andrea Basso 6. Send message (Emb , R, S, πc ) to the server and store ϕb . – On input ServerComplete from the environment and message (Emb , R, S, πc ) from the user U , the server S proceeds as follows: 1. Verify the proof πc and sample αk ← Z∗n , 2. Compute ϕk : Emb → Embk := Emb /⟨R + [k]S⟩, 3. Compute Rk = [αk ]ϕk (Pb ), Sk = [αk ]ϕk (Qb ), where Pb , Qb = BB (Emb ), 4. Compute πk ← Ppar ((Emb , Pb , Qb , Embk , Rk , Sk ), (Ẽ, P̃ , Q̃, ẼC ), k, αk )2 , 5. Send (pk, Embk , Rk , Sk , πk ) to the user U . – On input (pk = j(Ec ), Embk , Rk , Sk , πk ) from the server S, the user U proceeds as follows: 1. Verify the proof πk , 2. Compute b0 , b1 such that ⟨[b0 ]Pb + [b1 ]Qb ⟩ = ker ϕ̂b , where Pb , Qb = Bd (Emb ), 3. Compute ϕu : Embk → Emk := Embk /⟨[b0 ]Rk + [b1 ]Sk ⟩, 4. Compute y = H̄(x, pk, j(Em k)) and output (Eval, pk, y). Fig. 7: The verifiable OPRF protocol. Parameter selection. Firstly, we discuss how to select the starting curves E0 and Ẽ. As mentioned in Section 5, the cryptanalysis on masked-torsion SIDH with a starting curve with small endomorphism [15, Section 4.2] does not apply here, since the message isogeny removes this property from the starting curve of the blinding isogeny. Hence, the curve E0 does not need to have unknown endomorphism ring. However, the situation is different for Ẽ: as observed in [4], knowledge of End Ẽ allows to find collisions in the server’s commitment. Thus, knowing End Ẽ would allow the server to break verifiability, since it could prove parallelness to two distinct isogenies. It is thus necessary that the curve Ẽ is generated by a trusted party or through a multiparty trusted setup ceremony, such as the one presented in [3]. The main parameter of the OPRF protocol is the prime p. Firstly, if the message isogeny is the composition of many isogenies whose kernel is defined over Fp4 , the value p + 1 does not need have a dedicated factor. Then, for the main exchange, i.e. the blinding, server’s isogeny, unblinding part, we need to smooth coprime integers NB and NK that are highly composite to prevent the SIDH attacks. Following the analysis of Section 5, we have NB ≈ NK ≈ 22956 . Lastly, the proofs of knowledge Piso and Ppar require a third cofactor NS that is coprime with both NB and NK . To guarantee the hardness of Problems 6 and 7, the integer NS needs to be of the same length as NB and NK . However, since torsion points of order NS do not need to be masked, the value NS can be a prime power. Putting this 2 The proof algorithm does not receive torsion points because, as discussed in Section 6, they are not necessary to prove parallelness. A Post-Quantum Oblivious PRF from Isogenies 27 together, we obtain that the prime p needs to be of the form p = NB NS NK f − 1 and be at least 8868-bit long to guarantee λ = 128 bits of security. Note that the new computation of the message isogeny and the new proofs of knowledge has significantly reduced the size of the prime; compared to the OPRF protocol by Boneh, Kogan, and Woo, we use a prime that is 5.8× larger, while relying on an SIDH protocol with isogenies that are 9.2× longer. Efficiency. We now estimate the communication cost of the OPRF proto- col. The largest components are the non-interactive proofs of knowledge: given the analysis of the previous sections, they are less than 1.7λ(35 log p + 51λ)- bit long. Since log p ≈ 10λ log λ, we obtain that one OPRF execution requires 1.7λ2 (350 log λ + 51) bits of communication. For λ = 128, this corresponds to a transcript of 8.7 MB. We remark that the size of the proofs is particularly large due to the Unruh transform needed to prove security in the UC framework. If the proofs were made non-interactive via the Fiat-Shamir transform, a single execution of the verifiable OPRF with λ = 128 would require 1.9 MB of com- munication on average and 3.8 MB in the worst case. Such an OPRF may be used in instances where security in the UC framework is not necessary. A direct comparison with the protocol by Boneh, Kogan, and Woo [5] is not sim- ple since their bandwidth estimate does not appear to include the Unruh trans- form overhead. We estimate that one execution of the OPRF from [5] requires at least 10.9 MB3 . Our protocol is thus more compact than that in [5], despite be- ing round-optimal and secure against both the one-more unpredictability attack and the SIDH attacks. This is made possible by the fact that the sigma protocols are highly optimized and have ternary challenges, which significantly reduces the overhead introduced in the Unruh transform. Indeed, if we compare a version of the two protocols with the Fiat-Shamir transform, our OPRF uses 31% more bandwidth than the one in [5]. We summarize the state of post-quantum OPRF protocols in Table 1. 8 Conclusion In this work, we presented a post-quantum verifiable oblivious PRF protocol that is moderately compact and round-optimal. The protocol is the first round- 3 In [5, Section 5], the authors estimate that the largest response in the sigma protocol Rcom requires 6 log p + 5λ bits. The protocol has a challenge space of size 6, and it needs to be repeated 3.8λ times to obtain a negligible soundness error. Without considering the size of the committments, the Unruh-based NIZKP contains 6 hashed values that are as long as the largest response, per each iteration. The transcript of an Rcom proof thus requires at least 3.8λ × 6(6 log p + 5λ) bits. The entire OPRF hence requires three times as much (three such proofs are used), plus 5λ log p bits for the proof of parallel isogenies. 4 The number of communication rounds depends on the underlying OT construction. An update to [24] suggests four rounds may be necessary. 5 Recent work by Heimberger, Meisingseth, and Rechberger [18] suggests such con- struction may be insecure. 28 Andrea Basso Table 1: Post-quantum OPRF protocols secure against malicious clients. Protocol Rounds Bandwidth (avg.) Verifiable Secure [1] (LWE) 2 >128 GB ✓ ✓ [5] (CSIDH) 34 424 kB ✗ ✓5 [5] (SIDH)FO 6 1.4 MB ✓ ✗ [5] (SIDH)Unruh 6 >10.9 MB ✓ ✗ [This work]FO 2 1.9 MB ✓ ✓ [This work]Unruh 2 8.7 MB ✓ ✓ optimal OPRF based on isogenies, and it is several orders of magnitude more compact than the existing round-optimal protocol. To obtain this protocol, we started from an insecure protocol by Boneh, Kogan, and Woo, and we proposed an efficient countermeasure against the one-more unpredictability attack, in- tegrated the existing SIDH countermeasures, developed a new zero-knowledge proof of isogeny that works with the SIDH countermeasures, and proposed a novel non-interactive proof of parallel isogeny that reduced the number of rounds to two. The protocol is an important stepping stone towards fully practical post- quantum OPRFs, but its performance is hindered by the inefficiency of the SIDH countermeasures. In future work, we aim at developing more efficient solutions: a moderate reduction in the degree of the isogenies would significantly improve the efficiency of the protocol. It is also interesting to improve the proof of parallel isogeny by avoiding validating the commitment isogeny at every interaction. Acknowledgements. The author thanks Christophe Petit and Luca de Feo for various suggestions, and Tako Boris Fouotsa, Christophe Petit, Chloe Mar- tindale, and the anonymous reviewers of Crypto and the PQCifris workshop for feedback on earlier versions of this work. The author would also like to thank Luca de Feo, Antonin Leroux, and Benjamin Wesolowski for fruitful discussions on isogeny-based zero-knowledge proofs at the Banff International Research Sta- tion workshop “Supersingular Isogeny Graphs in Cryptography”. This work has been supported in part by EPSRC via grant EP/R012288/1, under the RISE (http://www.ukrise.org) programme. References 1. Albrecht, M.R., Davidson, A., Deo, A., Smart, N.P.: Round-optimal verifiable oblivious pseudorandom functions from ideal lattices. In: Garay, J. (ed.) PKC 2021, Part II. LNCS, vol. 12711, pp. 261–289. Springer, Heidelberg (May 2021). https: //doi.org/10.1007/978-3-030-75248-4 10 2. Azarderakhsh, R., Jao, D., Kalach, K., Koziel, B., Leonardi, C.: Key compression for isogeny-based cryptosystems. In: Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography. pp. 1–10. ACM (2016) A Post-Quantum Oblivious PRF from Isogenies 29 3. Basso, A., Codogni, G., Connolly, D., De Feo, L., Fouotsa, T.B., Lido, G.M., Mor- rison, T., Panny, L., Patranabis, S., Wesolowski, B.: Supersingular curves you can trust. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part II. LNCS, vol. 14005, pp. 405–437. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978- 3-031-30617-4 14 4. Basso, A., Kutas, P., Merz, S.P., Petit, C., Sanso, A.: Cryptanalysis of an obliv- ious PRF from supersingular isogenies. In: Tibouchi, M., Wang, H. (eds.) ASI- ACRYPT 2021, Part I. LNCS, vol. 13090, pp. 160–184. Springer, Heidelberg (Dec 2021). https://doi.org/10.1007/978-3-030-92062-3 6 5. Boneh, D., Kogan, D., Woo, K.: Oblivious pseudorandom functions from isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 520–550. Springer, Heidelberg (Dec 2020). https://doi.org/10.1007/978-3-030- 64834-3 18 6. Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: 42nd FOCS. pp. 136–145. IEEE Computer Society Press (Oct 2001). https://doi.org/10.1109/SFCS.2001.959888 7. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 423–447. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4 15 8. Charles, D.X., Lauter, K.E., Goren, E.Z.: Cryptographic hash functions from ex- pander graphs. Journal of Cryptology 22(1), 93–113 (Jan 2009). https://doi.org/ 10.1007/s00145-007-9002-x 9. Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) CRYPTO’82. pp. 199–203. Plenum Press, New York, USA (1982) 10. Costello, C., Longa, P., Naehrig, M.: Efficient algorithms for supersingular isogeny Diffie-Hellman. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 572–601. Springer, Heidelberg (Aug 2016). https://doi.org/10.1007/ 978-3-662-53018-4 21 11. Davidson, A., Goldberg, I., Sullivan, N., Tankersley, G., Valsorda, F.: Privacy Pass: Bypassing internet challenges anonymously. Proc. Priv. Enhancing Technol. 2018(3), 164–180 (2018). https://doi.org/10.1515/popets-2018-0026 12. De Feo, L., Dobson, S., Galbraith, S.D., Zobernig, L.: SIDH proof of knowledge. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part II. LNCS, vol. 13792, pp. 310– 339. Springer, Heidelberg (Dec 2022). https://doi.org/10.1007/978-3-031-22966- 4 11 13. Eisenträger, K., Hallgren, S., Lauter, K.E., Morrison, T., Petit, C.: Supersingular isogeny graphs and endomorphism rings: Reductions and solutions. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 329– 368. Springer, Heidelberg (Apr / May 2018). https://doi.org/10.1007/978-3-319- 78372-7 11 14. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO’86. LNCS, vol. 263, pp. 186– 194. Springer, Heidelberg (Aug 1987). https://doi.org/10.1007/3-540-47721-7 12 15. Fouotsa, T.B., Moriya, T., Petit, C.: M-SIDH and MD-SIDH: Countering SIDH at- tacks by masking information. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 282–309. Springer, Heidelberg (Apr 2023). https: //doi.org/10.1007/978-3-031-30589-4 10 16. Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 303– 30 Andrea Basso 324. Springer, Heidelberg (Feb 2005). https://doi.org/10.1007/978-3-540-30576- 7 17 17. Galbraith, S.D.: Authenticated key exchange for SIDH. Cryptology ePrint Archive, Report 2018/266 (2018), https://eprint.iacr.org/2018/266 18. Heimberger, L., Meisingseth, F., Rechberger, C.: Oprfs from isogenies: Designs and analysis. Cryptology ePrint Archive, Paper 2023/639 (2023), https://eprint.iacr. org/2023/639 19. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, B.Y. (ed.) Post-Quantum Cryptography - 4th In- ternational Workshop, PQCrypto 2011. pp. 19–34. Springer, Heidelberg (Nov / Dec 2011). https://doi.org/10.1007/978-3-642-25405-5 2 20. Jarecki, S., Kiayias, A., Krawczyk, H.: Round-optimal password-protected secret sharing and T-PAKE in the password-only model. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 233–253. Springer, Heidelberg (Dec 2014). https://doi.org/10.1007/978-3-662-45608-8 13 21. Jarecki, S., Kiayias, A., Krawczyk, H., Xu, J.: TOPPSS: Cost-minimal password- protected secret sharing based on threshold OPRF. In: Gollmann, D., Miyaji, A., Kikuchi, H. (eds.) ACNS 17. LNCS, vol. 10355, pp. 39–58. Springer, Heidelberg (Jul 2017). https://doi.org/10.1007/978-3-319-61204-1 3 22. Jarecki, S., Krawczyk, H., Xu, J.: OPAQUE: An asymmetric PAKE protocol se- cure against pre-computation attacks. In: Nielsen, J.B., Rijmen, V. (eds.) EU- ROCRYPT 2018, Part III. LNCS, vol. 10822, pp. 456–486. Springer, Heidelberg (Apr / May 2018). https://doi.org/10.1007/978-3-319-78372-7 15 23. Jarecki, S., Liu, X.: Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 577–594. Springer, Heidelberg (Mar 2009). https: //doi.org/10.1007/978-3-642-00457-5 34 24. Lai, Y.F., Galbraith, S.D., Delpech de Saint Guilhem, C.: Compact, efficient and UC-secure isogeny-based oblivious transfer. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 213–241. Springer, Hei- delberg (Oct 2021). https://doi.org/10.1007/978-3-030-77870-5 8 25. Maino, L., Martindale, C., Panny, L., Pope, G., Wesolowski, B.: A direct key recovery attack on SIDH. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 448–471. Springer, Heidelberg (Apr 2023). https: //doi.org/10.1007/978-3-031-30589-4 16 26. Merz, S.P., Minko, R., Petit, C.: Another look at some isogeny hardness assump- tions. In: Topics in Cryptology - CT-RSA 2020 - the Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24-28, 2020, Proceed- ings. pp. 496–511 (2020) 27. Naor, M., Reingold, O.: Number-theoretic constructions of efficient pseudo-random functions. In: 38th FOCS. pp. 458–467. IEEE Computer Society Press (Oct 1997). https://doi.org/10.1109/SFCS.1997.646134 28. Robert, D.: Breaking SIDH in polynomial time. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part V. LNCS, vol. 14008, pp. 472–503. Springer, Heidelberg (Apr 2023). https://doi.org/10.1007/978-3-031-30589-4 17 29. Silverman, J.H.: The Arithmetic of Elliptic Curves, vol. 106. Springer Science & Business Media (2009) 30. Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 755–784. Springer, Heidelberg (Apr 2015). https://doi.org/10.1007/ 978-3-662-46803-6 25