Hweehwa Pang
Skip Abstract Section
Abstract
The number of successful attacks on the Internet shows that it is very difficult to guarantee the security of online servers over extended periods of time. A breached server that is not detected in time may return incorrect query answers to users. In this article, we introduce authentication schemes for users to verify that their query answers from an online server are complete (i.e., no qualifying tuples are omitted) and authentic (i.e., all the result values are legitimate). We introduce a scheme that supports range selection, projection as well as primary key-foreign key join queries on relational databases. We also present authentication schemes for single- and multi-attribute range aggregate queries. The schemes complement access control mechanisms that rewrite queries dynamically, and are computationally secure. We have implemented the proposed schemes, and experiment results showed that they are practical and feasible schemes with low overheads.
- <scp>Anderson, R., Needham, R., and Shamir, A.</scp> 1998. The Steganographic file system. In <it>Information Hiding, 2nd International Workshop</it>. Portland, OR. D. Aucsmith Ed.Google Scholar
- <scp>Boneh, D., Gentry, C., Lynn, B., and Shacham, H.</scp> 2003. Aggregate and verifiably encrypted signatures from bilinear maps. In <it>Proceedings of Advances in Cryptology (EUROCRYPT'03)</it>, E. Biham Ed., <it>Lecture Notes in Computer Science</it>, Springer-Verlag. 416--432. Google ScholarDigital Library
- <scp>Cheng, W., Pang, H., and Tan, K.-L.</scp> 2006. Authenticating multi-dimensional query results in data publishing. In <it>Proceedings of the 20th Annual IFIP WG 11.3 Working Conference on Data and Applications Security</it>.Google Scholar
- <scp>Chokani, S.</scp> 1992. Trusted Products Evaluation. <it>Comm. ACM 35,</it> 7, 64--76. Google ScholarDigital Library
- <scp>Chun, S.-J., Chung, C.-W., Lee, J.-H., and Lee, S.-L.</scp> 2001. Dynamic update cube for range-sum queries. In <it>Proceedings of the International Conference on Very Large Data Bases (VLDB'01)</it>. 521--530. Google ScholarDigital Library
- <scp>Damiani, E., di Vimercati, S. D. C., Foresti, S., Jajodia, S., Paraboschi, S., and Samarati, P.</scp> 2005a. Metadata management in outsourced encrypted databases. In <it>Proceedings of the 2nd VLDB Workshop on Secure Data Management (SDM'05)</it>. Google ScholarDigital Library
- <scp>Damiani, E., di Vimercati, S. D. C., Foresti, S., Samarati, P., and Viviani, M.</scp> 2005b. Measuring Inference Exposure in Outsourced Encrypted Databases. In <it>Proceedings of the 1st Workshop on Quality of Protection</it>.Google Scholar
- <scp>Devanbu, P., Gertz, M., Martel, C., and Stubblebine, S.</scp> 2000. Authentic data publication over the Internet. In <it>14th IFIP Working Conference in Database Security</it>. 102--112. Google ScholarDigital Library
- <scp>Devanbu, P., Gertz, M., Martel, C., and Stubblebine, S.</scp> 2003. Authentic data publication over the Internet. <it>J. Comput. Secur. 11</it>, 291--314. Google ScholarDigital Library
- <scp>DriveCrypt</scp>. Secure hard disk encryption. http://www.drivecrypt.com.Google Scholar
- <scp>DSS</scp>. 1991. Proposed federal information processing standard for digital signature standard (DSS). <it>Federal Register 56, 169</it>, 42980--42982.Google Scholar
- <scp>EFS</scp>. Encrypting file system for windows 2000. http://www.microsoft.com/windows2000/techinfo/howitworks/security/encrypt. asp.Google Scholar
- <scp>Geffner, S., Agrawal, D., and Abbadi, A. E.</scp> 2000. The dynamic data cube. In <it>Proceedings of the International Conference on Extending Database Technology (EDBT'00)</it>. 237--253. Google ScholarDigital Library
- <scp>Gray, J., Chaudhuri, S., Bosworth, A., Layman, A., Reichart, D., Venkatrao, M., Pellow, F., and Pirahesh, H.</scp> 1997. Data Cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. <it>J. Data Min. Knowl. Discov. 1,</it> 1, 29--53. Google ScholarDigital Library
- <scp>Hacigümüs, H., Iyer, B. R., Li, C., and Mehrotra, S.</scp> 2002. Executing SQL over encrypted data in the database-service-provider model. In <it>Proceedings of the ACM International Conference on Management of Data</it> (<it>SIGMOD'02</it>). 216--227. Google ScholarDigital Library
- <scp>Ho, C.-T., Agrawal, R., Megiddo, N., and Srikant, R.</scp> 1997. Range Queries in OLAP data cubes. In <it>Proceedings of the ACM International Conference on Management of Data</it> (<it>SIGMOD'97</it>). 73--88. Google ScholarDigital Library
- <scp>Li, F., Hadjieleftheriou, M., Kollios, G., and Reyzin, L.</scp> 2006. Dynamic authenticated index structures for outsourced databases. In <it>Proceedings of the 25th ACM International Conference on Management of Data</it> (<it>SIGMOD'06</it>). 121--132. Google ScholarDigital Library
- <scp>Li, J. and Omiecinski, E. R.</scp> 2005. Efficiency and security trade-off in supporting range queries on encrypted databases. In <it>Proceedings of the 19th Annual IFIP WG 11.3 Working Conference on Data and Applications Security</it>. Google ScholarDigital Library
- <scp>Ma, D., Deng, R. H., Pang, H., and Zhou, J.</scp> 2005. Authenticating query results from untrusted servers. In <it>Proceedings of the 7th International Conference on Information and Communications Security</it>. Google ScholarDigital Library
- <scp>Martel, C., Nuckolls, G., Devanbu, P., Gertz, M., Kwong, A., and Stubblebine, S.</scp> 2004. A general model for authenticated data structures. <it>Algorithmica 39,</it> 1, 21--41. Google ScholarDigital Library
- <scp>Merkle, R.</scp> 1989. A certified digital signature. In <it>Proceedings of Advances in Cryptology (Crypto'89), </it>Lecture Notes in Computer Science. vol. 0435. 218--238. Google ScholarDigital Library
- <scp>Mykletun, E., Narasimha, M., and Tsudik, G.</scp> 2004. Authentication and integrity in outsourced databases. In <it>Proceedings of the Network and Distributed System Security Symposium</it>.Google Scholar
- <scp>Narasimha, M. and Tsudik, G.</scp> 2006. Authentication of outsourced databases using signature aggregation and chaining. In <it>Proceedings of the 11th International Conference on Database Systems for Advanced Applications, (DASFAA'06)</it>, 420--436. Google ScholarDigital Library
- <scp>Neuman, B. and Tso, T.</scp> 1994. Kerberos: An authentication service for computer networks. <it>IEEE Comm. 32,</it> 9, 33--38.Google Scholar
- <scp>Oracle VPD</scp>. 2002. The virtual private database in Oracle9ir2: An Oracle technical white paper. http://otn.oracle.com/deploy/security/oracle9ir2/pdf/vpd9ir2twp.pdf.Google Scholar
- <scp>Pang, H., Jain, A., Ramamritham, K., and Tan, K.-L.</scp> 2005. Verifying completeness of relational query results in data publishing. In <it>Proceedings of the ACM International Conference on Management of Data</it> (<it>SIGMOD'05</it>). 407--418. Google ScholarDigital Library
- <scp>Pang, H. and Tan, K.</scp> 2004. Authenticating query results in edge computing. In <it>IEEE International Conference on Data Engineering</it>. 560--571. Google ScholarDigital Library
- <scp>Pang, H., Tan, K., and Zhou, X.</scp> 2003. StegFS: A Steganographic file system. In <it>Proceedings of the 19th International Conference on Data Engineering</it>. Bangalore, India, 657--668.Google Scholar
- <scp>Papadias, D., Kalnis, P., Zhang, J., and Tao, Y.</scp> 2001. Efficient OLAP operations in spatial data warehouses. In <it>Proceedings of the 7th International Symposium on Spatial and Temporal Databases</it>. 443--459. Google ScholarDigital Library
- <scp>Papadias, D., Tao, Y., Kalnis, P., and Zhang, J.</scp> 2002. Indexing spatio-temporal data warehouses. In <it>IEEE International Conference on Data Engineering</it>. 166--175. Google ScholarDigital Library
- <scp>PGPdisk</scp>. http://www.pgpi.org/products/pgpdisk/.Google Scholar
- <scp>Przydatek, B., Song, D., and Perrig, A.</scp> 2003. SIA: Secure information aggregation in sensor networks. In <it>Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, (SenSys'03)</it>. 255--265. Google ScholarDigital Library
- <scp>Rivest, R.</scp> 1992. RFC 1321: The MD5 Message-Digest Algorithm. Internet Activities Board. Google ScholarDigital Library
- <scp>Rivest, R. and Shamir, A.</scp> 2001. PayWord and MicroMint: Two simple micropayment schemes. In http://theory.lcs.mit.edu/rivest/RivestShamir-mpay.pdf. Google ScholarDigital Library
- <scp>Rivest, R., Shamir, A., and Adleman, L.</scp> 1978. A method for obtaining digital signatures and public-key cryptosystems. <it>Comm. ACM 21,</it> 2, 120--126. Google ScholarDigital Library
- <scp>Robinson, J.</scp> 1981. The K-D-B-Tree: A search structure for large multidimensional dynamic indexes. In <it>Proceedings of the ACM International Conference on Management of Data (SIGMOD'81)</it>. 10--18. Google ScholarDigital Library
- <scp>Samet, H.</scp> 1984. The Quadtree and Related Hierarchical Data Structures. <it>ACM Comput. Surv. 16,</it> 2, 187--260. Google ScholarDigital Library
- <scp>Sandhu, R. and Samarati, P.</scp> 1994. Access Control: Principles and Practice. <it>IEEE Comm. 32,</it> 9, 40--48.Google Scholar
- <scp>SHA</scp>. 2001. Secure hashing algorithm. National Institute of Science and Technology. FIPS 180-2.Google Scholar
- <scp>Zhang, D., Tsotras, V. J., and Gunopulos, D.</scp> 2002. Efficient aggregation over objects with extent. In <it>Symposium on Principles of Database Systems (PODS ACM SIGACT-SIGMOD-SIGART'02)</it>. 121--132. Google ScholarDigital Library
Index Terms
- Verifying Completeness of Relational Query Answers from Online Servers
Recommendations
Verifying completeness of relational query results in data publishing
SIGMOD '05: Proceedings of the 2005 ACM SIGMOD international conference on Management of dataIn data publishing, the owner delegates the role of satisfying user queries to a third-party publisher. As the publisher may be untrusted or susceptible to attacks, it could produce incorrect query results. In this paper, we introduce a scheme for users ...
First-order under-approximations of consistent query answers
Consistent Query Answering (CQA) is a principled approach for answering queries on inconsistent databases. The consistent answer to a query q on an inconsistent database db is the intersection of the answers to q on all repairs, where a repair is any ...
Adding completeness information to query answers over spatial databases
SIGSPATIAL '14: Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information SystemsReal-life spatial databases are inherently incomplete. This is in particular the case when data from different sources are combined. An extreme example are volunteered geographical information systems like OpenStreetMap.
When querying such databases the ...
Comments