Welcome to the resource topic for 2011/429
Title:
Round-efficient Oblivious Database Manipulation
Authors: Sven Laur, Jan Willemson, Bingsheng Zhang
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 selection, 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\log n) rounds, which achieves optimal communication and time complexity and works over any ring Z_N. Secondly, we show that the round complexity \tau_{bd} of a bit decomposition protocol can be almost matched with oblivious transfer, and that there exists an oblivious transfer protocol with O(\tau_{bd}\log^*n) rounds. Finally, we also show how to construct round-efficient shuffle protocols with optimal asymptotic computation complexity and provide several optimizations.
ePrint: https://eprint.iacr.org/2011/429
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .