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 $\epsilon$ -mPPI , the first work to provide the distributed document search with quantitatively differentiated privacy preservation. In the design of $\epsilon$ -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 $\epsilon$ -mPPI construction in the multi-domain information network which lacks mutual trusts between domains. Towards a secure $\epsilon$ -mPPI construction 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 $\epsilon$ -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.