A post-quantum Distributed OPRF from the Legendre PRF
Type
conference lecture
Date Issued
2026-05-10
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.
Language
English
HSG Classification
contribution to scientific community
Refereed
Yes
Event Title
International Workshop on Foundations and Applications of Privacy-Enhancing Cryptography (affiliated with Eurocrypt 2026)
Event Location
Italy, Rome
Event Date
May 10, 2026
Official URL
Subject(s)
Division(s)