LEAP: A Fast, Lattice-based OPRF with Application to Private Set Intersection

Oblivious pseudorandom functions (OPRFs) are important primitives in cryptographic protocols and privacy-preserving technologies. The growing interest in OPRFs, both in theory and practice, has led to the development of numerous constructions and variations. However, most of these constructions rely on classical assumptions. Potential future quantum attacks may limit the practicality of those OPRFs for real-world applications.

To close this gap, we introduce LEAP, a novel OPRF based on lattice assumptions. Fundamentally, LEAP builds upon the Spring (Banerjee et al., FSE 2024) pseudorandom function (PRF), which relies on the learning with rounding assumption, and integrates techniques from multi-party computation, specifically Oblivious Transfer (OT) and Oblivious Linear Evaluation (OLE). With this combination of oblivious protocols, we extend one of the basic approaches to construct an OPRF from OT alone to enable us to build an OPRF that can be evaluated in less than a millisecond on a modern computer.

Efficiency-wise, our prototype implementation achieves computation times of just 11 microseconds for the client and 750 microseconds for the server, assuming some base OT preprocessing. Moreover, LEAP requires an amortized communication cost of 23 KB per evaluation, where the client only has to send around 380 bytes online. To demonstrate the practical applicability of LEAP, we present an efficient private set intersection (PSI) protocol built on top of LEAP. This not only showcases the efficiency and versatility of LEAP but also highlights its potential for integration into various privacy-preserving applications: On our benchmarking, we can compute an unbalanced set intersection with set sizes of 2^24 and 2^15 in under a minute of online time and 2.5 minutes overall, with our unoptimized implementation.