Cryptology ePrint Archive: Report 2007/027
Verifying Data Integrity with Few Queries to Untrusted Memory
Nachiketh R. Potlapally
Abstract: We present a novel technique for verifying the integrity of data stored in an untrusted memory with a small number of memory accesses.
Memory integrity verification, which enables detection of tampering of data stored in untrusted memory, is an essential requirement of
secure processors that provide private and tamper-proof computation.
Limited on-chip storage in a secure processor makes it necessary
for it to store data (including program code) in an untrusted external memory where it is easily susceptible to adversarial tampering. Thus, to ensure validity of computation, it is extremely important to have techniques that can verify integrity of data stored in untrusted memory. Existing memory integrity verification techniques, like Merkle trees, impose very high communication overhead, i.e., large number of queries from processor to memory, in order to perform data integrity
verification. Given that memory latency is very high compared to execution speed of the processor, this imposes a significant running time penalty for applications executing on the processor. Our proposed technique, which is based on Chinese remaindering theorem, performs integrity verification with low communication
overhead while incurring a modest increase in on-chip storage requirement. We present the details of the proposed technique and provide corresponding proofs of security and correctness.
Category / Keywords: applications / Memory integrity, hash functions
Publication Info: This is a preliminary version, and has not been published anywhere
Date: received 26 Jan 2007, withdrawn 2 Feb 2007
Contact author: npotlapa at princeton edu
Available format(s): (-- withdrawn --)
Version: 20070202:213303 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]