The ongoing threat of malware has raised significant security and privacy concerns. Motivated by these issues, the cloud-based detection system is of increasing interest to detect large-scale malware as it releases the burden of client and improves the detection efficiency. However, most existing cloud-based detection systems overlook the data privacy protection during the malware detection. In this paper, we propose a cloud-based anti-malware system named PriMal, which protects the data privacy of both the cloud server and the client, while still achieves usable detection performance. In the PriMal, a newly designed private malware signature set intersection (PMSSI) protocol is involved to enable both the cloud server and client to achieve malware confirmation without revealing the data privacy in semi-honest model. Moreover, we propose the relevant signature engine to reduce the detection range and overhead. The experimental results show that PriMal offers a practical approach to achieve both usable malware detection and strong data privacy preservation.