Research On R-ASL Algorithm And Its Application In Dynamic Provable Data Possession

To provide users with vast amounts of on-demand storage services is one of the important applications of cloud computing. Users often make their large data, such as archive file, astronomical data and meteorological data stored and managed by the cloud service provider (CSP). Because users’ data is placed within the control domain of the CSP rather than the users’, it is difficult for users to believe that the data can not be tempered by the CSP or the system administrator, that is, the users can not make sure whether the data stored in the CSP is integrated. The traditional network security mechanisms can not meet the requirements for data integrity verification in cloud storage environment.The current solutions to verify the data integrity in cloud storage environment are mainly devided into two categories:1) Users download all the data and then verify the integrity of the data, but users have to pay to CSP for downloading. At the same time, this method will cause high network bandwidth and users’ storage space;2) Users use provable data possession(PDP) scheme. The scheme is based on certain sorts of knowledge proof, and allows users verify the integrity of the data without downloading all the data. At the same time, the scheme provides high probability guarantee. However, this method only supports static data, and it isn’t in favor of dynamic data.To solve the problem that current PDP scheme doesn’t support dynamic data, this paper presents a dynamic provable data possession(DPDP) scheme. This scheme allows users verify the integrity of data and update(such as insert, delete and modify) the data. In order to construct the DPDP scheme, this paper proposes a new authenticated data structure. The new structure is rank-based authenticated skip lists(R-ASL). R-ASL incorporates the concept of rank and adopts a new hash function. This paper first introduces how to compute the node value through the new hash function and how to construct the R-ASL which is implemented in the DPDP scheme. And then, the algorithm of inserting, modifying and removing in the R-ASL is presented. At last, this paper implements the DPDP scheme and evaluates performance of the DPDP scheme. The experimental analysis shows that the DPDP scheme’s communication cost and computational cost from the server due to updating is acceptable.