Paper 2021/593
Differentially Oblivious Database Joins: Overcoming the Worst-Case Curse of Fully Oblivious Algorithms
Shumo Chu, Danyang Zhuo, Elaine Shi, and T-H. Hubert Chan
Abstract
Numerous high-profile works have shown that access patterns
to even encrypted databases can leak
secret information and sometimes even lead to reconstruction
of the entire database.
To thwart access pattern leakage, the literature
has focused on {\it oblivious}
algorithms, where obliviousness requires that
the access patterns leak nothing about the input data.
In this paper, we consider the {\tt Join} operator,
an important database primitive that has been extensively studied
and optimized. Unfortunately, any {\it fully oblivious}
{\tt Join} algorithm would require {\it always} padding the result
to the {\it worst-case} length which is {\it quadratic} in the data size
Note: This is the online full version containing formal algorithm description and detailed proofs.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Major revision. ITC 2021
- Keywords
- Differential obliviousnessdifferential privacyoblivious algorithmsdatabase joinsinstance-specific performance
- Contact author(s)
- runting @ gmail com
- History
- 2021-08-09: revised
- 2021-05-10: received
- See all versions
- Short URL
- https://ia.cr/2021/593
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/593, author = {Shumo Chu and Danyang Zhuo and Elaine Shi and T-H. Hubert Chan}, title = {Differentially Oblivious Database Joins: Overcoming the Worst-Case Curse of Fully Oblivious Algorithms}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/593}, year = {2021}, url = {https://eprint.iacr.org/2021/593} }