Cryptology ePrint Archive: Report 2012/682

Proofs of Retrievability with Public Verifiability and Constant Communication Cost in Cloud

Jiawei Yuan and Shucheng Yu

Abstract: For data storage outsourcing services, it is important to allow data owners to efficiently and securely verify that the storage sever stores their data correctly. To address this issue, several proof-of-retrievability (POR) schemes have been proposed wherein a storage sever must prove to a verifier that all of a client's data are stored correctly. While existing POR schemes offer decent solutions addressing various practical issues, they either have a non-trivial (linear or quadratic) communication complexity, or only support private verification, i.e., only the data owner can verify the remotely stored data. It remains open to design a POR scheme that achieves both public verifiability and constant communication cost simultaneously.

In this paper, we solve this open problem and propose the first POR scheme with public verifiability and constant communication cost: in our proposed scheme, the message exchanged between the prover and verifier is composed of a constant number of group elements; different from existing private POR constructions, our scheme allows public verification and releases the data owners from the burden of staying online. We achieved these by tailoring and uniquely combining techniques such as constant size polynomial commitment and homomorphic linear authenticators. Thorough analysis shows that our proposed scheme is efficient and practical. We prove the security of our scheme based on the Computational Diffie-Hellman Problem, the Strong Diffie-Hellman assumption and the Bilinear Strong Diffie-Hellman assumption.\end{abstract}

Category / Keywords: public-key cryptography / Proofs of Retrievability, Cloud Storage, Public Verification, Integrity Check, Constant Communication, Polynomial Commitment

Date: received 3 Dec 2012, last revised 7 Mar 2013

Contact author: jxyuan at ualr edu

Available format(s): PDF | BibTeX Citation

Version: 20130308:040309 (All versions of this report)

Short URL: ia.cr/2012/682

Discussion forum: Show discussion | Start new discussion