Abstract
We address the problem of verifying the accuracy of query results provided by an untrusted third party Publisher on behalf of a trusted data Owner. We propose a flexible database verification structure, the Hybrid Authentication Tree (HAT), based on fast cryptographic hashing and careful use of a more expensive one-way accumulator. This eliminates the dependence on tree height of earlier Merkle tree based proposals and improves on the VB tree, a recent proposal to reduce proof sizes, by eliminating a trust assumption and reliance on signatures. An evaluation of the Hybrid Authentication Tree against the VB tree and Authentic Publication showing that a HAT provides the smallest proofs and faster verification than the VB tree. With moderate bandwidth limitations, the HATs low proof overhead reduces transfer time to significantly outweigh the faster verification time of Authentic Publication. A HAT supports two verification modes that can vary per query and per Client to match Client resources and applications. This flexibility allows the HAT to match the best performance of both hash based and accumulator based methods.
Chapter PDF
Similar content being viewed by others
References
Anagnostopoulos, A., Goodrich, M.T., Tamassia, R.: Persistent authenticated dictionaries and their applications. In: Davida, G.I., Frankel, Y. (eds.) ISC 2001. LNCS, vol. 2200, p. 379. Springer, Heidelberg (2001)
Benaloh, J., de Mare, M.: One-way accumulators: A decentralized alternative to digital signatures. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 274–285. Springer, Heidelberg (1994)
Bertino, E., Carminati, B., Ferrari, E., Thuraisingham, B., Gupta, A.: Selective and authentic third-party distribution of xml documents. IEEE Transactions on Knowledge and Data Engineering 16(10), 1263–1278 (2004)
Buldas, A., Laud, P., Lipmaa, H.: Eliminating counterevidence with applications to accountable certificate management. Journal of Computer Security 10, 273–296 (2002)
Devanbu, P., Gertz, M., Kwong, A., Martel, C., Nuckolls, G., Stubblebine, S.G.: Flexible authentication of xml documents. In: Proceedings of the 8th ACM Conference on Computer and Communications Security (CCS-8), pp. 136–145 (2001)
Devanbu, P.T., Gertz, M., Martel, C.U., Stubblebine, S.G.: Authentic publication over the internet. Journal of Computer Security 3(11), 291–314 (2003)
Goodrich, M., Tamassia, R., Schwerin, A.: Implementation of an authenticated dictionary with skip lists and commutative hashing. In: DISCEX II (2001)
Goodrich, M.T., Tamassia, R., Triandopoulos, N., Cohen, R.: Authenticated data structures for graph and geometric searching. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 295–313. Springer, Heidelberg (2003)
Li, J., Krohn, M.N., Mazires, D., Shasha, D.: Secure untrusted data repository (sundr). In: Proceedings of the 6th Symposium on Operating Systems Design and Implementation, pp. 91–106 (2004)
Maniatis, P., Baker, M.: Enabling the archival storage of signed documents. In: Proceedings of the USENIX Conference on File and Storage Technologies (FAST 2002), Monterey, CA, USA, January 2002, pp. 31–45. USENIX Association (2002)
Martel, C.U., Nuckolls, G., Devanbu, P.T., Gertz, M., Kwong, A., Stubblebine, S.G.: A general model for authenticated data structures. Algorithmica 39(1), 21–41 (2004)
Menenzes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1996)
Merkle, R.: Protocols for public key cryptosystems. In: Proceedings of the IEEE Symposium on Security and Privacy, pp. 122–134. IEEE Computer Society Press, Los Alamitos (1980)
Micali, S., Rabin, M.O., Kilian, J.: Zero-knowledge sets. In: Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), pp. 80–91 (2003)
Naor, M., Nissim, K.: Certificate revocation and certificate update. IEEE Journal on Selected Areas in Communications 18(4), 561–570 (2000)
Nyberg, K.: Fast accumulated hashing. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 83–87. Springer, Heidelberg (1996)
Pang, H., Tan, K.-L.: Authenticating query results in edge computing. In: Proceedings of the 20th International Conference on Data Engineering, ICDE 2004 (2004)
Smith, A., Ostrovsky, R., Rackoff, C.: Efficient consistency proofs for generalized queries on a committed database. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1041–1053. Springer, Heidelberg (2004)
Sander, T.: Efficient accumulators without trapdoor. In: Varadharajan, V., Mu, Y. (eds.) ICICS 1999. LNCS, vol. 1726, pp. 252–262. Springer, Heidelberg (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 IFIP International Federation for Information Processing
About this paper
Cite this paper
Nuckolls, G. (2005). Verified Query Results from Hybrid Authentication Trees. In: Jajodia, S., Wijesekera, D. (eds) Data and Applications Security XIX. DBSec 2005. Lecture Notes in Computer Science, vol 3654. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535706_7
Download citation
DOI: https://doi.org/10.1007/11535706_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28138-2
Online ISBN: 978-3-540-31937-5
eBook Packages: Computer ScienceComputer Science (R0)