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 $O(n\log^*n)$ time and communication with $O(\log n)$ rounds. In particular, for all conceivable $n$, the $\log^*n$ factor will be equal to the constant $2$, and therefore we achieve a near-linear running time. Median, our rounds-optimized construction, builds on the classic parallel medians-based insecure merge approach of Valiant (SIAM J. Comput., 1975), later explored in the secure setting by Blunk et al. (2022), and requires $O(n \log^c n)$, $1<c<2$, communication with $O(\log \log n)$ rounds. We introduce two additional constructions that merge input lists of different sizes. SquareRootMerge, merges lists of sizes $n^{\frac{1}{2}}$ and $n$, and runs in $O(n)$ time and communication with $O(\log n)$ rounds. CubeRootMerge is closely inspired by Blunk et al.'s (2022) construction and merges lists of sizes $n^{\frac{1}{3}}$ and $n$. It runs in $O(n)$ time and communication with $O(1)$ rounds. We optimize our constructions for concrete efficiency. Today, concretely efficient secure merge protocols rely on standard techniques such as GMW or generic sorting. These approaches require an $O(n \log n)$ size circuit of $O(\log n)$ depth. In contrast, our constructions are more efficient and also achieve superior asymptotics. We benchmark our constructions and obtain significant improvements. For example, Logstar reduces bandwidth costs $\approx 3.3\times$ and Median reduces rounds $\approx2.22\times$.
Metadata
- Available format(s)
- 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-02-19: last of 2 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}, note = {\url{https://eprint.iacr.org/2024/159}}, url = {https://eprint.iacr.org/2024/159} }