Oblivious Message Retrieval

Show & Tell
1

Proof of Concept Implementation of an Improved Oblivious Message Retrieval (OMR) Scheme

OMR leverages HE to enhance UX while maintaining full-anonymity in secure messaging apps and privacy-preserving blockchains. For an introduction to OMR, you might find Eran Tromer’s talk at RWC 2022 helpful: https://youtu.be/dOAMi_uFv_Y?feature=shared&t=3000

Feature Requests: During the implementation, we identified several features missing in the OpenFHE library that could benefit various applications, including ours.

  1. Serialization/Compression of the evaluation keys using hash seeds. This can easily reduce the keysize by approximately half.
  2. Level-specific rotation keys. This can significantly reduce the keysize when most rotations occur at lower levels.
  3. Serialization of ciphertext regarding the ciphertext modulus smaller than 64-bit. This can reduce the ciphertext size during transmissions, particularly after applying ‘compress’ (See Feature 4).
  4. Independent selection of the base-level ciphertext modulus from the RNS limbs in BFV scheme. This can reduce the ciphertext size after applying ‘compress’ together with Feature 3.
  5. Ring Switching (Field Switching in BGV-Style Homomorphic Encryption). This feature is used in several works including our own, to reduce computational/communication complexity after consuming computational budgets (e.g. HERMES: Efficient Ring Packing using MLWE Ciphertexts and Application to Transciphering, Respire: High-Rate PIR for Databases with Small Records). One specific challenge we faced was: Is there a way to set the RNS moduli to specific values?

Thank you for your efforts maintaining and improving this library for the community!

6 Likes
2

Hi @keewoolee,

Thank you for sharing your work and the code for the POC implementation. Some of these features would certainly be nice to add to OpenFHE. We will look at the implementation more carefully later and will reach out to you.