Date Added: Dec 2009
Hash tables are fundamental data structures that optimally answer membership queries. Suppose a client stores n element 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. The authors design efficient and secure protocols for optimally authenticating (non-)membership queries on hash tables, using cryptographic accumulators as the basic security primitive and applying them in a novel hierarchical way over the stored data.