A post-quantum Distributed OPRF from the Legendre PRF
Journal
Computer Security – ESORICS 2025
ISSN
0302-9743
Type
conference paper
Date Issued
2025
Author(s)
Abstract
A distributed OPRF enables a client to evaluate a pseudo-random function on a client-chosen input using a distributed key shared among multiple servers, ensuring that the servers learn nothing about the input or output, while the client learns nothing about the key. We present a post-quantum OPRF suitable for a distributed server setting, requiring only two rounds of communication between the client and servers, with server-to-server communication limited to a pre-computation phase. Our approach leverages the Legendre PRF, computed through a single MPC multiplication and opening during the online phase. We introduce a novel MPC technique that achieves multiplication and opening in one round using replicated secret sharing (RSS) in a malicious adversarial model. This allows for the quantum-secure, verifiable evaluation of the Legendre OPRF against malicious adversaries under a threshold assumption, without requiring inter-server communication. Beyond the Legendre PRF, this method is also of interest for general MPC operations. To our knowledge, our distributed OPRF (dOPRF) is the first post-quantum construction with these properties. We compare our approach to state-of-the-art MPC solutions and provide an implementation of our proposed dOPRF, benchmarking it against existing OPRF constructions. In our comparison, our dOPRF protocol demonstrates superior efficiency.
Language
English
Keywords
distributed OPRF
Legendre PRF
MPC
HSG Classification
contribution to scientific community
Refereed
Yes
Publisher
Springer Nature Switzerland
Event Title
ESORICS
Event Location
Toulouse, France
Event Date
21-23, 09, 2025
Subject(s)
Division(s)
File(s)![Thumbnail Image]()
open.access
Name
Distributed_DOPRF_with_MPC.pdf
Size
578.7 KB
Format
Adobe PDF
Checksum (MD5)
09d5fd65ec046571464a8dc2e746f925