Paper 2009/625
Cryptographic Accumulators for Authenticated Hash Tables
Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos
Abstract
Hash tables are fundamental data structures that optimally answer membership queries. Suppose a client stores $n$ elements in a hash table that is outsourced at a remote server. Authenticating the hash table functionality, i.e., verifying the correctness of queries answered by the server and ensuring the integrity of the stored data, is crucial because the server, lying outside the administrative control of the client, can be malicious. 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.
Metadata
- Available format(s)
- PDF PS
- Publication info
- Published elsewhere. This is an extended version of the CCS 2008 paper "Authenticated Hash Tables"
- Keywords
- cryptographic accumulatorsauthenticated data structures
- Contact author(s)
- cpap @ cs brown edu
- History
- 2009-12-26: received
- Short URL
- https://ia.cr/2009/625
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2009/625, author = {Charalampos Papamanthou and Roberto Tamassia and Nikos Triandopoulos}, title = {Cryptographic Accumulators for Authenticated Hash Tables}, howpublished = {Cryptology {ePrint} Archive, Paper 2009/625}, year = {2009}, url = {https://eprint.iacr.org/2009/625} }