Privacy-Preserving Multi-Keyword Search in Information Networks
Yuzhe Tang, Ling Liu · IEEE Transactions on Knowledge and Data Engineering · 2015
In emerging information networks, it is crucially important to provide efficient search on distributed documents while preserving their owners' privacy, for which privacy preserving indexes or PPI presents a possible solution. An understudied problem for the PPI techniques is how to provide differentiated privacy preservation in the presence of multi-keyword document search. The differentiation is necessary as terms and phrases bear innate differences in their semantic meanings. In this paper, we present ϵ-MPPI, the first work to provide the distributed document search with quantitatively differentiated privacy preservation. In the design of ϵ-MPPI, we identified a suite of challenging problems and proposed novel solutions. For one, we formulated the quantitative privacy computation as an optimization problem that strikes a balance between privacy preservation and search efficiency. We also addressed the challenging problem of secure ϵ-MPPI construction in the multi-domain information network which lacks mutual trusts between domains. Towards a secure ϵ-MPPIconstruction with practically acceptable performance, we proposed to optimize the performance of secure multi-party computations by making a novel use of secret sharing. We implemented the ϵ-MPPI construction protocol with a functioning prototype. We conducted extensive experiments to evaluate the prototype's effectiveness and efficiency based on a real-world dataset.