In this chapter, we describe efficient protocols for performing reads and writes in private arrays according to private indices. The protocols are implemented on top of the arithmetic black box (ABB) and can be composed freely to build larger privacy-preserving applications. We present two approaches to speed up private reads and writes — one based on precomputation and the other one on sorting. We show how several different problems become significantly more tractable while preserving the privacy of inputs. In particular, our second approach opens up a large class of parallel algorithms for adoption to run on SMC platforms.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com