Paper 2024/1955

Gold OPRF: Post-Quantum Oblivious Power Residue PRF

Abstract

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 $$ that maps an integer $$ modulo a public prime $$ to the element $$, where $$ is public and $$. At the core of our constructions are efficient novel methods for evaluating $$ within two-party computation ($$), achieving different security requirements. Here, the server $$ holds the PRF key $$ whereas the client $$ holds the PRF input $$, and they jointly evaluate $$ in 2PC. $$ 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 $$ and a malicious $$: a $$ that just uses a single (V)OLE correlation, and has a communication complexity of $$ field elements ($$ field elements if we only require a uniformly sampled key) and a computational complexity of $$ field operations. We refer to this as half-malicious security. • For malicious $$ and $$: a $$ that just uses $$ VOLE correlations, and has a communication complexity of $$ field elements and a computational complexity of $$ field operations. These constructions support additional features and extensions, e.g., batched evaluations with better amortized costs where $$ repeatedly evaluates the PRF under the same key. Furthermore, we extend $$ to Verifiable OPRFs and use the methodology from Beullens et al. (ePrint’24) to obtain strong OPRF security in the universally composable setting. All the protocols are efficient in practice. We implemented $$—with (PQ) VOLEs—and benchmarked them. For example, our half-malicious (resp. malicious) $$-batched PQ OPRFs incur about $$B (resp. $$KB) of amortized communication for $$ and large enough $$.