FlexDPDP: Flexlist-Based Optimized Dynamic Provable Data Possession

Abstract

With increasing popularity of cloud storage, efficiently proving the integrity of data stored on 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 based on block indices 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) updates on the data structure for a file with n blocks.

To overcome this problem, we introduce FlexList, a 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 (dynamic provable data possession (DPDP) with FlexList instead of RBASL) on PlanetLab, demonstrating that FlexDPDP performs comparable to the most efficient static storage scheme (provable data possession (PDP)) while providing dynamic data support.

References

1. Ittai Abraham, Gregory Chockler, Idit Keidar, and Dahlia Malkhi. 2006. Byzantine Disk Paxos: Optimal resilience with Byzantine shared memory. Distributed Computing 18, 5, 387--408. DOI:http://dx.doi.org/10.1007/s00446-005-0151-6
2. M. Adelson-Velskii and E. M. Landis. 1963. An algorithm for the organization of information. Defense Technical Information Center 146, 263--266.
3. Aris Anagnostopoulos, Michael T. Goodrich, and Roberto Tamassia. 2001. Persistent authenticated dictionaries and their applications. In Proceedings of the 2001 ISC Conference (ISC’01).
4. Giuseppe Ateniese, Randal Burns, Reza Curtmola, Joseph Herring, Osama Khan, Lea Kissner, Zachary Peterson, and Dawn Song. 2011. Remote data checking using provable data possession. ACM Transactions on Information and System Security 14, 1, Article No. 12. DOI:http://dx.doi.org/10.1145/1952982.1952994
5. Giuseppe Ateniese, Seny Kamara, and Jonathan Katz. 2009. Proofs of storage from homomorphic identification protocols. In Proceedings of the 2009 ASIACRYPT Conference (ASIACRYPT’09).
6. Giuseppe Ateniese, Roberto Di Pietro, Luigi V. Mancini, and Gene Tsudik. 2008. Scalable and efficient provable data possession. In Proceedings of the 2008 SecureComm Conference (SecureComm’08). http://eprint.iacr.org/2008/114
7. Giuseppe Di Battista and Bernardo Palazzi. 2007. Authenticated relational tables and authenticated skip lists. In Proceedings of the 2007 DBSec Conference (DBSec’07).
8. Rudolf Bayer. 1972. Symmetric binary b-trees: Data structure and maintenance. Acta Informatica 1, 290--306. http://www.springerlink.com/content/qh51m2014673513j/.
9. Alysson Bessani, Miguel Correia, Bruno Quaresma, Fernando André, and Paulo Sousa. 2013. DepSky: Dependable and secure storage in a cloud-of-clouds. ACM Transactions on Storage 9, 4, Article No. 12.
10. Kaouthar Blibech and Alban Gabillon. 2005. CHRONOS: An authenticated dictionary based on skip lists for timestamping systems. In Proceedings of the 2005 SWS Conference (SWS’05).
11. Kaouthar Blibech and Alban Gabillon. 2006. A new timestamping scheme based on skip lists. In Proceedings of the 2006 ICCSA Conference (ICCSA’06).
12. Hans-J. Boehm, Russ Atkinson, and Michael Plass. 1995. Ropes: An alternative to strings. Software: Practice and Experience 25, 12, 1315--1330.
13. Boost C++ Libraries. 2015. Boost Asio Library. Retrieved June 27, 2016, from http://www.boost.org/doc/libs.
14. Kevin D. Bowers, Ari Juels, and Alina Oprea. 2009. HAIL: A high-availability and integrity layer for cloud storage. In Proceedings of the 2009 CCS Conference (CCS’09). 187--198. DOI:http://dx.doi.org/10.1145/1653662.1653686
15. Brownie Points Project. 2016. Brownie Cashlib Cryptographic Library. Retrieved June 27, 2016, from http://github.com/brownie/cashlib.
16. Christian Cachin, Idit Keidar, and Alexander Shraer. 2009. Trusting the cloud. ACM SIGACT News 40, 2, 81--86.
17. Christian Cachin and Stefano Tessaro. 2006. Optimal resilience for erasure-coded Byzantine distributed storage. In Proceedings of the 2006 DSN Conference (DSN’06). IEEE, Los Alamitos, CA, USA.
18. David Cash, Alptekin Küpçü, and Daniel Wichs. 2013. Dynamic proofs of retrievability via oblivious RAM. Journal of Cryptology (2015). DOI:10.1007/s00145-015-9216-2
19. Nishanth Chandran, Bhavana Kanukurthi, and Rafail Ostrovsky. 2013. Locally updatable and locally decodable codes. In Proceedings of the 2014 TCC Conference (TCC'14).
20. Gregory Chockler, Rachid Guerraoui, Idit Keidar, and Marko Vukolic. 2009. Reliable distributed storage. Computer 42, 4, 60--67.
21. Gregory Chockler and Dahlia Malkhi. 2002. Active disk Paxos with infinitely many processes. In Proceedings of the 2002 ACM PODC Conference (PODC’02). ACM, New York, NY.
22. Scott A. Crosby and Dan S. Wallach. 2011. Authenticated dictionaries: Real-world costs and trade-offs. ACM Transactions on Information and System Security 14, 2, Article No. 17.
23. Reza Curtmola, Osama Khan, Randal Burns, and Giuseppe Ateniese. 2008. MR-PDP: Multiple-replica provable data possession. In Proceedings of the 2008 ICDCS Conference (ICDCS’08).
24. Yevgeniy Dodis, Salil Vadhan, and Daniel Wichs. 2009. Proofs of retrievability via hardness amplification. In Proceedings of the 2009 TCC Conference (TCC’09). http://eprint.iacr.org/2009/041.pdf.
25. C. Chris Erway, Alptekin Küpçü, Charalampos Papamanthou, and Roberto Tamassia. 2015. Dynamic provable data possession. ACM Transactions on Information and System Security 17, 4, Article No. 15. http://eprint.iacr.org/2008/432.
26. Ertem Esiner, Alptekin Küpçü, and Öznur Özkasap. 2014. Analysis and optimization on FlexDPDP: A practical solution for dynamic provable data possession. In Proceedings of the 2014 ICC Conference (ICC’14).
27. Mohammad Etemad and Alptekin Küpçü. 2013a. Database outsourcing with hierarchical authenticated data structures. In Proceedings of the 2013 ICISC Conference (ICISC’13).
28. Mohammad Etemad and Alptekin Küpçü. 2013b. Transparent, distributed, and replicated dynamic provable data possession. In Proceedings of the 2013 ACNS Conference (ACNS’13).
29. Eli Gafni and Leslie Lamport. 2003. Disk Paxos. Distributed Computing 16, 1, 1--20. DOI:http://dx.doi.org/10.1007/s00446-002-0070-8
30. Michael T. Goodrich, Charalampos Papamanthou, and Roberto Tamassia. 2007. On the cost of persistence and authentication in skip lists. In Proceedings of the 2007 WEA Conference (WEA’07). 94--107.
31. Michael T. Goodrich, Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos. 2008. Athos: Efficient authentication of outsourced file systems. In Proceedings of the 2008 ISC Conference (ISC’08).
32. Michael T. Goodrich and Roberto Tamassia. 2001. Efficient Authenticated Dictionaries with Skip Lists and Commutative Hashing. Technical Report. Johns Hopkins Information Security Institute.
33. Michael T. Goodrich, Roberto Tamassia, and Andrew Schwerin. 2001. Implementation of an authenticated dictionary with skip lists and commutative hashing. In Proceedings of the 2001 DARPA Conference (DARPA’01).
34. Garth Goodson, Jay Wylie, Gregory Ganger, and Micheal Reiter. 2004. Efficient Byzantine-tolerant erasure-coded storage. In Proceedings of the 2004 DSN Conference (DSN’04).
35. James Hendricks, Gregory R. Ganger, and Michael K. Reiter. 2007. Low-overhead Byzantine fault-tolerant storage. In Proceedings of the 2007 ACM SOSP Conference (SOSP’07). ACM, New York, NY.
36. Prasad Jayanti, Tushar Deepak Chandra, and Sam Toueg. 1998. Fault-tolerant wait-free shared objects. Journal of the ACM 45, 3, 451--500.
37. Ari Juels and Burton S. Kaliski. 2007. PORs: Proofs of retrievability for large files. In Proceedings of the 2007 ACM CCS Conference (CCS’07).
38. Barbara Liskov and Rodrigo Rodrigues. 2006. Tolerating Byzantine faulty clients in a quorum system. In Proceedings of the 2006 IEEE ICDCS Conference (ICDCS’06). 34.
39. Dahlia Malkhi and Michael Reiter. 1998. Byzantine quorum systems. Distributed Computing 11, 203--213.
40. Petros Maniatis and Mary Baker. 2003. Authenticated append-only skip lists. Acta Mathematica 137, 151--169.
41. Sarah Meiklejohn, Chris Erway, Alptekin Küpçü, Theodora Hinkle, and Anna Lysyanskaya. 2010. ZKPDL: Enabling efficient implementation of zero-knowledge proofs and electronic cash. In Proceedings of the 2010 USENIX Security Conference (USENIX Security’10).
42. R. C. Merkle. 1987. A digital signature based on a conventional encryption function. In Advances in Cryptology—CRYPTO’87. Lecture Notes in Computer Science, Vol. 293. Springer, 269--378.
43. M. Naor and K. Nissim. 2000. Certificate revocation and certificate update. IEEE Journal on Selected Areas in Communications 18, 4, 561--570. DOI:http://dx.doi.org/10.1109/49.839932
44. A. Oprea, M. K. Reiter, and K. Yang. 2005. Space-efficient block storage integrity. In Proceedings of the 2005 NDSS Conference (NDSS’05).
45. Charalampos Papamanthou and Roberto Tamassia. 2007. Time and space efficient algorithms for two-party authenticated data structures. In Proceedings of the 2007 ICICS Conference (ICICS’07).
46. PlanetLab. 2007. Node Requirements. Retrieved June 27, 2016, from https://planet-lab.org/node/225.
47. Daniel J. Polivy and Roberto Tamassia. 2002. Authenticating distributed data using web services and XML signatures. In Proceedings of the 2002 ACM XML Security Workshop (XML Security’02).
48. William Pugh. 1990a. A Skip List Cookbook. Technical Report. University of Maryland, College Park, MD.
49. William Pugh. 1990b. Skip lists: A probabilistic alternative to balanced trees. Communications of the ACM 33, 6, 668--676.
50. T. S. J. Schwarz and E. L. Miller. 2006. Store, forget, and check: Using algebraic signatures to check remotely administered storage. In Proceedings of the 2006 IEEE ICDCS Conference (ICDCS’06).
51. Hovav Shacham and Brent Waters. 2013. Compact proofs of retrievability. Journal of Cryptology 26, 3, 442--483. DOI:http://dx.doi.org/10.1007/s00145-012-9129-2
52. Elaine Shi, Emil Stefanov, and Charalampos Papamanthou. 2013. Practical dynamic proofs of retrievability. In Proceedings of the 2013 ACM CCS Conference (CCS’13). DOI:http://dx.doi.org/10.1145/2508859.2516669
53. Paul T. Stanton, Benjamin McKeown, Randal C. Burns, and Giuseppe Ateniese. 2010. FastAD: An authenticated directory for billions of objects. ACM SIGOPS Operating Systems Review 44, 1, 45--49.
54. Qian Wang, Cong Wang, Jin Li, Kui Ren, and Wenjing Lou. 2009. Enabling public verifiability and data dynamics for storage security in cloud computing. In Proceedings of the 2009 ESORICS Conference (ESORICS’09). http://eprint.iacr.org/2009/281.
55. Yihua Zhang and Marina Blanton. 2013. Efficient dynamic provable data possession of remote data via balanced update trees. In Proceedings of the 2013 ASIA CCS Conference (ASIA CCS’13). 183--194.
56. Qingji Zheng and Shouhuai Xu. 2011. Fair and dynamic proofs of retrievability. In Proceedings of the 2011 CODASPY Conference (CODASPY’11).
57. Minqi Zhou, Rong Zhang, Wei Xie, Weining Qian, and Aoying Zhou. 2010. Security and privacy in cloud computing: A survey. In Proceedings of the 2010 IEEE SKG Conference (SKG’10).

Index Terms

• Information systems

  • Information storage systems

    • Storage architectures

      • Cloud based storage