The 2Hash OPRF Framework and Efficient Post-Quantum Instantiations

An Oblivious Pseudo-Random Function (OPRF) is a two- party protocol for jointly evaluating a Pseudo-Random Function (PRF). OPRFs are a prime tool for building secure authentication and key exchange from passwords, private set intersection, private information retrieval, and many other privacy-preserving systems. While classical OPRFs run as fast as a TLS Handshake, current quantum-safe OPRF candidates with malicious security are still practically inefficient. In this paper, we propose a framework for constructing OPRFs from secure two-party computation. The framework captures a family of so- called 2Hash PRFs, which sandwich a function evaluation in between two hashes. The core of our framework is a compiler that yields an OPRF from a secure evaluation of any function that is key-collision resistant and one-more unpredictable. We instantiate this compiler by providing such functions built from Legendre symbols or from a block cipher. We then give a case-tailored protocol for securely evaluating our Legendre-based function, built from Oblivious Transfer (OT) and Zero-Knowledge Proofs (ZKP). Instantiated with lattice-based OT and proofs based on Vector Oblivious Linear Evaluation (VOLE), we obtain the first somewhat prac- tically efficient quantum-safe OPRF with active security. Instantiated for 128 bits of security, we estimate that our OPRF would finish in approxi- mately 0.6 seconds on a WAN network with 30 ms latency and 25 Mbps bandwidth with less than 1 MB of total communication.