Round-Efficient Oblivious Database Manipulation

Abstract. Most of the multi-party computation frameworks can be viewed as oblivious databases where data is stored and processed in a secret-shared form. However, data manipulation in such databases can be slow and cumbersome without dedicated protocols for certain database operations. In this paper, we provide efficient protocols for oblivious se-lection, filtering and shuffle—essential tools in privacy-preserving data analysis. As the first contribution, we present a 1-out-of-n oblivious transfer protocol with O(log logn) rounds, which achieves optimal com-munication and time complexity and works over any ring ZN. Secondly, we show that the round complexity τbd of a bit decomposition proto-col can be almost matched with oblivious transfer, and that there ex-ists an oblivious transfer protocol with O(τbd log ∗ n) rounds. Finally, we also show how to construct round-efficient shuffle protocols with optimal asymptotic computation complexity and provide several optimizations