A novel secure data outsourcing scheme based on data hiding and secret sharing for relational databases

Data encryption-based and secret sharing-based data outsourcing schemes protect the confidentiality of sensitive attributes but not their secrecy. Ciphertexts/shares generated by a data encryption/secret sharing scheme can attract the attention of interceptors. Thus, it is desired to hide the existence of highly-sensitive attributes (as secret attributes) in the outsourced relations in addition to protecting their contents. This paper proposes a novel scheme that integrates data hiding with secret sharing for relational databases to protect both the secrecy and confidentiality of secret attributes. It embeds one or multiple secret attributes in a relation into one or multiple cover attributes in the same relation. A set of share (and possibly index) columns are constructed such that they are pretended to be associated with only the cover attributes, while those share columns and some virtual share columns can be used to recover both the secret and cover attributes. What interceptors observe in each relation include the attributes stored in plaintext and the share (and possibly index) columns associated with the cover attributes but not any extra column. Thus, they find nothing suspicious. This is the first effective data hiding scheme for relational databases that protects the secrecy of secret attributes.