Authenticated hash tables

Charalampos Papamanthou, Roberto Tamassia, Nikos Triandopoulos

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

101 Scopus citations

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 so that the client can save space or achieve load balancing. 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 membersiup queries on hash tables: for any fixed constants 0 < e < 1 and k > 1/e, the server can provide a proof of integrity of the answer to a (non-)membership query in constant time, requiring O (ne / logke-1 n) time to treat updates, yet keeping the communication and verification costs constant. This is the first construction for authenticating a hash table with constant query cost and sublinear update cost. Our solution employs the RSA accumulator in a nested way over the stored data, strictly improving upon previous accumulator-based solutions. Our construction applies to two concrete data authentication models and lends itself to a scheme that achieves different trade-offs namely, constant update time and O(ne /logke n) query time for fixed e > 0 and k > 0. An experimental evaluation of our solution shows very good scalability.

Original languageEnglish
Title of host publicationProceedings of the 15th ACM Conference on Computer and Communications Security, CCS'08
Pages437-448
Number of pages12
DOIs
StatePublished - 2008
Event15th ACM conference on Computer and Communications Security, CCS'08 - Alexandria, VA, United States
Duration: 27 Oct 200831 Oct 2008

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference15th ACM conference on Computer and Communications Security, CCS'08
Country/TerritoryUnited States
CityAlexandria, VA
Period27/10/0831/10/08

Keywords

  • Authentication
  • Hash tables
  • RSA accumulator
  • Verification

Fingerprint

Dive into the research topics of 'Authenticated hash tables'. Together they form a unique fingerprint.

Cite this