Cryptology ePrint Archive: Report 2013/789

Proofs of Data Possession and Retrievability Based on MRD Codes

Shuai Han and Shengli Liu and Kefei Chen and Dawu Gu

Abstract: Proofs of Data Possession (PoDP) scheme is essential to data outsourcing. It provides an efficient audit to convince a client that his/her file is available at the storage server, ready for retrieval when needed. An updated version of PoDP is Proofs of Retrievability (PoR), which proves the client's file can be recovered by interactions with the storage server. We propose a PoDP/PoR scheme based on Maximum Rank Distance (MRD) codes. The client file is encoded block-wise to generate homomorphic tags with help of an MRD code. In an audit, the storage provider is able to aggregate the blocks and tags into one block and one tag, due to the homomorphic property of tags. The algebraic structure of MRD codewords enables the aggregation to be operated over a binary field, which simplifies the computation of storage provider to be the most efficient XOR operation. We also prove two security notions, unforgeability served for PoDP and soundness served for PoR with properties of MRD codes. Meanwhile, the storage provider can also audit itself to locate and correct errors in the data storage to improve the reliability of the system, thanks to the MRD code again.

Category / Keywords: cryptographic protocols / data integrity, dependable storage, error localization, cloud computing

Date: received 26 Nov 2013, last revised 14 Aug 2016

Contact author: dalen17 at sjtu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20160815:052501 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]