Logstar: Efficient Almost-Linear Time Secure Merge
Srinivasan Raghuraman
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 < 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^{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^{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) 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 ~ 3.3x and Median reduces rounds ~ 2.43x. Joint work with Suvradip Chakraborty, Stanislav Peceny, and Peter Rindal.
Bio:
Dr. Srinivasan Raghuraman received his Ph.D. in Cryptography from MIT in 2020 working with Prof. Shafi Goldwasser, specializing in infrastructures for secure multi-party computation. His Ph.D. thesis focused on enabling reliable communication, secure computation, and fair computation in an incomplete network that also provides reusability, transferability, and fault-tolerance. Srini joined Visa Research as a Staff Research Scientist in June 2020. As a member of the Advanced Cryptography team at Visa Research, his research interests are in cryptography, blockchain, and secure computation. He has published papers in several international conferences and journals, including CRYPTO, EUROCRYPT, Theory of Cryptography Conference (TCC), International Association for Cryptologic Research International Conference on Practice and Theory of Public-Key Cryptography (IACR PKC), and others. Srini also joined MIT as a Lecturer in EECS in February 2023.