Mutual Secure Search Through Additive Homomorphic Encryption

In the information age, organizations, corporations and individuals own large amounts of data and have great demands to exchange data. With the emergence of service providers for data query, query processing that preserves both the query privacy at the client and the data privacy at the server is a new research problem. This problem exists in many practical applications. However, most existing studies focus on either the data privacy or the query privacy separately. Although secure multiparty computation is a proper computing paradigm for this problem, it has significant communication overheads and computation overheads, thus unable to scale up to large datasets.In this paper, we combine conditional oblivious transfer and homomorphic encryption in cryptography together with database indexing techniques for private search on key-value datasets. In the context of private search on key-value stores, we first present an oblivious index traversal framework. By designing this framework, we can ensure that the server cannot trace the index traversal path of a query during evaluation, thus protecting the privacy of client, and the server returns the query value only to protect the data privacy of server.The framework is generic and can support a variety of query types with a suitable homomorphic encryption algorithm in place. Based on this framework, we propose secure protocols for classic key search queries on multi-level indexes like B+-tree and R-tree indexes. Then we analyzed the security of the framework and proved it. At last, we analyzed the performance of the proposed framework together with optimization. The results show that the performance is efficient under various parameter settings.