Towards efficient proofs of retrievability

Proofs of Retrievability (POR) is a cryptographic formulation for remotely auditing the integrity of files stored in the cloud, without keeping a copy of the original files in local storage. In a POR scheme, a user Alice backups her data file together with some authentication data to a potentially dishonest cloud storage server Bob. Later, Alice can periodically and remotely verify the integrity of her data file using the authentication data, without retrieving back the data file. Besides security, performances in communication, storage overhead and computation are major considerations. Shacham and Waters (Asiacrypt '08) gave a fast scheme with O(sλ) bits communication cost and a factor of 1/s file size expansion where λ is the security parameter. In this paper, we incorporate a recent construction of constant size polynomial commitment scheme (Kate, Zaverucha and Goldberg, Asiacrypt '10) into Shacham and Waters scheme. The resulting scheme requires O(λ) communication bits (particularly, 920 bits if a 160 bits elliptic curve group is used or 3512 bits if a 1024 bits modulo group is used) per verification and a factor of 1/s file size expansion. Experiment results show that our proposed scheme is indeed efficient and practical. Our security proof is based on Strong Diffie-Hellman Assumption.