Paper 2022/590
Secure Merge in Linear Time and O(log log N) Rounds
Abstract
The problem of Secure Merge consists of combining two sorted lists (which are either held separately by two parties, or secret-shared among two or more parties), and outputting a single merged (sorted) list, secret-shared among all parties.
Just as insecure algorithms for comparison-based sorting are slower than merging (i.e., for lists of size
Note: Revised for readability and clarity of exposition.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Secure MergeSecure SortSecure DatabasePrivate Set Intersection.
- Contact author(s)
-
mark @ stealthsoftwareinc com
paul @ stealthsoftwareinc com
sam @ stealthsoftwareinc com
steve @ stealthsoftwareinc com
rafail @ cs ucla edu - History
- 2024-02-04: revised
- 2022-05-17: received
- See all versions
- Short URL
- https://ia.cr/2022/590
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/590, author = {Mark Blunk and Paul Bunn and Samuel Dittmer and Steve Lu and Rafail Ostrovsky}, title = {Secure Merge in Linear Time and O(log log N) Rounds}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/590}, year = {2022}, url = {https://eprint.iacr.org/2022/590} }