Authenticated hash tables

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 membership queries on hash tables: for any fixed constants 0 < ε < 1 and κ > 1/ε, the server can provide 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 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(n^ε/log^κε n) query time for fixed ε > 0 and κ > 0. An experimental evaluation of our solution shows very good scalability.

REFERENCES

• 1: Giuseppe Ateniese , Randal Burns , Reza Curtmola , Joseph Herring , Lea Kissner , Zachary Peterson , Dawn Song, Provable data possession at untrusted stores, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315318]
• 2: N. Baric and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In Proc. EUROCRYPT, pp. 480--494, 1997.
• 3: Josh Benaloh , Michael de Mare, One-way accumulators: a decentralized alternative to digital signatures, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.274-285, January 1994, Lofthus, Norway
• 4: Manuel Blum , Will Evans , Peter Gemmell , Sampath Kannan , Moni Naor, Checking the correctness of memories, Proceedings of the 32nd annual symposium on Foundations of computer science, p.90-99, October 01-04, 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185352]
• 5: Ahto Buldas , Peeter Laud , Helger Lipmaa, Accountable certificate management using undeniable attestations, Proceedings of the 7th ACM conference on Computer and communications security, p.9-17, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352604]
• 6: Jan Camenisch , Anna Lysyanskaya, Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.61-76, August 18-22, 2002
• 7: J. Lawrence Carter , Mark N. Wegman, Universal classes of hash functions (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.106-112, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803400]
• 8: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 9: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm Meyer auf der Heide , Hans Rohnert , Robert E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 10: C. Dwork, M. Naor, G.N. Rothblum, and V. Vaikuntanathan. How efficient can memory checking be? Manuscript, 2008.
• 11: R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random oracle. In Proc. EUROCRYPT, pp. 123--139, 1999.
• 12: M. T. Goodrich, C. Papamanthou, and R. Tamassia. On the cost of persistence and authentication in skip lists. In Proc. Workshop on Experimental Algorithms (WEA), pp. 94--107, 2007.
• 13: Michael T. Goodrich , Charalampos Papamanthou , Roberto Tamassia , Nikos Triandopoulos, Athos: Efficient Authentication of Outsourced File Systems, Proceedings of the 11th international conference on Information Security, September 15-18, 2008, Taipei, Taiwan [doi>10.1007/978-3-540-85886-7_6]
• 14: Michael T. Goodrich , Roberto Tamassia , Jasminka Hasic, An Efficient Dynamic and Distributed Cryptographic Accumulator, Proceedings of the 5th International Conference on Information Security, p.372-388, September 30-October 02, 2002
• 15: M.T. Goodrich, R. Tamassia, and A. Schwerin. Implementation of an authenticated dictionary with skip lists and commutative hashing. In Proc. DARPA Information Survivability Conference and Exposition II (DISCEX II), pp 68--82, 2001.
• 16: M.T. Goodrich, R. Tamassia, and N. Triandopoulos. Super-efficient verification of dynamic outsourced databases. In Proc. CT-RSA, pp. 407--424, 2008.
• 17: M.T. Goodrich, R. Tamassia, N. Triandopoulos, and R. Cohen. Authenticated data structures for graph and geometric searching. In Proc. CT-RSA, pp. 295--313, 2003.
• 18: Andreas Hutflesz , Hans-Werner Six , Peter Widmayer, Globally Order Preserving Multidimensional Linear Hashing, Proceedings of the Fourth International Conference on Data Engineering, p.572-579, February 01-05, 1988
• 19: C. M. Kenyon and J.S. Vitter. Maximum queue size and hashing with lazy deletion. Algorithmica, 6:597--619, 1991.
• 20: Jiangtao Li , Ninghui Li , Rui Xue, Universal Accumulators with Efficient Nonmembership Proofs, Proceedings of the 5th international conference on Applied Cryptography and Network Security, June 05-08, 2007, Zhuhai, China [doi>10.1007/978-3-540-72738-5_17]
• 21: Nathan Linial , Ori Sasson, Non-expansive hashing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.509-518, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237999]
• 22: Charles Martel , Glen Nuckolls , Premkumar Devanbu , Michael Gertz , April Kwong , Stuart G. Stubblebine, A General Model for Authenticated Data Structures, Algorithmica, v.39 n.1, p.21-41, January 2004 [doi>10.1007/s00453-003-1076-8]
• 23: Ralph C. Merkle, A Certified Digital Signature, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.218-238, August 20-24, 1989
• 24: J.K. Mullin. Spiral storage: Efficient dynamic hashing with constant-performance. Computer J., 28:330--334, 1985.
• 25: Moni Naor , Kobbi Nissim, Certificate revocation and certificate update, Proceedings of the 7th conference on USENIX Security Symposium, p.17-17, January 26-29, 1998, San Antonio, Texas
• 26: L. Nguyen. Accumulators from bilinear pairings and applications. In Proc. CT-RSA, pp. 275--292, 2005.
• 27: G. Nuckolls. Verified query results from hybrid authentication trees. In Proc. Data and Applications Security (DBSec), pages 84--98, 2005.
• 28: C. Papamanthou and R. Tamassia. Time and space efficient algorithms for two-party authenticated data structures. In Proc. Int. Conf. on Information and Communications Security (ICICS), pp. 1--15, 2007.
• 29: Tomas Sander, Efficient Accumulators without Trapdoor Extended Abstracts, Proceedings of the Second International Conference on Information and Communication Security, p.252-262, November 09-11, 1999
• 30: Tomas Sander , Amnon Ta-Shma , Moti Yung, Blind, Auditable Membership Proofs, Proceedings of the 4th International Conference on Financial Cryptography, p.53-71, February 20-24, 2000
• 31: V. Shoup. NTL: A library for doing number theory. http://www.shoup.net/ntl/.
• 32: R. Tamassia. Authenticated data structures. In Proc. European Symp. on Algorithms (ESA), pp. 2--5, 2003.
• 33: R. Tamassia and N. Triandopoulos. Computational bounds on hierarchical data processing with applications to information security. In Proc. Int. Colloquium on Automata, Languages and Programming (ICALP), pp. 153--165, 2005.
• 34: Roberto Tamassia , Nikos Triandopoulos, Efficient Content Authentication in Peer-to-Peer Networks, Proceedings of the 5th international conference on Applied Cryptography and Network Security, June 05-08, 2007, Zhuhai, China [doi>10.1007/978-3-540-72738-5_23]
• 35: P. Wang, H. Wang, and J. Pieprzyk. A new dynamic accumulator for batch updates. In Proc. Int. Conf. on Information and Communications Security (ICICS), pp. 98--112, 2007.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Algorithms, Security, Theory, Verification

Keywords:
authentication, hash tables, rsa accumulator, verification