Paper 2021/1049

Binary Search in Secure Computation

Marina Blanton and Chen Yuan

Abstract

Binary search is one of the most popular algorithms in computer science. Realizing it in the context of secure multiparty computation which demands data-oblivious execution, however, is extremely non-trivial. It has been previously implemented only using oblivious RAM (ORAM) for secure computation and in this work we initiate the study of this topic using conventional secure computation techniques based on secret sharing. We develop a suite of protocols with different properties and of different structure for searching a private dataset of $m$ elements by a private numeric key. Our protocols result in $O(m)$ and $O(\sqrt{m})$ communication using only standard and readily available operations based on secret sharing. We further extend our protocols to support write operations, namely, binary search that obliviously updates the selected element, and realize two variants: updating non-key fields and updating the key field. Our implementation results indicate that even after applying known and our own optimizations to the fastest ORAM constructions, our solutions are faster than optimized ORAM schemes for datasets of up to $2^{30}$ elements and by up to two orders of magnitude. We hope that this work will prompt further interest in seeking efficient realizations of this important problem.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.NDSS'22
Keywords
secure multi-party computationsecret sharing
Contact author(s)
mblanton @ buffalo edu
History
2021-11-20: revised
2021-08-16: received
See all versions
Short URL
https://ia.cr/2021/1049
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1049,
      author = {Marina Blanton and Chen Yuan},
      title = {Binary Search in Secure Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1049},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1049}},
      url = {https://eprint.iacr.org/2021/1049}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.