Paper 2011/102

Optimal and Parallel Online Memory Checking

Charalampos Papamanthou and Roberto Tamassia

Abstract

Memory checking studies the problem of cryptographically verifying the correctness of untrusted indexed storage. After a series of results yielding checkers with $O(\log n)$ query complexity, Dwork, Naor, Ruthblum and Vaikuntanathan~\cite{naor-lower-mm08} derived an $\Omega(\log n/\log \log n)$ lower bound on the query complexity of any checker operating on memory words of polylogarithmic size, where $n$ is the number of memory indices. In view of this lower bound, we make the following two contributions: (1) We construct an \emph{optimal online memory checker} of $\Theta(\log n/\log \log n)$ query complexity, closing in this way the relevant complexity gap. Our construction employs pseudorandom functions and a simple data grouping technique inspired by I/O algorithms. (2) In our second and main result, we put forth the notion of \emph{parallel online memory checking} and provide parallel checker constructions with $O(1)$ query complexity and $O(\log n)$ processors. We initially show that checkers that use \emph{secret} small memory, including our optimal checker, are easily parallelizable; However, checkers that use only \emph{reliable} small memory cannot be naturally parallelized. We overcome this barrier by employing an algebraic hash function based on lattices assumptions and construct such parallel checkers with only reliable memory. To achieve our result, we establish and exploit a property that we call \emph{repeated linearity} of lattice-based hash functions, that might be of independent interest. Applications of our checkers include \emph{update-optimal} external memory authenticated data structures. We construct an authenticated B-tree data structure which can be updated with \emph{two} I/Os, outperforming the \emph{logarithmic} update complexity of hash-based external memory Merkle trees.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
authenticated data structureslattice-based cryptographymemory checking
Contact author(s)
cpap @ cs berkeley edu
History
2012-07-09: last of 6 revisions
2011-03-02: received
See all versions
Short URL
https://ia.cr/2011/102
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/102,
      author = {Charalampos Papamanthou and Roberto Tamassia},
      title = {Optimal and Parallel Online Memory Checking},
      howpublished = {Cryptology ePrint Archive, Paper 2011/102},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/102}},
      url = {https://eprint.iacr.org/2011/102}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.