Privacy-Preserving Multi-Keyword Search in Information Networks

Yuzhe Tang, Ling Liu

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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.

Original languageEnglish (US)
Article number7052326
Pages (from-to)2424-2437
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number9
StatePublished - Sep 1 2015


  • Privacy
  • federated databases
  • indexing
  • information networks
  • secure multi-party computations

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Privacy-Preserving Multi-Keyword Search in Information Networks'. Together they form a unique fingerprint.

Cite this