Secure partial encryption with adversarial functional dependency constraints in the database-as-a-service model

Boxiang Dong, Hui (Wendy) Wang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


Cloud computing enables end-users to outsource their dataset and data management needs to a third-party service provider. One of the major security concerns of the outsourcing paradigm is how to protect sensitive information in the outsourced dataset. In some applications, only partial values are considered sensitive. In general, the sensitive information can be protected by encryption. However, data dependency constraints (together with the unencrypted data) in the outsourced data may serve as adversary knowledge and bring security vulnerabilities to the encrypted data. In this paper, we focus on functional dependency (FD), an important type of data dependency constraints, and study the security threats by the adversarial FDs. We design a practical scheme that can defend against the FD attack by encrypting a small amount of non-sensitive data (encryption overhead). We prove that finding the scheme that leads to the optimal encryption overhead is NP-complete, and design efficient heuristic algorithms, under the presence of one or multiple FDs. We design a secure query rewriting scheme that enables the service provider to answer various types of queries on the encrypted data with provable security guarantee. We extend our study to enforce security when there are conditional functional dependencies (CFDs) and data updates. We conduct an extensive set of experiments on two real-world datasets. The experiment results show that our heuristic approach brings small amounts of encryption overhead (at most 1% more than the optimal overhead), and enjoys a 10-time speedup compared with the optimal solution. Besides, our approach can reduce up to 90% of the encryption overhead of state-of-the-art solution.

Original languageEnglish
Pages (from-to)1-20
Number of pages20
JournalData and Knowledge Engineering
StatePublished - Jul 2018


  • Data outsourcing
  • Database management
  • Database-as-a-service
  • Management of integrity constraints
  • Security, integrity, and protection


Dive into the research topics of 'Secure partial encryption with adversarial functional dependency constraints in the database-as-a-service model'. Together they form a unique fingerprint.

Cite this