Summary
In an outsourced database (ODB) system the database owner publishes data through a number of remote servers, with the goal of enabling clients at the edge of the network to access and query the data more efficiently. As servers might be untrusted or can be compromised, query authentication becomes an essential component of ODB systems. In this chapter we present three techniques to authenticate election range queries and we analyze their performance over different cost metrics. In addition, we discuss extensions to other query types.
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
Hacigumus, H., Iyer, B.R., Mehrotra, S.: Providing database as a service. In: Proc. of International Conference on Data Engineering (ICDE). (2002) 29–40
Hore, B., Mehrotra, S., Tsudik, G.: A privacy-preserving index for range queries. In: Proc. of Very Large Data Bases (VLDB). (2004) 720–731
Agrawal, R., Srikant, R.: Privacy-preserving data mining. In: Proc. of ACM Management of Data (SIGMOD). (2000) 439–450
Evfimievski, A., Gehrke, J., Srikant, R.: Limiting privacy breaches in privacy preserving data mining. In: Proc. of ACM Symposium on Principles of Database Systems (PODS). (2003) 211–222
Hacigumus, H., Iyer, B.R., Li, C., Mehrotra, S.: Executing SQL over encrypted data in the database service provider model. In: Proc. of ACM Management of Data (SIGMOD). (2002) 216–227
Miklau, G., Suciu, D.: Controlling access to published data using cryptography. In: Proc. of Very Large Data Bases (VLDB). (2003) 898–909
Rizvi, S., Mendelzon, A., Sudarshan, S., Roy, P.: Extending query rewriting techniques for fine-grained access control. In: Proc. of ACM Management of Data (SIGMOD). (2004) 551–562
Bouganim, L., Ngoc, F.D., Pucheral, P., Wu, L.: Chip-secured data access: Reconciling access rights with data encryption. In: Proc. of Very Large Data Bases (VLDB). (2003) 1133–1136
Pang, H., Jain, A., Ramamritham, K., Tan, K.L.: Verifying completeness of relational query results in data publishing. In: Proc. of ACM Management of Data (SIGMOD). (2005) 407–418
Sion, R.: Query execution assurance for outsourced databases. In: Proc. of Very Large Data Bases (VLDB). (2005) 601–612
Anagnostopoulos, A., Goodrich, M., Tamassia, R.: Persistent authenticated dictionaries and their applications. In: ISC. (2001) 379–393
Goodrich, M., Tamassia, R., Triandopoulos, N., Cohen, R.: Authenticated data structures for graph and geometric searching. In: CT-RSA. (2003) 295–313
Tamassia, R., Triandopoulos, N.: Computational bounds on hierarchical data processing with applications to information security. In: ICALP. (2005) 153–165
Li, F., Yi, K., Hadjieleftheriou, M., Kollios, G.: Proof-infused streams: Enabling authentication of sliding window queries on streams. In: Proc. of Very Large Data Bases (VLDB). (2007)
Papadopoulos, S., Yang, Y., Papadias, D.: CADS: Continuous authentication on data streams. In: Proc. of Very Large Data Bases (VLDB). (2007)
McCurley, K.: The discrete logarithm problem. In: Proc. of the Symposium in Applied Mathematics, American Mathematical Society (1990) 49–74
National Institute of Standards and Technology: FIPS PUB 180-1: Secure Hash Standard. National Institute of Standards and Technology (1995)
Wang, X., Yin, Y., Yu, H.: Finding collisions in the full sha-1. In: CRYPTO. (2005)
Wang, X., Yao, A., Yao, F.: New collision search for SHA-1 (2005) Presented at the rump session of Crypto 2005.
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing 17(2) (1988) 96–99
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM (CACM) 21(2) (1978) 120–126
Pang, H., Tan, K.L.: Authenticating query results in edge computing. In: Proc. of International Conference on Data Engineering (ICDE). (2004) 560–571
Mykletun, E., Narasimha, M., Tsudik, G.: Authentication and integrity in outsourced databases. In: Symposium on Network and Distributed Systems Security (NDSS). (2004)
Narasimha, M., Tsudik, G.: Dsac: Integrity of outsourced databases with signature aggregation and chaining. In: Proc. of Conference on Information and Knowledge Management (CIKM). (2005) 235–236
Mykletun, E., Narasimha, M., Tsudik, G.: Signature bouquets: Immutability for aggregated/condensed signatures. In: European Symposium on Research in Computer Security (ESORICS). (2004) 160–176
Merkle, R.C.: A certified digital signature. In: Proc. of Advances in Cryptology (CRYPTO). (1989) 218–238
Naor, M., Nissim, K.: Certificate revocation and certificate update. In: Proceedings 7th USENIX Security Symposium (San Antonio, Texas). (1998)
Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., Stubblebine, S.: A general model for authenticated data structures. Algorithmica 39(1) (2004) 21–41
Li, F., Hadjieleftheriou, M., Kollios, G., Reyzin, L.: Dynamic authenticated index structures for outsourced databases. In: Proc. of ACM Management of Data (SIGMOD). (2006)
Comer, D.: The ubiquitous B-tree. ACM Computing Surveys 11(2) (1979) 121–137
Cheng, W., Pang, H., Tan, K.: Authenticating multi-dimensional query results in data publishing. In: DBSec. (2006)
Nuckolls, G.: Verified query results from hybrid authentication trees. In: DBSec. (2005) 84–98
Micali, S.: Efficient certificate revocation. Technical Report MIT/LCS/TM-542b, Massachusetts Institute of Technology, Cambridge, MA (1996)
Narasimha, M., Tsudik, G.: Authentication of outsourced databases using signature aggregation and chaining. In: DASFAA. (2006) 420–436
Lazaridis, I., Mehrotra, S.: Progressive approximate aggregate queries with a multi-resolution tree structure. In: Proc. of ACM Management of Data (SIGMOD). (2001) 401–412
Tao, Y., Papadias, D.: Range aggregate processing in spatial databases. IEEE Transactions on Knowledge and Data Engineering (TKDE) 16(12) (2004) 1555–1570
Li, F., Hadjieleftheriou, M., Kollios, G., Reyzin, L.: Authenticated index sturctures for aggregation queries in outsourced databases. Technical report, CS Dept., Boston University (2006)]
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer Science+Business Media, LLC.
About this chapter
Cite this chapter
Li, F., Hadjileftheriou, M., Kollios, G., Reyzin, L. (2008). Authenticated Index Structures for Outsourced Databases. In: Gertz, M., Jajodia, S. (eds) Handbook of Database Security. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-48533-1_5
Download citation
DOI: https://doi.org/10.1007/978-0-387-48533-1_5
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-48532-4
Online ISBN: 978-0-387-48533-1
eBook Packages: Computer ScienceComputer Science (R0)