Paper 2023/1969

Secure and Practical Functional Dependency Discovery in Outsourced Databases

Xinle Cao, Zhejiang University
Yuhan Li, Zhejiang University
Dmytro Bogatov, Amazon Inc.
Jian Liu, Zhejiang University
Kui Ren, Zhejiang University

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.

Available format(s)
Cryptographic protocols
Publication info
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
2023-12-31: approved
2023-12-29: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.