Paper 2023/1703

Memory Checking for Parallel RAMs

Surya Mathialagan, Massachusetts Institute of Technology

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 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 local storage. In this work, we define and initiate the formal study of memory checking for 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 even more desirable property in this setting. Assuming only the existence of one-way functions, 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. In addition, 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. Our constructions match the best known simulation overhead of the memory checkers in the standard single-user RAM setting. As an application of our parallel memory checking constructions, we additionally construct the first maliciously secure oblivious parallel RAM (OPRAM) with polylogarithmic overhead.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2023
Memory checkingParallel RAMsOblivious RAMs
Contact author(s)
smathi @ mit edu
2023-11-03: approved
2023-11-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Surya Mathialagan},
      title = {Memory Checking for Parallel RAMs},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1703},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.