Abstract | ||
---|---|---|
In the third-party model for the distribution of data, the trusted data creator or owner provides an untrusted distributor D with integrity verification (IV) items that are stored at D in addition to the n data items. When a user U has a subset of n' of those n data items and needs to verify their integrity, U is provided by D with a number of IV items that U uses to verify its data's integrity. The model forbids U from receiving any information about the n-n' data items that the user is not authorized to access, and assumes that D has no signature authority (it stores only pre-signed IVs). Most of the published work in this area uses the Merkle tree or variants thereof, and typically requires D to store a linear or close to linear (in n) number s(n) of IV items that are pre-signed by the trusted authority. Moreover, most of the existing schemes impose on D a non-constant amount of computation work t(n) (typically logarithmic in n) in order to provide U with the IV items that enable U to verify the integrity of its data; we call h(n) the number of such IV items. The h(n) values found in the literature are non-constant, i.e., they actually do depend on the number of data items. The main contribution of this paper is to achieve linear s(n), constant h(n) and constant or logarithmic t(n) when the n data items are organized in a tree hierarchy T, and the user's subset of n' items form a subtree T'. The cases of T' considered are when T' is (i) rooted at a node v and of depth k below v; and (ii) reachable in k hops from v going both up and down in T. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1109/ICDCS.2008.53 | ICDCS |
Keywords | Field | DocType |
merkle tree,n data item,data item,iv item,tree hierarchies,integrity verification,third-party data authentication,computation work,constant h,data creator,node v,user u,data integrity,government,servers,information security,distributed databases,digital signatures,authentication,data structures,generators,data security,distributed computing,message authentication,cryptography | Data structure,Authentication,Cryptography,Computer science,Tree (data structure),Computer network,Digital signature,Data integrity,Merkle tree,Hierarchy,Distributed computing | Conference |
ISSN | Citations | PageRank |
1063-6927 | 4 | 0.43 |
References | Authors | |
19 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Hao Yuan | 1 | 83 | 5.10 |
Mikhail J. Atallah | 2 | 3828 | 340.54 |