Paper 2013/645

FlexDPDP: FlexList-based Optimized Dynamic Provable Data Possession

Ertem Esiner, Adilet Kachkeev, Samuel Braunfeld, Alptekin Küpçü, and Öznur Özkasap

Abstract

With increasing popularity of cloud storage, efficiently proving the integrity of data stored at an untrusted server has become significant. Authenticated Skip Lists and Rank-based Authenticated Skip Lists (RBASL) have been used to provide support for provable data update operations in cloud storage. However, in a dynamic file scenario, an RBASL falls short when updates are not proportional to a fixed block size; such an update to the file, even if small, may result in O(n) block updates to the RBASL, for a file with n blocks. To overcome this problem, we introduce FlexList: Flexible Length-Based Authenticated Skip List. FlexList translates variable-size updates to O(u/B) insertions, removals, or modifications, where u is the size of the update, and B is the (average) block size. We further present various optimizations on the four types of skip lists (regular, authenticated, rank-based authenticated, and FlexList). We build such a structure in O(n) time, and parallelize this operation for the first time. We compute one single proof to answer multiple (non-)membership queries and obtain efficiency gains of 35%, 35% and 40% in terms of proof time, energy, and size, respectively. We propose a method of handling multiple updates at once, achieving efficiency gains of up to 60% at the server side and 90% at the client side. We also deployed our implementation of FlexDPDP (DPDP with FlexList instead of RBASL) on the PlanetLab, demonstrating that FlexDPDP performs comparable to the most efficient static storage scheme (PDP), while providing dynamic data support.

Note: Extended version with full pseudocode and comparison with PDP and DPDP.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
cloud storageskip listauthenticated dictionaryprovable data possessiondata integrity
Contact author(s)
akupcu @ ku edu tr
History
2015-02-10: revised
2013-10-10: received
See all versions
Short URL
https://ia.cr/2013/645
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/645,
      author = {Ertem Esiner and Adilet Kachkeev and Samuel Braunfeld and Alptekin Küpçü and Öznur Özkasap},
      title = {FlexDPDP: FlexList-based Optimized Dynamic Provable Data Possession},
      howpublished = {Cryptology ePrint Archive, Paper 2013/645},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/645}},
      url = {https://eprint.iacr.org/2013/645}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.