CryptoDB
Memory Checking for Parallel RAMs
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| Award: | TCC Best Young Researcher Award |
| Abstract: | When outsourcing a database to an untrusted remote server, one might want to verify the integrity of contents while accessing it. To solve this, Blum et al. [FOCS `91] propose the notion of \emph{memory checking}. Memory checking allows a user to run a RAM program on a remote server, with the ability to verify integrity of the storage with small private storage. In this work, we define and initiate the formal study of memory checking for \emph{Parallel RAMs} (PRAMs). The parallel RAM model is very expressive and captures many modern architectures such as multi-core architectures and cloud clusters. When multiple clients run a PRAM algorithm on a shared remote server, it is possible that there are concurrency issues that cause inconsistencies. Therefore, integrity verification is also a desirable property in this setting. We construct an online memory checker (one that reports faults as soon as they occur) for PRAMs with $O(\log N)$ simulation overhead in both work and depth. Moreover, we construct an offline memory checker (one that reports faults only after a long sequence of operations) with amortized $O(1)$ simulation overhead in both work and depth. As an application of our parallel memory checking constructions, we construct a \emph{maliciously secure oblivious parallel RAM} (OPRAM) with polylogarithmic overhead. |
BibTeX
@inproceedings{tcc-2023-33642,
title={Memory Checking for Parallel RAMs},
publisher={Springer-Verlag},
author={Surya Mathialagan},
year=2023
}