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 19 Aug 2015
Contact author: jiaxu2001 at gmail com
Available format(s): PDF | BibTeX Citation
Note: Major updates.
(1) Significantly improved system formulation.
(2) Complete and rigorous security proof.
(3) Remove "privacy-preserving" feature, to make the algorithm and proof simpler and easier to understand.
Version: 20150819:075948 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]