(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.
Category / Keywords: authenticated data structures, lattice-based cryptography, memory checking Date: received 1 Mar 2011, last revised 8 Jul 2012 Contact author: cpap at cs berkeley edu Available format(s): PDF | BibTeX Citation Version: 20120709:013338 (All versions of this report) Short URL: ia.cr/2011/102 Discussion forum: Show discussion | Start new discussion