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

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.