Cryptology ePrint Archive: Report 2022/380

A Linear-Time 2-Party Secure Merge Protocol

Brett Hemenway Falk and Rohit Nema and 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.

Category / Keywords: cryptographic protocols / Secure Computation, Homomorphic Encryption, Oblivious Protocols

Original Publication (with minor differences): CSCML 2022

Date: received 23 Mar 2022

Contact author: rnema at ucla edu

Available format(s): PDF | BibTeX Citation

Version: 20220328:143314 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]