Lightweight delegatable proofs of storage

Proofs of Storage (including Proofs of Retrievability and Provable Data Possession) 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 a POS scheme, which on one side is as efficient as privately verifiable POS schemes, and on the other side can support third party auditor and can efficiently 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 approximately N times using N CPU cores in parallel, before I/O cost becomes the bottleneck. We prove that our scheme is sound under Bilinear Strong Diffie-Hellman Assumption in standard model.