Abstract: The lack of effective verifiable deletion mechanism over outsourced data, which will cause the problems of data abuse, user′s privacy leakage, and so on. In this paper, a verifiable outsourced data deletion scheme based on Rank-based Merkle Hash tree (RMHT) for cloud storage is proposed. The proposed scheme guarantees data confidentiality through data encryption with secure data encryption scheme, and implements data integrity auditing by storing the data blocks in RMHT. Finally, the proposed scheme achieves data deletion by removing the corresponding leaf nodes, meanwhile, realizes deletion result verification by rebuilding the RMHT with the remaining data blocks. Security proof demonstrates that this proposed scheme is able to simultaneously realize confidentiality, integrity and verifiable deletion over outsourced data without interacting with a third party. And the simulation experimental results show that compared with the previous verifiable deletion schemes over outsourced data, this proposed scheme is able to greatly reduce the computation overhead.