To save time and money, businesses and individuals have begun outsourcing their data and computations to cloud computing services. These entities would, however, like to ensure that the queries they request from the cloud services are being computed correctly. In this paper, we use the principles of economics and competition to vastly reduce the complexity of query verification on outsourced data. We consider two cases: First, we consider the scenario where multiple non-colluding data outsourcing services exist, and then we consider the case where only a single outsourcing service exists. Using a game theoretic model, we show that given the proper incentive structure, we can effectively deter dishonest behavior on the part of the data outsourcing services with very few computational and monetary resources. We prove that the incentive for an outsourcing service to cheat can be reduced to zero. Finally, we show that a simple verification method can achieve this reduction through extensive experimental evaluation.
  We are interested in the integrity of the query results from an outsourced database service provider. Alice passes a set D of d-dimensional points, together with some authentication tag T, to an untrusted service provider Bob. Later, Alice issues some query over D to Bob, and Bob should produce the query result and a proof based on D and T. Alice wants to verify the integrity of the query result with the help of the proof, using only the private key. In this paper, we consider aggregate query conditional on multidimensional range selection. In its basic form, a query asks for the total number of data points within a d-dimensional range. We are concerned about the number of communication bits required and the size of the tag T. We give a scheme that requires O(d log N) communication bits to authenticate an aggregate count query conditional on d-dimensional range selection, where N is the number of points in the dataset. The security of our scheme relies on Generalized Knowledge of Exponent Assumption proposed by Wu and Stinson [1]. The low communication bandwidth is achieved due to a new functional encryption scheme, which exploits a special property of BBG HIBE scheme [2]. Besides counting, our scheme can be extended to support summing, finding of the minimum and usual (nonaggregate) range selection with similar complexity, and the proposed approach potentially can be applied to other queries by using suitable functional encryption schemes. An increasing number of enterprises outsource their IT services to third parties who can offer these services for a much lower cost due to economy of scale. Quality of service is a major concern in outsourcing. In particular, query integrity, which means that query results returned by the service provider are both correct and complete, must be assured. Previous work requires clients to manage data locally to audit the results sent back by the server, or database engine to be modified for generating authenticated results. In this paper, we introduce a novel integrity audit mechanism that eliminating these costly requirements. In our approach, we insert a small amount of records into an outsourced database so that the integrity of the system can be effectively audited by analyzing the inserted records in the query results. We study both randomized and deterministic approaches for generating the inserted records, as how these records are generated has significant implications for storage and performance. Furthermore, we show that our method is provable secure, which means it can withstand any attacks by an adversary whose computation power is bounded. Our analytical and empirical results demonstrate the effectiveness of our method.  In this paper we propose and analyze a method for proofs of actual query execution in an outsourced database framework, in which a client outsources its data management needs to a specialized provider. The solution is not limited to simple selection predicate queries but handles arbitrary query types. While this work focuses mainly on read-only, compute-intensive (e.g. data-mining) queries, it also provides preliminary mechanisms for handling data updates (at additional costs). We introduce query execution proofs; for each executed batch of queries the database service provider is required to provide a strong cryptographic proof that provides assurance that the queries were actually executed correctly over their entire target data set. We implement a proof of concept and present experimental results in a real-world data mining application, proving the deployment feasibility of our solution. We analyze the solution and show that its overheads are reasonable and are far outweighed by the added security benefits. For example an assurance level of over 95 can be achieved with less than 25 execution time overhead. In data publishing, the owner delegates the role of satisfying user queries to a third-party publisher. As the publisher may be untrusted or susceptible to attacks, it could produce incorrect query results. In this paper, we introduce a scheme for users to verify that their query results are complete (i.e., no qualifying tuples are omitted) and authentic (i.e., all the result values originated from the owner). The scheme supports range selection on key and non-key attributes, project as well as join queries on relational databases. Moreover, the proposed scheme complies with access control policies, is computationally secure, and can be implemented efficiently. In the third-party model for the distribution of data, the trusted data creator or owner provides an untrusted party V with data and integrity verification (IV) items for that data. When a user U gets a subset of the data at D or is already in possession of that subset, U may request from D the IV items that make it possible for U to verify the integrity of its data: D must then provide U with the (hopefully small) number of needed IVs. Most of the published work in this area uses the Merkle tree or variants thereof. For the problem of 2-dimensional range data, the best published solutions require V to store O(n log n) IV items for a database of n items, and allow a user IA to be sent only O(log n) of those IVs for the purpose of verifying the integrity of the data it receives from D (regardless of the size of lA's query rectangle). For data that is modeled as a 2-dimensional grid (such as GIS or image data), this paper shows that better bounds are possible: The number of IVs stored at D (and the time it takes to compute them) can be brought down to O(n), and the number of IVs sent to IA for verification can be brought down to a constant. Database outsourcing requires that a query server constructs a proof of result correctness, which can be verified by the client using the data owner's signature. Previous authentication techniques deal with range queries on a single relation using an authenticated data structure (ADS). On the other hand, authenticated join processing is inherently more complex than ranges since only the base relations (but not their combination) are signed by the owner. In this paper, we present three novel join algorithms depending on the ADS availability: (i) Authenticated Indexed Sort Merge Join (AISM), which utilizes a single ADS on the join attribute, (ii) Authenticated Index Merge Join (AIM) that requires an ADS (on the join attribute) for both relations, and (iii) Authenticated Sort Merge Join (ASM), which does not rely on any ADS. We experimentally demonstrate that the proposed methods outperform two benchmark algorithms, often by several orders of magnitude, on all performance metrics, and effectively shift the workload to the outsourcing service. Finally, we extend our techniques to complex queries that combine multi-way joins with selections and projections.  In the Outsourced Database (ODB) model, entities outsource their data management needs to a third-party service provider. Such a service provider offers mechanisms for its clients to create, store, update, and access (query) their databases. This work provides mechanisms to ensure data integrity and authenticity for outsourced databases. Specifically, this article provides mechanisms that assure the querier that the query results have not been tampered with and are authentic (with respect to the actual data owner). It investigates both the security and efficiency aspects of the problem and constructs several secure and practical schemes that facilitate the integrity and authenticity of query replies while incurring low computational and communication costs.