Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

A post-quantum Distributed OPRF from the Legendre PRF

Nan Cheng

Published May 10, 2026• 0 citations
OpenAlex

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.

Related papers

High-throughput Verifiable Distributed OPRF from Gold PRF

Nan Cheng, Yohei Watanabe, Yugo Kasashima +2 more

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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 12, 2026•0 citations

Gold OPRF: Post-Quantum Oblivious Power-Residue PRF

Yibin Yang, Fabrice Benhamouda, Shai Halevi +2 more

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$\lambda$, we consider the PRF Gold$k(x)$that maps an integer$x$modulo a public prime$p=2^{\lambda}\cdot g+1$to the element$(k+x)^{g}\text{mod}\ p$, where$g$is public and$\log g\approx 2\lambda$. 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$\mathcal{P}_{s}$holds the PRF key$k$whereas the client$\mathcal{P}_{c}$holds the PRF input$x$, and they jointly evaluate Gold in$2\mathbf{PC}$. 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$\mathcal{P}_{s}$and a malicious$\mathcal{P}_{c}$: 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$\mathcal{O}(\lambda)$field operations. We refer to this as half-malicious security. •For malicious$\mathcal{P}_{s}$and$\mathcal{P}_{c}$: a 2PC-Gold that just uses$\frac{\lambda}{4}+\mathcal{O}(1)$VOLE correlations, and has a communication complexity of$\frac{\lambda}{4}+\mathcal{O}(1)$field elements and a computational complexity of$\mathcal{O}(\lambda)$field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where$\mathcal{P}_{c}$repeatedly 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$\lambda=128$.

IEEE Symposium on Security and Privacy (S&P)•May 12, 2025•11 citations

Pool: A Practical OT-based OPRF from Learning with Rounding

Alex Davidson, Amit Deo, Louis Tremblay Thibault

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.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Nov 19, 2025•1 citation

A Maliciously-Secure Post-Quantum OPRF from Crypto Dark Matter

Diego F. Aranha, Aron van Baarsen, A C Hansen +2 more

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.

IEEE Symposium on Security and Privacy (S&P)•May 18, 2026•2 citations

Efficient Maliciously Secure Oblivious Exponentiations

Carsten Baum, Jens Berlips, W Q Chen +17 more

Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance. Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor o ( 1 ) as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments. Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does not rely on the OEP but nevertheless only has overhead o ( 1 ) over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers.

IACR Communications in Cryptology•Oct 7, 2024•3 citations

Efficient Post-Quantum OPRF from TFHE Key Transformation with Application to OPAQUE

Mihail Plesa, Robert Poenaru, S Ebert David

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.

•Mar 18, 2026•0 citations
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.
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λ\lambdaλ, we consider the PRF Goldk(x)k(x)k(x)that maps an integerxxxmodulo a public primep=2λ⋅g+1p=2^{\lambda}\cdot g+1p=2λ⋅g+1to the element(k+x)gmod p(k+x)^{g}\text{mod}\ p(k+x)gmod p, wheregggis public andlog⁡g≈2λ\log g\approx 2\lambdalogg≈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 serverPs\mathcal{P}_{s}Ps​holds the PRF keykkkwhereas the clientPc\mathcal{P}_{c}Pc​holds the PRF inputxxx, and they jointly evaluate Gold in2PC2\mathbf{PC}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-honestPs\mathcal{P}_{s}Ps​and a maliciousPc\mathcal{P}_{c}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 ofO(λ)\mathcal{O}(\lambda)O(λ)field operations. We refer to this as half-malicious security. •For maliciousPs\mathcal{P}_{s}Ps​andPc\mathcal{P}_{c}Pc​: a 2PC-Gold that just usesλ4+O(1)\frac{\lambda}{4}+\mathcal{O}(1)4λ​+O(1)VOLE correlations, and has a communication complexity ofλ4+O(1)\frac{\lambda}{4}+\mathcal{O}(1)4λ​+O(1)field elements and a computational complexity ofO(λ)\mathcal{O}(\lambda)O(λ)field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs wherePc\mathcal{P}_{c}Pc​repeatedly 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\lambda=128λ=128.
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.
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.
Oblivious Pseudorandom Functions (OPRFs) allow a client to evaluate a pseudorandom function (PRF) on her secret input based on a key that is held by a server. In the process, the client only learns the PRF output but not the key, while the server neither learns the input nor the output of the client. The arguably most popular OPRF is due to Naor, Pinkas and Reingold (Eurocrypt 2009). It is based on an Oblivious Exponentiation by the server, with passive security under the Decisional Diffie-Hellman assumption. In this work, we strengthen the security guarantees of the NPR OPRF by protecting it against active attacks of the server. We have implemented our solution and report on the performance. Our main result is a new batch OPRF protocol which is secure against maliciously corrupted servers, but is essentially as efficient as the semi-honest solution. More precisely, the computation (and communication) overhead is a multiplicative factor o ( 1 ) as the batch size increases. The obvious solution using zero-knowledge proofs would have a constant factor overhead at best, which can be too expensive for certain deployments. Our protocol relies on a novel version of the DDH problem, which we call the Oblivious Exponentiation Problem (OEP), and we give evidence for its hardness in the Generic Group model. We also present a variant of our maliciously secure protocol that does not rely on the OEP but nevertheless only has overhead o ( 1 ) over the known semi-honest protocol. Moreover, we show that our techniques can also be used to efficiently protect threshold blind BLS signing and threshold ElGamal decryption against malicious attackers.
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.