Paper 2024/188

HomeRun: High-efficiency Oblivious Message Retrieval, Unrestricted

Yanxue Jia, Purdue University
Varun Madathil, North Carolina State University
Aniket Kate, Purdue University / Supra Research

In the realm of privacy-preserving blockchain applications such as Zcash, oblivious message retrieval (OMR) enables recipients to privately access messages directed to them on blockchain nodes (or bulletin board servers). OMR prevents servers from linking a message and its corresponding recipient's address, thereby safeguarding recipient privacy. Several OMR schemes have emerged recently to meet the demands of these privacy-centric blockchains; however, we observe that existing solutions exhibit shortcomings in various critical aspects and may only achieve certain objectives inefficiently, sometimes relying on trusted hardware, thereby impacting their practical utility. This work introduces a novel OMR protocol, HomeRun, that leverages two semi-honest, non-colluding servers to excel in both performance and security attributes as compared to the current state-of-the-art. HomeRun stands out by providing unlinkability across multiple requests for the same recipient's address. Moreover, it does not impose a limit on the number of pertinent messages that can be received by a recipient, which thwarts ``message balance exhaustion'' attacks and enhances system usability. HomeRun also empowers servers to regularly delete the retrieved messages and the associated auxiliary data, which mitigates the constantly increasing computation costs and storage costs incurred by servers. Remarkably, none of the existing solutions offer all of these features collectively. Finally, thanks to its judicious use of highly efficient cryptographic building blocks, HomeRun is highly performant: Specifically, the total runtime of servers in HomeRun is $3830 \times$ less than that in the work by Liu et al. (CRYPTO '22) based on fully-homomorphic encryption, and at least $1459 \times$ less than that in the design by Madathil et al. (USENIX Security '22) based on two semi-honest and non-colluding servers, using a single thread in a WAN setting.

Available format(s)
Cryptographic protocols
Publication info
PrivacyBlockchainOblivious Message Retrieval
Contact author(s)
jia168 @ purdue edu
vrmadath @ ncsu edu
aniket @ purdue edu
2024-02-09: approved
2024-02-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yanxue Jia and Varun Madathil and Aniket Kate},
      title = {HomeRun: High-efficiency Oblivious Message Retrieval, Unrestricted},
      howpublished = {Cryptology ePrint Archive, Paper 2024/188},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.