TY - GEN
T1 - Authenticated hash tables
AU - Papamanthou, Charalampos
AU - Tamassia, Roberto
AU - Triandopoulos, Nikos
PY - 2008
Y1 - 2008
N2 - 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.
AB - 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.
KW - Authentication
KW - Hash tables
KW - RSA accumulator
KW - Verification
UR - http://www.scopus.com/inward/record.url?scp=68849097095&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=68849097095&partnerID=8YFLogxK
U2 - 10.1145/1455770.1455826
DO - 10.1145/1455770.1455826
M3 - Conference contribution
AN - SCOPUS:68849097095
SN - 9781595938107
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 437
EP - 448
BT - Proceedings of the 15th ACM Conference on Computer and Communications Security, CCS'08
T2 - 15th ACM conference on Computer and Communications Security, CCS'08
Y2 - 27 October 2008 through 31 October 2008
ER -