Abstract: With the development of cloud computing technology, more individuals and organizations have chosen cloud services to store and maintain their data and reduce the burden on local storage and corresponding maintenance costs. However, although the cloud computing infrastructure is more powerful and reliable than personal computing devices, the cloud storage server is not completely trusted due to various internal and external threats; therefore, users need to regularly check whether their data stored in the cloud server are intact. Therefore, in recent years, researchers have proposed a variety of schemes for data integrity auditing in cloud storage. Among them, in a part of public auditing schemes for cloud storage based on homomorphic authenticators, random sampling of data blocks, and random masking techniques, users need to store and maintain a two-dimensional (2D) table related to the index information of data blocks in the file. When a user’s outsource data need to be frequently updated to avoid forgery attacks due to the similar index value of data block being reused, the design and maintenance of the 2D table become cumbersome. In this study, to solve the abovementioned problem, an index–stub table structure was first proposed, which is simple and easy to maintain. On the basis of this structure, a third-party auditor auditing scheme with a privacy-preserving property was proposed for cloud storage. This scheme can effectively support various remote dynamic operations for outsource data at the block level. Then, a formal security proof for data integrity guarantee provided by the scheme was given under the random oracle model. A formal security analysis was also given for the privacy-preserving property of the audit protocol. Finally, the performance of the scheme was theoretically analyzed and compared with relevant experiments. Results indicate that the scheme has high efficiency.