Computational bounds on hierarchical data processing with applications to information security

Roberto Tamassia, Nikos Triandopoulos

Research output: Contribution to journalConference articlepeer-review

31 Scopus citations

Abstract

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).

Original languageEnglish
Pages (from-to)153-165
Number of pages13
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3580
DOIs
StatePublished - 2005
Event32nd International Colloquium on Automata, Languages and Programming, ICALP 2005 - Lisbon, Portugal
Duration: 11 Jul 200515 Jul 2005

Fingerprint

Dive into the research topics of 'Computational bounds on hierarchical data processing with applications to information security'. Together they form a unique fingerprint.

Cite this