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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. AsiaCCS
Keywords
OPRFCSIDHAttackNaor-ReingoldOPAQUEPSIPost-Quantum
Contact author(s)
lena heimberger @ tugraz at
History
2024-02-14: last of 3 revisions
2023-05-05: received
See all versions
Short URL
https://ia.cr/2023/639
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/639,
      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},
      url = {https://eprint.iacr.org/2023/639}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.