Existing provable data possession mechanisms mainly focus on the single-cloud-tenant scenario. When extended to multiple-cloud-tenant scenario, they are infeasible to be deployed in real world due to extremely high computation costs arising from processing a large volume of data. To address this issue, we present a secure and efficient provable data possession protocol named PDPMT. Similar to the mechanisms of this field, PDPMT is based on public-key digital signature techniques. However, compared to other well-known approaches, PDPMT organizes multiple data blocks into clusters and designs a novel signing algorithm which can reduce the computation costs significantly. Experimental results show that the proposed protocol is feasible for real-world applications.