Paper 2023/1969
Secure and Practical Functional Dependency Discovery in Outsourced Databases
Abstract
The popularity of cloud computing has made outsourced databases prevalent in real-world applications. To protect data security, numerous encrypted outsourced databases have been proposed for this paradigm. However, the maintenance of encrypted databases has scarcely been addressed. In this paper, we focus on a typical maintenance task --- functional dependency (FD) discovery. We develop novel FD protocols in encrypted databases while guaranteeing minimal leakages: nothing is revealed besides the database size and the actual discovered FDs. As far as we know, we are the first to formally define secure FD discovery with minimal leakage. We present two oblivious FD protocols and prove them secure in the presence of the persistent adversary (monitoring processes on the server). The first protocol leverages Oblivious RAM (ORAM) and is suitable for dynamic databases. The second protocol relies on oblivious sorting and is more practical in static databases due to high parallelism. We also present a thorough experimental evaluation of the proposed methods.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- encrypted databasesdata managementfunctional dependency discoveryobliviousness
- Contact author(s)
-
xinlecao72 @ gmail com
yuhan2165 @ zju edu cn
bogatov @ amazon com
liujian2411 @ zju edu cn
kuiren @ zju edu cn - History
- 2023-12-31: approved
- 2023-12-29: received
- See all versions
- Short URL
- https://ia.cr/2023/1969
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2023/1969,
author = {Xinle Cao and Yuhan Li and Dmytro Bogatov and Jian Liu and Kui Ren},
title = {Secure and Practical Functional Dependency Discovery in Outsourced Databases},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1969},
year = {2023},
url = {https://eprint.iacr.org/2023/1969}
}