{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T01:52:22Z","timestamp":1785376342343,"version":"3.55.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2015,4,24]],"date-time":"2015-04-24T00:00:00Z","timestamp":1429833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"T\u00dcB0TAK","award":["CNS 0627553, CNS 1228485, IIS 0713403 and OCI 0724806"],"award-info":[{"award-number":["CNS 0627553, CNS 1228485, IIS 0713403 and OCI 0724806"]}]},{"name":"T\u00dcB0TAK","award":["112E115"],"award-info":[{"award-number":["112E115"]}]},{"name":"T\u00dcB0TAK","award":["IC1306 and IC1206"],"award-info":[{"award-number":["IC1306 and IC1206"]}]},{"name":"T\u00dcB0TAK","award":["-"],"award-info":[{"award-number":["-"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2015,4,24]]},"abstract":"<jats:p>\n            As storage-outsourcing services and resource-sharing networks have become popular, the problem of efficiently proving the integrity of data stored at untrusted servers has received increased attention. In the Provable Data Possession (PDP) model, the client preprocesses the data and then sends them to an untrusted server for storage while keeping a small amount of meta-data. The client later asks the server to prove that the stored data have not been tampered with or deleted (without downloading the actual data). However, existing PDP schemes apply only to static (or append-only) files. We present a definitional framework and efficient constructions for Dynamic Provable Data Possession (DPDP), which extends the PDP model to support provable updates to stored data. We use a new version of authenticated dictionaries based on rank information. The price of dynamic updates is a performance change from\n            <jats:italic>O<\/jats:italic>\n            (1) to\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            (or\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03b5<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            )) for a file consisting of\n            <jats:italic>n<\/jats:italic>\n            blocks while maintaining the same (or better, respectively) probability of misbehavior detection. Our experiments show that this slowdown is very low in practice (e.g., 415KB proof size and 30ms computational overhead for a 1GB file). We also show how to apply our DPDP scheme to outsourced file systems and version control systems (e.g., CVS).\n          <\/jats:p>","DOI":"10.1145\/2699909","type":"journal-article","created":{"date-parts":[[2015,4,28]],"date-time":"2015-04-28T12:43:57Z","timestamp":1430225037000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":361,"title":["Dynamic Provable Data Possession"],"prefix":"10.1145","volume":"17","author":[{"given":"C. Chris","family":"Erway","sequence":"first","affiliation":[{"name":"AppNeta, Inc., MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alptekin","family":"K\u00fcp\u00e7\u00fc","sequence":"additional","affiliation":[{"name":"Ko\u00e7 University, \u0130stanbul, Turkey"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charalampos","family":"Papamanthou","sequence":"additional","affiliation":[{"name":"ECE and UMIACS, University of Maryland, College Park, MD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[{"name":"Brown University, Providence, RI, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,4,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/648025.744371"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1952982.1952994"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1460877.1460889"},{"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.1007\/s00145-009-9040-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185212"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/647097.717005"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653686"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38348-9_17"},{"key":"e_1_2_1_11_1","volume-title":"Locally updatable and locally decodable codes","author":"Chandran Nishanth","unstructured":"Nishanth Chandran , Bhavana Kanukurthi , and Rafail Ostrovsky . 2014. Locally updatable and locally decodable codes . In TCC. Springer , 489--514. Nishanth Chandran, Bhavana Kanukurthi, and Rafail Ostrovsky. 2014. Locally updatable and locally decodable codes. In TCC. Springer, 489--514."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2014.23184"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 9th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology (ASIACRYPT\u201903)","author":"Clarke Dwaine E.","unstructured":"Dwaine E. Clarke , Srinivas Devadas , Marten van Dijk , Blaise Gassend , and G. Edward Suh . 2003. Incremental multiset hash functions and their application to memory integrity checking . In Proceedings of the 9th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology (ASIACRYPT\u201903) . 188--207. Dwaine E. Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, and G. Edward Suh. 2003. Incremental multiset hash functions and their application to memory integrity checking. In Proceedings of the 9th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology (ASIACRYPT\u201903). 188--207."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.68"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00457-5_30"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1653662.1653688"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","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 Intelligent Cloud Computing (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 Intelligent Cloud Computing (ICC\u201914).","DOI":"10.1007\/978-3-319-19848-4_5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38980-1_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85886-7_6"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the DARPA Information Survivability Conference & Exposition II (DISCEX&rsquo;\u201901)","author":"Goodrich M. T.","unstructured":"M. T. Goodrich , R. Tamassia , and A. Schwerin . 2001. Implementation of an authenticated dictionary with skip lists and commutative hashing . In Proceedings of the DARPA Information Survivability Conference & Exposition II (DISCEX&rsquo;\u201901) . 68--82. M. T. Goodrich, R. Tamassia, and A. Schwerin. 2001. Implementation of an authenticated dictionary with skip lists and commutative hashing. In Proceedings of the DARPA Information Survivability Conference & Exposition II (DISCEX&rsquo;\u201901). 68--82."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315317"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40517-4_12"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1090694.1090698"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1894863.1894876"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/356989.357007"},{"key":"e_1_2_1_30_1","volume-title":"Efficient Cryptography for the Next Generation Secure Cloud: Protocols, Proofs, and Implementation","author":"K\u00fcp\u00e7\u00fc Alptekin","unstructured":"Alptekin K\u00fcp\u00e7\u00fc . 2010b. Efficient Cryptography for the Next Generation Secure Cloud: Protocols, Proofs, and Implementation . Lambert Academic Publishing . Alptekin K\u00fcp\u00e7\u00fc. 2010b. Efficient Cryptography for the Next Generation Secure Cloud: Protocols, Proofs, and Implementation. Lambert Academic Publishing."},{"key":"e_1_2_1_31_1","volume-title":"Official arbitration with secure cloud storage application. Computer Journal","author":"K\u00fcp\u00e7\u00fc Alptekin","year":"2013","unstructured":"Alptekin K\u00fcp\u00e7\u00fc . 2013. Official arbitration with secure cloud storage application. Computer Journal ( 2013 ). DOI:http:\/\/dx.doi.org\/10.1093\/comjnl\/bxt138 10.1093\/comjnl Alptekin K\u00fcp\u00e7\u00fc. 2013. Official arbitration with secure cloud storage application. Computer Journal (2013). DOI:http:\/\/dx.doi.org\/10.1093\/comjnl\/bxt138"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142488"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation -","volume":"6","author":"Li Jinyuan","year":"2004","unstructured":"Jinyuan Li , Maxwell Krohn , David Mazi\u00e8res , and Dennis Shasha . 2004 . Secure untrusted data repository (SUNDR) . In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation - Volume 6 (OSDI&rsquo;\u201904). USENIX Association, Berkeley, CA. Jinyuan Li, Maxwell Krohn, David Mazi\u00e8res, and Dennis Shasha. 2004. Secure untrusted data repository (SUNDR). In Proceedings of the 6th Conference on Symposium on Operating Systems Design & Implementation - Volume 6 (OSDI&rsquo;\u201904). USENIX Association, Berkeley, CA."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 4th Conference on Symposium on Operating System Design & Implementation -","volume":"4","author":"Maheshwari Umesh","year":"2000","unstructured":"Umesh Maheshwari , Radek Vingralek , and William Shapiro . 2000 . How to build a trusted database system on untrusted storage . In Proceedings of the 4th Conference on Symposium on Operating System Design & Implementation - Volume 4 (OSDI&rsquo;\u201900). USENIX Association, Berkeley, CA, 10--26. Umesh Maheshwari, Radek Vingralek, and William Shapiro. 2000. How to build a trusted database system on untrusted storage. In Proceedings of the 4th Conference on Symposium on Operating System Design & Implementation - Volume 4 (OSDI&rsquo;\u201900). USENIX Association, Berkeley, CA, 10--26."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the International Cryptology Conference (CRYPTO\u201987)","author":"Merkle R. C.","year":"1987","unstructured":"R. C. Merkle . 1987 . A digital signature based on a conventional encryption function . In Proceedings of the International Cryptology Conference (CRYPTO\u201987) . 369--378. R. C. Merkle. 1987. A digital signature based on a conventional encryption function. In Proceedings of the International Cryptology Conference (CRYPTO\u201987). 369--378."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/800116.803773"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060293"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 7th Conference on USENIX Security Symposium -","volume":"7","author":"Naor Moni","year":"1998","unstructured":"Moni Naor and Kobbi Nissim . 1998 . Certificate revocation and certificate update . In Proceedings of the 7th Conference on USENIX Security Symposium - Volume 7 (SSYM\u201998). USENIX Association, Berkeley, CA. Moni Naor and Kobbi Nissim. 1998. Certificate revocation and certificate update. In Proceedings of the 7th Conference on USENIX Security Symposium - Volume 7 (SSYM\u201998). USENIX Association, Berkeley, CA."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.71"},{"key":"e_1_2_1_40_1","unstructured":"A. Oprea M. K. Reiter and K. Yang. 2005. Space-efficient block storage integrity. In NDSS.  A. Oprea M. K. Reiter and K. Yang. 2005. Space-efficient block storage integrity. In NDSS."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1785001.1785003"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455826"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_44_1","first-page":"300","article-title":"Polynomial codes over certain finite fields","volume":"8","author":"Reed I.","year":"1960","unstructured":"I. Reed and G. Solomon . 1960 . Polynomial codes over certain finite fields . Journal of SIAM 8 (1960), 300 -- 304 . I. Reed and G. Solomon. 1960. Polynomial codes over certain finite fields. Journal of SIAM 8 (1960), 300--304.","journal-title":"Journal of SIAM"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2006.80"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-012-9129-2"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516669"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2420950.2420985"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_2"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_13"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833620"},{"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\/1943513.1943546"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699909","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2699909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:59Z","timestamp":1750227419000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2699909"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,24]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,4,24]]}},"alternative-id":["10.1145\/2699909"],"URL":"https:\/\/doi.org\/10.1145\/2699909","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"value":"1094-9224","type":"print"},{"value":"1557-7406","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,24]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}