Paper 2024/450

The 2Hash OPRF Framework and Efficient Post-Quantum Instantiations

Ward Beullens, IBM Research - Zurich
Lucas Dodgson, ETH Zurich
Sebastian Faller, IBM Research - Zurich
Julia Hesse, IBM Research - Zurich
Abstract

An Oblivious Pseudo-Random Function (OPRF) is a two-party protocol for jointly evaluating a Pseudo-Random Function (PRF), where a user has an input x and a server has an input k. At the end of the protocol, the user learns the evaluation of the PRF using key k at the value x, while the server learns nothing about the user's input or output. 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 are still practically inefficient. In this paper, we propose a framework for constructing OPRFs from post-quantum multi-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, and from AES encryption. 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 ZKPs, we obtain a quantum-safe OPRF that completes in 0.57 seconds, with less than 1MB of communication.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Oblivious Pseudo-Random FunctionLegendre PRFVOLE
Contact author(s)
wbe @ zurich ibm com
lucasdodgson @ protonmail com
sebastian faller @ ibm com
juliahesse2 @ gmail com
History
2024-03-18: approved
2024-03-15: received
See all versions
Short URL
https://ia.cr/2024/450
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/450,
      author = {Ward Beullens and Lucas Dodgson and Sebastian Faller and Julia Hesse},
      title = {The {2Hash} {OPRF} Framework and Efficient Post-Quantum Instantiations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/450},
      year = {2024},
      url = {https://eprint.iacr.org/2024/450}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.