TY - JOUR
T1 - Computational bounds on hierarchical data processing with applications to information security
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
PY - 2005
Y1 - 2005
N2 - We introduce hierarchical data processing (HDP) problems, a class of computations over a collection of values associated with a set of n elements, based on a directed acyclic graph (DAG). We present an Ω(log n) lower bound on various computational cost measures for HDP problems and we develop an efficient randomized DAG scheme for HDP problems. We apply our results to data authentication through cryptographic hashing and multicast key distribution using key-graphs. We show that both problems involve HDP and prove logarithmic lower bounds on their computational and communication costs. Using our new DAG scheme, we present a new efficient authenticated dictionary and a new skip-list version with expected search complexity 1.25 log2 n + O(1).
AB - We introduce hierarchical data processing (HDP) problems, a class of computations over a collection of values associated with a set of n elements, based on a directed acyclic graph (DAG). We present an Ω(log n) lower bound on various computational cost measures for HDP problems and we develop an efficient randomized DAG scheme for HDP problems. We apply our results to data authentication through cryptographic hashing and multicast key distribution using key-graphs. We show that both problems involve HDP and prove logarithmic lower bounds on their computational and communication costs. Using our new DAG scheme, we present a new efficient authenticated dictionary and a new skip-list version with expected search complexity 1.25 log2 n + O(1).
UR - http://www.scopus.com/inward/record.url?scp=26444561838&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=26444561838&partnerID=8YFLogxK
U2 - 10.1007/11523468_13
DO - 10.1007/11523468_13
M3 - Conference article
AN - SCOPUS:26444561838
SN - 0302-9743
VL - 3580
SP - 153
EP - 165
JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
T2 - 32nd International Colloquium on Automata, Languages and Programming, ICALP 2005
Y2 - 11 July 2005 through 15 July 2005
ER -