International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Update-Optimal Authenticated Structures Based on Lattices

Charalampos Papamanthou
Roberto Tamassia
Search ePrint
Search Google
Abstract: We study the problem of authenticating a \emph{dynamic table} with $n$ entries in the authenticated data structures model, which is related to memory checking. We present the first dynamic authenticated table that is \emph{update-optimal}, using a \emph{lattice-based} construction. In particular, the update time is $O(1)$, improving in this way the ``a priori'' $O(\log n)$ update bounds for previous constructions, such as the Merkle tree. Moreover, the space used by our data structure is $O(n)$ and logarithmic bounds hold for the other complexity measures, such as \emph{proof size}. To achieve this result, we exploit the \emph{linearity} of lattice-based hash functions and show how the security of lattice-based digests can be guaranteed under updates. This is the first construction achieving constant update bounds without causing other time complexities to increase beyond logarithmic. All previous solutions enjoying constant update complexity have $\Omega(n^\epsilon)$ proof or query bounds. As an application of our lattice-based authenticated table, we provide the first construction of an authenticated Bloom filter, an update-intensive data structure that falls into our model.
  title={Update-Optimal Authenticated Structures Based on Lattices},
  booktitle={IACR Eprint archive},
  keywords={authenticated data structures, lattice-based cryptography},
  note={ 14798 received 7 Mar 2010, last revised 8 Jul 2010},
  author={Charalampos Papamanthou and Roberto Tamassia},