We design efficient and secure protocols for optimally authenticating (non-)membership queries on hash tables, using cryptographic accumulators as our basic security primitive and applying them in a novel hierarchical way over the stored data. We provide the first construction for authenticating a hash table with \emph{constant query} cost and \emph{sublinear update} cost, strictly improving upon previous methods. Our first solution, based on the RSA accumulator, allows the server to provide a proof of integrity of the answer to a membership query in \emph{constant} time and supports updates in $O\left(n^{\epsilon}\log n\right)$ time for any fixed constant $0<\epsilon<1$, yet keeping the communication and verification costs constant. It also lends itself to a scheme that achieves different trade-offs---namely, constant update time and $O(n^{\epsilon})$ query time.
Our second solution uses an accumulator that is based on bilinear pairings to achieve $O(n^{\epsilon})$ update time at the server while keeping all other complexities constant. Both schemes apply to two concrete data authentication models and an experimental evaluation shows good scalability.
Category / Keywords: cryptographic accumulators, authenticated data structures Publication Info: This is an extended version of the CCS 2008 paper "Authenticated Hash Tables" Date: received 18 Dec 2009 Contact author: cpap at cs brown edu Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20091226:162919 (All versions of this report) Discussion forum: Show discussion | Start new discussion