International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Verifying Data Integrity with Few Queries to Untrusted Memory

Nachiketh R. Potlapally
Search ePrint
Search Google
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.
  title={Verifying Data Integrity with Few Queries to Untrusted Memory},
  booktitle={IACR Eprint archive},
  keywords={applications / Memory integrity, hash functions},
  note={This is a preliminary version, and has not been published anywhere 13546 received 26 Jan 2007, withdrawn 2 Feb 2007},
  author={Nachiketh R. Potlapally},