Paper 2022/380 Original: eprint.iacr.org/2022/380 ↗
A Linear-Time 2-Party Secure Merge Protocol
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
- Preprint.
- History
- 2022-03-28: last updated
- 2022-03-28: published
- Short URL
- https://ia.cr/2022/380
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}