{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T20:30:24Z","timestamp":1759091424890,"version":"3.41.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2011,9,1]],"date-time":"2011-09-01T00:00:00Z","timestamp":1314835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0524211"],"award-info":[{"award-number":["CNS-0524211"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>Authenticated dictionaries are a widely discussed paradigm to enable verifiable integrity for data storage on untrusted servers, such as today\u2019s widely used \u201ccloud computing\u201d resources, allowing a server to provide a \u201cproof,\u201d typically in the form of a slice through a cryptographic data structure, that the results of any given query are the correct answer, including that the absence of a query result is correct. Persistent authenticated dictionaries (PADs) further allow queries against older versions of the structure. This research presents implementations of a variety of different PAD algorithms, some based on Merkle tree-style data structures and others based on individually signed \u201ctuple\u201d statements (with and without RSA accumulators). We present system throughput benchmarks, indicating costs in terms of time, storage, and bandwidth as well as considering how much money would be required given standard cloud computing costs. We conclude that Merkle tree PADs are preferable in cases with frequent updates, while tuple-based PADs are preferable with higher query rates. For Merkle tree PADs, red-black trees outperform treaps and skiplists. Applying Sarnak-Tarjan\u2019s versioned node strategy, with a cache of old hashes at every node, to red-black trees yields the fastest Merkle tree PAD implementation, notably using half the memory of the more commonly used mutation-free path copying strategy. For tuple PADs, although we designed and implemented an algorithm using RSA accumulators that offers constant update size, constant storage per update, constant proof size, and sublinear computation per update, we found that RSA accumulators are so expensive that they are never worthwhile. We find that other optimizations in the literature for tuple PADs are more cost-effective.<\/jats:p>","DOI":"10.1145\/2019599.2019602","type":"journal-article","created":{"date-parts":[[2011,10,4]],"date-time":"2011-10-04T13:24:18Z","timestamp":1317734658000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Authenticated Dictionaries"],"prefix":"10.1145","volume":"14","author":[{"given":"Scott A.","family":"Crosby","sequence":"first","affiliation":[{"name":"Rice University"}]},{"given":"Dan S.","family":"Wallach","sequence":"additional","affiliation":[{"name":"Rice University"}]}],"member":"320","published-online":{"date-parts":[[2011,9]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"263","article-title":"An algorithm for the organization of information","volume":"146","author":"Adelson-Velskii G.","year":"1962","unstructured":"Adelson-Velskii , G. and Landis , E. M. 1962 . An algorithm for the organization of information . Proc. USSR Acad. Sci. 146 , 263 -- 266 . Adelson-Velskii, G. and Landis, E. M. 1962. An algorithm for the organization of information. Proc. USSR Acad. Sci. 146, 263--266.","journal-title":"Proc. USSR Acad. Sci."},{"volume-title":"Proceedings of the International Conference on Information Security (ISC). 379--393","author":"Anagnostopoulos A.","key":"e_1_2_1_2_1","unstructured":"Anagnostopoulos , A. , Goodrich , M. T. , and Tamassia , R . 2001. Persistent authenticated dictionaries and their applications . In Proceedings of the International Conference on Information Security (ISC). 379--393 . Anagnostopoulos, A., Goodrich, M. T., and Tamassia, R. 2001. Persistent authenticated dictionaries and their applications. In Proceedings of the International Conference on Information Security (ISC). 379--393."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185430"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63531"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 14th International Workshop on Implementation of Functional Languages. 34","author":"Bagwell P.","year":"2002","unstructured":"Bagwell , P. 2002 . Fast functional lists, hash-lists, deques and variable length arrays . In Proceedings of the 14th International Workshop on Implementation of Functional Languages. 34 . Bagwell, P. 2002. Fast functional lists, hash-lists, deques and variable length arrays. In Proceedings of the 14th International Workshop on Implementation of Functional Languages. 34."},{"volume-title":"Proceedings of EuroCrypt. 480--494","author":"Bari N.","key":"e_1_2_1_6_1","unstructured":"Bari , N. and Pfitzmann , B . 1997. Collision-free accumulators and fail-stop signature schemes without trees . In Proceedings of EuroCrypt. 480--494 . Bari, N. and Pfitzmann, B. 1997. Collision-free accumulators and fail-stop signature schemes without trees. In Proceedings of EuroCrypt. 480--494."},{"volume-title":"Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (EuroCrypt\u201993)","author":"Benaloh J.","key":"e_1_2_1_7_1","unstructured":"Benaloh , J. and de Mare, M. 1993. One-way accumulators: A decentralized alternative to digital signatures . In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (EuroCrypt\u201993) . 274--285. Benaloh, J. and de Mare, M. 1993. One-way accumulators: A decentralized alternative to digital signatures. In Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (EuroCrypt\u201993). 274--285."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/277651.277660"},{"key":"e_1_2_1_9_1","first-page":"238","article-title":"Partially persistent data structures of bounded degree with constant update time","volume":"3","author":"Brodal G. S.","year":"1996","unstructured":"Brodal , G. S. 1996 . Partially persistent data structures of bounded degree with constant update time . Nordic J. Comput. 3 , 3, 238 -- 255 . Brodal, G. S. 1996. Partially persistent data structures of bounded degree with constant update time. Nordic J. Comput. 3, 3, 238--255.","journal-title":"Nordic J. Comput."},{"volume-title":"Proceedings of CRYPTO\u201902","author":"Camenisch J.","key":"e_1_2_1_10_1","unstructured":"Camenisch , J. and Lysyanskaya , A . 2002. Dynamic accumulators and application to efficient revocation of anonymous credentials . In Proceedings of CRYPTO\u201902 . 61--76. Camenisch, J. and Lysyanskaya, A. 2002. Dynamic accumulators and application to efficient revocation of anonymous credentials. In Proceedings of CRYPTO\u201902. 61--76."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00468-1_27"},{"key":"e_1_2_1_12_1","unstructured":"Cohen B. 2003. Incentives build robustness in BitTorrent. Tech. rep. bittorrent.org. Cohen B. 2003. Incentives build robustness in BitTorrent. Tech. rep. bittorrent.org."},{"volume-title":"Proceedings of ESORICS\u201909","author":"Crosby S. A.","key":"e_1_2_1_13_1","unstructured":"Crosby , S. A. and Wallach , D. S . 2009. Super-efficient aggregating history-independent persistent authenticated dictionaries . In Proceedings of ESORICS\u201909 . 671--688. Crosby, S. A. and Wallach, D. S. 2009. Super-efficient aggregating history-independent persistent authenticated dictionaries. In Proceedings of ESORICS\u201909. 671--688."},{"key":"e_1_2_1_14_1","volume-title":"Fern: An updatable authenticated dictionary suitable for distributed caching. In Computer Network Security. Communications in Computer and Information Science","author":"Freudenthal E.","year":"2007","unstructured":"Freudenthal , E. , Herrera , D. , Gutstein , S. , Spring , R. , and Longpre , L . 2007 . Fern: An updatable authenticated dictionary suitable for distributed caching. In Computer Network Security. Communications in Computer and Information Science , vol. 1 , Springer , Berlin , 141--146. Freudenthal, E., Herrera, D., Gutstein, S., Spring, R., and Longpre, L. 2007. Fern: An updatable authenticated dictionary suitable for distributed caching. In Computer Network Security. Communications in Computer and Information Science, vol. 1, Springer, Berlin, 141--146."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/505452.505453"},{"volume-title":"Proceedings of the 9th International Symposium on High Performance Computer Architecture (HPCA).","author":"Gassend B.","key":"e_1_2_1_16_1","unstructured":"Gassend , B. , Suh , G. , Clarke , D. , Dijk , M. , and Devadas , S . 2003. Caches and hash trees for efficient memory integrity verification . In Proceedings of the 9th International Symposium on High Performance Computer Architecture (HPCA). Gassend, B., Suh, G., Clarke, D., Dijk, M., and Devadas, S. 2003. Caches and hash trees for efficient memory integrity verification. In Proceedings of the 9th International Symposium on High Performance Computer Architecture (HPCA)."},{"volume-title":"Proceedings of the DARPA Information Survivability Conference & Exposition II (DISCEX II). 68--82","author":"Goodrich M.","key":"e_1_2_1_17_1","unstructured":"Goodrich , M. , Tamassia , R. , and Schwerin , A . 2001. Implementation of an authenticated dictionary with skip lists and commutative hashing . In Proceedings of the DARPA Information Survivability Conference & Exposition II (DISCEX II). 68--82 . Goodrich, M., Tamassia, R., and Schwerin, A. 2001. Implementation of an authenticated dictionary with skip lists and commutative hashing. In Proceedings of the DARPA Information Survivability Conference & Exposition II (DISCEX II). 68--82."},{"volume-title":"Proceedings of the 5th International Conference on Information Security (ISC). 372--388","author":"Goodrich M. T.","key":"e_1_2_1_18_1","unstructured":"Goodrich , M. T. , Tamassia , R. , and Hasic , J . 2002. An efficient dynamic and distributed cryptographic accumulator . In Proceedings of the 5th International Conference on Information Security (ISC). 372--388 . Goodrich, M. T., Tamassia, R., and Hasic, J. 2002. An efficient dynamic and distributed cryptographic accumulator. In Proceedings of the 5th International Conference on Information Security (ISC). 372--388."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85886-7_6"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/38714.38755"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1456469.1456479"},{"key":"e_1_2_1_23_1","unstructured":"Kaplan H. 2001. Persistent data structures. In Handbook on Data Structures and Applications D. Mehta and S. Sahni Eds. CRC Press. Kaplan H. 2001. Persistent data structures. In Handbook on Data Structures and Applications D. Mehta and S. Sahni Eds. CRC Press."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/647502.728330"},{"volume-title":"Proceedings of the USENIX Symposium on Operating Systems Design & Implementation (OSDI).","author":"Li J.","key":"e_1_2_1_25_1","unstructured":"Li , J. , Krohn , M. , Mazi\u00e8res , D. , and Shasha , D . 2004. Secure untrusted data repository (SUNDR) . In Proceedings of the USENIX Symposium on Operating Systems Design & Implementation (OSDI). Li, J., Krohn, M., Mazi\u00e8res, D., and Shasha, D. 2004. Secure untrusted data repository (SUNDR). In Proceedings of the USENIX Symposium on Operating Systems Design & Implementation (OSDI)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72738-5_17"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of CRYPTO\u201989","author":"Merkle R. C.","year":"1989","unstructured":"Merkle , R. C. 1989 . A certified digital signature . In Proceedings of CRYPTO\u201989 . 218--238. Merkle, R. C. 1989. A certified digital signature. In Proceedings of CRYPTO\u201989. 218--238."},{"volume-title":"Efficient certificate revocation. Tech. rep. TM-542b","author":"Micali S.","key":"e_1_2_1_28_1","unstructured":"Micali , S. 1996. Efficient certificate revocation. Tech. rep. TM-542b , Massachusetts Institute of Technology , Cambridge, MA . http:\/\/www.ncstrl.org:8900\/ncstrl\/servlet\/search?formname=detail\\&id=oai&percnt;&percnt;3Ancstrlh&percnt;3Amitai&percnt;3AMIT-LCS&percnt;2F&percnt;2FMIT&percnt;2FLCS&percnt;2FTM-542b. Micali, S. 1996. Efficient certificate revocation. Tech. rep. TM-542b, Massachusetts Institute of Technology, Cambridge, MA. http:\/\/www.ncstrl.org:8900\/ncstrl\/servlet\/search?formname=detail\\&id=oai&percnt;&percnt;3Ancstrlh&percnt;3Amitai&percnt;3AMIT-LCS&percnt;2F&percnt;2FMIT&percnt;2FLCS&percnt;2FTM-542b."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258638"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060293"},{"volume-title":"Proceedings of EuroCrypt. 77--85","author":"Naccache D.","key":"e_1_2_1_31_1","unstructured":"Naccache , D. , M\u2019Raihi , D. , Vaudenay , S. , and Raphaeli , D . 1994. Can DSA be improved? Complexity trade-offs with the digital signature standard . In Proceedings of EuroCrypt. 77--85 . Naccache, D., M\u2019Raihi, D., Vaudenay, S., and Raphaeli, D. 1994. Can DSA be improved? Complexity trade-offs with the digital signature standard. In Proceedings of EuroCrypt. 77--85."},{"volume-title":"Proceedings of the USENIX Security Symposium.","author":"Naor M.","key":"e_1_2_1_32_1","unstructured":"Naor , M. and Nissim , K . 1998. Certificate revocation and certificate update . In Proceedings of the USENIX Security Symposium. Naor, M. and Nissim, K. 1998. Certificate revocation and certificate update. In Proceedings of the USENIX Security Symposium."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380844"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30574-3_19"},{"volume-title":"Recommendation for Key Management --- Part 1: General","author":"Special Publication","key":"e_1_2_1_35_1","unstructured":"NIST Special Publication 800-57. 2007. Recommendation for Key Management --- Part 1: General . National Institute for Standards and Technology . NIST Special Publication 800-57. 2007. Recommendation for Key Management --- Part 1: General. National Institute for Standards and Technology."},{"volume-title":"Purely Functional Data Structures","author":"Okasaki C.","key":"e_1_2_1_36_1","unstructured":"Okasaki , C. 1999. Purely Functional Data Structures . Cambridge University Press . Okasaki, C. 1999. Purely Functional Data Structures. Cambridge University Press."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455770.1455826"},{"volume-title":"Proceedings of the USENIX Conference on File and Storage Technologies.","author":"Peterson Z. N. J.","key":"e_1_2_1_38_1","unstructured":"Peterson , Z. N. J. , Burns , R. , Ateniese , G. , and Bono , S . 2007. Design and implementation of verifiable audit trails for a versioning file system . In Proceedings of the USENIX Conference on File and Storage Technologies. Peterson, Z. N. J., Burns, R., Ateniese, G., and Bono, S. 2007. Design and implementation of verifiable audit trails for a versioning file system. In Proceedings of the USENIX Conference on File and Storage Technologies."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/645928.672387"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-314X(80)90084-0"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2007.44"},{"volume-title":"Proceedings of the 17th USENIX Security Symposium (Security\u201908)","author":"Sandler D. R.","key":"e_1_2_1_42_1","unstructured":"Sandler , D. R. , Derr , K. , and Wallach , D. S . 2008. VoteBox: A tamper-evident, verifiable electronic voting system . In Proceedings of the 17th USENIX Security Symposium (Security\u201908) . Sandler, D. R., Derr, K., and Wallach, D. S. 2008. VoteBox: A tamper-evident, verifiable electronic voting system. In Proceedings of the 17th USENIX Security Symposium (Security\u201908)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/6138.6151"},{"volume-title":"Proceedings of the USENIX Security Symposium. 109--120","author":"Shapiro J. S.","key":"e_1_2_1_44_1","unstructured":"Shapiro , J. S. and Vanderburgh , J . 2002. Access and integrity control in a public-access, high-assurance configuration management system . In Proceedings of the USENIX Security Symposium. 109--120 . Shapiro, J. S. and Vanderburgh, J. 2002. Access and integrity control in a public-access, high-assurance configuration management system. In Proceedings of the USENIX Security Symposium. 109--120."},{"volume-title":"Proceedings of the 16th Annual Network and Distributed Systems Security Symposium (NDSS).","author":"Williams P.","key":"e_1_2_1_45_1","unstructured":"Williams , P. , Sion , R. , and Shasha , D . 2009. The blind stone tablet: Outsourcing durability . In Proceedings of the 16th Annual Network and Distributed Systems Security Symposium (NDSS). Williams, P., Sion, R., and Shasha, D. 2009. The blind stone tablet: Outsourcing durability. In Proceedings of the 16th Annual Network and Distributed Systems Security Symposium (NDSS)."}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2019599.2019602","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2019599.2019602","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:42Z","timestamp":1750273662000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2019599.2019602"}},"subtitle":["Real-World Costs and Trade-Offs"],"short-title":[],"issued":{"date-parts":[[2011,9]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["10.1145\/2019599.2019602"],"URL":"https:\/\/doi.org\/10.1145\/2019599.2019602","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"type":"print","value":"1094-9224"},{"type":"electronic","value":"1557-7406"}],"subject":[],"published":{"date-parts":[[2011,9]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}