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 a 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. (ITC, 2025), 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 (ITC, 2025) 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. Despite extensive research, efficient secure merge still relies on Batcher's merging network or generic sorting, with $O(n\log n)$ circuit size and $O(\log n)$ depth. Ours are the first constructions to lower their concrete costs through better asymptotics and small constants. Two-party implementations of all four protocols show that, for $n=2^{20}$ 32-bit elements per list, Logstar reduces online communication by $2.09\times$ versus Batcher and $3.69\times$ versus shuffled quicksort. Median reduces Batcher's online rounds by $19.0\%$, using $2.03\times$ its online communication. For unequal inputs, SquareRootMerge and CubeRootMerge reduce Batcher's online communication by $3.34\times$ and $4.69\times$, respectively.