Paper 2023/232
Crypto Dark Matter on the Torus: Oblivious PRFs from shallow PRFs and FHE
Abstract
Partially Oblivious Pseudorandom Functions (POPRFs) are 2-party protocols that allow a client to learn pseudorandom function (PRF) evaluations on inputs of its choice from a server. The client submits two inputs, one public and one private. The security properties ensure that the server cannot learn the private input, and the client cannot learn more than one evaluation per POPRF query. POPRFs have many applications including password-based key exchange and privacy-preserving authentication mechanisms. However, most constructions are based on classical assumptions, and those with post quantum security suffer from large efficiency drawbacks. In this work, we construct a novel POPRF from lattice assumptions and the “Crypto Dark Matter” PRF candidate (TCC’18) in the random oracle model. At a conceptual level, our scheme exploits the alignment of this family of PRF candidates, relying on mixed modulus computations, and programmable bootstrapping in the torus fully homomorphic encryption scheme (TFHE). We show that our construction achieves malicious client security based on circuit-private FHE, and client privacy from the semantic security of the FHE scheme. We further explore a heuristic approach to extend our scheme to support verifiability, based on the difficulty of computing cheating circuits in low depth. This would yield a verifiable (P)OPRF. We provide a proof-of-concept implementation and preliminary benchmarks of our construction. For the core online OPRF functionality, we require amortised 10.0KB communication per evaluation and a one-time per-client setup communication of 2.5MB.
Note: fix definition of VOPRF (scheme unchanged)
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2024
- Keywords
- oblivious PRFlatticesFHE
- Contact author(s)
-
martin albrecht @ kcl ac uk
a davidson @ fct unl pt
amit deo @ zama ai
daniel gardham @ surrey ac uk - History
- 2024-07-15: last of 5 revisions
- 2023-02-20: received
- See all versions
- Short URL
- https://ia.cr/2023/232
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/232, author = {Martin R. Albrecht and Alex Davidson and Amit Deo and Daniel Gardham}, title = {Crypto Dark Matter on the Torus: Oblivious {PRFs} from shallow {PRFs} and {FHE}}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/232}, year = {2023}, url = {https://eprint.iacr.org/2023/232} }