Authenticated hash tables

Hash tables are fundamental data structures that optimally answer membership queries. Suppose a client stores n ele-ments 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 ensur-ing 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 au-thenticating membership queries on hash tables: for any fixed constants 0 < ǫ < 1 and κ> 1/ǫ, the server can pro-vide a proof of integrity of the answer to a (non-)membership query in constant time, requiring O nǫ / logκǫ−1 n time to treat updates, yet keeping the communication and verifica-tion costs constant. This is the first construction for authen-ticating 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 ap-plies to two concrete data authentication models and lends itself to a scheme that achieves different trade-offs—namely, constant update time and O(nǫ / logκǫ n) query time for fixed ǫ> 0 and κ> 0. An experimental evaluation of our solution shows very good scalability