Towards secure and practical query services over encrypted data in cloud computing

The rapid development of cloud computing enables the individuals and enterprises to outsource local data to a cloud server and leverage the server's resources for various query services. Although such service outsourcing paradigm can bring tremendous benefits, many security and privacy issues are raised and become the major concern of cloud computing practices. Encrypting the sensitive user information (e.g. data and queries) certainly ensures the confidentiality. However, encryption raises new challenges of performing query process over ciphertexts and are frequently at odds with the practical performance. In this thesis, we attempt to address the challenges of realizing secure and practical query services in the public cloud. In particular, we pay attention to two critical query services, i.e. searching and retrieval. Our first work centers on the promising but challenging task of similarity search over encrypted data in the cloud. Mitigating the performance bottlenecks of client-side filtering in existing solutions necessitates revealing similarity scores to the server, which requires not only new cryptographic schemes to compute plaintext similarity scores from ciphertexts but also new solutions to deal with potential security vulnerabilities raised by disclosure of similarity scores. We propose novel solutions to these challenges as well as develop a new pruning approach to speed up query processing. Our next two works target at secure data retrieval services, which aim to efficiently retrieve outsourced data without disclosing access patterns. Hiding access patterns widely relies on the usage of oblivious shuffles (OS) for erasing the correlations between outsourced data and their physical locations in the server. Unfortunately, all existing OS methods suffer from the bottlenecks of moving outsourced data from the server to the client for shuffling the data or peeling off extra encryption layers. We believe that such movement-based oblivious shuffling violates key principles of the outsourcing model. To eliminate this void, we develop the first OS method that completely avoids the movement of outsourced data, regardless of the number of shuffles. On the basis of this work, we present an efficient solution to support secure data retrieval services over outsourced databases with practical access pattern protection.