Authenticated Hash Tables Based on Cryptographic Accumulators

Charalampos Papamanthou, Roberto Tamassia, Nikos Triandopoulos

Research output: Contribution to journalArticlepeer-review

41 Scopus citations

Abstract

Suppose a client stores n elements in a hash table that is outsourced to an untrusted server. We address the problem of authenticating the hash table operations, where the goal is to design protocols capable of verifying the correctness of queries and updates performed by the server, thus ensuring the integrity of the remotely stored data across its entire update history. Solutions to this authentication problem allow the client to gain trust in the operations performed by a faulty or even malicious server that lies outside the administrative control of the client. We present two novel schemes that implement an authenticated hash table. An authenticated hash table exports the basic hash-table functionality for maintaining a dynamic set of elements, coupled with the ability to provide short cryptographic proofs that a given element is a member or not of the current set. By employing efficient algorithmic constructs and cryptographic accumulators as the core security primitive, our schemes provide constant proof size, constant verification time and sublinear query or update time, strictly improving upon previous approaches. Specifically, in our first scheme which is based on the RSA accumulator, the server is able to construct a (non-)membership proof in constant time and perform updates in (Formula Presented.) time for any fixed constant 0 < ϵ < 1. A variation of this scheme achieves a different trade-off, offering constant update time and O(nϵ) query time. Our second scheme uses an accumulator based on bilinear pairings to achieve O(nϵ) update time at the server while keeping all other complexities constant. A variation of this scheme achieves O(nϵlogn) time for queries and constant update time. An experimental evaluation of both solutions shows their practicality.

Original languageEnglish
Pages (from-to)664-712
Number of pages49
JournalAlgorithmica (New York)
Volume74
Issue number2
DOIs
StatePublished - 1 Feb 2016

Keywords

  • Authenticated data structures
  • Cloud computing security
  • Cryptographic accumulators

Fingerprint

Dive into the research topics of 'Authenticated Hash Tables Based on Cryptographic Accumulators'. Together they form a unique fingerprint.

Cite this