Privacy-Preserving Multi-Keyword Search in Information Networks

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.