Welcome to the resource topic for 2024/159
Title:
Logstar: Efficient Linear* Time Secure Merge
Authors: Suvradip Chakraborty, Stanislav Peceny, Srinivasan Raghuraman, Peter Rindal
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 median-based merge approach of Valiant (SIAM J. Comput., 1975), and requires O(n \log^c n), 1<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 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 a O(n \log n) sized circuit of O(\log n) depth. In contrast, our constructions are efficient and 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.43\times.
ePrint: https://eprint.iacr.org/2024/159
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .