Android is the primary target for mobile malware. To protect users, phone vendors (e.g., Samsung and Huawei) usually leverage third-party security service providers (e.g., VirusTotal and Qihoo 360) to detect malicious apps in app stores and collect apps' runtime behaviors on users' phones to further spot malware missed in the previous step. However, this practice could cause privacy concerns to phone vendors, users and security service providers. Specifically, phone vendors do not want to share apps (including the paid ones) with security service providers, while the latter do not want to share the malware signatures with the former. Moreover, users do not want to expose apps' runtime behaviors to third parties. These concerns would cause a real dilemma for each involved party. In this paper, we propose a privacy-preserving malware detection system for Android, in which the privacy (or assets) of phone vendors, users, and security service providers are protected. It detects malicious apps in phone vendor's app stores and on users' phones, without directly sharing apps, apps' runtime behaviors, and malware signatures to other parties. We implement a prototype system called PPMDroid and apply several optimizations to save bandwidth and speed up the process. Extensive evaluation results with real malware samples demonstrate the effectiveness and efficiency of our system.