| Database outsourcing is an important emerging trend which involves data owners delegating their data management needs to an external service provider. An increasing number of enterprises outsource their IT functions or business processes to third-parties who offer these services with a lower cost due to the economy of scale. Since a service provider is almost never fully trusted, quality of service has become a major concern in outsourcing. However, the potentially explosive growth of database outsourcing is hampered by security concerns, namely data privacy and query integrity of outsourced databases. Most IT services evolve around data processing, which poses a special requirement on data and query integrity:the clients must be ensured that query results returned by the service provider are both correct and complete. Previous work requires clients to manage data locally to audit the results sent back by the server, or the server to modify the database engine for generating authenticated results. In this thesis, we introduce a novel integrity audit mechanism that bypasses these costly requirements. 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. |
