Abstract
Database outsourcing is an important emerging trend which involves data owners delegating their data management needs to an external service provider. Since a service provider is almost never fully trusted, security and privacy of outsourced data are important concerns. A core security requirement is the integrity and authenticity of outsourced databases. Whenever someone queries a hosted database, the results must be demonstrably authentic (with respect to the actual data owner) to ensure that the data has not been tampered with. Furthermore, the results must carry a proof of completeness which will allow the querier to verify that the server has not omitted any valid tuples that match the query predicate. Notable prior work ([4,9,15]) focused on various types of Authenticated Data Structures. Another prior approach involved the use of specialized digital signature schemes. In this paper, we extend the state-of-the-art to provide both authenticity and completeness guarantees of query replies. Our work analyzes the new approach for various base query types and compares it with Authenticated Data Structures. We also point out some possible security flaws in the approach suggested in the recent work of [15].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bellare, M., Goldreich, O., Goldwasser, S.: Incremental cryptography and application to virus protection. In: 27th Annual Symposium of Theory of Computing (1995)
Bellare, M., Micciancio, D.: A new paradigm for collsion-free hashing: Incrementality at reduced cost. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, Springer, Heidelberg (1999)
Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, Springer, Heidelberg (2003)
Devanbu, P., Gertz, M., Martel, C., Stubblebine, S.G.: Authentic third-party data publication. In: 14th IFIP Working Conference in Database Security (2000)
Hacigümüş, H., Iyer, B., Li, C., Mehrotra, S.: Executing SQL over Encrypted Data in the Database-Service-Provider Model. In: SIGMOD (2002)
Hacigümüş, H., Iyer, B., Mehrotra, S.: Encrypted Database Integrity in Database Service Provider Model. In: CSES 2002 IFIP WCC (2002)
Hacigümüş, H., Iyer, B., Mehrotra, S.: Providing Database as a Service. In: ICDE 2002 (2002)
Hore, B., Mehrotra, S., Tsudik, G.: A Privacy-Preserving Index for Range Queries. In: VLDB (2004)
Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., Stubblebine, S.G.: A general model for authenticated data structures. Algorithmica 39(1) ( January 2004)
Menezes, A.J., van Oorschot, P.C., Vanstone, S.A.: Handbook of applied cryptography. CRC Press, Boca Raton (1997)
Merkle, R.: Protocols for public key cryptosystems. In: IEEE Symposium on Research in Security and Privacy (1980)
Mykletun, E., Narasimha, M., Tsudik, G.: Authentication and Integrity in Outsourced Databases. In: Network and Distributed Systems Security (2004)
National Institute of Standards and Technology (NIST). Secure Hash Standard. FIPS PUB 180-1 (April 1995)
OpenSSL Project, http://www.openssl.org
Pang, H., Tan, K.-L.: Authenticating Query Results in Edge Computing. In: ICDE (2004)
Rivest, R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21(2) (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Narasimha, M., Tsudik, G. (2006). Authentication of Outsourced Databases Using Signature Aggregation and Chaining. In: Li Lee, M., Tan, KL., Wuwongse, V. (eds) Database Systems for Advanced Applications. DASFAA 2006. Lecture Notes in Computer Science, vol 3882. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11733836_30
Download citation
DOI: https://doi.org/10.1007/11733836_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33337-1
Online ISBN: 978-3-540-33338-8
eBook Packages: Computer ScienceComputer Science (R0)