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)$, $c \approx 1.71$, 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 Batcher's merging network or generic sorting. These approaches require an $O(n \log n)$ size circuit of $O(\log n)$ depth. Despite significant research thrust, no work has been able to reduce their concrete costs. Our constructions are the first to be more efficient by improving their asymptotics and maintaining small constants. We analytically benchmark against these constructions and show that Logstar reduces bandwidth costs $\approx2.0\times$ and Median reduces rounds $\approx1.5\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-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} }