A General Model for Authenticated Data Structures
The DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,319
Algorithms on strings, trees, and sequences
Gusfield, D. (1997) · Cited by 1,697
Merkle, R. C. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_21 · Cited by 1,691 · cited 3×
“This construction, due to Merkle [20], [21], is called a Merkle hash tree and it has been used by several authors to solve problems related to authentic publication [22], [15], [9].”
BackgroundMethodHow to time-stamp a digital document
Haber, S., & Stornetta, W. S. (1991) · Journal of Cryptology · doi:10.1007/bf00196791 · Cited by 1,483 · cited 2×
“Related Work. The idea of data authentication has been considered for timestamping [ 15 ] and micro-payments [5].”
MethodProtocols for Public Key Cryptosystems
Merkle, R. C. (1980) · 1980 IEEE Symposium on Security and Privacy · doi:10.1109/sp.1980.10006 · Cited by 1,418 · cited 4×
“This construction, due to Merkle [20], [21], is called a Merkle hash tree and it has been used by several authors to solve problems related to authentic publication [22], [15], [9].”
BackgroundMethodInfluentialSkip lists: a probabilistic alternative to balanced trees
Pugh, W. (1990) · Communications of the ACM · doi:10.1145/78973.78977 · Cited by 1,165 · cited 1×
“Skip lists [23] can provide an attractive alternative to trees, and Goodrich et al.”
BackgroundThe art of computer programming. Vol.1: Fundamental algorithms
Knuth, D. E. (1978) · Virtual Defense Library (Ministerio de Defensa) · Cited by 827
Certificate revocation and certificate update
Naor, M., & Nissim, K. (2000) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.839932 · Cited by 493 · cited 9×
“Naor and Nissim [22] describe a method for producing authenticated versions of arbitrary data structures.”
BackgroundMethodInfluentialAuthentic Third-Party Data Publication
Devanbu, P., Gertz, M., Martel, C., & Stubblebine, S. G. (2002) · IFIP International Federation for Information Processing · doi:10.1007/0-306-47008-x_9 · Cited by 227 · cited 4×
“Authenticated MDRTs were also discussed in [9].”
MethodInfluentialSelf-citationNew Data Structures for Orthogonal Range Queries
Willard, D. E. (1985) · SIAM Journal on Computing · doi:10.1137/0214019 · Cited by 197 · cited 3×
“The new structure is a bounded degree DAG, so we can again apply Theorem 4 using the complexity result from [26].”
BackgroundMethodInfluential
Cited by
Dynamic authenticated index structures for outsourced databases
Li, F., Hadjieleftheriou, M., Kollios, G., & Reyzin, L. (2006) · Proceedings of the 2006 ACM SIGMOD international conference on Management of data · doi:10.1145/1142473.1142488 · Cited by 415
Verifiable Delegation of Computation over Large Datasets
Benabbas, S., Gennaro, R., & Vahlis, Y. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_7 · Cited by 379
Verifiable Computation over Large Database with Incremental Updates
Chen, X., Li, J., Weng, J., Ma, J., & Lou, W. (2016) · IEEE Transactions on Computers · doi:10.1109/tc.2015.2512870 · Cited by 257
Verifiable delegation of computation on outsourced data
Backes, M., Fiore, D., & Reischuk, R. M. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516681 · Cited by 193
“Existing work addresses both static settings and dynamic settings (where data structures can be updated), and it mostly focuses on specific data structure operations, such as range search queries over databases [31, 36], authenticated dictionaries [21, 41, 30], and set operations over a dynamic collection of sets [42].”
BackgroundvSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases
Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., & Papamanthou, C. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.43 · Cited by 170
“, range queries [43], [47], joins [59], [62], [30], pattern matching [27], [48], set operations [50], [21], [41], polynomial evaluation [9], graph queries [35], [61], and search problems [45], [46].”
BackgroundVerifying computations with state
Braun, B., Feldman, A. J., Ren, Z., Setty, S., Blumberg, A. J., & Walfish, M. (2013) · Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles · doi:10.1145/2517349.2522733 · Cited by 167
“First, Pantry relies on Merkle trees [53] to authenticate a large untrusted memory, an idea used in theory [17] and in practice (for smartcards [30], databases [27, 49, 52], file systems [34, 43], etc.”
MethodBalloon: A Forward-Secure Append-Only Persistent Authenticated Data Structure
Pulls, T., & Peeters, R. (2015) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-24177-7_31 · Cited by 30
Continuous Tamper-Proof Logging Using TPM 2.0
Sinha, A., Jia, L., England, P., & Lorch, J. R. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-08593-7_2 · Cited by 30
Metadata
- Authors
- Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., & Stubblebine, S. G.
- Venue
- Algorithmica
- Published
- 2004-01-27
- Volume
- 39
- Issue
- 1
- Pages
- 21-41
- ISSN
- 0178-4617 (ISSN-L)
- 1432-0541
- OpenAlex
- W2169731081
- Cited by
- 210
- References
- 16
- FWCI
- 9.49
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.