Towards constant bandwidth overhead integrity checking of untrusted data

D. Clarke, G.E. Suh, B. Gassend, A. Sudan, M. Van Dijk, S. Devadas

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We present an adaptive tree-log scheme to improve the performance of checking the integrity of arbitrarily-large untrusted data, when using only a small fixed-sited trusted state. Currently, hash trees are used to check the data. In many systems that use hash trees, programs perform many data operations before performing a critical operation that exports a result outside of the program's execution environment. The adaptive tree-log scheme we present uses this observation to harness the power of the constant runtime bandwidth overhead of a log-based scheme. For all programs, the adaptive tree-log scheme's bandwidth overhead is guaranteed to never be worse than a parameterizable worst case bound. Furthermore, for all programs, as the average number of times the program accesses data between critical operations increases, the adaptive tree-log scheme's bandwidth overhead moves from a logarithmic to a constant bandwidth overhead. © 2005 IEEE.
Original languageEnglish
Title of host publicationProceedings - 2005 IEEE Symposium on Security and Privacy, IEEE S and P 2005
Pages139-153
DOIs
Publication statusPublished - 2005
Externally publishedYes
Event2005 IEEE Symposium on Security and Privacy, IEEE S and P 2005 - , United States
Duration: 8 May 200511 May 2005

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
ISSN (Print)1081-6011

Conference

Conference2005 IEEE Symposium on Security and Privacy, IEEE S and P 2005
Country/TerritoryUnited States
Period8/05/0511/05/05

Fingerprint

Dive into the research topics of 'Towards constant bandwidth overhead integrity checking of untrusted data'. Together they form a unique fingerprint.

Cite this