Cryptology ePrint Archive: Report 2014/395

Lightweight and Privacy-Preserving Delegatable Proofs of Storage

Jia Xu and Anjia Yang and Jianying Zhou and Duncan S. Wong

Abstract: Proofs of storage (POR or PDP) is a cryptographic tool, which enables data owner or third party auditor to audit integrity of data stored remotely in a cloud storage server, without keeping a local copy of data or downloading data back during auditing. We observe that all existing publicly verifiable POS schemes suffer from a serious drawback: It is extremely slow to compute authentication tags for all data blocks, due to many expensive group exponentiation operations. Surprisingly, it is even much slower than typical network uploading speed, and becomes the bottleneck of the setup phase of the POS scheme. We propose a new variant formulation called "Delegatable Proofs of Storage". In this new relaxed formulation, we are able to construct POS schemes, which on one side is as efficient as private key POS schemes, and on the other side can support third party auditor and can switch auditors at any time, close to the functionalities of publicly verifiable POS schemes. Compared to traditional publicly verifiable POS schemes, we speed up the tag generation process by at least several hundred times, without sacrificing efficiency in any other aspect. Like many existing schemes, we can also speed up our tag generation process by N times using N CPU cores in parallel. We prove that our scheme is sound under Bilinear Strong Diffie-Hellman Assumption, and it is privacy preserving against auditor under Discrete Log Assumption. Both proofs are given in standard model.

Category / Keywords: cryptographic protocols / Proof of Storage, Provable Data Possession, Homomorphic Authentication Tag, Privacy-Preserving, Applied Cryptography, Cloud Storage

Date: received 30 May 2014, last revised 2 May 2016

Contact author: jiaxu2001 at gmail com

Available format(s): PDF | BibTeX Citation

Note: Some refinement in writing.

Version: 20160502:150926 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]