Abstract: The integrity of user's data is one of the problems which is most concerned when users using cloud storage service to store their data and files. The data users commit to cloud storage servers may be lost and modified. Users need a technology to check the integrity and validity of their data and files when accessing them. By considering the limit of the calculation resource of users and the security request of cloud storage service, an integrity verification protocol based on improved skip lists and short signature is proposed, which can support dynamic operation. By combining accessible counting and skip lists, this protocol can support inserting and deleting data block at any position efficiently. The analysis and experiment show that the proposed protocol is security and efficient.