Paper 2023/534

Group Oblivious Message Retrieval

Zeyu Liu, Yale University
Eran Tromer, Boston University
Yunhao Wang, Columbia University
Abstract

Anonymous message delivery, as in private communication and privacy-preserving blockchain applications, ought to protect recipient metadata: a message should not be inadvertently linkable to its destination. But how can messages then be delivered to each recipient, without each recipient scanning all messages? Recent work constructed Oblivious Message Retrieval (OMR) protocols that outsource this job to untrusted servers in a privacy-preserving manner. We consider the case of group messaging, where each message may have multiple recipients (e.g., in a group chat or blockchain transaction). Direct use of prior OMR protocols in the group setting increases the servers' work linearly in the group size, rendering it prohibitively costly for large groups. We thus devise new protocols where the servers' cost grows very slowly with the group size, while recipients' cost is low and independent of the group size. Our approach uses Fully Homomorphic Encryption and other lattice-based techniques, building on and improving on prior work. The efficient handling of groups is attained by encoding multiple recipient-specific clues into a single polynomial or multilinear function that can be efficiently evaluated under FHE, and via preprocessing and amortization techniques. We formally study several variants of Group Oblivious Message Retrieval (GOMR) and describe corresponding GOMR protocols. Our implementation and benchmarks show, for parameters of interest, cost reductions of orders of magnitude compared to prior schemes. For example, the servers' cost is ${\sim}\$3.36$ per million messages scanned, where each message may address up to $15$ recipients.

Note: Editorial improvements and the lower bounds; an extended version of the publication at S&P 2024.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. S&P 2024
Keywords
Anonymous message deliveryFully homomorphic encryption
Contact author(s)
zeyu liu @ yale edu
eprint2eran @ tromer org
yw3736 @ columbia edu
History
2024-05-19: last of 2 revisions
2023-04-13: received
See all versions
Short URL
https://ia.cr/2023/534
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/534,
      author = {Zeyu Liu and Eran Tromer and Yunhao Wang},
      title = {Group Oblivious Message Retrieval},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/534},
      year = {2023},
      url = {https://eprint.iacr.org/2023/534}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.