{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T13:53:22Z","timestamp":1762955602164,"version":"3.41.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T00:00:00Z","timestamp":1471305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004410","name":"Scientific and Technological Research Council of Turkey","doi-asserted-by":"crossref","award":["112E115 and 109M761"],"award-info":[{"award-number":["112E115 and 109M761"]}],"id":[{"id":"10.13039\/501100004410","id-type":"DOI","asserted-by":"crossref"}]},{"name":"T\u00fcrk Telekom Inc.","award":["11315-06"],"award-info":[{"award-number":["11315-06"]}]},{"name":"European Union COST Actions","award":["IC0804, IC1206 and IC1306"],"award-info":[{"award-number":["IC0804, IC1206 and IC1306"]}]},{"name":"Ko\u00e7 Sistem Inc."}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2016,8,29]]},"abstract":"<jats:p>\n            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\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) updates on the data structure for a file with\n            <jats:italic>n<\/jats:italic>\n            blocks.\n          <\/jats:p>\n          <jats:p>\n            To overcome this problem, we introduce FlexList, a flexible length-based authenticated skip list. FlexList translates variable-size updates to\n            <jats:italic>O<\/jats:italic>\n            (\u2308 u\/B \u2309) insertions, removals, or modifications, where\n            <jats:italic>u<\/jats:italic>\n            is the size of the update and\n            <jats:italic>B<\/jats:italic>\n            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\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\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.\n          <\/jats:p>","DOI":"10.1145\/2943783","type":"journal-article","created":{"date-parts":[[2016,8,16]],"date-time":"2016-08-16T12:14:20Z","timestamp":1471349660000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["FlexDPDP"],"prefix":"10.1145","volume":"12","author":[{"given":"Ertem","family":"Esiner","sequence":"first","affiliation":[{"name":"Ko\u00e7 University, Computer Science and Engineering, \u0130stanbul, Turkey"}]},{"given":"Adilet","family":"Kachkeev","sequence":"additional","affiliation":[{"name":"Ko\u00e7 University, Computer Science and Engineering, \u0130stanbul, Turkey"}]},{"given":"Samuel","family":"Braunfeld","sequence":"additional","affiliation":[{"name":"Ko\u00e7 University, Computer Science and Engineering, \u0130stanbul, Turkey"}]},{"given":"Alptekin","family":"K\u00fcp\u00e7\u00fc","sequence":"additional","affiliation":[{"name":"Ko\u00e7 University, Computer Science and Engineering, \u0130stanbul, Turkey"}]},{"given":"\u00d6znur","family":"\u00d6zkasap","sequence":"additional","affiliation":[{"name":"Ko\u00e7 University, Computer Science and Engineering, \u0130stanbul, Turkey"}]}],"member":"320","published-online":{"date-parts":[[2016,8,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-005-0151-6"},{"key":"e_1_2_1_2_1","first-page":"263","article-title":"An algorithm for the organization of information","volume":"146","author":"Adelson-Velskii M.","year":"1963","unstructured":"M. Adelson-Velskii and E. M. Landis . 1963 . An algorithm for the organization of information . Defense Technical Information Center 146 , 263 -- 266 . M. Adelson-Velskii and E. M. Landis. 1963. An algorithm for the organization of information. Defense Technical Information Center 146, 263--266.","journal-title":"Defense Technical Information Center"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/648025.744371"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1952982.1952994"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10366-7_19"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460877.1460889"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1770560.1770564"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289509"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535929"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1103022.1103037"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11751595_43"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380251203"},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"Libraries Boost","year":"2015","unstructured":"Boost C++ Libraries . 2015 . Boost Asio Library . Retrieved June 27, 2016, from http:\/\/www.boost.org\/doc\/libs. Boost C++ Libraries. 2015. Boost Asio Library. Retrieved June 27, 2016, from http:\/\/www.boost.org\/doc\/libs."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653686"},{"key":"e_1_2_1_15_1","volume-title":"Retrieved","author":"Project Brownie Points","year":"2016","unstructured":"Brownie Points Project . 2016 . Brownie Cashlib Cryptographic Library . Retrieved June 27, 2016, from http:\/\/github.com\/brownie\/cashlib. Brownie Points Project. 2016. Brownie Cashlib Cryptographic Library. Retrieved June 27, 2016, from http:\/\/github.com\/brownie\/cashlib."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1556154.1556173"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2006.56"},{"key":"e_1_2_1_18_1","volume-title":"Dynamic proofs of retrievability via oblivious RAM. Journal of Cryptology","author":"Cash David","year":"2015","unstructured":"David Cash , Alptekin K\u00fcp\u00e7\u00fc , and Daniel Wichs . 2013. Dynamic proofs of retrievability via oblivious RAM. Journal of Cryptology ( 2015 ). DOI:10.1007\/s00145-015-9216-2 10.1007\/s00145-015-9216-2 David Cash, Alptekin K\u00fcp\u00e7\u00fc, and Daniel Wichs. 2013. Dynamic proofs of retrievability via oblivious RAM. Journal of Cryptology (2015). DOI:10.1007\/s00145-015-9216-2"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2014 TCC Conference (TCC'14)","author":"Chandran Nishanth","year":"2013","unstructured":"Nishanth Chandran , Bhavana Kanukurthi , and Rafail Ostrovsky . 2013 . Locally updatable and locally decodable codes . In Proceedings of the 2014 TCC Conference (TCC'14) . Nishanth Chandran, Bhavana Kanukurthi, and Rafail Ostrovsky. 2013. Locally updatable and locally decodable codes. In Proceedings of the 2014 TCC Conference (TCC'14)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2009.126"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571837"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2019599.2019602"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.68"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699909"},{"volume-title":"Proceedings of the 2014 ICC Conference (ICC\u201914)","author":"Esiner Ertem","key":"e_1_2_1_26_1","unstructured":"Ertem Esiner , Alptekin K\u00fcp\u00e7\u00fc , and \u00d6znur \u00d6zkasap. 2014. Analysis and optimization on FlexDPDP: A practical solution for dynamic provable data possession . In Proceedings of the 2014 ICC Conference (ICC\u201914) . Ertem Esiner, Alptekin K\u00fcp\u00e7\u00fc, and \u00d6znur \u00d6zkasap. 2014. Analysis and optimization on FlexDPDP: A practical solution for dynamic provable data possession. In Proceedings of the 2014 ICC Conference (ICC\u201914)."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 2013 ICISC Conference (ICISC\u201913)","author":"Etemad Mohammad","year":"2013","unstructured":"Mohammad Etemad and Alptekin K\u00fcp\u00e7\u00fc . 2013 a. Database outsourcing with hierarchical authenticated data structures . In Proceedings of the 2013 ICISC Conference (ICISC\u201913) . Mohammad Etemad and Alptekin K\u00fcp\u00e7\u00fc. 2013a. Database outsourcing with hierarchical authenticated data structures. In Proceedings of the 2013 ICISC Conference (ICISC\u201913)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38980-1_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-002-0070-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1768570.1768581"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85886-7_6"},{"key":"e_1_2_1_32_1","volume-title":"Goodrich and Roberto Tamassia","author":"Michael","year":"2001","unstructured":"Michael T. Goodrich and Roberto Tamassia . 2001 . Efficient Authenticated Dictionaries with Skip Lists and Commutative Hashing. Technical Report. Johns Hopkins Information Security Institute . Michael T. Goodrich and Roberto Tamassia. 2001. Efficient Authenticated Dictionaries with Skip Lists and Commutative Hashing. Technical Report. Johns Hopkins Information Security Institute."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/DISCEX.2001.932160"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009382.1009729"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294269"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278305"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315317"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2006.83"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004460050050"},{"key":"e_1_2_1_40_1","first-page":"151","article-title":"Authenticated append-only skip lists","volume":"137","author":"Maniatis Petros","year":"2003","unstructured":"Petros Maniatis and Mary Baker . 2003 . Authenticated append-only skip lists . Acta Mathematica 137 , 151 -- 169 . Petros Maniatis and Mary Baker. 2003. Authenticated append-only skip lists. Acta Mathematica 137, 151--169.","journal-title":"Acta Mathematica"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 2010 USENIX Security Conference (USENIX Security\u201910)","author":"Meiklejohn Sarah","year":"2010","unstructured":"Sarah Meiklejohn , Chris Erway , Alptekin K\u00fcp\u00e7\u00fc , 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\u201910) . Sarah Meiklejohn, Chris Erway, Alptekin K\u00fcp\u00e7\u00fc, 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\u201910)."},{"key":"e_1_2_1_42_1","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology\u2014CRYPTO\u201987","author":"Merkle R. C.","unstructured":"R. C. Merkle . 1987. A digital signature based on a conventional encryption function . In Advances in Cryptology\u2014CRYPTO\u201987 . Lecture Notes in Computer Science , Vol. 293 . Springer , 269--378. R. C. Merkle. 1987. A digital signature based on a conventional encryption function. In Advances in Cryptology\u2014CRYPTO\u201987. Lecture Notes in Computer Science, Vol. 293. Springer, 269--378."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.839932"},{"volume-title":"Proceedings of the 2005 NDSS Conference (NDSS\u201905)","author":"Oprea A.","key":"e_1_2_1_44_1","unstructured":"A. Oprea , M. K. Reiter , and K. Yang . 2005. Space-efficient block storage integrity . In Proceedings of the 2005 NDSS Conference (NDSS\u201905) . A. Oprea, M. K. Reiter, and K. Yang. 2005. Space-efficient block storage integrity. In Proceedings of the 2005 NDSS Conference (NDSS\u201905)."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1785001.1785003"},{"volume-title":"Retrieved","year":"2007","key":"e_1_2_1_46_1","unstructured":"PlanetLab. 2007 . Node Requirements . Retrieved June 27, 2016, from https:\/\/planet-lab.org\/node\/225. PlanetLab. 2007. Node Requirements. Retrieved June 27, 2016, from https:\/\/planet-lab.org\/node\/225."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/764792.764805"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2006.80"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-012-9129-2"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516669"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1740390.1740401"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1813084.1813114"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484313.2484339"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1943513.1943546"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/SKG.2010.19"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2943783","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2943783","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:45Z","timestamp":1750222485000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2943783"}},"subtitle":["Flexlist-Based Optimized Dynamic Provable Data Possession"],"short-title":[],"issued":{"date-parts":[[2016,8,16]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8,29]]}},"alternative-id":["10.1145\/2943783"],"URL":"https:\/\/doi.org\/10.1145\/2943783","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2016,8,16]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}