Paper 2024/544

A post-quantum Distributed OPRF from the Legendre PRF

Novak Kaluderovic, University of St. Gallen
Nan Cheng, University of St. Gallen
Katerina Mitrokotsa, University of St. Gallen

A distributed OPRF allows a client to evaluate a pseudorandom function on an input chosen by the client using a distributed key shared among multiple servers. This primitive ensures that the servers learn nothing about the input nor the output, and the client learns nothing about the key. We present a post-quantum OPRF in a distributed server setting, which can be computed in a single round of communication between a client and the servers. The only server-to-server communication occurs during a precomputation phase. The algorithm is based on the Legendre PRF which can be computed from a single MPC multiplication among the servers. To this end we propose two MPC approaches to evaluate the Legendre PRF based on replicated and optimised secret sharing, respectively. Furthermore, we propose two methods that allows us to perform MPC multiplication in an efficient way that are of independent interest. By employing the latter, we are able to evaluate the Legendre OPRF in a fashion that is quantum secure, verifiable and secure against malicious adversaries under a threshold assumption, as well as computable in a single round of interaction. To the best of our knowledge, our proposed distributed OPRFs are the first post-quantum secure offering such properties. We also provide an implementation of our protocols, and benchmark it against existing OPRF constructions.

Available format(s)
Cryptographic protocols
Publication info
OPRFPost-quantumLegendre PRFDistributed OPRFMPC
Contact author(s)
novak kaluderovic @ unisg ch
nan cheng @ unisg ch
katerina mitrokotsa @ unisg ch
2024-04-08: approved
2024-04-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Novak Kaluderovic and Nan Cheng and Katerina Mitrokotsa},
      title = {A post-quantum Distributed {OPRF} from the Legendre {PRF}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/544},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.