Back to Search
Start Over
Linear-time 2-party secure merge from additively homomorphic encryption.
- Source :
-
Journal of Computer & System Sciences . Nov2023, Vol. 137, p37-49. 13p. - Publication Year :
- 2023
-
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 protocols for comparison and equality testing. [ABSTRACT FROM AUTHOR]
- Subjects :
- *INTERSTELLAR communication
*RSA algorithm
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 137
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 164156408
- Full Text :
- https://doi.org/10.1016/j.jcss.2023.04.007