Study On Efficient Search And Secure Audit For Outsourced Data In Cloud Computing

Cloud computing, the new term for the long dreamed vision of computing as a utility, can offers plenty of benefits for real-world applications, such as on-demand self-service, ubiquitous network access, rapid resource elasticity, usage-based pricing, outsourcing, etc. One of the fundamental advantages of cloud computing is the so-called outsourcing paradig-m. That is, the resource-constrained users can enjoy seemly unlimited computation re-sources by outsourcing computation-intensive task to the cloud server. As the important branch of outsourcing computation, database outsourcing has attracted considerable interest from academic community, which can enables the data owner to delegate the database man-agement to a cloud server that provides various database services to different users. Despite the tremendous benefits, the outsourced database paradigm inevitably suffers from some new security challenges. Specifically, due to the self-interest and hardware/software fail-ures, the dishonest cloud servers may execute only a fraction of search operations honestly and/or return an incorrect and/or incomplete result of the query requests. What’s worse, s-ince users no longer possess data copy in local, it is difficult to check the integrity of search result by himself. Therefore, one of the most critical challenges is how to effectively solve the integrity auditing of outsourced database.In this dissertation, we focus on the key issues in secure data outsourcing scenario, mainly including:(1) How to achieve verifiable search for outsourced database; (2) How to realize efficient approximate nearest neighbor search in high-dimensional space; (3) How to support user traceability in secure data deduplication. The main contributions of our work can be summarized as follows:1. We make the first attempt to formally address the problem of integrity of search result in outsourced database when an empty set is returned. By introducing a new cryp-tographic primitive-Bloom Filter Tree (BFT), we propose a new verifiable auditing scheme for outsourced database, which can simultaneously achieve the correctness and completeness of search results even if the cloud server intentionally returns an empty set. Compared with the existing solutions, the proposed scheme is also effec-tive even in the encrypted outsourced database which ensures the confidentiality of the sensitive data. (Chapter 3)2. We further study the problem of verifiable search for outsourced database. By lever-aging invertible Bloom filter, we present a flexible and verifiable search scheme for outsourced database. The proposed scheme can achieve verifiability of search result while efficient data update. That is, it does not require any change for the current database when a new data tuple is inserted. This makes it can be applicable to dynam-ic outsourced database scenario. In addition, we extend the proposed construction to multi-user setting by incorporating multi-party searchable encryption. By adopting an index contains separate searchable contents for the data owner and other authorized users, the extended scheme can effectively resist collusion attack between the cloud server and any malicious users. (Chapter 4)3. We investigate the approximate nearest neighbor (ANN) search for outsourced database. By incorporating locality-sensitive hashing and order-preserving encryp-tion, we propose a novel ANN search scheme over encrypted high-dimensional data. The proposed construction can simultaneously achieve efficient ANN search and data privacy, while supporting efficient range query over encrypted data. (Chapter 5)4. We focus on the problem of tracing the identities of malicious users in secure data deduplication. We introduce user traceability functionality in secure data deduplica-tion for the first time. It enables to trace a malicious user in case of duplicate faking attack. We propose a concrete deduplication scheme called TrDup, which enables to trace the identities of malicious users. More specifically, each user generates a kind of anonymous signature for the uploaded file-a variant of traceable signature scheme is used. Once a duplicate faking attack happens, the tracing agent can reveal the identity of the malicious user without revealing identities of other users or linking their files in the cloud system. (Chapter 6)...