Biblio

Nowadays database outsourcing has become business owners' preferred option and they are benefiting from its flexibility, reliability, and low cost. However, because database service providers cannot always be fully trusted and data owners will no longer have a direct control over their own data, how to make the outsourced data secure becomes a hot research topic. From the data integrity protection aspect, the client wants to make sure the data returned is correct, complete, and up-to-date. Previous research work in literature put more efforts on data correctness, while data completeness is still a challenging problem to solve. There are some existing works that tried to protect the completeness of data. Unfortunately, these solutions were considered not fully solving the problem because of their high communication or computation overhead. The implementations and limitations of existing works will be further discussed in this paper. From the data confidentiality protection aspect, order-preserving encryption (OPE) is a widely used encryption scheme in protecting data confidentiality. It allows the client to perform range queries and some other operations such as GROUP BY and ORDER BY over the OPE encrypted data. Therefore, it is worthy to develop a solution that allows user to verify the query completeness for an OPE encrypted database so that both data confidentiality and completeness are both protected. Inspired by this motivation, we propose a new data completeness protecting scheme by inserting fake tuples into databases. Both the real and fake tuples are OPE encrypted and thus the cloud server cannot distinguish among them. While our new scheme is much more efficient than all existing approaches, the level of security protection remains the same.

As cloud storage and computing gains popularity, data entrusted to the cloud has the potential to be exposed to more people and thus more vulnerable to attacks. It is important to develop mechanisms to protect data privacy and integrity so that clients can safely outsource their data to the cloud. We present a method for ensuring data completeness which is one facet of the data integrity problem. Our approach converts a standard database to a Completeness Protected Database (CPDB) by inserting some semantic fake data before outsourcing it to the cloud. These fake data are initially produced using our generating function which uses Order Preserving Encryption, which allows the user to be able to regenerate these fake data and match them to fake data returned from a range query to check for completeness. The CPDB is innovative in the following ways: (1) fake data is deterministically generated but is semantically indistinguishable from other existing data; (2) since fake data is generated by deterministic functions, data owners do not need to locally store the fake data that have been inserted, instead they can re-generate fake data using the functions; (3) no costly data encryption/signature is used in our scheme compared to previous work which encrypt/sign the entire database.