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

Demo #7: A Simulator for Cooperative and Automated Driving...

Mohammed Lamine Bouchouia (Telecom Paris - Institut Polytechnique de Paris), Jean-Philippe Monteuuis (Qualcomm Technologies Inc), Houda Labiod (Telecom Paris - Institut Polytechnique de Paris), Ons Jelassi (Telecom Paris - Institut Polytechnique de Paris), Wafa Ben Jaballah (Thales) and Jonathan Petit (Qualcomm Technologies Inc)

Read More

Demo #12: Too Afraid to Drive: Systematic Discovery of...

Ziwen Wan (UC Irvine), Junjie Shen (UC Irvine), Jalen Chuang (UC Irvine), Xin Xia (UCLA), Joshua Garcia (UC Irvine), Jiaqi Ma (UCLA) and Qi Alfred Chen (UC Irvine)

Read More

FirmWire: Transparent Dynamic Analysis for Cellular Baseband Firmware

Grant Hernandez (University of Florida), Marius Muench (Vrije Universiteit Amsterdam), Dominik Maier (TU Berlin), Alyssa Milburn (Vrije Universiteit Amsterdam), Shinjo Park (TU Berlin), Tobias Scharnowski (Ruhr-University Bochum), Tyler Tucker (University of Florida), Patrick Traynor (University of Florida), Kevin Butler (University of Florida)

Read More

MIRROR: Model Inversion for Deep Learning Network with High...

Shengwei An (Purdue University), Guanhong Tao (Purdue University), Qiuling Xu (Purdue University), Yingqi Liu (Purdue University), Guangyu Shen (Purdue University), Yuan Yao (Nanjing University), Jingwei Xu (Nanjing University), Xiangyu Zhang (Purdue University)

Read More