Abstract. We propose a one-round 1-out-of-n computationally-private information retrieval protocol for ℓ-bit strings with low-degree polylogarithmic receivercomputation, linear sender-computation and communication Θ(k · log 2 n + ℓ · log n), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1out-of-n oblivious-transfer protocol for ℓ-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model. Keywords. Computationally-private information retrieval, length-flexible additively homomorphic public-key cryptosystem, oblivious transfer. 1
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.