{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T20:52:21Z","timestamp":1769201541644,"version":"3.49.0"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,1,9]],"date-time":"2015-01-09T00:00:00Z","timestamp":1420761600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-014-9968-3","type":"journal-article","created":{"date-parts":[[2015,1,8]],"date-time":"2015-01-08T16:44:51Z","timestamp":1420735491000},"page":"664-712","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Authenticated Hash Tables Based on Cryptographic Accumulators"],"prefix":"10.1007","volume":"74","author":[{"given":"Charalampos","family":"Papamanthou","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Tamassia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikos","family":"Triandopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,1,9]]},"reference":[{"issue":"1","key":"9968_CR1","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/1952982.1952994","volume":"14","author":"G Ateniese","year":"2011","unstructured":"Ateniese, G., Burns, R.C., Curtmola, R., Herring, J., Khan, O., Kissner, L., Peterson, Z.N.J., Song, D.: Remote data checking using provable data possession. ACM Trans. Inf. Syst. Secur. 14(1), 12 (2011)","journal-title":"ACM Trans. Inf. Syst. Secur."},{"key":"9968_CR2","doi-asserted-by":"crossref","unstructured":"Baric, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 1233 of LNCS, pp. 480\u2013494 (1997)","DOI":"10.1007\/3-540-69053-0_33"},{"key":"9968_CR3","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of Conference on Computer and Communications Security (CCS), ACM, pp. 62\u201373 (1993)","DOI":"10.1145\/168588.168596"},{"key":"9968_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Proceedings of International Cryptology Conference (CRYPTO), vol. 8043 of LNCS, pp. 90\u2013108 (2013)","DOI":"10.1007\/978-3-642-40084-1_6"},{"key":"9968_CR5","doi-asserted-by":"crossref","unstructured":"Benaloh, J., de Mare, M.: One-way accumulators: a decentralized alternative to digital signatures. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 765 of LNCS, pp. 274\u2013285 (1993)","DOI":"10.1007\/3-540-48285-7_24"},{"issue":"2\/3","key":"9968_CR6","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF01185212","volume":"12","author":"M Blum","year":"1994","unstructured":"Blum, M., Evans, W.S., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. Algorithmica 12(2\/3), 225\u2013244 (1994)","journal-title":"Algorithmica"},{"issue":"2","key":"9968_CR7","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s00145-007-9005-7","volume":"21","author":"D Boneh","year":"2008","unstructured":"Boneh, D., Boyen, X.: Short signatures without random oracles and the SDH assumption in bilinear groups. J. Cryptol. 21(2), 149\u2013177 (2008)","journal-title":"J. Cryptol."},{"key":"9968_CR8","doi-asserted-by":"crossref","unstructured":"Braun, B., Feldman, A.J., Ren, Z., Setty, S.T.V., Blumberg, A.J., Walfish, M.: Verifying computations with state. In: Proceedings of Symposium on Operating Systems Principles (SOSP), ACM, pp. 341\u2013357 (2013)","DOI":"10.1145\/2517349.2522733"},{"key":"9968_CR9","doi-asserted-by":"crossref","unstructured":"Buldas, A., Laud, P., Lipmaa, H.: Accountable certificate management using undeniable attestations. In: Proceedings of Conference on Computer and Communications Security (CCS), ACM, pp. 9\u201318 (2000)","DOI":"10.1145\/352600.352604"},{"key":"9968_CR10","doi-asserted-by":"crossref","unstructured":"Camenisch, J., Kohlweiss, M., Soriente, C.: An accumulator based on bilinear maps and efficient revocation for anonymous credentials. In: Proceedings of Public Key Cryptography (PKC), vol. 5443 of LNCS, pp. 481\u2013500 (2009)","DOI":"10.1007\/978-3-642-00468-1_27"},{"key":"9968_CR11","doi-asserted-by":"crossref","unstructured":"Camenisch, J., Kohlweiss, M., Soriente, C.: An accumulator based on bilinear maps and efficient revocation for anonymous credentials. In: Proceedings of Public Key Cryptography (PKC), vol. 5443 of LNCS, pp. 481\u2013500 (2009)","DOI":"10.1007\/978-3-642-00468-1_27"},{"key":"9968_CR12","doi-asserted-by":"crossref","unstructured":"Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Proceedings of Security in Communication Networks (SCN), vol. 2576 of LNCS, pp. 268\u2013289 (2002)","DOI":"10.1007\/3-540-36413-7_20"},{"key":"9968_CR13","doi-asserted-by":"crossref","unstructured":"Canetti, R., Paneth, O., Papadopoulos, D., Triandopoulos, N.: Verifiable set operations over outsourced databases. In: Proceedings of Public Key Cryptography (PKC), vol. 8383 of LNCS, pp. 113\u2013130 (2014)","DOI":"10.1007\/978-3-642-54631-0_7"},{"key":"9968_CR14","doi-asserted-by":"crossref","unstructured":"Carter, I.L., Wegman, M.N.: Universal classes of hash functions. In: Proceedings of Symposium on Theory of Computing (STOC), ACM, pp. 106\u2013112 (1977)","DOI":"10.1145\/800105.803400"},{"key":"9968_CR15","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"9968_CR16","unstructured":"Damg\u00e5rd, I., Triandopoulos, N.: Supporting non-membership proofs with bilinear-map accumulators. http:\/\/eprint.iacr.org\/ , Cryptology ePrint Archive, Report 2008\/538 (2008)"},{"key":"9968_CR17","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., Tarjan, R.E.: Dynamic perfect hashing: upper and lower bounds. SIAM J. Comput. 23, 738\u2013761 (1994)","journal-title":"SIAM J. Comput."},{"key":"9968_CR18","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M., Rothblum, G.N., Vaikuntanathan, V.: How efficient can memory checking be? In: Proceedings of Theoretical Cryptography Conference (TCC), vol. 5444 of LNCS, pp. 503\u2013520 (2009)","DOI":"10.1007\/978-3-642-00457-5_30"},{"key":"9968_CR19","doi-asserted-by":"crossref","unstructured":"Erway, C., K\u00fcp\u00e7\u00fc, A., Papamanthou, C., Tamassia, R.: Dynamic provable data possession. In: Proceedings of Conference on Computer and Communications Security (CCS), ACM, pp. 213\u2013222 (2009)","DOI":"10.1145\/1653662.1653688"},{"key":"9968_CR20","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 1592 of LNCS, pp. 123\u2013139 (1999)","DOI":"10.1007\/3-540-48910-X_9"},{"key":"9968_CR21","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Papamanthou, C., Tamassia, R.: On the cost of persistence and authentication in skip lists. In: Proceedings of Workshop on Experimental Algorithms (WEA), vol. 4525 of LNCS, pp. 94\u2013107 (2007)","DOI":"10.1007\/978-3-540-72845-0_8"},{"key":"9968_CR22","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Tamassia, R., Hasic, J.: An efficient dynamic and distributed cryptographic accumulator. In: Proceedings of Information Security Conference (ISC), vol. 2433 of LNCS, pp. 372\u2013388 (2002)","DOI":"10.1007\/3-540-45811-5_29"},{"key":"9968_CR23","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Tamassia, R., Schwerin, A.: Implementation of an authenticated dictionary with skip lists and commutative hashing. In: Proceedings of DARPA Information Survivability Conference and Exposition II (DISCEX II), pp. 68\u201382 (2001)","DOI":"10.1109\/DISCEX.2001.932160"},{"key":"9968_CR24","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Tamassia, R., Triandopoulos, N.: Super-efficient verification of dynamic outsourced databases. In: Proceedings of RSA Conference, Cryptographers\u2019 Track (CT-RSA), vol. 4964 of LNCS, pp. 407\u2013424 (2008)","DOI":"10.1007\/978-3-540-79263-5_26"},{"issue":"3","key":"9968_CR25","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1007\/s00453-009-9355-7","volume":"60","author":"MT Goodrich","year":"2011","unstructured":"Goodrich, M.T., Tamassia, R., Triandopoulos, N.: Efficient authenticated data structures for graph connectivity and geometric search problems. Algorithmica 60(3), 505\u2013552 (2011)","journal-title":"Algorithmica"},{"key":"9968_CR26","doi-asserted-by":"crossref","unstructured":"Hutflesz, A., Six, H.-W., Widmayer, P.: Globally order preserving multidimensional linear hashing. In: Proceedings of International Conference on Data Engineering (ICDE), IEEE, pp. 572\u2013579 (1988)","DOI":"10.1109\/ICDE.1988.105505"},{"key":"9968_CR27","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1007\/BF01759063","volume":"6","author":"CM Kenyon","year":"1991","unstructured":"Kenyon, C.M., Vitter, J.S.: Maximum queue size and hashing with lazy deletion. Algorithmica 6, 597\u2013619 (1991)","journal-title":"Algorithmica"},{"key":"9968_CR28","unstructured":"Kosba, A.E., Papadopoulos, D., Papamanthou, C., Sayed, M.F., Shi, E., Triandopoulos, N.: TrueSet: nearly practical verifiable set computations. In: Usenix Security Symposium (USENIX SECURITY) (2014)"},{"key":"9968_CR29","doi-asserted-by":"crossref","unstructured":"Li, J., Li, N., Xue, R.: Universal accumulators with efficient nonmembership proofs. In: Proceedings of Applied Cryptography and Network Security (ACNS), vol. 4521 of LNCS, pp. 253\u2013269 (2007)","DOI":"10.1007\/978-3-540-72738-5_17"},{"key":"9968_CR30","doi-asserted-by":"crossref","unstructured":"Linial, N., Sasson, O.: Non-expansive hashing. In: Proceedings of Symposium on Theory of Computing (STOC), ACM, pp. 509\u2013517 (1996)","DOI":"10.1145\/237814.237999"},{"key":"9968_CR31","unstructured":"Lynn, B.: On the implementation of pairing-based cryptosystems. Ph.D. thesis, Stanford University, Stanford, California (2008)"},{"issue":"1","key":"9968_CR32","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s00453-003-1076-8","volume":"39","author":"C Martel","year":"2004","unstructured":"Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., Stubblebine, S.G.: A general model for authenticated data structures. Algorithmica 39(1), 21\u201341 (2004)","journal-title":"Algorithmica"},{"key":"9968_CR33","doi-asserted-by":"crossref","unstructured":"Merkle, R.C.: A certified digital signature. In: Proceedings of International Cryptology Conference (CRYPTO), vol. 435 of LNCS, pp. 218\u2013238 (1989)","DOI":"10.1007\/0-387-34805-0_21"},{"key":"9968_CR34","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1093\/comjnl\/28.3.330","volume":"28","author":"JK Mullin","year":"1985","unstructured":"Mullin, J.K.: Spiral storage: efficient dynamic hashing with constant-performance. Comput. J. 28, 330\u2013334 (1985)","journal-title":"Comput. J."},{"key":"9968_CR35","unstructured":"NTL: A library for doing number theory. http:\/\/www.shoup.net\/ntl\/"},{"key":"9968_CR36","unstructured":"Naor, M., Nissim, K.: Certificate revocation and certificate update. In: Usenix Security Symposium (USENIX SECURITY), pp. 217\u2013228 (1998)"},{"key":"9968_CR37","doi-asserted-by":"crossref","unstructured":"Nguyen, L.: Accumulators from bilinear pairings and applications. In: Proceedings of RSA Conference, Cryptographers\u2019 Track (CT-RSA), vol. 3376 of LNCS, pp. 275\u2013292 (2005)","DOI":"10.1007\/978-3-540-30574-3_19"},{"key":"9968_CR38","doi-asserted-by":"crossref","unstructured":"Nuckolls, G.: Verified query results from hybrid authentication trees. In: Proceedings of Working Conference on Data and Applications Security (DBSEC), vol. 3654 of LNCS, pp. 84\u201398 (2005)","DOI":"10.1007\/11535706_7"},{"key":"9968_CR39","unstructured":"Overmars, M.H.: The Design of Dynamic Data Structures, vol. 156 of LNCS, Springer, London (1983)"},{"key":"9968_CR40","unstructured":"Papamanthou, C.: Cryptography for efficiency: new directions in authenticated data structures. Ph.D. thesis, Brown University, Providence, Rhode Island (2011)"},{"key":"9968_CR41","unstructured":"PBC: The pairing-based cryptography library. http:\/\/crypto.stanford.edu\/pbc\/"},{"key":"9968_CR42","doi-asserted-by":"crossref","unstructured":"Papamanthou, C., Shi, E., Tamassia, R., Yi, K.: Streaming authenticated data structures. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), vol. 7881 of LNCS, pp. 353\u2013370 (2013)","DOI":"10.1007\/978-3-642-38348-9_22"},{"key":"9968_CR43","doi-asserted-by":"crossref","unstructured":"Papamanthou, C., Tamassia, R.: Time and space efficient algorithms for two-party authenticated data structures. In: Proceedings of International Conference on Information and Communications Security (ICICS), vol. 4861 of LNCS, pp. 1\u201315 (2007)","DOI":"10.1007\/978-3-540-77048-0_1"},{"key":"9968_CR44","doi-asserted-by":"crossref","unstructured":"Papamanthou, C., Tamassia, R., Triandopoulos, N.: Authenticated hash tables. In: Proceedings of Conference on Computer and Communications Security (CCS), ACM, pp. 437\u2013448 (2008)","DOI":"10.1145\/1455770.1455826"},{"key":"9968_CR45","doi-asserted-by":"crossref","unstructured":"Papamanthou, C., Tamassia, R., Triandopoulos, N.: Optimal verification of operations on dynamic sets. In: Proceedings of International Cryptology Conference (CRYPTO), vol. 6841 of LNCS, pp. 91\u2013110 (2011)","DOI":"10.1007\/978-3-642-22792-9_6"},{"key":"9968_CR46","doi-asserted-by":"crossref","unstructured":"Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: Nearly practical verifiable computation. In: Proceedings of Symposium on Security and Privacy (SSP), IEEE, pp. 238\u2013252 (2013)","DOI":"10.1109\/SP.2013.47"},{"issue":"139","key":"9968_CR47","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1090\/S0025-5718-1977-0436662-8","volume":"31","author":"FP Preparata","year":"1977","unstructured":"Preparata, F.P., Sarwate, D.V.: Computational complexity of Fourier transforms over finite fields. Math. Comput. 31(139), 740\u2013751 (1977)","journal-title":"Math. Comput."},{"key":"9968_CR48","doi-asserted-by":"crossref","unstructured":"Sander, T.: Efficient accumulators without trapdoor (extended abstract). In: Proceedings of International Conference on Information and Communications Security (ICICS), vol. 1726 of LNCS, pp. 252\u2013262 (1999)","DOI":"10.1007\/978-3-540-47942-0_21"},{"key":"9968_CR49","doi-asserted-by":"crossref","unstructured":"Sander, T., Ta-Shma, A., Yung, M.: Blind, auditable membership proofs. In: Proceedings of Financial Cryptography (FC), vol. 1962 of LNCS, pp. 53\u201371 (2001)","DOI":"10.1007\/3-540-45472-1_5"},{"key":"9968_CR50","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139165464","volume-title":"A Computational Introduction to Number Theory and Algebra","author":"V Shoup","year":"2005","unstructured":"Shoup, V.: A Computational Introduction to Number Theory and Algebra. Cambridge University Press, New York (2005)"},{"key":"9968_CR51","doi-asserted-by":"crossref","unstructured":"Tamassia, R.: Authenticated data structures. In: Proceedings of European Symposium on Algorithms (ESA), vol. 2832 of LNCS, pp. 2\u20135 (2003)","DOI":"10.1007\/978-3-540-39658-1_2"},{"key":"9968_CR52","doi-asserted-by":"crossref","unstructured":"Tamassia, R., Triandopoulos, N.: Computational bounds on hierarchical data processing with applications to information security. In: Proceedings of International Colloquium on Automata, Languages and Programming (ICALP), vol. 3580 of LNCS, pp. 153\u2013165 (2005)","DOI":"10.1007\/11523468_13"},{"key":"9968_CR53","doi-asserted-by":"crossref","unstructured":"Tamassia, R., Triandopoulos, N.: Efficient content authentication in peer-to-peer networks. In: Proceedings of Applied Cryptography and Network Security (ACNS), vol. 4521 of LNCS, pp. 354\u2013372 (2007)","DOI":"10.1007\/978-3-540-72738-5_23"},{"key":"9968_CR54","unstructured":"Tamassia, R., Triandopoulos, N.: Certification and authentication of data structures. In: Proceedings of Alberto Mendelzon Workshop on Foundations of Data Management (2010)"},{"key":"9968_CR55","doi-asserted-by":"crossref","unstructured":"Wang, P., Wang, H., Pieprzyk, J.: A new dynamic accumulator for batch updates. In: Proceedings of International Conference on Information and Communications Security (ICICS), vol. 4861 of LNCS, pp. 98\u2013112 (2007)","DOI":"10.1007\/978-3-540-77048-0_8"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9968-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9968-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9968-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,19]],"date-time":"2019-08-19T12:20:55Z","timestamp":1566217255000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9968-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,9]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9968"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9968-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,9]]}}}