Privacy-preserving search on encrypted data

Abstract

As the value of data has been gradually discovered, more and more data-as-a-service systems spring up. With the increasing awareness of privacy, data has to be encrypted for various considerations. For example, in cloud computing, to prevent malicious cloud server stealing sensitive information, before outsourcing, data should be encrypted. On the other hand, in data trading, encryption is also required by the data owner to avoid revealing the unpaid database. Simple encryption protects the confidentiality of data but prevents one from efficient computation over ciphertext.

In this thesis, we investigate the problem of privacy-preserving search over encrypted data in several applications: (i) searching over outsourced private-key encrypted data; (ii) oblivious keyword search; (iii) call for search on the blockchain. The first two settings are two existing topics that have been widely studied. We develop more powerful functionalities and enhanced security for these two applications. The third setting is a new search model we propose.

For searching over outsourced private-key encrypted data, our work focus on the pattern matching problem in the database system. We enrich the search capability to support boolean query of substrings with wildcards. We extend the protocol to enable the system to automatically determine the optimized $k$ value for top-$k$ query. We also adopt and implement another encryption method that supports secure calculation on feature vector converted from strings can contain floating point numbers. We prove our construction is secure. The experiment results confirm that our scheme can achieve high search quality.

For the oblivious keyword search problem, we observe a leakage-abuse attack on the recent work that the adversary can abuse the leakage from a queried keyword to decrypt the results of another keyword. We, therefore, propose a scheme with enhanced security. We prove the security of our protocol and conduct experiments to show its efficiency.

Finally, we propose a ``Call for Search'' model on the blockchain. Our model enables the user to broadcast the search query and multiple data owners can help search and answer actively over their dataset securely and efficiently. We consider a set of security issues that might occur in this new model and provide schemes to defend against them. Our scheme is proved to be secure. For practical considerations, we implement our protocols and deploy smart contracts on the private network of the Ethereum platform. The evaluation results show that our construction can work smoothly on current blockchain platforms.

To conclude, we tackle the private search problems in three different application models. We consider the improvements concerning functionality, security, and efficiency and provide solutions to throw light on how to address these issues in similar problems.