                           OPRFs from Isogenies: Designs and Analysis
                Lena Heimberger                                      Tobias Hennerbichler                                   Fredrik Meisingseth
        lena.heimberger@iaik.tugraz.at                            Graz University of Technology                       Graz University of Technology and
         Graz University of Technology                                    Graz, Austria                                         Know-Center
                 Graz, Austria                                                                                                  Graz, Austria

                                          Sebastian Ramacher                                        Christian Rechberger
                                AIT Austrian Institute of Technology                              Graz University of Technology
                                          Vienna, Austria                                                 Graz, Austria
ABSTRACT                                                                                      CCS CONCEPTS
Oblivious Pseudorandom Functions (OPRFs) are an elementary                                    • Security and privacy → Public key (asymmetric) techniques.
building block in cryptographic and privacy-preserving applica-
tions. While there are numerous pre-quantum secure OPRF con-                                  KEYWORDS
structions, it is unclear which of the proposed options for post-                             Oblivious Pseudorandom Function, CSIDH, Isogenies, OPAQUE,
quantum secure constructions are practical for modern-day ap-                                 Private Set Intersection, OPUS
plications. In this work, we focus on isogeny group actions, as
the associated low bandwidth leads to efficient constructions. We                             ACM Reference Format:
introduce OPUS, a novel Naor-Reingold-based OPRF from isoge-                                  Lena Heimberger, Tobias Hennerbichler, Fredrik Meisingseth, Sebastian
nies without oblivious transfer, and show efficient evaluations of                            Ramacher, and Christian Rechberger. 2024. OPRFs from Isogenies: Designs
the Naor-Reingold PRF using CSIDH and CSI-FiSh. Additionally,                                 and Analysis. In ACM Asia Conference on Computer and Communications
                                                                                              Security (ASIA CCS ’24), July 1–5, 2024, Singapore, Singapore. ACM, New
we analyze a previous proposal of a CSIDH-based OPRF and that
                                                                                              York, NY, USA, 14 pages. https://doi.org/10.1145/3634737.3645010
the straightforward instantiation of the protocol leaks the server’s
private key. As a result, we propose mitigations to address those
shortcomings, which require additional hardness assumptions. Our                              1     INTRODUCTION
results report a very competitive protocol when combined with                                 Cloud computing, authenticated key exchange and secure data
lattices for Oblivious Transfer.                                                              sharing are ubiquitous in modern-day computation. All of these
   Our evaluation shows that OPUS and the repaired, generic con-                              high-level applications may use Oblivious Pseudorandom Func-
struction are competitive with other proposals in terms of runtime                            tions (OPRFs) as an underlying building block to strengthen security
efficiency and communication size. More concretely, OPUS achieves                             and guarantee privacy. Informally, OPRFs take input from a client
almost two orders of magnitude less communication overhead com-                               and a key from a server, then return a pseudorandom output to the
pared to the next-best lattice-based OPRF at the cost of higher                               client. The OPRF is secure when the client learns nothing about the
latency and higher computational cost, and the repaired construc-                             key, and the server learns nothing about the output or the client
tion. Finally, we demonstrate the efficiency of OPUS and the generic                          input. This basic functionality gives rise to various applications.
NR-OT in two use cases: first, we instantiate OPAQUE, a protocol                                 For example, consider password authentication: To prove the
for asymmetric authenticated key exchange. Compared to classical                              knowledge of a pre-registered password, the client transmits their
elliptic curve cryptography, which is considered insecure in the                              password, ideally in a salted and hashed form. The server checks the
presence of efficient quantum computers, this results in less than                            transmitted password against a stored record and authenticates the
100 × longer computation on average and around 1000× more com-                                client if the record matches the password. However, passwords no-
munication overhead. Second, we perform an unbalanced private                                 toriously lack entropy and may be recovered from a server record in
set intersection and show that the communication overhead can                                 the event of a breach. In addition, this ideal setting is not always the
be roughly the same when using isogenies or elliptic curves, at the                           case, as attacks leaking cleartext passwords are still common. For ex-
cost of much higher runtime. Conversely, for sets of the size 210 ,                           ample, PwnedPasswords [Hun] consolidates breaches of passwords
we report a runtime around 200× slower than the elliptic curve                                and finds over 90 matches when searching for plain text breaches.
PSI. This concretizes the overhead of performing PSI and using                                This attack vector can be mitigated by never storing passwords on
OPAQUE with isogenies for the first time.                                                     a server in the first place. A great example of a protocol solving the
                                                                                              password storage problem is OPAQUE, an asymmetric password-
                                                                                              authenticated key agreement protocol for which standardization
                                                                                              efforts are ongoing at the CFRG [DFHSW22].
                                                                                                 Use cases of ORPFs expand beyond passwords and include pri-
                                                                                              vate set intersection (PSI), where two parties with respective datasets
This work is licensed under a Creative Commons Attribution International 4.0 License.         wish to compute the overlapping elements in both sets without
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore                                            revealing their non-shared elements. This can be used for private
                                                                                              contact discovery [KRS+ 19] to protect the highly sensitive social
© 2024 Copyright held by the owner/author(s).
ACM ISBN 979-8-4007-0482-6/24/07.
https://doi.org/10.1145/3634737.3645010                                                       graph of messenger app users from ever being uploaded to a server.




                                                                                        575
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore        Lena Heimberger, Tobias Hennerbichler, Fredrik Meisingseth, Sebastian Ramacher, and Christian Rechberger


   While there is a variety of sound and efficient constructions                   represented in CSIDH as the private exponent vector. This array
for OPRFs from classical primitives, efficient and secure OPRFs                    of 𝑘 elements (𝑒 1, . . . , 𝑒𝑘 ) forms the private key whereas a single
from post-quantum hardness assumptions remain an open ques-                        element of the vector is called a key coefficient. Each key coefficient
tion. An interesting primitive for quantum-resistant OPRFs are                     𝑒𝑖 is a random element in the range [−𝑚, 𝑚]. 𝑚 is a bound obtained
isogenies, which have small communication complexity but suffer                                                                                   log 𝑝
                                                                                   from the parameter generation to store approximately 22 bits.
from slow runtimes. Until now, there was only one OPRF based on                    The sign of the key coefficient describes the direction of the walk:
CSIDH [BKW20]. We show that the naïve approach to the imple-                       Walking 𝑒 steps from some point and then −𝑒 steps results in re-
mentation is not sufficient, and subsequently propose a fix using                  turning to the starting point. This is a result of the dual isogeny
uniform sampling for the keys as used in the signature scheme CSI-                 theorem, which states that for each isogeny 𝐸 → 𝐸 ′ , a correspond-
FiSh [BKV19]. We combine the OPRF with a lattice-based Oblivious                   ing isogeny 𝐸 ′ → 𝐸 exists. The dual isogeny can be directly used
Transfer protocol to achieve a relatively fast construction that com-              to invert the key: negating each key coefficient 𝑒𝑖 ↦→ −𝑒𝑖 results in
putes the OPRF in under 100 ms online time. Of independent inter-                  the inversion of 𝑘, which we will denote as 𝑘 −1 . It is also possible
est, we report that the Naor-Reingold PRF is nearly constant-time                  to add two private keys, where their respective coefficient vectors
with respect to the input length when using the lattice reductions                 are added, which we will denote as 𝑘 + 𝑙, with 𝑘 and 𝑙 being CSIDH
of CSI-FiSh. Based on the work on this OPRF, we introduce OPUS,                    private keys. Following the notation in [LGD21], we use s ∗ 𝐸 as
a novel construction that only uses CSIDH operations. It efficiently               shorthand to denote the class group action between 𝔰 = {𝔩𝑠11 · · · 𝔩𝑘𝑠𝑘 }
computes the Naor-Reingold OPRF while only using 60% of the                        and 𝐸 using the vector s = (𝑠 1, . . . , 𝑠𝑘 ).
group actions of the previous proposal, without needing a trusted                      The corresponding CSIDH public key is the Montgomery coef-
setup. Furthermore, we present the first post-quantum implemen-                    ficient 𝐴 ∈ F𝑝 of the supersingular curve 𝐸 : 𝑣 2 = 𝑢 3 + 𝐴𝑢 2 + 𝑢
tation of OPAQUE using two isogeny-based OPRFs. In addition,                       and deterministically obtained by repeatedly applying the private
we implemented and evaluate private set intersection with both                     key to the base curve 𝐸 0 : 𝑣 2 = 𝑢 3 + 0 · 𝑢 2 + 𝑢. Of 𝑝 possible public
OPRFs.                                                                                                     √
                                                                                   keys, approximately 𝑝 of those keys are valid, meaning that they
                                                                                   describe supersingular curves.
2     PRELIMINARIES
                                                                                   2.1.2 Computational Assumptions. For the security proof, we recall
We recall (Oblivious) Pseudorandom Functions.
                                                                                   the key recovery problem [CLM+ 18, Problem 10] for CSIDH.
Definition 1 (Pseudorandom Function). A pseudorandom func-
                                                                                      Problem 1 (Key Recovery Problem). Given the two different
tion (PRF) [GGM84, GGM86] is a deterministic and polynomial time
                                                                                   supersingular curves 𝐸, 𝐸 ′ ∈ E, find an s ∈ 𝐶𝑙 (O) such that s∗𝐸 = 𝐸 ′ .
function 𝐹 : {0, 1}𝑘 × {0, 1}𝑥 → {0, 1}𝑛 such that 𝐹 i there is no
probabilistic polynomial-time algorithm to distinguish any output                     [LGD21] give a useful lemma showing that sampling elements of
𝑁 from a randomly chosen element from {0, 1}𝑛 .                                    the class group 𝐶𝑙 (O) is statistically close to uniform which follows
                                                                                   directly from Problem 1.
Definition 2 (Oblivious Pseudorandom Function). An oblivious
pseudorandom function (OPRF) [FIPR05] is a protocol between two                      Lemma 1 (Computational Hiding in CSIDH). Given a curve 𝐸 ∈
parties. One party holds the secret key 𝐾 and the other holds their                E and a distribution 𝐷 on 𝐶𝑙 (O), let 𝐷 ∗ 𝐸 be the distribution on E of
secret input 𝑋 . The OPRF privately realizes the joint computation                            $
                                                                                   𝑎∗𝐸 for 𝑎 ←− 𝐷. If 𝐷 is statistically indistinguishable from the uniform
outputting 𝐹 (𝐾, 𝑋 ) for a PRF 𝐹 to the party holding 𝑋 , and nothing              distribution on 𝐶𝑙 (O), 𝐷 ∗ 𝐸 is statistically indistinguishable from
to the party holding 𝐾.                                                            the uniform distribution on E. Therefore, we say that 𝐷 statistically
                                                                                   hides 𝐸.
2.1     CSIDH
                                                                                      We recall the computational CSIDH problem from [CLM+ 18].
CSIDH [CLM+ 18], was originally proposed as a quantum-safe re-
placement for Diffie-Hellman key exchanges. It builds on the ideas                    Problem 2 (Computational CSIDH Problem). Given curves
of Couveignes [Cou06] and Rostovtsev-Stolbunov [RS06](CRS), but                    𝐸 ∈ E, r ∗ 𝐸 ∈ E, and s ∗ 𝐸 ∈ E where r, s ∈ 𝐶𝑙 (O), find 𝐸 ′ ∈ E such
restricts the isogeny graph to supersingular curves over F𝑝 . 𝑝 is a               that 𝐸 ′ = r ∗ s ∗ 𝐸.
                           Î                                        √
prime in the form 𝑝 = 4 𝑛𝑖=1 ℓ𝑖 − 1 and 𝑝 ≡ 3 mod 4. For 𝜋 = −𝑝
                                                                                      Finally, we recall the decisional CSIDH problem from [EKP20]:
and O = Z[𝜋], each ℓ𝑖 splits the endomorphism ring O into 𝔩𝑖
isogenies with degree ℓ𝑖 . The isogeny 𝜙 : 𝐸 → 𝐸 ′ is a map from                      Problem 3. Decisional CSIDH Problem Given the set of curves E
an elliptic curve 𝐸 to another curve 𝐸 ′ that preserves the point at               and the ideal class group 𝐶𝑙 (O), the decisional CSIDH (D-CSIDH)
infinity and the algebraic structure [Sil86]. Hence, both curves have              problem asks to distinguish between the following two distributions:
the same number of rational points. The isogeny is unique up to                                                               $             $
                                                                                       • (𝐸, 𝐻, 𝑎 ∗ 𝐸, 𝑎 ∗ 𝐻 ) with 𝐸, 𝐻 ←
                                                                                                                         − E and 𝑎 ←
                                                                                                                                   − 𝐶𝑙 (O).
isomorphism. It is computed using Velu’s formula [Vél71].                                                                       $
   The heart of CSIDH is the group action ∗, which iteratively com-                    • (𝐸, 𝐻, 𝐸 ′, 𝐻 ′ ) where 𝐸, 𝐻, 𝐸 ′, 𝐻 ′ ←
                                                                                                                                − E.
putes the ℓ𝑖 isogenies. It acts on the set of elliptic curves Eℓℓ𝑝 (O, 𝜋),         If for all PPT adversaries A, the advantage in distinguishing the two
denoted as E. To ensure the group action is efficient, each ℓ𝑖 is re-              distributions is negligible, we say that the C-CSIDH assumption holds.
quired to be a small, distinct, odd prime.
                                                                                   2.1.3 Parameterization and Security. The size of the prime 𝑝 de-
2.1.1 Private Key and Public Key. The ideal class group 𝐶𝑙 (O) acts                notes the security parameter of CSIDH. There is heavy disagree-
freely and transitively on E. The element {𝔩𝑒11 · · · 𝔩𝑘𝑒𝑘 } of 𝐶𝑙 (O) is          ment in the literature on the secure parameterization of CSIDH




                                                                             576
OPRFs from Isogenies: Designs and Analysis                                                                                            ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore


[BLMP19, BS20, Pei20], as several theoretical and concrete quan-                                    call finalization element, 𝑓 𝑖𝑛 = 𝑘 0 ◦ 𝑟 1−1 ◦ . . . ◦ 𝑟𝑛−1 to the client.
tum attacks with subexponential complexity dispute that a prime                                     The client now performs a final group action with the finalization
𝑝 which is 512 bits long is sufficient for security. Related work on                                element and the blinded group elements to obtain the result:
OPRFs [BKW20] recommends using 2260-bit prime numbers for
aggressive parameterization and 5280-bit primes for a conserva-                                     𝑘 1 𝑥 1 ◦ 𝑟 1 ◦ . . . ◦ 𝑘𝑛 𝑥𝑛 ◦ 𝑟𝑛 ◦ 𝑘 0 ◦ 𝑟 1−1 ◦ . . . ◦ 𝑟𝑛−1 = 𝑘 0 ◦ 𝑘 1 𝑥 1 ◦ 𝑘𝑛 𝑥𝑛
tive instantiation based on analysis of these algorithms. Recent
work analyzing and implementing CSIDH with bigger primes con-                                       2.5     Notation
cludes that a bitlength of at least 2048 bits, up to 9216 bits is neces-                            We write a vector v as a bold, lowercase variable, which is used for
sary [CSCJR22].                                                                                     private exponent vectors. For two vectors a and b, a + b and a − b
   For best comparability with other implementations, we use the                                    denote coefficient-wise addition and substraction.
512-bit reference implementation of CSIDH throughout this pa-                                          We denote the sequential application of the group action
per, but point out that the prime length may not be sufficient. An                                  csidh(csidh(𝐸, a), b) as b ∗ (a ∗ 𝐸). Due to the commutativity of
additional benefit of this implementation is the use of hardware                                    CSIDH, this is also equivalent to (a + b) ∗ 𝐸. We denote the zero
instructions, which speed up the computation.                                                       curve as 𝐸 0 and any other curve as 𝐸, potentially annotating it to
                                                                                                    give more context. For example, the result of applying some key c
2.2     CSI-FiSh                                                                                    will be denoted 𝐸𝑐 = csidh(c, 𝐸 0 ) = c ∗ 𝐸 0 .
Building on CSIDH, the signature scheme CSI-FiSh introduces a                                          We will use an ideal functionality keygen() to sample random,
                                                                                                                                                            $
uniform representation of the class group elements. In their pa-                                    uniform CSIDH private keys. [k1, k2 ] ←
                                                                                                                                          − keygen() samples two
per, this is necessary for the Fiat-Shamir transformation to obtain                                 random, independent and uniform keys. We will call a curve 𝐸 ran-
a signature scheme, but the use cases stretch beyond signatures.                                                                                        $
                                                                                                    domized after sampling a private key r ←− keygen() and computing
Intuitively, increasing the bound 𝑚 of the key coefficient comes
                                                                                                    𝐸 ′ = r ∗ 𝐸. We remove the property after applying r −1 to the curve
closer to sampling uniformly over the class group. To sample fully
                                                                                                    𝐸 ′ , therefore removing the randomness.
uniform keys, CSI-FiSh computes the class number and class group
structure and reduces the key after the arithmetic operation to
                                                                                                    2.6     Benchmarks
avoid leakage. Due to the different distribution of the class group
ideals, the group action is around 15% slower.                                                      All benchmarks, unless specified otherwise, are averaged over 100
                                                                                                    executions with random input and have been run on a computer
2.3     The Naor-Reingold Pseudorandom Function                                                     with an AMD Ryzen 7 PRO 4750U Processor with a fixed proces-
                                                                                                    sor speed at 1.7 GHz and 24 GiB RAM, under the Linux kernel
        (NR-PRF)
                                                                                                    6.1.44-1-lts. We will refer to this setup as the test machine. Unless
The Naor-Reingold PRF [NR04] is a generic construction for PRFs                                     otherwise stated, the input length to the OPRF is 128 bits.
from Abelian group actions that is widely used in the literature
and practice. The PRF requires 𝑛 + 1 group elements, or keys, for                                   3     ATTACKING AND REPAIRING THE
𝑛 bits of PRF input. To compute the PRF, we take the initial group
element 𝑘 0 . For each input bit 𝑥𝑖 for 𝑖 ∈ [1, 𝑛], a group action is
                                                                                                          GENERIC NAOR-REINGOLD OPRF FROM
performed if the 𝑖 𝑡ℎ bit 𝑥𝑖 is set. For a group action denoted as ◦,                                     CSIDH
the Naor-Reingold PRF is defined as                                                                 Previous work [BKW20] describes the Naor-Reingold (NR) OPRF
                                                                                                    for CSIDH to compare against their SIDH-based proposal. While the
   𝐹 𝑁 𝑅 ((𝑘 0, 𝑘 1, . . . , 𝑘𝑛 , 𝐸 0 ), (𝑥 1, . . . , 𝑥𝑛 )) := 𝑘 0 ◦ 𝑘 1𝑥 1 ◦ . . . ◦ 𝑘𝑛𝑥𝑛
                                                                                                    latter has been broken [BKM+ 21] and subsequently repaired [Bas23],
where the exponentiation with 𝑥𝑖 may be read as perform ◦ if input                                  the approximations for the Naor-Reingold OPRF from CSIDH are
bit is set.                                                                                         widely cited in the literature and have not been studied further.
                                                                                                    We fill this gap with a thorough investigation of both NR-PRF and
2.4     Oblivious Transfer and Naor-Reingold OPRF                                                   NR-OPRF from CSIDH. More concretely, we show in this section
The NR-PRF gives rise to oblivious evaluation using oblivious trans-                                that the naïve instantiation of the OPRF leads to a full key recovery
fer (OT). OT takes two messages (𝑚 0, 𝑚 1 ) from the sender, usually                                in a passive attack and propose a mitigation.
the server, and a choice bit 𝑐 from the receiver, usually the client.
The protocol functionality returns 𝑚𝑐 to the client and is secure                                   3.1     Instantiating the NR-PRF from CSIDH
when the client learns nothing about 𝑚 1−𝑐 and the server learns                                    To instantiate the NR-PRF with CSIDH, the protocol samples 𝑛 + 1
nothing about 𝑐.                                                                                    CSIDH private keys and computes the group action as in Section 2.3.
   To compute the NR-PRF obliviously using OT, the input 𝑋 is bit-                                  The textbook variant of the PRF outlined in Figure 1 is prohibitively
decomposed into 𝑋 = [𝑥 1, . . . , 𝑥𝑛 ] to use as an input for the OT. The                           slow, requiring 𝑛+1 sequential group actions to compute the PRF for
server samples 𝑛 blinding elements [𝑟 1, . . . , 𝑟𝑛 ] and inputs 𝑟𝑖 , 𝑘𝑖 ◦ 𝑟𝑖                       𝑛 input bits. A recent paper [ADMP20] describes an effective way
to the OT, with 𝑟𝑖 perfectly hiding 𝑘𝑖 . The client queries the OT with                             to evaluate the PRF by splitting the evaluation into two parts: First,
each 𝑥𝑖 to obtain 𝑘𝑖 𝑥𝑖 ◦ 𝑟𝑖 and aggregates all results with the group                              a subset-product, in the case of CSIDH addition of all key elements
action to obtain the blinded group element 𝑘 1 𝑥 1 ◦ 𝑟 1 ◦ . . . ◦ 𝑘𝑛 𝑥𝑛 ◦ 𝑟𝑛 .                     where 𝑥𝑖 = 1, is computed. This first step can be parallelized. The
To finalize the computation, the server evaluates the inverse of all                                group action is then evaluated using the aggregated key elements
blinding elements with the key and sends the result, which we will                                  in a second step on the base curve.




                                                                                              577
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore                                 Lena Heimberger, Tobias Hennerbichler, Fredrik Meisingseth, Sebastian Ramacher, and Christian Rechberger



                            𝐹 𝑁 𝑅−𝐶𝑆𝐼 𝐷𝐻 ((k0, k1, . . . , kn ), (𝑥 1, . . . , 𝑥𝑛 )) :=
                                                                                                                                           recomputating the PRF
                                        k0 ∗ k1 𝑥 1 ∗ . . . ∗ kn 𝑥𝑛 ∗ 𝐸 0                                                                     updating the PRF
                                                                                                                            0.3
Figure 1: Naor-Reingold PRF from CSIDH using 𝐸 0 as a start-
ing curve. We use 𝑘𝑖𝑥𝑖 as a shorthand notation for perform the




                                                                                                               time in s
group action with 𝑘𝑖 if and only if 𝑥𝑖 is set.
                                                                                                                            0.2

                      𝐹 𝑁 𝑅−𝐶𝑆𝐼 𝐷𝐻 −𝑂𝑃𝑇 ((k0, k1, . . . , kn, 𝐸 0 ), (𝑥 1, . . . , 𝑥𝑛 )) :=
                                               𝑛
                                                          !
                                             ∑︁
                                        k0 +      ki 𝑥 𝑖 ∗ 𝐸 0                                                              0.1
                                                    𝑖=1


Figure 2: Optimized two-step Naor-Reingold PRF from                                                                           0
CSIDH. The first step is a subset-sum of the required keys                                                                        0        50          100      150            200         250
and the second step is the application of the group action to                                                                                             updated bits
the base curve 𝐸 0 .
                                                                                                           Figure 4: Runtime divergence between updating 𝑥 bits of the
                                                                                                           PRF vs. recomputing the full 256 bits of the PRF.
                                ·105
                      1.5
                                         without optimization
                                          with optimization                                                                𝐹 𝑁 𝑅−𝐶𝑆𝐼 𝐹𝑖𝑆ℎ−𝑂𝑃𝑇 ((k0, k1, . . . , kn, 𝐸 0 ), (𝑥 1, . . . , 𝑥𝑛 )) :=
                                                                                                                                                         𝑛
                                                                                                                                                                             !
                                                                                                                                                       ∑︁
                                                                                                                                  reduce_mod (k0 +             ki ∗ 𝑥𝑖 ), 𝑐𝑛 ∗ 𝐸 0
    time in seconds




                        1
                                                                                                                                                              𝑖=1


                                                                                                           Figure 5: Optimized two-step Naor-Reingold PRF from
                                                                                                           CSIDH. The first step is a subset-sum of the required keys
                      0.5                                                                                  and the second step is the application of the group action to
                                                                                                           the base curve 𝐸 0 .




                                                                                                           of sampling a correct point is ℓ𝑖ℓ−1
                        0
                            0          100       200       300      400                   500                                                   𝑖
                                                                                                                                                  . Therefore, the optimization
                                               PRF input length in bits                                    is particularly of interest for an aggressive parameter choice in
                                                                                                           CSIDH.
Figure 3: Runtime divergence between the traditional Naor-                                                    Additionaly, this PRF is updatable; that is, if parts of the input
Reingold CSIDH PRF in blue and the same PRF with our                                                       change, updating the output requires a single group action to update
optimization in green for different bit lengths.                                                           the PRF. This is useful for applications requiring to hash multiple
                                                                                                           inputs, so the individual inputs differ in less than 𝑛2 bits. In Figure 4,
                                                                                                           we show that the effort between recomputing the OPRF and up-
   The subset-sum computation requires a tiny tweak in the CSIDH
                                                                                                           dating a previous result holds fairly clearly to our expectations: It
implementation1 , from 8-bit to 32-bit key elements to avoid over-
                                                                                                           is cheaper to update the OPRF when less than 128 bits differ and
flows. Other than adding addition and subtraction subroutines, the
                                                                                                           otherwise recomputation is more efficient. Note that the divergence
implementation is the same. In Figure 3, we benchmark the PRF
                                                                                                           in the runtime is due to non-uniform keys in CSIDH.
computation for input sizes between 1 and 512 bits. We see that
the two-step computation approach reduces the evaluation time.                                             3.1.1 Instantiation from CSI-FiSh. The PRF is even more efficient
This is due to two factors: one, the key coefficients are in the range                                     with CSI-FiSh, as the keys can be added and then reduced modulo
[−5, 5] and will partially cancel out when added, reducing the re-                                         the class group number as depicted in Figure 5 The reduction step
quired steps on the isogeny graph. Two, the optimization saves 𝑛 −1                                        leads to an almost constant-time computation. In Figure 6, we show
computations of the first step of the algorithm, which is computing                                        the improvement in runtime when using a reduction, leading to an
a point of the correct order. A smaller value of ℓ𝑖 corresponds to a                                       almost constant time complexity when computing the PRF, inde-
higher cost in computing a point of correct order, as the probability                                      pendent of the input. More concretely, the difference between the
1 All CSIDH benchmarks use the reference implementation from https://yx7.cc/code/                          lowest and the highest execution time is 0.0032s for the optimized
csidh/csidh-latest.tar.xz, which is from 27-06-2021.                                                       variant and 0.4377s for the aggregation variant.




                                                                                                     578
OPRFs from Isogenies: Designs and Analysis                                                                                ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore


                                                                                               aborts [Lyu09]. To translate the technique to the CSIDH setting,
                                    aggregation only                                           SeaSign uses somewhat short, long-term secret keys k with coeffi-
                      0.6       aggregation and reduction                                      cients 𝑘𝑖 ∈ [−𝐵, 𝐵]𝑘 for some 𝐵 and large, ephemeral secret keys
                                                                                               r with each coefficient 𝑟𝑖 ∈ [−(𝛿 + 1)𝐵, (𝛿 + 1)𝐵]𝑘 , rejecting any r
                                                                                               where the vector r − k contains a coefficient is outside of the range
    time in seconds




                                                                                               [−𝛿𝐵, 𝛿𝐵]. In the NR-OT setting, the long-term sender keys are the
                      0.4                                                                      short keys s and the ephemeral keys are sampled as r. While using
                                                                                               tactics from SeaSign is a good mitigation, it puts a computational
                                                                                               load on the server and introduces the drawbacks of lattice signa-
                                                                                               tures in the scheme. Additionally, the large ephemeral keys add
                      0.2                                                                      communication overhead to the protocol.
                                                                                                  Most of these issues are mitigated by using the sampling algo-
                                                                                               rithm from the signature scheme CSI-FiSh [BKV19] introduced
                                                                                               in Section 2.2. The protocol would largely remain the same, with
                       0                                                                       ki + ri being a reduced element of the class group.
                            0     100      200       300      400       500
                                         PRF input length in bits                              3.3.1 Trusted Setup in Oblivious Transfer. Another roadblock on
                                                                                               the way to a secure NR-OT instantiation is the underlying OT.
Figure 6: Comparing PRF runtimes using aggregation only                                        The estimations for the communication complexity of the NR-
and aggregation and a reduction modulo the class group                                         OT [BKW20] use an isogeny-based OT protocol [LGD21] that re-
number before applying the group action.                                                       quires a supersingular curve with an unknown endomorphism ring.
                                                                                               A recent paper [BCC+ 23] proposes an algorithm for the generation
                                                                                               of supersingular curves with unknown endomorphism over F𝑝 2 .
3.2                   Oblivious NR-PRF from CSIDH
                                                                                               However, there are no known efficient algorithms for the curves
The OPRF in [BKW20] is not rigorously described; they initially                                over F𝑝 used by CSIDH, which is denoted as an open problem in
give a description of the NR-PRF in Protocol 24 of the same paper.                             the same paper. Therefore, using the OPRF protocol requires either
In a later paragraph, they state instantiating their protocol with                             an efficient construction of curves with unknown endomorphism
CSIDH results in a NR-OPRF similar to the protocol in Section 2.3.                             over F𝑝 or a different OT protocol without a trusted setup.
Since the protocol uses OT, we will call it NR-OT henceforth. Using
our addition trick from Section 2.3, a correct intuition to compute                            3.3.2 Alternate OT protocols using CSIDH. The semi-honest proto-
the OPRF is to instantiate the OT with (ri, ki + ri ) and finalizing                           col of [dSGOPS20] gives similar performance to the OT protocol
                         Í
the OT by sending k0 ∗ 𝑛𝑖=1 −ri .                                                              of [LGD21], but requiring two trusted curves for the setup. A good
                                                                                               alternative may be the single-bit OT of [ADMP20], which requires
3.2.1 Analyzing the Construction. While the OPRF above produces
                                                                                               a key distribution closer to uniform than CSIDH and therefore
a correct result, due to the non-uniform representation of the CSIDH
                                                                                               uses the CSI-FiSh key sampling algorithm for the entire protocol.
private key, the construction leaks the server key. 2 A passive ad-
                                                                                               The main issue with this protocol is that the number of isogeny
versary, that is, an adversary who carries out the protocol faithfully,
                                                                                               computations depends on the length of the client input and the
can observe the distribution of the blinded keys.
                                                                                               bitlength of the input log2 𝑝 = 𝜎. The overall number of isogeny
3.2.2 Key Leakage Example. Consider the key coefficient 𝑘𝑖 = 𝑦,                                computations would be 𝛾 (5𝜎 + 5). For an input length of 128 bits
with 𝑦 ∈ [𝑚, −𝑚] (for a discussion on bounds, see Section 2.1).                                and a key size of 256 bits, this would amount to 164480 isogeny
When it is blinded with a random element 𝑟𝑖 , the blinded element                              computations, which is prohibitive.
𝑟𝑖 + 𝑘𝑖 is always within the range [𝑦 − 𝑚, 𝑦 + 𝑚], as the blinding co-                            Hence, to instantiate the protocol chose a two-round OT pro-
efficient is uniformly sampled within the same range 𝑟𝑖 ∈ [−𝑚, 𝑚].                             tocol based on additive homomorphic encryption [BDK+ 20], as it
Over several iterations, 𝑟𝑖 will change and reveal more and more in-                           provides an implementation and is round-optimal. In addition, the
formation about the key, giving the information outright when the                              protocol offers batching, making it more efficient for multiple OT
difference between the blinding results is 2𝑚. To obtain the correct                           invocations, and expects the input to be given as a GMP integer,
coefficient 𝑦, take the largest result 𝑙 and compute 𝑦 := 𝑙 − 𝑚.                               which is how CSI-FiSh encodes the private key. The protocol is
                                                                                               implemented in C++ using Microsoft SEAL [SEA21] for the ho-
3.3                   Fixing the NR-OPRF                                                       momorphic operations. Using the BFV [Bra12, FV12] scheme, it
Signature schemes using the Fiat-Shamir Transformation[FS87]                                   follows in three steps, with □ denoting homomorphic operations
require uniform keys as well. For CSIDH, the signature scheme                                  on encrypted messages.
SeaSign [DG19] mitigates the non-uniform mitigation by rejection                                  (1) The client encrypts their choice bit 𝑐𝑏 = Enc(𝑝𝑘, 𝑏) and
sampling, concretely using the Fiat-Shamir transformation with                                        sends it to the server.
2 In personal communication, authors of [BKW20] confirmed that the specific instan-               (2) The server computes 𝑐𝑚𝑏 = (𝑚 0  (1 ⊟ 𝑐𝑏 )) ⊞ (𝑚 1  𝑐𝑏 ) and
tiation of their construction using class groups (or isogenies) blinds the class group                sends 𝑐𝑚𝑏 to the client.
element representing the key by multiplying a random element, but that the non-                   (3) The client decrypts the ciphertext to obtain 𝑚𝑏 = Dec(𝑠𝑘, 𝑐𝑚𝑏 )
uniform key distribution leads to the CSIDH instantiation of protocol [BKW20] being
"currently broken".                                                                            Using the OT and CSI-FiSh, the full protocol is displayed in Figure 7.




                                                                                         579
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore                         Lena Heimberger, Tobias Hennerbichler, Fredrik Meisingseth, Sebastian Ramacher, and Christian Rechberger


 Server                                                                  Client
                                                                                                               Table 2: Comparison of OPUS complexity on the test machine.
 keys 𝐾 = k0 , . . . , kn                                                input 𝑋 = [𝑥 1 , . . . , 𝑥𝑛 ]         The overall time is the addition of the time from the client
 R ← [0]                                                                 K ← [0]                               and the server, as the protocol is sequential.
 for 𝑖 ∈ [1, 𝑛] :                                                        for 𝑖 ∈ [1, 𝑁 ] :
          $
      ri ←
         − keygen()
                                                                                                                   Bit-     Keygen    Comp.
      k i ri ← ri + k i                                                                                                                          Client      Server      Overall
      ki ri ← reduce_mod(ki ri )
                                                                                                                   length    PRF       PRF
      R ← R + ri                     ri                    𝑥𝑖                  K ← K + 𝑥𝑖 ∗ ki + ri                                               3.00s        5.73s      8.73s
                                    k i ri              𝑥 𝑖 ∗ k i + ri
                                                                                                                   128      0.11ms    168ms
                                             2                                                                                                 8.06 kiB    16.06 kiB   24.13 kiB
                                             1 -OT                                                                                                5.83s       11.30s     17.13s
                                                                                                                   256      0.26ms    234ms
                                                                         k ← reduce_mod(K)                                                      16.1 kiB     32.1 kiB   48.13 kiB
 𝐸 𝑓 𝑖𝑛 ← (k0 − R) ∗ 𝐸 0                     𝐸 𝑓 𝑖𝑛                      𝐸 ← k ∗ 𝐸 𝑓 𝑖𝑛
                                                                                                                                                 11.47s       22.42s     33.89s
                                                                                                                   512      0.51ms    326ms
                                                                                                                                               32.06 kiB    64.06 kiB   96.13 kiB
                                                                         return 𝐸


Figure 7: Full protocol of evaluating the NR-OPRF with CSI-
FiSh and 𝑁 OT calls. The function reduce_mod describes the
reduction modulo the class group number.                                                                       4     OPUS: OBLIVIOUS PSEUDORANDOM
                                                                                                                     FUNCTION USING CSIDH
                                                                                                               While the above construction is relatively efficient, it would be of
                                                                                                               interest to build a similar OPRF exclusively from a single type of
Table 1: Comparison between PRF and OPRF execution time
                                                                                                               problem, i.e., isogenies, without the need for hard lattice problems.
locally on the test machine for our NR-OT OPRF. The net-
                                                                                                               To avoid sending any private keys over the network, we propose
work traffic is always denoted as sent kilobytes. OT keygen
                                                                                                               OPUS, a novel OPRF that only sends evaluated curves, that is,
is a separate column for key generation measuring the client
                                                                                                               CSIDH public keys. In the protocol, both parties iteratively blind
communication and computation time.
                                                                                                               their intermediate results, with the client getting anything useful
                                                                                                               only in the end, beforehand computing over randomized curves.
   Input-           Keygen         Comp.                                                                       This eliminates the need for a trusted setup, which is the main
                                             Client    Server             OT keygen
   length            PRF            PRF                                                                        obstacle hampering other OPRF protocols from CSIDH. The main
                                              90ms      91ms                 429ms                             operations in OPUS are blinding and key addition. In each step, the
   128               204ms         43ms                                                                        client blinds a curve, starting with 𝐸 0 , with a random class group
                                             128 kiB   256 kiB               256 kiB
                                              97ms      97ms                 428ms                             element rc,i and sends it to the server, which returns the curve
   256               378ms         43ms                                                                        blinded again with its own, fresh blinding element 𝑟𝑠,𝑖 and once with
                                             256 kiB   512 kiB               256 kiB
                                             101ms     101ms                 427ms                             the own blinding element and the key. Now, the client decides based
   512               763ms         45ms                                                                        on the 𝑖 𝑡ℎ bit of the input with which curve the computation should
                                             384 kiB   768 kiB               256 kiB
                                                                                                               continue, blinding again to ensure the server learns nothing about
                                                                                                               their choice. By the hiding Lemma 1, this perfectly protects the
                                                                                                               client input and the server keys from malicious parties, see Figure 8.


3.3.3 Performance. Using the lattice-based OT, the NR-OT OPRF
becomes relatively efficient. This is due to two factors: first, the                                           4.1       Efficiency
added keys are reduced modulo the class number, which results in                                               Once again, the OPRF is made more efficient with the addition trick
a very fast PRF runtime, see Section 3.1.1. This results in a protocol                                         from Section 2.3, as both client and server aggregate the blinding
that only requires two group actions to complete. Second, while                                                keys in vector 𝑅 to quickly reduce the number of group actions.
the lattice OT requires a lot of communication, it is relatively fast.                                         Overall, OPUS needs 2𝑛 + 1 group action computations for the
                                                                                                               server and 𝑛 + 1 for the client. Experimental runtimes can be found
3.3.4 Conclusion. The construction repairs the issues from the                                                 in Table 2.
initial proposal [BKW20], namely by using an OT protocol that                                                     The low communication cost gives lower bandwidth require-
does not require a trusted setup and using the sampling approach                                               ments. This is also of benefit in cloud environments and when data
from CSI-FiSh for uniform keys. This introduces two new issues:                                                is transmitted over cellular networks. An additional advantange
First, the OT protocol allows the client’s choice bit to be neither                                            of OPUS is that the server carries the highest computational load,
0 nor 1, which may result in a response that is a superposition of                                             while the client only has to perform 𝑛 + 1 CSIDH computations.
messages. Hence, the security model is weaker, as a semi-honest                                                   Aside from the isogeny computations, the main performance
client would only be passively secure. Second, when using uniform                                              issue in OPUS is the large number of rounds. To address this con-
sampling, the class group structure is only available for primes of                                            cern, we rented virtual machines around the world and used them
length 512 [BKV19] or 1024 [DFK+ 23], which may not provide a                                                  as clients performing OPUS with a server in London. As clear
sufficient security margin as discussed in Section 2.1.3.                                                      from Figure 9, the runtime of OPUS directly corresponds to the




                                                                                                         580
OPRFs from Isogenies: Designs and Analysis                                                                                                                                            ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore




                                             Server                                                                                                            Client
                                                                            $
                                              {k0 , k1 , · · · , kn } ←
                                                                      − keygen()                                                                               input 𝑋 ← {𝑥 1 , · · · , 𝑥𝑛 },
                                             rs ← [0]                                                                                                          rc ← [0], 𝐸𝑐𝑙𝑖𝑒𝑛𝑡 ← 𝐸 0
                                             foreach i ∈ {1, . . . , 𝑛}:                                                                                       foreach i ∈ {1, . . . , 𝑛}:
                                                                                                                                                                               $
                                                                                                                                                                       rc,i ←
                                                                                                                                                                            − keygen()
                                                             $                                                       𝐸𝑏𝑙𝑖𝑛𝑑𝑒𝑑
                                                     rs,i ←
                                                          − keygen()                                                                                                   𝐸𝑏𝑙𝑖𝑛𝑑𝑒𝑑 ← rc,i ∗ 𝐸𝑐𝑙𝑖𝑒𝑛𝑡
                                                     𝐸𝑠,𝑖,0 ← rs,i ∗ 𝐸𝑏𝑙𝑖𝑛𝑑𝑒𝑑
                                                     𝐸𝑠,𝑖,1 ← ki ∗ 𝐸𝑠,𝑖,0

                                                     rs ← rs − rs,i                                                 𝐸𝑠,𝑖,0 , 𝐸𝑠,𝑖,1                                    𝐸𝑐𝑙𝑖𝑒𝑛𝑡 ← 𝐸𝑠,𝑖,𝑥𝑖

                                                                                                                                                                       rc ← rc − rc,i
                                              . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Finalize and Unblind . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
                                                                                                                  rc,0 ∗ 𝐸𝑐𝑙𝑖𝑒𝑛𝑡                               rc,0 ←
                                                                                                                                                                       $
                                                                                                                                                                    − keygen()

                                                                                                                           𝐸𝑠                                                     
                                             𝐸𝑠 ← (k0 + rs ) ∗ rc,0 ∗ 𝐸𝑐𝑙𝑖𝑒𝑛𝑡                                                                                  𝐸𝑐𝑙𝑖𝑒𝑛𝑡 ← rc − rc,0 ∗ 𝐸𝑠
                                                                                                                                                               return 𝐸𝑐𝑙𝑖𝑒𝑛𝑡

                                                                         Figure 8: The full protocol of our novel OPRF 𝑂𝑃𝑈 𝑆.


                                                                                                      Delhi                          This discloses the user’s identity when revealing the OPRF result.
                                                                                                                                     For example, the PrivacyPass protocol [DGS+ 18] hands out tokens
                                                                                                                                     to the user after they completed a CAPTCHA. These tokens can
                         300
                                                                                   Sydney                                            be redeemed instead of completing a new CAPTCHA. By using
  ping in milliseconds




                                                                                                                                     a different key for each challenge, the browser can distinguish
                                                                      Tokio                                                          tokens handed out for different challenges and track the user across
                                                                  Santiago                                                           websites.
                         200
                                                                                                                                         To mitigate this attack, some OPRFs are verifiable, which means
                                                    LosAngeles                                                                       the functionality ensures a server uses a certain key that it previ-
                                                                                                                                     ously committed to for the evaluation. Adding verifiability to OPUS
                         100              SouthCarolina                                                                              is difficult as the communication is entirely over randomized curves,
                                                                                                                                     similar to the challenges imposed by the requirements for malicious
                                          TelAviv
                                                                                                                                     security. Another OPRF based on isogenies over F𝑝 2 [Bas23] uses a
                                   Netherlands                                                                                       proof of parallel isogeny, which provides a zero-knowledge proof to
                                    London
                           0                                                                                                         show that two curves were computed by applying the same secret
                               0       10      20     30        40                               50               60                 key to two starting curves and torsion points. Unfortunately, this
                                            OPRF execution in seconds                                                                does not carry over to CSIDH’s F𝑝 and cannot be applied OPUS or
Figure 9: Online runtimes of clients in different cities com-                                                                        the NR-OT. A recent survey [BFGP23] details strategies and gives
puting OPUS with a bit length of 128 with a server in London.                                                                        an overview of zero-knowledge proofs for isogenies. While it seems
All machines run on Debian 11 using the simplest Google                                                                              possible, we leave the task of constructing a verifiable OPRF for
Cloud instance.                                                                                                                      future work.

                                                                                                                                      5       SECURITY ANALYSIS
round-trip time of the ping. In a real-life setting, this overhead may                                                                To prove our novel OPRF secure against a semi-honest adversary
be mitigated by running several, distributed instances of a server.                                                                   in the ROM, we will first show that the OPUS is a PRF. We now
                                                                                                                                      show that the protocol OPUS in Figure 8 generates output in corre-
4.2                      Verifiability                                                                                                spondence to the CSIDH NR-PRF 𝐹 𝑁 𝑅 from Section 2.3.
When the OPRF is used as a building block in a protocol, and the                                                                         Proposition 1 (OPUS produces correct NR-PRF outputs).
resulting OPRF output is utilized at a later stage, it is crucial to                                                                  For all keys k ∈ K and inputs x ∈ {0, 1}𝑛 , the output of an honest
safeguard user anonymity by preventing any link between the                                                                           computation of OPUS is an evaluation of the CSIDH-based 𝐹 𝑁 𝑅 . That
result and the OPRF evaluation. For instance, a malicious server                                                                      is P[𝐹𝑂𝑃𝑈 𝑆 (k, x) = 𝐹 𝑁 𝑅 (k, x)] = 1, with the probability being over
may tag an individual by using a distinct key for OPRF evaluation.                                                                    the internal randomness of OPUS.




                                                                                                                            581
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore                       Lena Heimberger, Tobias Hennerbichler, Fredrik Meisingseth, Sebastian Ramacher, and Christian Rechberger


   Experiment om-PRF:                                                                               This notion, as shown by Everspaugh et al., implies the weaker
                        $                                                                        one-more unpredictability security notion of OPRFs. Note though,
      • (𝑝𝑘, 𝑠𝑘) ←        − K, 𝑞, 𝑐 ← 0                                                          that in Figure 10, the PRF-Srv oracle is modelled as a single query.
      • (𝑖 1, . . . , 𝑖 ℓ , 𝑏 ′ ) ← A RoR,PRF-Srv                                                In our case, this algorithm takes part in a multi-round protocol,
      • If ℓ > 𝑞 or 𝑐 ≥ ℓ or ∃𝛼 ≠ 𝛽 : 𝑖𝛼 = 𝑖 𝛽 return 0.                                         whereas the output depends on client-provided random values
      • Return 𝛽 ′ =
                                Éℓ
                                   𝛼=1 𝑏𝑖𝛼                                                       which on their own depend on previous outputs of PRF-Srv. We
   RoR(𝑚):                                                                                       will however keep the notation for simplicity and assume that all
                                  $                $                                             the required information to produce a transcript is passed as part
         • 𝑞 ← 𝑞 + 1, 𝑏𝑞 ←
                         − {0, 1} 𝑍 0 ←
                                      − R, 𝑍 1 ← 𝐹𝑘 (𝑚)
                                                                                                 of 𝑚. We now show that OPUS is one-more pseudorandom based
         • Return 𝑍𝑏𝑞
                                                                                                 on the D-CSIDH assumption:
   PRF-Srv(𝑚):
                                                                                                   Theorem 1. If the D-CSIDH assumption holds, then OPUS is one-
      • 𝑐 ←𝑐 +1
                                                                                                 more pseudorandom.
      • Return PRF-Srv𝑘 (𝑚)
                                                                                                    Proof. The basic idea is to replace the use of the secret key 𝑘𝑖
Figure 10: Security game for one-more pseudorandomness.                                          step-by-step with randomly sampled curves.
                                                                                                     • Game 0: The initial game.
                                                                                                     • Game 𝑖: Everything is as before, but compute 𝐸𝑠,𝑖,1 by sam-
   Correctness of OPUS. Given input 𝑋 = (𝑥 1, . . . , 𝑥𝑛 ) and keys                                     pling uniformly at random from E.
𝐾 = (k0, . . . , kn ), the client C initializes 𝐸 ← 𝐸 0 . For each 𝑖 ∈ [1, 𝑛],                       • Transition 𝑖 − 1 to 𝑖: an adversary that can distinguish be-
C generates a random key rc,i and sends a randomized curve rc,i ∗ 𝐸                                     tween game 𝑖 − 1 and 𝑖, can also solve D-CSIDH. Indeed, let
to the server S, which samples their randomness rs,i and returns                                        (𝐸, 𝐻, 𝐸 ′, 𝐻 ′ ) be from a D-CSIDH challenger. We set 𝐸𝑠,𝑖,0 ←
𝐸𝑖,0 ← rs,i ∗ 𝐸 and 𝐸𝑖,1 ← ki ∗ rs,i ∗ 𝐸 to C. If 𝑥𝑖 = 1, C sets 𝐸 ← 𝐸𝑖,0                               𝐻 and 𝐸𝑠,𝑖,1 ← 𝐻 ′ which interpolates between the two
and 𝐸 ← 𝐸𝑖,1 otherwise. Clearly, repeating this step 𝑛 times is                                         games.3
equivalent to computing                                                                          In Game 𝑛, the adversary can only guess as none of the 𝑘 1, . . . 𝑘𝑛
                Í𝑛                Í𝑛               Í𝑛           𝑥𝑖  ∗ 𝐸  .
                   𝑖=1 rs,i +         𝑖=1 rc,i +       𝑖=1 ki           0                        are used in the protocol execution.                                  □

The computation is finalized by C blinding the result again with                                    Proofing the security of OPUS in the universal composability
the term rc,0 and sending it to the server, which applies k0 as well                             model and in an adaptive setting, is currently open and future
as the sum of the inverse blinding terms rs such that                                            work. To achieve adaptve security, it would be required at least to
              Í                       Í           Í           Í                                produce the output of OPUS via a random oracle, i.e., by outputting
         (k0 − 𝑛𝑖=1 rs,i ) ∗    rc,0 + 𝑛𝑖=1 rs,i + 𝑛𝑖=1 rc,i + 𝑛𝑖=1 ki 𝑥𝑖 ∗ 𝐸 0 ,
                                                                                                 𝐻 (𝑚, 𝐸𝑐𝑙𝑖𝑒𝑛𝑡 ), as observed by Jarecki et al. [JKX18].
which is equivalent to
                     Í𝑛                       Í𝑛          𝑥𝑖  ∗ 𝐸 .                             6    CASE STUDY: OPAQUE
                        𝑖=0 rc,i + k0 +          𝑖=1 ki           0
                                                                                                 The OPAQUE [JKX18] protocol introduces a Password-Authenticated
The client is left to compute the inverse of their respective blinding                           Key Exchange (PAKE) protocol that does not reveal the user’s pass-
elements such that                                                                               word to the server. Instead, it performs an OPRF calculation with
         Í𝑛                       Í𝑛                     Í𝑛          𝑥𝑖  ∗ 𝐸 ,                  the server, using the hash of the password as the user’s input and a
            𝑖=0 −(rc,i ) ∗            𝑖=0 rc,i + 𝑘 0 +      𝑖=1 ki           0
                                                                                                 PRF key provided by the server. Hence, offline dictionary attacks
which is equivalent to computing                                                                 effectively require compromise of the server’s PRF key and are oth-
                                    Í                                                            erwise rendered impossible. OPAQUE is unable to prevent online
                               (k0 + 𝑖=1 ki 𝑥𝑖 ) ∗ 𝐸 0 .
                                                                                                 attacks, yet they incur additional costs for the attacker as they have
Therefore, OPUS correctly evaluates the NR-PRF for honest parties.                               to perform the client’s side of the OPRF evaluation. To make online
                                                                □                                attacks even more costly, additional client hardening steps (e.g.,
                                                                                                 memory hard functions) can be employed as discussed in [JKX18].
  Consequently, we obtain the following corollary from [BKW20,                                      OPAQUE consists of two phases: Password Registration and
Theorem 23]:                                                                                     Password Authentication with Key Generation. Authentication and
   Corollary 1. Assuming computational CSIDH (cf. Problem 2)                                     key generation are accomplished by either combining the OPRF
holds, then OPUS is a secure pseudorandom function.                                              with an asymmetric PAKE (aPAKE) or an Authenticated Key Ex-
                                                                                                 change (AKE) protocol. In our implementation, we focus on the
  For the security proof, we consider the one-more pseudoran-                                    composition using the AKE protocol, since no CSIDH-based aPAKE
domess security game of Everspaugh et al. [ECS+ 15] in the fully                                 protocols are available. During registration, both parties generate a
oblivious setting.                                                                               long-term asymmetric keypair, later used during authentication to
Definition 3. A OPRF 𝐹𝑘 : M → R provides one-more pseu-                                          perform the AKE protocol. Using the output of the OPRF, the client
dorandomess if for any PPT adversory A the advantage in the                                      derives a symmetric key and uses it to encrypt its private key. For
one-more pesudorandomness experiment defined in Figure 10,                                       3We could set 𝐸             ′
                                                                                                                0 ← 𝐸 and 𝐸 would represent the public key of the server. As we do
| Pr[om-PRF = 1] − 12 | is negligible.                                                           not have a public key, though, this step is not required.




                                                                                           582
OPRFs from Isogenies: Designs and Analysis                                                                                                                             ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore


 Client                                                      Server                                                 Client                                                                     Server
                                                                                $                                   username, password
 username, password                                          {k0 , . . . , k256 } ←
                                                                                  − keygen()
                                                                                                                                username                                                       Retrieve User Record for given username
              username
                                                                                                                                                      Hash(password)                     k
                                 Hash(password)          k                                                                                                                       OPUS
                                                  OPUS
                                                                                                                                                           out
                                        out                                                                                                                                                                     c, n
                                                                                                                    y ← Hash(password| |out)
 y ← Hash(password| |out)
 rw ← HkdfExtract(y| |PWHash(y) )                                                                                   rw ← HkdfExtract(y| |PWHash(y) )
                                                                                                                    (ekT , dkT ) ← KEM.KeyGen()
 (ekC , dkC ) ← KEM.KeyGen()                                 (ekS , dkS ) ← KEM.KeyGen()
                                                                                                                    (IpkC | |IpkS | |IskC ) ← AuthDecrw (c, n)
 (vkC , skC ) ← SIG.KeyGen()                                 (vkS , skS ) ← SIG.KeyGen()
                                                                                                                                                                                                                                !
 IpkC ← (ekC , vkC )                                         IpkS ← (ekS , vkS )                                    𝜎C ← SIG.SignskC (ekT )                                                    SIG.VerifyvkC (ekT , 𝜎C ) = 1

 IskC ← (dkC , skC )                                         IskS ← (dkS , skS )                                                  ekT , 𝜎C                                                     (K, C, 𝜏 ) ← KEM.EncapekC ()
                                                                               IpkS                                                                                                            (KT , CT , 𝜏T ) ← KEM.EncapekT ()
                                                                                                                    K ← KEM.DecapdkC (C, 𝜏 )                                                   K1 ← Exts (K); K2 ← Exts (KT )
   $         256                                                $        256
 n←
  − {0, 1}                                                   s←
                                                              − {0, 1}                                              KT ← KEM.DecapdkT (CT , 𝜏T )                                               sid ← username| |hostname| |IpkC | |IpkS | |ekT | |C| |CT
 c ← AuthEncrw (IpkC | |IpkS | |IskC , n)                                                                           K1 ← Exts (K); K2 ← Exts (KT )                                             kS | |k ← FK1 (sid) ⊕ FK2 (sid)
                                                                                                                    sid ← username| |hostname| |IpkC | |IpkS | |ekT | |C| |CT                  𝜎 ← SIG.SignskS (sid)
              c, n, IpkC                                     User Record: IpkS | |IskS | |IpkC | |c| |n| |s| |k     kC | |k ← FK1 (sid) ⊕ FK2 (sid)                                            b←𝜎 ⊕k
                                                             Store User Record for given username                   𝜎 ←b⊕k                                                                               C, CT , 𝜏, 𝜏T , b, s

                                                                                                                                             !
                                                                                                                    SIG.VerifyvkS (sid, 𝜎 ) = 1
Figure 11: Description of PQ OPAQUE Password Registration
                                                                                                                    Output kC as shared secret key                                             Output kS as shared secret key



                                                                                                                   Figure 12: Description of PQ OPAQUE Password Authentica-
                                                                                                                   tion and Key Generation

                                                                                                                   Table 3: Comparison between the execution time of li-
simplicity, our implementation includes the client and server public                                               bopaque and our two OPAQUE instantiations. The execution
key in the encryption process. The ciphertext is sent and stored on                                                time is averaged over 100 runs. Reg. refers to the registration
the server. During authentication the server fetches the ciphertext                                                and Auth. to the authentication phase of the protocol.
and sends it to the client, where it is decrypted after performing the
OPRF again, requiring the user to only remember their password,
                                                                                                                    Function                       libopaque                       PQ                             PQ / libopaque
but not the long-term keypair, to authenticate. A shared key is then
                                                                                                                                                                                OPUS NR-OT                      OPUS       NR-OT
generated by performing the AKE protocol.
                                                                                                                    Reg. Client                    119.37ms                     39.82s       11.59s             × 333.62             × 97.10
                                                                                                                    Reg. Server                    95.63ms                      39.84s       11.61s             × 416.62             × 121.42
6.1        Post-Quantum OPAQUE Implementation                                                                       Auth. Client                   96.54ms                      31.21s       3.25s              × 323.27             × 33.69
Constructing a post-quantum version of the OPAQUE protocol re-                                                      Auth. Server                   120.32ms                     32.01s       2.74s              × 268.15             × 22.80
quires the replacement of the used OPRF and AKE protocols with
suitable post-quantum variants. We instantiate two PQ versions,
one using our novel OPRF OPUS and the other one using our NR-                                                      6.2 Comparison to Pre-Quantum
OT OPRF. Both versions use a post-quantum secure replacement                                                           implementation
of the X3DH protocol, proposed by Hashimoto et al [HKKP21], as                                                     To measure the performance difference, we compare our implemen-
the AKE. We chose this AKE since it provides security against Key                                                  tation to libopaque,4 an open-source, pre-quantum implementa-
Compromise Impersonation (KCI) attacks and forward secrecy, as                                                     tion of OPAQUE. The average execution time for the client and
required by the OPAQUE protocol, and is suitable for implementa-                                                   the server is shown in Table 3, while the communication cost is
tion using CSIDH-based primitives. The protocol is based on a Key                                                  shown in Table 4. Our implementation is the first PQ-secure in-
Encapsulation Mechanism (KEM) scheme and a signature scheme.                                                       stantiation of the OPAQUE protocol. While it leads to a increase
We chose the CSIDH-based CSIKE [Qi22] as the KEM, since it is                                                      in execution time and communication cost, this concretizes the
IND-CCA secure as required by the used AKE. As the signature                                                       overhead of switching to post-quantum cryptography for advanced
scheme, we chose CSI-FiSh [BKV19], as there already is an im-                                                      protocols.
plementation available. The full protocol flow for the OPAQUE
Password Registration and Password Authentication is detailed in                                                   7      CASE STUDY: PRIVATE SET INTERSECTION
Figure 11 and Figure 12 respectively. Exts and FK are PRF using                                                    In a private set intersection (PSI), two or more parties, commonly
KMAC256 instead of HMAC256, since we require variable length                                                       a server and a client, hold data sets 𝑆 and 𝐶. After performing the
output. The PRF uses s and K as the respective keys, with different                                                PSI protocol, one or both parties learn 𝑆 ∩ 𝐶 without revealing
labels to differentiate between Exts and FK .                                                                      anything about the other parties set. In the client-server case, the
   Note that the security of PAKE is defined in the UC setting and                                                 sets are very often unbalanced, as the server set is much larger
OPAQUE is proven secure for UC-secure OPRFs. As this is left open                                                  than the client set |𝑆 | ≫ |𝐶 |. A well-studied application of PSI is
as future work for OPUS, we consider the evaluation of OPUS with
in an OPAQUE as an outlook for future applications of OPUS.                                                        4 https://github.com/stef/libopaque




                                                                                                             583
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore          Lena Heimberger, Tobias Hennerbichler, Fredrik Meisingseth, Sebastian Ramacher, and Christian Rechberger


Table 4: Comparison between the communication overhead                              Table 5: PSI comparison using ECNR, NR-OT, and OPUS as
of libopaque and our PQ OPAQUE instantiations                                       the OPRF for set intersection. The ECNR column combines
                                                                                    base and online for better comparability.
 Function            libopaque         PQ                 PQ / libopaque
                                    OPUS NR-OT          OPUS      NR-OT                        parameters            setup                       online
                                                                                               |𝑆 | |𝐶 |    |𝑆 |          |𝐶 |         |𝑆 |           |𝐶 |
 Reg. Client         224B           64kiB      817kiB   × 294.4   × 3733
                                                        × 770     × 2307.4                                  0.26s          0.51s       0.06s           0.10s
 Reg. Server         64B            48kiB      144kiB                                          20    20
 Auth. Client        160B           17kiB      769kiB   × 106.1   × 4920.2                                  134 bytes      1 byte      128 kiB         0.75MiB




                                                                                       NR-OT
                                                        × 208.2   × 515.7                                   1.63s          1.88s       3.11s           3.15s
 Auth. Server        320B           65kiB      161kiB                                          25    25
                                                                                                            263 bytes      1 byte      4MiB            8.5 MiB
                                                                                                            45.04s         45.28s      99.66s          99.71s
                                                                                               210   210
Private Contact Discovery, where clients want to know which of                                              4.31 MiB       1 byte      128 MiB         256.6 MiB
their contacts also use the same service [KRS+ 19].                                                         0.26s          0.26s       15.47s          15.91s
   To perform PSI using OPRFs, the holder of the larger set com-                               20    20
                                                                                                            133 bytes      0 bytes     17.07 kiB       9.04 kiB




                                                                                       OPUS
putes the PRF for each set entry and, optionally, inserts the results                                       8.71s          8.71s       328.46s         329.14s
in an efficient data structure, e.g. a cuckoo filter. Then, the OPRF is                        25    25
                                                                                                            262 bytes      0 bytes     546.25 kiB      290.26 kiB
computed in the online phase. The client uses their set entries as                                          303.38s        303.38s     16367.12s       16367.60s
input and the server oblivious evaluates them with the same key                                210   210
                                                                                                            4.31 kiB       0 bytes     34.14 MiB       18.08 MiB
as in the keyed PRF and checks whether the result is in the filter.
                                                                                                            0.01s          0s          0.23s           0.05s
   Performing PSI without a verifiable OPRF may lead to a tag-                                 20    20
                                                                                                            133 bytes      0 bytes     12.04 kiB       16 bytes
ging attack where a malicious server uses different keys for each
                                                                                       ECNR
                                                                                                            0.02s          0s          0.21s           0.06s
client when performing the OPRF, leading to the identification                                 25    25
                                                                                                            262 bytes      0 bytes     137.05 kiB      512 bytes
of the results later (see also Section 4.2). This is why previous
                                                                                                            0.3s           0s          0.64s           0.57s
work by [KRS+ 19] relaxes the security assumption and assumes                                  210   210
                                                                                                            4.36 kiB       0 bytes     4.04 MiB        16 kiB
a malicious client and a semi-honest server. They also postulate
three goals for unbalanced PSI: The server should perform the
computationally most expensive tasks, all expensive tasks are only
performed once and updates are fast. We now instantiate their PSI
framework with both isogeny-based OPRFs and compare it to our
implementation. Of independent interest, we propose a small opti-                   conditional on updating the bit length of both the hash function
mization for the setup of the elliptic curve Naor-Reingold(ECNR)                    and the base OT length, but unfortunately do not integrate the
PSI protocol in the full version using precomputation tricks. The                   extensions in their implementation.
results can be found in Table 5.                                                       To perform PSI with OPUS, we use parallel execution to amortize
                                                                                    the round cost. Observe that the protocol is relatively stateless, as
7.1     PSI with ECNR                                                               a curve is either awaiting evaluation or in transit. More concretely,
The ECNR-PSI protocol is divided into three phases: First setup                     on a client side, the client either awaits a server result or performs
phase, where a Cuckoo filter is filled with the PRF results of server               a blinding/unblinding evaluation. This can be parallelized by at-
set entries and sent to the client. Then, a base phase, where some                  taching an ID to the curve to note the element that is evaluated.
initial, data-independent Oblivious Transfer is performed. Using                    Since we assume that the server is semi-honest, the client can trust
cheap symmetric cryptography, the parties generate many more OT                     the server that the ID is correct. In Figure 13, the ID is denoted
pairs from this base OT using a technique called OT Extension. Then,                as 𝑖. To keep track of the current index, we attach a state variable
in the online phase, the OPRF is performed using the extended OT                    𝑗. Then, the only state kept on the client about an element is the
pairs. This is currently the most efficient PSI protocol. [KRS+ 19]                 corresponding unblinding key.

7.2     PSI with NR-OT                                                              7.3        PSI with OPUS
The implementation with the NR-OT is relatively close to the ECNR                   The server pregenerates all blinding keys and computes the un-
files. The setup phase is identical other than replacing the com-                   blinding element at the time an element is first seen. This simplifies
munication interface with the one provided by the PQ-OT imple-                      the implementation and also ensures that no intermediate values
mentation. Since the PQ-OT implementation does not provide an                       are leaked when the client decides to finish the computation prema-
implementation for OT extensions, we skip the base phase and                        turely by setting 𝑗 = 𝑛. Using the stateless approach, we forego the
only implement an online phase. In the online phase, the OPRF is                    limitation imposed by the required rounds in the protocols, as we
performed with all client elements.                                                 simply evaluate other set elements while an element is in transit.
    The communication overhead may be lower when using OT                              In our measurements, the client seems to perform badly in the
extensions, which uses symmetric cryptography to generate more                      setup phase. This is a measurement artifact as most of the time is
OT pairs from a few base OT queries. [BDK+ 20] show that the                        spent waiting for the cuckoo filter from the server due to the choice
IKNP protocol [IKNP03] is secure against quantum adversaries                        of network connection.




                                                                              584
OPRFs from Isogenies: Designs and Analysis                                                                                                                                                                                             ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore


                                                                                                                                                                                                            7.4    Result and Overhead
 Server
                                 $
                                                                                                                                    Client
                                                                                                                                                                                                            We compare against the EC-NR implementation of [KRS+ 19] as it is
 {k0 , k1 , · · · , kn } ←
                         − keygen()
                                                                                                                                                                                                            the most performant implementation of OPRFs for set intersection.
 𝑙 inputs {𝑆 1 , · · · , 𝑆𝑙 }                                                                                                       𝑚 inputs {𝐶 1 , · · · , 𝐶𝑚 }
 𝐶𝐹 = cuckoofilter()
                                                                                                                                                                                                               While we were able to remedy the round cost of OPUS, the high
 foreach i ∈ {1, . . . , 𝑙 }:                                                                                                                                                                               number of group action computations still make the protocol less
    CF.insert(PRF(𝑋𝑙 ) )                                                                     CF                                     𝐸𝑐𝑙𝑖𝑒𝑛𝑡 = [ ]                                                           efficient than the NR-OT protocol. However, OPUS requires less
 foreach i ∈ {1, . . . , 𝑚}:                                                                                                        foreach i ∈ {1, . . . , 𝑚}:                                             than 14× the bandwidth of the NR-OT protocol, making it more
    rs,i ← [0]                                                                                                                           rc,i ← [0], 𝐸𝑐𝑙𝑖𝑒𝑛𝑡,𝑖 ← 𝐸 0                                        attractive for use-cases where bandwidth criteria are of concern.
    foreach j ∈ {1, . . . , 𝑛}:                                                                                                          foreach j ∈ {1, . . . , 𝑛}:
                                                                                                                                                       $
                                                                                                                                                                                                               We point out that recent work [HSW23] optimizes the PSI pro-
                                                                                                                                             rc,i,j ←
                                                                                                                                                    − keygen()
                                                                                                                                                                                                            tocol with sublinear communication size of the server’s client data-
         rs,i,j ←
                  $
                − keygen()                                                         (𝐸𝑏𝑙𝑖𝑛𝑑𝑒𝑑 , 𝑖, 𝑗 )                                        𝐸𝑏𝑙𝑖𝑛𝑑𝑒𝑑 ← rc,i,j ∗ 𝐸𝑐𝑙𝑖𝑒𝑛𝑡
                                                                                                                                                                                                            base, which may make the ECNR protocol more efficient.
         𝐸𝑠,𝑖,0 ← rs,i,j ∗ 𝐸𝑏𝑙𝑖𝑛𝑑𝑒𝑑
         𝐸𝑠,𝑖,1 ← ki ∗ 𝐸𝑠,𝑖,0

         rs,i ← rs,i − rs,i,j                                                    (𝐸𝑠,𝑖,0 , 𝐸𝑠,𝑖,1 , 𝑖, 𝑗 )                                   𝐸𝑐𝑙𝑖𝑒𝑛𝑡,𝑖 ← 𝐸𝑠,𝑖,𝑐𝑖,𝑗

                                                                                                                                             rc,i ← rc,i − rc,i,j
 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Finalize . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   8     RELATED WORK
                                                                                                                                                                                                            OPUS and the generic NR-OPRF from isogenies are only two of
                                                                            (rc,i,0 ∗ 𝐸𝑐𝑙𝑖𝑒𝑛𝑡,𝑖 , 𝑖, 𝑚)                                  rc,i,0 ←
                                                                                                                                                   $
                                                                                                                                                − keygen()
                                                                                                                                                                                                            several recent proposals. In Table 6 we provide a comparison of
    𝐸𝑠,𝑖 ← (k0 + rs ) ∗ rc,i,0 ∗ 𝐸𝑐𝑙𝑖𝑒𝑛𝑡,𝑖                                             (𝐸𝑠,𝑖 , 𝑖, 𝑗 )                                                                  
                                                                                                                                         𝐸𝑐𝑙𝑖𝑒𝑛𝑡 .append( rc,i − rc,i,0 ∗ 𝐸𝑠,𝑖 )                            these proposals which we discuss in more detail below. Note that
                                                                                                                                    return 𝐶𝐹 .contains(𝐸𝑐𝑙𝑖𝑒𝑛𝑡 )                                           the estimates for the communication complexity may change dras-
                                                                                                                                                                                                            tically as the concrete security of CSIDH remains an open research
Figure 13: Amortizing the round cost of OPUS by reducing                                                                                                                                                    question (cf. Section 2.1.3).
the state and adding labels.                                                                                                                                                                                    The CSIDH proposals of this paper only cover Naor-Reingold
                                                                                                                                                                                                            style OPRFs. SIDH, which also uses isogenies but operates over
                                                                                                                                                                                                            F𝑝 2 , uses isogenies of degree two and three and is not commutative,
                                                                                                                                                                                                            enables the construction of a Diffie-Hellman style OPRF [Bas23,
                                                                                                                                                                                                            BKW20]. The resulting OPRF is round-optimal and gives rise to
                                                                                                                                                                                                            a verifiable construction, which the Naor-Reingold Constructions
7.3.1 Updatable OPRF. For very large sets, the probability that                                                                                                                                             (including ours) do not offer, but requires a 9000 bit prime due to the
several elements are quite similar is relatively high. It would be                                                                                                                                          SIDH attack mitigations [FMP23]. A drawback of the SIDH-based
thus be beneficial to take an existing evaluation and update the                                                                                                                                            construction is that an epensive trusted setup is necessary [BCC+ 23].
value where the bits differ. This could yield a runtime improvement:                                                                                                                                            On the lattice side, an initial proposal for round-optimal, ver-
consider two inputs 𝑋 1, 𝑋 2 and the evaluation 𝑌1 = OPUS(𝑋 1 ), with                                                                                                                                       ifiable OPRFs [ADDS21] has a very large overhead imposed by
𝑋 1 ⊕ 𝑋 2 having a low Hamming weight. A potential improvement                                                                                                                                              heavy zero-knowledge proofs. A proof-of-concept implementation
could come from an updatable form of OPUS, where 𝑌1 is updated                                                                                                                                              is available in Sage and takes around one second for an offline
at the indices. For example, imagine 𝑋 1 and 𝑋 2 only differ at the                                                                                                                                         computation, being around nine times faster than OPUS. However,
first bit, which is set in 𝑋 2 but not 𝑋 1 , and the third bit, which is                                                                                                                                    the implementation is not necessarily complete, as it omits proofs
not set in 𝑋 2 but is set in 𝑋 1 . Then, OPUS(𝑋 2 ) can be computed as                                                                                                                                      and samples from a uniform instead of a Gaussian distribution.
OPUS(𝑋 1 ) = 𝑘 1 ∗ 𝑘 3−1 ∗ OPUS(𝑋 2 ). This results directly from the                                                                                                                                           A recent lattice OPRF [ADDG23] improves the communication
commutativity of CSIDH.                                                                                                                                                                                     cost in a malicious setting. The provided implementation in Rust
   The simple realization of this functionality has the client reveal                                                                                                                                       does not include the non-interactive zero-knowledge proofs needed
the indices where two inputs 𝑋 1, 𝑋 2 differ. The parties then engage                                                                                                                                       for a malicious client security and therefore is only semi-honest,
in a reduced execution of OPUS, where the server responds with                                                                                                                                              while the communication estimates in Table 6 include proofs from
(r ∗ ki −1 ∗ 𝐸, ki ∗ r ∗ 𝐸) for the given indices 𝑖. The client iteratively                                                                                                                                 a malicious client. Comparing the runtime of OPUS to [ADDG23]
updates the PRF by selecting the correct output. Note that the                                                                                                                                              is a bit more nuanced. While the former needs ≈ 15s for the key
finalization step is still necessary for the unblinding to ensure that                                                                                                                                      generation, the NR-OT OPRF is vastly faster, as it only requires
no intermediate results are leaked, but without adding k0 .                                                                                                                                                 0.14ms for the same operation. The communication complexity of
   While this produces another PRF result, the simple protocol                                                                                                                                              the lattice OPRF is also largely dominated by the key generation,
violates the OPRF security guarantee of the server learning nothing                                                                                                                                         which accounts for 108.5 MB of the communication cost. For the
about the client input, since the server knows the index where                                                                                                                                              actual OPRF, only 36 kB of communication are necessary, which is
two evaluations differ. An extended version sends some dummy                                                                                                                                                slightly more than OPUS. A big advantage of the construction is the
indices as well and requires the server to respond with (r ∗ k −1 ∗                                                                                                                                         lower round complexity. The current impelmentation gives around
𝐸, r ∗ 𝐸, k ∗ r ∗ 𝐸), with r ∗ 𝐸 being used if the index was a dummy                                                                                                                                        14.4s of execution time, making the NR-OPRF with a CSIDH security
index. This approach would reduce the latency introduced by the                                                                                                                                             parameter 𝑝 = 512 vastly faster. However, the authors describe an
rounds and the group actions, but requires either very similar inputs                                                                                                                                       optimization that could lead to both OPRFs matching in speed.
or extensive preprocessing by the client to ensure the results are                                                                                                                                              Dinur et al. [DGH+ 21] propose a very efficient, semi-honest
updated ideally.                                                                                                                                                                                            OPRF using preprocessing and dedicated symmetric primitives.




                                                                                                                                                                                                      585
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore     Lena Heimberger, Tobias Hennerbichler, Fredrik Meisingseth, Sebastian Ramacher, and Christian Rechberger


Table 6: Comparison with all other post-quantum OPRF proposals. DM denotes the dark matter PRF [BIP+ 18, CCKK21]. The
instances aim at a security level of roughly 128 bits and use log2 𝑝 = 512 for the isogeny protocols.


                                                                comm.        model         no        no trusted      full impl.
     work                      assumption            rounds      cost        (C-S)      preproc.       setup         available     verifiable
 [ADDS21]                      R(LWE)+SIS              2          2MB           -          ✓              ✓              ✓             p
 [ADDS21]                      R(LWE)+SIS              2       > 128GB          -          ✓              ✓              p             ✓
  [SHB23]                      multivariate            3       𝛾 · 13 kB        -          p              ✓              p             ✓
 [DGH+ 21]                         DM                  2         308 B          -          p              p              p             p
 [ADDG23]                      DM+lattices             2        16.9MB          -          ✓              ✓              ✓             ✓
   [Bas23]                    Isogenies F𝑝 2           2         3.0MB          -          ✓              p              p             p
   [Bas23]                    Isogenies F𝑝 2           2         8.7MB          -          ✓              p              p             ✓
    NR-OT              Isogenies F𝑝 + lattices         2       20.54 kB         -          ✓              p              p              p
    NR-OT              Isogenies F𝑝 + lattices         4       34.88 kB         -          ✓              p              p              p
    NR-OT         Isogenies F𝑝 + lattices + HE OT      2        640 kB          -          ✓              ✓              ✓              p
    OPUS                      CSIDH                   258      24.7 kB          -          ✓              ✓              ✓              p



They also require a trusted third party to generate correlated ran-               Of independent interest, we also discuss the Naor-Reingold PRF
domness. The implementation is unfortunately not publicly avail-               in CSIDH further and give a concrete strategy that gives rise to
able. A different path is taken by Seres et al.[SHB23], who use their          optimizations in all of our protocols and also enables somewhat fast
result that key-recovery of the Legendre PRF is equivalent to solv-            offline computation of both our novel OPRF and the Naor-Reingold
ing sparse multivariate equations over a prime field to construct              OPRF. All the code to obtain our benchmarks and the CSV files
an OPRF. It requires a preprocessing step to distribute correlated             for the figures are available with the submission and will be made
randomness amongst the participants of the protocol.                           public with the publication of this paper.
                                                                                  To show the real-world impact of our protocols, we benchmarked
                                                                               the OPRFs for two use-cases: first, asymmetric password authen-
                                                                               tication using OPAQUE, where we report an overhead of around
9    CONCLUSION
                                                                               35× for authentication and 123× for registration. Second, we im-
In this paper, we have shown that the computational complexity of              plement private set intersection with the OPRFs. To the best of our
Naor-Reingold OPRFs can be significantly reduced by using prop-                knowledge, these are the first implementations of a post-quantum
erties of the CSIDH group action. We introduced OPUS, an OPRF                  version of OPAQUE and PSI using isogenies.
that gains its hardness directly from the underlying CSIDH group
action. The new construction explores the generic construction of
Naor-Reingold protocols, which traditionally use oblivious trans-                 Future Work. While our results are immediately useful for a
fer to send blinded private keys. In comparison to previous work,              variety of protocols requiring OPRFs, the slow group action is
OPUS has three strong advantages: First, it can be used stand-alone            still hindering large-scale deployment. Based on our findings, we
without requiring any trusted setup. The only hardness assumption              envision future studies for the applicability of OPUS and the NR-OT
is CSIDH which improves over previous propsals [BKW20]. Second,                OPRF, especially in settings with low bandwidth.
the simple structure also makes it straightforward to extend to a                 The recent call for threshold cryptography by NIST [BDV20]
threshold and distributed OPRFs. Third, OPUS requires 40% fewer                opens a new avenue for post-quantum threshold schemes which
isogeny computations than the best previous CSIDH-based OPRF                   distribute the secret key amongst several servers but only requires
proposals. When using no preprocessing, no trusted setup, and a                that 𝑡 out of 𝑛 honest servers are required to produce an OPRF
semi-honest client and server, OPUS requires 83× less communi-                 result. For CSIDH, a recent paper [DM20] demonstrates threshold
cation than the next-best approach which uses LWR. The main                    key sharing. Their results should be directly applicable to OPUS
drawback of our construction is the large number of rounds, which              and the NR-OT to obtain a threshold OPRF.
can be amortized over several executions.                                         On the implementation side, we point out that the current imple-
   We also revisited the previous proposal CSIDH-based OPRF from               mentations are neither optimized nor side-channel free, and that the
Boneh et al. [BKW20] and showed that the implementation is more                code is not audited. We expect a side-channel free implementation
complex than described in the original paper: A straightforward                to be relatively easy for OPUS, as it only requires side-channel free
implementation leaks the entire server key after a few evaluations.            key addition and group actions, as well as the conditional assign-
To secure the construction, it is necessary to use CSI-FiSh, which             ment of 𝐸𝑐𝑙𝑖𝑒𝑛𝑡 . On a theoretical side, elliptic curves with trusted
introduces several new hardness assumptions, concretely lattice                setup over F𝑝 would greatly add to the current research, as it eases
assumptions for either rejection sampling or reducing the private              concretizing the overhead of the OT for the NR-OT proposal over
key, and also also adds additional overhead.                                   OPUS using only isogenies.




                                                                         586
OPRFs from Isogenies: Designs and Analysis                                                                                       ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore


ACKNOWLEDGMENTS                                                                                    [BKW20] Dan Boneh, Dmitry Kogan, and Katharine Woo. Oblivious pseudoran-
                                                                                                              dom functions from isogenies. In Shiho Moriai and Huaxiong Wang,
We wholeheartedly thank Carsten Baum for many helpful discus-                                                 editors, ASIACRYPT 2020, Part II, volume 12492 of LNCS, pages 520–550.
sions concerning OPUS and OPRFs. In addition, we are gracious of                                              Springer, Heidelberg, December 2020.
                                                                                                  [BLMP19] Daniel J. Bernstein, Tanja Lange, Chloe Martindale, and Lorenz Panny.
the very helpful feedback of the reviewers of PKC2022 and CCS2023                                             Quantum circuits for the CSIDH: Optimizing quantum evaluation of
on an earlier draft of this work. Furthermore, we thank Serge Bazan-                                          isogenies. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019,
ski for some helpful suggestions and Yifan Zheng for spotting two                                             Part II, volume 11477 of LNCS, pages 409–441. Springer, Heidelberg, May
                                                                                                              2019.
errors in an earlier draft of this paper. Finally, we thank the authors                               [Bra12] Zvika Brakerski. Fully homomorphic encryption without modulus
of [BKW20] for clarifications on their instantiation. This work was                                           switching from classical GapSVP. In Reihaneh Safavi-Naini and Ran
partly funded by the Digital Europe Program under grant agree-                                                Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 868–886.
                                                                                                              Springer, Heidelberg, August 2012.
ment number 101091642 (“QCI-CAT”), from the European Union’s                                           [BS20] Xavier Bonnetain and André Schrottenloher. Quantum security analysis
Horizon Europe research and innovation programme under the                                                    of CSIDH. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020,
                                                                                                              Part II, volume 12106 of LNCS, pages 493–522. Springer, Heidelberg, May
project “Quantum Security Networks Partnership” (QSNP, grant                                                  2020.
agreement number 101114043), and the “DDAI” COMET module                                         [CCKK21] Jung Hee Cheon, Wonhee Cho, Jeong Han Kim, and Jiseung Kim. Adven-
within the COMET – Competence Centers for Excellent Technolo-                                                 tures in crypto dark matter: Attacks and fixes for weak pseudorandom
                                                                                                              functions. In Juan Garay, editor, PKC 2021, Part II, volume 12711 of
gies Programme, funded by the Austrian Federal Ministries BMK                                                 LNCS, pages 739–760. Springer, Heidelberg, May 2021.
and BMDW, the Austrian Research Promotion Agency (FFG), the                                              +
                                                                                                 [CLM 18] Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and
province of Styria (SFG) and partners from industry and academia.                                             Joost Renes. CSIDH: An efficient post-quantum commutative group ac-
                                                                                                              tion. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018,
The COMET Programme is managed by FFG.                                                                        Part III, volume 11274 of LNCS, pages 395–427. Springer, Heidelberg,
                                                                                                              December 2018.
REFERENCES                                                                                           [Cou06] Jean-Marc Couveignes. Hard homogeneous spaces. Cryptology ePrint
                                                                                                              Archive, Report 2006/291, 2006. https://eprint.iacr.org/2006/291.
 [ADDG23] Martin R. Albrecht, Alex Davidson, Amit Deo, and Daniel Gardham.                       [CSCJR22] Jorge Chávez-Saab, Jesús-Javier Chi-Domínguez, Samuel Jaques, and
              Crypto dark matter on the torus: Oblivious PRFs from shallow PRFs                               Francisco Rodríguez-Henríquez. The SQALE of CSIDH: sublinear Vélu
              and FHE. Cryptology ePrint Archive, Report 2023/232, 2023. https:                               quantum-resistant isogeny action with low exponents. Journal of
              //eprint.iacr.org/2023/232.                                                                     Cryptographic Engineering, 12(3):349–368, September 2022.
  [ADDS21] Martin R. Albrecht, Alex Davidson, Amit Deo, and Nigel P. Smart. Round-             [DFHSW22] Alex Davidson, Armando Faz-Hernández, Nick Sullivan, and Christo-
              optimal verifiable oblivious pseudorandom functions from ideal lattices.                        pher A. Wood. Oblivious Pseudorandom Functions (OPRFs) using Prime-
              In Juan Garay, editor, PKC 2021, Part II, volume 12711 of LNCS, pages                           Order Groups. Internet-Draft draft-irtf-cfrg-voprf-12, Internet Engineer-
              261–289. Springer, Heidelberg, May 2021.                                                        ing Task Force, August 2022. Work in Progress.
 [ADMP20] Navid Alamati, Luca De Feo, Hart Montgomery, and Sikhar Patranabis.                            +
                                                                                                  [DFK 23] Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-
              Cryptographic group actions and applications. In Shiho Moriai and                               Philipp Merz, Lorenz Panny, and Benjamin Wesolowski. SCALLOP:
              Huaxiong Wang, editors, ASIACRYPT 2020, Part II, volume 12492 of                                Scaling the CSI-FiSh. In PKC 2023, Part I, LNCS, pages 345–375. Springer,
              LNCS, pages 411–439. Springer, Heidelberg, December 2020.                                       Heidelberg, May 2023.
     [Bas23] Andrea Basso. A post-quantum round-optimal oblivious PRF from                            [DG19] Luca De Feo and Steven D. Galbraith. SeaSign: Compact isogeny sig-
              isogenies. Cryptology ePrint Archive, Report 2023/225, 2023. https:                             natures from class group actions. In Yuval Ishai and Vincent Rijmen,
              //eprint.iacr.org/2023/225.                                                                     editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 759–
   [BCC+ 23] Andrea Basso, Giulio Codogni, Deirdre Connolly, Luca De Feo, Tako Boris                          789. Springer, Heidelberg, May 2019.
              Fouotsa, Guido Maria Lido, Travis Morrison, Lorenz Panny, Sikhar Pa-                       +
                                                                                                 [DGH 21] Itai Dinur, Steven Goldfeder, Tzipora Halevi, Yuval Ishai, Mahimna
              tranabis, and Benjamin Wesolowski. Supersingular curves you can trust.                          Kelkar, Vivek Sharma, and Greg Zaverucha. MPC-friendly symmet-
              In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology                               ric cryptography from alternating moduli: Candidates, protocols, and
              - EUROCRYPT 2023 - 42nd Annual International Conference on the                                  applications. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021,
              Theory and Applications of Cryptographic Techniques, Lyon, France,                              Part IV, volume 12828 of LNCS, pages 517–547, Virtual Event, August
              April 23-27, 2023, Proceedings, Part II, volume 14005 of Lecture Notes                          2021. Springer, Heidelberg.
              in Computer Science, pages 405–437. Springer, 2023.                                        +
                                                                                                  [DGS 18] Alex Davidson, Ian Goldberg, Nick Sullivan, George Tankersley, and Fil-
  [BDK+ 20] Niklas Büscher, Daniel Demmler, Nikolaos P. Karvelas, Stefan Katzen-                              ippo Valsorda. Privacy pass: Bypassing internet challenges anonymously.
              beisser, Juliane Krämer, Deevashwer Rathee, Thomas Schneider, and                               PoPETs, 2018(3):164–180, July 2018.
              Patrick Struck. Secure two-party computation in a quantum world. In                    [DM20] Luca De Feo and Michael Meyer. Threshold schemes from isogeny
              Mauro Conti, Jianying Zhou, Emiliano Casalicchio, and Angelo Spog-                              assumptions. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden,
              nardi, editors, ACNS 20, Part I, volume 12146 of LNCS, pages 461–480.                           and Vassilis Zikas, editors, PKC 2020, Part II, volume 12111 of LNCS,
              Springer, Heidelberg, October 2020.                                                             pages 187–212. Springer, Heidelberg, May 2020.
    [BDV20] Luís T. A. N. Brandão, Michael Davidson, and Apostol Vassilev. Nist                [dSGOPS20] Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Christophe Pe-
              roadmap toward criteria for threshold schemes for cryptographic primi-                          tit, and Nigel P. Smart. Semi-commutative masking: A framework
              tives, 2020.                                                                                    for isogeny-based protocols, with an application to fully secure two-
   [BFGP23] Ward Beullens, Luca De Feo, Steven D. Galbraith, and Christophe Petit.                            round isogeny-based OT. In Stephan Krenn, Haya Shulman, and
              Proving knowledge of isogenies – a survey. Cryptology ePrint Archive,                           Serge Vaudenay, editors, Cryptology and Network Security - 19th
              Paper 2023/671, 2023. https://eprint.iacr.org/2023/671.                                         International Conference, CANS 2020, Vienna, Austria, December 14-16,
    [BIP+ 18] Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, and David J. Wu.                          2020, Proceedings, volume 12579 of Lecture Notes in Computer Science,
              Exploring crypto dark matter: New simple PRF candidates and their ap-                           pages 235–258. Springer, 2020.
              plications. In Amos Beimel and Stefan Dziembowski, editors, TCC 2018,                      +
                                                                                                   [ECS 15] Adam Everspaugh, Rahul Chatterjee, Samuel Scott, Ari Juels, and Thomas
              Part II, volume 11240 of LNCS, pages 699–729. Springer, Heidelberg,                             Ristenpart. The pythia PRF service. In Jaeyeon Jung and Thorsten Holz,
              November 2018.                                                                                  editors, USENIX Security 2015, pages 547–562. USENIX Association,
  [BKM+ 21] Andrea Basso, Péter Kutas, Simon-Philipp Merz, Christophe Petit,                                  August 2015.
              and Antonio Sanso. Cryptanalysis of an oblivious PRF from super-                      [EKP20] Ali El Kaafarani, Shuichi Katsumata, and Federico Pintore. Lossy CSI-
              singular isogenies. In Mehdi Tibouchi and Huaxiong Wang, edi-                                   FiSh: Efficient signature scheme with tight reduction to decisional
              tors, ASIACRYPT 2021, Part I, volume 13090 of LNCS, pages 160–184.                              CSIDH-512. In Aggelos Kiayias, Markulf Kohlweiss, Petros Wallden,
              Springer, Heidelberg, December 2021.                                                            and Vassilis Zikas, editors, PKC 2020, Part II, volume 12111 of LNCS,
    [BKV19] Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren. CSI-FiSh:                            pages 157–186. Springer, Heidelberg, May 2020.
              Efficient isogeny based signatures through class group computations. In               [FIPR05] Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. Key-
              Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I,                          word search and oblivious pseudorandom functions. In Joe Kilian, editor,
              volume 11921 of LNCS, pages 227–247. Springer, Heidelberg, December                             TCC 2005, volume 3378 of LNCS, pages 303–324. Springer, Heidelberg,
              2019.




                                                                                         587
ASIA CCS ’24, July 1–5, 2024, Singapore, Singapore                   Lena Heimberger, Tobias Hennerbichler, Fredrik Meisingseth, Sebastian Ramacher, and Christian Rechberger


              February 2005.                                                                     [KRS+ 19] Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker,
    [FMP23] Tako Boris Fouotsa, Tomoki Moriya, and Christophe Petit. M-SIDH and                              and Christian Weinert. Mobile private contact discovery at scale. In
              MD-SIDH: Countering SIDH attacks by masking information. LNCS,                                 Nadia Heninger and Patrick Traynor, editors, USENIX Security 2019,
              pages 282–309. Springer, Heidelberg, June 2023.                                                pages 1447–1464. USENIX Association, August 2019.
       [FS87] Amos Fiat and Adi Shamir. How to prove yourself: Practical solutions to             [LGD21] Yi-Fu Lai, Steven D. Galbraith, and Cyprien Delpech de Saint Guil-
              identification and signature problems. In Andrew M. Odlyzko, editor,                           hem. Compact, efficient and UC-secure isogeny-based oblivious
              CRYPTO’86, volume 263 of LNCS, pages 186–194. Springer, Heidelberg,                            transfer. In Anne Canteaut and François-Xavier Standaert, editors,
              August 1987.                                                                                   EUROCRYPT 2021, Part I, volume 12696 of LNCS, pages 213–241.
      [FV12] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homo-                            Springer, Heidelberg, October 2021.
              morphic encryption. Cryptology ePrint Archive, Report 2012/144, 2012.                [Lyu09] Vadim Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and
              https://eprint.iacr.org/2012/144.                                                              factoring-based signatures. In Mitsuru Matsui, editor, ASIACRYPT 2009,
   [GGM84] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. On the cryp-                                 volume 5912 of LNCS, pages 598–616. Springer, Heidelberg, December
              tographic applications of random functions. In G. R. Blakley and                               2009.
              David Chaum, editors, CRYPTO’84, volume 196 of LNCS, pages 276–                       [NR04] Moni Naor and Omer Reingold. Number-theoretic constructions of
              288. Springer, Heidelberg, August 1984.                                                        efficient pseudo-random functions. Journal of the ACM, 51(2):231–262,
   [GGM86] Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct                             2004.
              random functions. Journal of the ACM, 33(4):792–807, October 1986.                    [Pei20] Chris Peikert. He gives C-sieves on the CSIDH. In Anne Canteaut and
  [HKKP21] Keitaro Hashimoto, Shuichi Katsumata, Kris Kwiatkowski, and Thomas                                Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS,
              Prest. An efficient and generic construction for signal’s handshake                            pages 463–492. Springer, Heidelberg, May 2020.
              (x3dh): Post-quantum, state leakage secure, and deniable. Cryptology                   [Qi22] Mingping Qi. An efficient post-quantum kem from csidh. Journal of
              ePrint Archive, Paper 2021/616, 2021. https://eprint.iacr.org/2021/616.                        Mathematical Cryptology, 16(1):103–113, 2022.
   [HSW23] Laura Hetz, Thomas Schneider, and Christian Weinert. Scaling mobile                       [RS06] Alexander Rostovtsev and Anton Stolbunov. Public-Key Cryptosystem
              private contact discovery to billions of users. Cryptology ePrint Archive,                     Based On Isogenies. Cryptology ePrint Archive, Report 2006/145, 2006.
              Paper 2023/758, 2023. https://eprint.iacr.org/2023/758.                                        https://eprint.iacr.org/2006/145.
       [Hun] Troy Hunt. Pwned websites. see https://haveibeenpwned.com/                           [SEA21] Microsoft SEAL (release 3.7). https://github.com/Microsoft/SEAL, Sep-
              pwnedwebsites.                                                                                 tember 2021. Microsoft Research, Redmond, WA.
   [IKNP03] Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending                    [SHB23] István András Seres, Máté Horváth, and Péter Burcs. The legendre pseu-
              oblivious transfers efficiently. In Dan Boneh, editor, CRYPTO 2003,                            dorandom function as a multivariate quadratic cryptosystem: security
              volume 2729 of LNCS, pages 145–161. Springer, Heidelberg, August                               and applications. In AAECC. Springer, 01 2023.
              2003.                                                                                  [Sil86] Joseph H. Silverman. The arithmetic of elliptic curves, volume 106 of
    [JKX18] Stanislaw Jarecki, Hugo Krawczyk, and Jiayu Xu. OPAQUE: An asymmet-                              Graduate texts in mathematics. Springer, 1986.
              ric PAKE protocol secure against pre-computation attacks. In Jesper Buus              [Vél71] J. Vélu. Isogénies entre courbes elliptiques. Comptes-Rendus de
              Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume                          l’Académie des Sciences, Série I, 273:238–241, juillet 1971.
              10822 of LNCS, pages 456–486. Springer, Heidelberg, April / May 2018.




                                                                                           588
