Paper 2023/639

OPRFs from Isogenies: Designs and Analysis

Lena Heimberger, Graz University of Technology
Tobias Hennerbichler, Graz University of Technology
Fredrik Meisingseth, Know-Center, Graz University of Technology
Sebastian Ramacher, Austrian Institute of Technology
Christian Rechberger, Graz University of Technology

Oblivious Pseudorandom Functions (OPRFs) are an elementary building block in cryptographic and privacy-preserving applications. However, while there are numerous pre-quantum secure OPRF constructions, few options exist in a post-quantum secure setting, and of those even fewer are practical for modern-day applications. In this work, we focus on isogeny group actions, as the associated low bandwidth leads to efficient constructions. Our results focus on the Naor-Reingold OPRF. We introduce OPUS, a novel OPRF from isogenies without oblivious transfer, and show efficient evaluations of the Naor-Reingold PRF using CSIDH and CSI-FiSh. Additionally, we analyze a previous proposal of a CSIDH-based OPRF and that 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 results report a very competitive protocol when combined with lattices for Oblivious Transfer. Our comparison against the state of the art shows that OPUS and the repaired, generic construction are competitive with other proposals in terms of speed and communication size. More concretely, OPUS achieves almost two orders of magnitude less communication overhead compared to the next-best lattice-based OPRF at the cost of higher latency and higher computational cost, and the repaired construction. Finally, we demonstrate the efficiency of OPUS and the generic NR-OT in two use cases: first, we instantiate OPAQUE, a protocol for asymmetric authenticated key exchange. Compared to classical elliptic curve cryptography, this results in less than 100 × longer computation on average and around 1000× more communication overhead. Second, we perform an unbalanced private set intersection and show that the communication overhead can be roughly the same when using isogenies or elliptic curves, at the cost of much higher runtime. Conversely, for sets of the size 210 , we report a runtime around 200× slower than the elliptic curve PSI. This concretizes the overhead of performing PSI and using OPAQUE with isogenies for the first time

Note: New version including an implementation of the generic OPRF, PSI benchmarks and an OPAQUE implementation based on isogenies, as well as a new game-based proof.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. AsiaCCS
Contact author(s)
lena heimberger @ tugraz at
2024-02-14: last of 3 revisions
2023-05-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lena Heimberger and Tobias Hennerbichler and Fredrik Meisingseth and Sebastian Ramacher and Christian Rechberger},
      title = {{OPRFs} from Isogenies: Designs and Analysis},
      howpublished = {Cryptology ePrint Archive, Paper 2023/639},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.