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 Goldk(x) that maps an integer x modulo a public prime p = 2λ ·g+ 1 to the element (k + x) g mod p, where g is public and log g ≈ 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 Ps holds the PRF key k whereas the client Pc holds the PRF input x, and they jointly evaluate Gold in 2PC. 2PC-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 Ps and 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 Ps and 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 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.
Research areas
