We propose Pool: a conceptually simple post-quantum (PQ) oblivious pseudorandom function (OPRF) protocol, that is round-optimal (with input-independent preprocessing), practically efficient, and has security based on the well-understood hardness of the learning with rounding (LWR) problem. Specifically, our design permits oblivious computation of the LWR-based pseudorandom function Fsk(x) = ⌉ H(x)⊤ ⋅ sk ⌋q,p, for random oracle H: {0,1} * → ℤ qn and uniformly chosen sk∈ {0,1} n. For 128-bits of semi-honest security, the Pool OPRF has an online communication cost of 11.9 kB, and a computational runtime of less than 3 ms on a single thread (via an open-source software implementation). This is more efficient (in either online communication cost or runtime) than constructions from well-known PQ PRFs, and is competitive even with constructions that only conjecture PQ security on lesser-known assumptions. As a result, our design gives high-performance, post-quantum variants of established OPRF applications in multi-party computation and private set operation protocols.
An oblivious pseudorandom function (OPRF) is a two-party protocol that enables a client to obtain F k (x) on an input x without learning the server-held key k , while the server learns nothing about x . OPRF is a fundamental building block in a wide range of privacy-preserving applications, including password-authenticated key exchange (PAKE), private set intersection (PSI), and distributed function secret sharing. In this work, we present the first concrete, high-throughput, post-quantum secure, verifiable distributed OPRF (dOPRF) tolerating t < n /2 malicious servers and a malicious client over replicated secret sharing, extending the recently introduced Gold OPRF of Yang et al. (IEEE S&P 2025) to a threshold setting. We adopt an offline-online paradigm and introduce new protocol designs for both phases. (i) In the offline phase, we develop efficient protocols for batched generation of replicated secret sharing of α e whose cost is independent of e . We present two complementary approaches, each designed for different parameter regimes: the first leverages a degenerate additive encoding under which exponentiation commutes with secret sharing; the second employs t+1 designated dealers that prove dual-share consistency via non-interactive zero-knowledge proofs, instantiated using both VOLE-in-the-Head and Ligero, yielding post-quantum security based solely on collision-resistant hashing. (ii) In the online phase, we propose a constant-round protocol that tightly integrates secure multiplication-and-opening with distributed zero-knowledge proof (DZKP) verification, reducing communication in every setting we evaluate and computation in all but the largest batched setting, compared to naively using the standard DZKP framework. (iii) We give a verifiable input protocol that enforces a possibly-malicious client providing well-formed inputs; its well-formedness check is absorbed into a hash exchange the online protocol already performs, and it lowers the client's upload from a full replicated share to one field element per server per input. Our end-to-end benchmarks show that the construction substantially outperforms the state-of-the-art Legendre-PRF dOPRF of Kaluđerović et al. (ESORICS 2025) in terms of communication across all evaluated settings, and remains practical up to (n,t)=(9,4), a regime where prior approaches become bandwidth- or memory-prohibitive.
We propose plausible post-quantum (PQ) oblivious pseudorandom functions (OPRFs) based on the Power-Residue PRF (Damgård CRYPTO'88), a generalization of the Legendre PRF. For security parameter
λ, we consider the PRF Gold
k(x)that maps an integer
xmodulo a public prime
p=2λ⋅g+1to the element
(k+x)gmod p, where
gis public and
logg≈2λ. At the core of our constructions are efficient novel methods for evaluating Gold within two-party computation (2PC-Gold), achieving different security requirements. Here, the server
Psholds the PRF key
kwhereas the client
Pcholds the PRF input
x, and they jointly evaluate Gold in
2PC. 2 PC-Gold uses standard Vector Oblivious Linear Evaluation (VOLE) correlations and is information-theoretic and constant-round in the (V)OLE-hybrid model. We show: •For a semi-honest
Psand a malicious
Pc: a 2PC-Gold that just uses a single (V)OLE correlation, and has a communication complexity of 3 field elements (2 field elements if we only require a uniformly sampled key) and a computational complexity of
O(λ)field operations. We refer to this as half-malicious security. •For malicious
Psand
Pc: a 2PC-Gold that just uses
4λ+O(1)VOLE correlations, and has a communication complexity of
4λ+O(1)field elements and a computational complexity of
O(λ)field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where
Pcrepeatedly evaluates the PRF under the same key. Furthermore, we extend 2PC-Gold to Verifiable OPRFs and use the methodology from Beullens et al. (Eurocrypt'25) to get strong OPRF security in the universally composable setting. All the protocols are efficient in practice. We implemented 2PC-Gold-with (PQ) VOLEs-and benchmarked them. For example, our half-malicious (resp. malicious) n-batched PQ OPRFs incur about 100B (resp. 1.9KB) of amortized communication for
λ=128.
Abstract We present a highly efficient post-quantum Randomized Oblivious Pseudorandom Function (OPRF) construction based on a novel TFHE key transformation technique. Unlike prior lattice-based OPRF schemes that rely on complex homomorphic PRF evaluation, our approach leverages the algebraic structure of TFHE to enable direct ciphertext transformation, resulting in significant performance improvements. Our protocol achieves strong security under the Learning With Errors (LWE) assumption and provides session unlinkability, making it well-suited for privacy-preserving applications. We demonstrate the practical efficiency of our construction with a Rust implementation, achieving substantial speedups over existing schemes. Furthermore, we show how our Randomized OPRF can be adapted for use in the OPAQUE password-authenticated key exchange protocol by employing a singularization technique to ensure deterministic outputs when required. This work highlights a new, practical path for post-quantum OPRFs with strong privacy and efficiency guarantees.
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.
We construct protocols for oblivious pseudorandom functions (OPRFs) based on alternating moduli assumptions in the 'Crypto Dark Matter' paradigm (Boneh et al, TCC 2016). Prior OPRFs based on this type of assumption were only secure against a semi-honest adversary. We show how to obtain maliciously secure protocols, by leveraging new cut-and-choose techniques for generating correlated randomness based on vector oblivious linear evaluation (VOLE), which allow efficient conversions between different moduli in zero-knowledge and secure two-party computation. Compared with the state-of-the-art GOLD OPRF (Yang et al, S&P 2025), our construction has a faster online phase in all settings, as well as overall better efficiency in the small-batch setting. Furthermore, our construction supports obtaining a secret-shared output, and can be extended to handle secretshared inputs. This opens up additional applications in variants of private set intersection and secure database operations.
Verifiable Random Functions (VRFs) and Oblivious Pseudorandom Functions (OPRFs) are essential cryptographic primitives in privacy-preserving applications such as anonymous authentication, private set intersection (PSI), and decentralized identity. Existing constructions, however, rely on number-theoretic assumptions that are vulnerable to quantum attacks. This PhD research project focuses on constructing efficient and practical VRFs and OPRFs from lattice-based assumptions to ensure post-quantum security. A key obstacle in these constructions is the overhead of zero-knowledge proofs (ZKPs), particularly range proofs, which are costly in terms of size and prover complexity. To address this, we investigate probabilistic techniques that relax exact correctness. In particular, we explore approximate range proofs and algebraic transformations, such as using automorphisms in polynomial rings to simulate inner product arguments via polynomial multiplication. These methods enable more efficient and scalable lattice-based constructions of VRFs, including group and context-bound variants, as well as OPRFs. The goal is to make these primitives practical for deployment in post-quantum privacy-preserving systems.