Cloud storage, one of the most attractive services offered by cloud computing, can provide users with boundless storage capacity. Thus, users can outsource their data to the cloud server for greatly saving local storage overhead. However, in cloud storage, due to the separation between data ownership and management, users lose the direct control over their outsourced data, resulting in plenty of security and privacy problems. In this project propose on the problem of verifiable outsourced data deletion, which is important but received less attention in industry and academia. We propose an efficient fine-grained outsourced data deletion scheme based on invertible Bloom filter, which can also achieve public and private verifiability of the storage and deletion results. If the cloud server does not honestly maintain/delete the data and generate corresponding evidences, users can easily detect the cloud server’s malicious behaviors with an overwhelming probability. Meanwhile, in data deletion and deletion result verification processes, the computational complexity is independent of the number of outsourced data blocks, which makes the proposed scheme be suitable for large-scale data deletion scenario. Moreover, we provide the detailed security analysis and performance evaluation, which can respectively demonstrate the security and practicability of the proposed scheme.