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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
PrivacyBlockchainOblivious Message Retrieval
Contact author(s)
jia168 @ purdue edu
vrmadath @ ncsu edu
aniket @ purdue edu
History
2024-02-09: approved
2024-02-07: received
See all versions
Short URL
https://ia.cr/2024/188
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/188,
      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},
      url = {https://eprint.iacr.org/2024/188}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.