Paper 2022/380
A Linear-Time 2-Party Secure Merge Protocol
Brett Hemenway Falk, Rohit Nema, and Rafail Ostrovsky
Abstract
We present a linear-time, space and communication data-oblivious algorithm for securely merging two private, sorted lists into a single sorted, secret-shared list in the two party setting. Although merging two sorted lists can be done insecurely in linear time, previous secure merge algorithms all require super-linear time and communication. A key feature of our construction is a novel method to obliviously traverse permuted lists in sorted order. Our algorithm only requires black-box use of the underlying Additively Homomorphic cryptosystem and generic secure computation schemes for comparison and equality testing.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. CSCML 2022
- Keywords
- Secure ComputationHomomorphic EncryptionOblivious Protocols
- Contact author(s)
- rnema @ ucla edu
- History
- 2022-03-28: received
- Short URL
- https://ia.cr/2022/380
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/380,
author = {Brett Hemenway Falk and Rohit Nema and Rafail Ostrovsky},
title = {A Linear-Time 2-Party Secure Merge Protocol},
howpublished = {Cryptology {ePrint} Archive, Paper 2022/380},
year = {2022},
url = {https://eprint.iacr.org/2022/380}
}
