A Linear-Time 2-Party Secure Merge Protocol
Brett Hemenway Falk, Rohit Nema, Rafail Ostrovsky
Abstract:
We present a linear-time, space and communication data-oblivious algorithm for securely merging two private, sorted lists into a single sorted, secret-shared list in the two party setting. Although merging two sorted lists can be done insecurely in linear time, previous secure merge algorithms all require super-linear time and communication. A key feature of our construction is a novel method to obliviously traverse permuted lists in sorted order. Our algorithm only requires black-box use of the underlying Additively Homomorphic cryptosystem and generic secure computation schemes for comparison and equality testing.
comment:
CSCML 2022: 408-427
Journal version: Journal of Computer and System Sciences 137: 37-49 (2023); published as "Linear-time 2-party secure merge from additively homomorphic encryption" [Journal]
Fetch PDF file of the paper