Marina Blanton (University at Buffalo (SUNY)), Chen Yuan (University at Buffalo (SUNY))

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 2 orders of magnitude. We hope that this work will prompt further interest in seeking efficient realizations of this important problem.

View More Papers

“So I Sold My Soul“: Effects of Dark Patterns...

Oksana Kulyk (ITU Copenhagen), Willard Rafnsson (IT University of Copenhagen), Ida Marie Borberg, Rene Hougard Pedersen

Read More

LogicMEM: Automatic Profile Generation for Binary-Only Memory Forensics via...

Zhenxiao Qi (UC Riverside), Yu Qu (UC Riverside), Heng Yin (UC Riverside)

Read More

PMTUD is not Panacea: Revisiting IP Fragmentation Attacks against...

Xuewei Feng (Tsinghua University), Qi Li (Tsinghua University), Kun Sun (George Mason University), Ke Xu (Tsinghua University), Baojun Liu (Tsinghua University), Xiaofeng Zheng (Institute for Network Sciences and Cyberspace, Tsinghua University; QiAnXin Technology Research Institute & Legendsec Information Technology (Beijing) Inc.), Qiushi Yang (QiAnXin Technology Research Institute & Legendsec Information Technology (Beijing) Inc.), Haixin Duan…

Read More

Usability of Cryptocurrency Wallets Providing CoinJoin Transactions

Simin Ghesmati (Uni Wien, SBA Research), Walid Fdhila (Uni Wien, SBA Research), Edgar Weippl (Uni Wien, SBA Research)

Read More