Paper 2023/232

Crypto Dark Matter on the Torus: Oblivious PRFs from shallow PRFs and FHE

Martin R. Albrecht, King's College London, SandboxAQ
Alex Davidson, NOVA LINCS & DI, FCT, Universidade NOVA de Lisboa
Amit Deo, Crypto Quantique, Zama
Daniel Gardham, University of Surrey

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: align with camera ready.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
oblivious PRFlatticesFHE
Contact author(s)
martin albrecht @ kcl ac uk
a davidson @ fct unl pt
amit deo @ zama ai
daniel gardham @ surrey ac uk
2024-03-01: last of 4 revisions
2023-02-20: received
See all versions
Short URL
No rights reserved


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.