Paper 2024/159
Logstar: Efficient Linear* Time Secure Merge
Abstract
Secure merge considers the problem of combining two sorted lists into a single sorted secret-shared list. Merge is a fundamental building block for many real-world applications. For example, secure merge can implement a large number of SQL-like database joins, which are essential for almost any data processing task such as privacy-preserving fraud detection, ad conversion rates, data deduplication, and many more.
We present two constructions with communication bandwidth and rounds tradeoff. Logstar, our bandwidth-optimized construction, takes inspiration from Falk and Ostrovsky (ITC, 2021) and runs in
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- MPCSecure MergeSecure Sort
- Contact author(s)
-
suvradip1111 @ gmail com
stan peceny @ gatech edu
srini131293 @ gmail com
peterrindal @ gmail com - History
- 2024-12-20: last of 5 revisions
- 2024-02-03: received
- See all versions
- Short URL
- https://ia.cr/2024/159
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/159, author = {Suvradip Chakraborty and Stanislav Peceny and Srinivasan Raghuraman and Peter Rindal}, title = {Logstar: Efficient Linear* Time Secure Merge}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/159}, year = {2024}, url = {https://eprint.iacr.org/2024/159} }