Paper 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.
Metadata
- Available format(s)
- -- withdrawn --
- Category
- Applications
- Publication info
- Published elsewhere. This is a preliminary version, and has not been published anywhere
- Keywords
- Memory integrityhash functions
- Contact author(s)
- npotlapa @ princeton edu
- History
- 2007-02-02: withdrawn
- 2007-01-26: received
- See all versions
- Short URL
- https://ia.cr/2007/027
- License
-
CC BY