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
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 "3rd gen" 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 benchmarks of our construction using the "Concrete" TFHE software library. For the core online OPRF functionality, client operations take only a few milliseconds, while server evaluation takes less than 3 seconds.

Available format(s)
Cryptographic protocols
Publication info
oblivious PRFlatticesFHE
Contact author(s)
martin albrecht @ kcl ac uk
a davidson @ fct unl pt
adeo @ cryptoquantique com
daniel gardham @ surrey ac uk
2023-02-21: approved
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.