With the rapid growth of mobile cloud computing, participatory sensing emerges as a new paradigm to explore our physical world at an unprecedented fine granularity by recruiting the pervasive sensor-enabled smart phones. While extensive optimization has been performed in the literature to coordinate the sensing activity of the cloud-based sensing server (or platform) and the participating smart phones so as to maximize the efficiency of participatory sensing, the privacy issue in the optimization has been largely overlooked. In this paper, we propose a novel privacy-preserving optimization framework that allows both the cloud-based platform and mobile users to share data for the formulation and solution of the optimization, but without revealing sensitive information that may lead to privacy leakage of each other. Our method is built upon a privacypreserving version of the well-known NP-hard weighted setcoverage problem. To accommodate privacy requirements in this framework, our solution uses a modified bloom filter along with a Diffie-Hellman-type exchange protocol among all participants for data aggregation, sharing, and presentation. Through extensive simulation we evaluate the privacy strength of the proposed approach and also verify its effectiveness and low overhead.