Paper 2011/429

Round-efficient Oblivious Database Manipulation

Sven Laur, Jan Willemson, and 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Full version of a paper to be published at ISC2011
Keywords
Secure multi-party computationoblivious transferverifiable shuffleoblivious filtering
Contact author(s)
jan willemson @ gmail com
History
2011-08-12: received
Short URL
https://ia.cr/2011/429
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/429,
      author = {Sven Laur and Jan Willemson and Bingsheng Zhang},
      title = {Round-efficient Oblivious Database Manipulation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2011/429},
      year = {2011},
      url = {https://eprint.iacr.org/2011/429}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.