International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 3, No. 1, 8 Feb. 2011
Cover page and Table of Contents: PDF (size: 431KB)
Author(s)
Ma Sha
1,*
Yang Bo
1
Li Kangshun
1
Index Terms
Database security, outsourced database, hashjoin, data authenticity
Abstract
In the Database As Service(DAS) model, authenticated join processing is more difficult than authenticated range query because the previous approach of authenticated range query, signature on a single relation, can not be used to verify join results directly. In this paper, an authenticated hash join processing algorithm is described in detail, which can take full advantage of database service since most of work is pushed to database service provider. We analyze the performance with respect to cost factors, such as communication cost, server-side cost and client-side cost. Finally, results of experiments validating our approach are also presented.
Cite This Paper
Ma Sha, Yang Bo, Li Kangshun, "A Method of Hash Join in the DAS Model", International Journal of Computer Network and Information Security(IJCNIS), vol.3, no.1, pp.26-32, 2011. DOI:10.5815/ijcnis.2011.01.04
Reference
[1]Hakan Hacigumus, Bala lyer, Chen Li, and Sharad Mehrotra, “Providing Database as a Service,” in Proc.of ICDE, San Jose, California, USA, February, 2002.
[2]Hakan Hacigumus, Bala lyer, Chen Li, and Sharad Mehrotra, “Executing SQL over Encrypted Data in the Database-Service-Provider Model,” in Proc. of ACM SIGMOND, ACM Press, 2002: 216-227.
[3]Yin Yang, Dimitris Papadias, Stavros Papadopoulos, and Panos Kalnis, “Authenticated Join Processing in Outsourced Database,” SIGMOD, Providence, RI, United states, 2009, pp. 5-17.
[4]M. Narasimha and G. Tsudik, “Authentication of outsourced databases using signature aggregation and chaining,” in Database Systems for Advanced Applications. 11th International Conference, DASFAA 2006. Proceedings, 12-15 April 2006, Berlin, Germany, 2006, pp. 420-36.
[5]R. C. Merkle, “A certified digital signature,” in Advances in Cryptology - CRYPTO '89. Proceedings, 20-24 Aug. 1989, Berlin, West Germany, 1990, pp. 218-38.
[6]F. Li, M. Hadjieleftheriou, G. Kollios and L. Reyzin, “Dynamic authenticated index structures for outsourced databases,” in 2006 ACM SIGMOD International Conference on Management of Data, June 27, 2006 - June 29, 2006, Chicago, IL, United states, 2006, pp. 121-132.
[7]K. Mouratidis, D. Sacharidis and H. Pang, “Partially materialized digest scheme: An efficient verification method for outsourced databases,” VLDB Journal, vol. 18, pp. 363-381, 2009.
[8]Davida, G..I., Wells, D.L., and Kam, J.B., “A Database Encryption System with Subkeys,” ACM Trans. Database Syst. 1981, 6(2): 312-328
[9]Min-Shiang, H. and Wei-Pang, Y., “Mulitilevel secure database encryption with subkeys,” Data and Knowledge Engineering 1997(22): 117-131
[10]Yuval Elovici, Ronen Waisenberg, Erez Shmueli, and Ehud Gudes, “A Structure Preserving Database Encryption Scheme,” SDM 2004, LNCS 3178(2004):28-40
[11]Ulrich Kuhn, “Analysis of a Database and Index Encryption Scheme,” SDM 2006, LNCS 4165: 146-159
[12]Hankan. Hacigumus, Bala lyer, and Sharad Mehrotra, “Efficient Execution of Aggregation Queries over Encrypted Relational Databases,” DASFAA 2004, LNCS 2973, Springer Berlin, 2004:125-136,
[13]E. amiani, S. D. C. di Vimercati, S. Jajodia, S.Paraboschi, and P. Samarati, “Balancing Confidentiality and Efficiency in Untrusted Relational DBMSs,” In Proc of the 10th ACM Conference on Computer and Communications Society, Washington, DC, USA, October, 2003: 27-31
[14]Erez Shmueli, Ronen Waisenberg, Yuval Elovici, and Ehud Gudes, “Designing Secure Indexes for Encrypted Databases,” Data and Applications Security 2005, LNCS 3654, Springer Berlin, 2005:54-68
[15]Jun Li and Edward R. Omiecinski, “Efficiency and Security Trade-Off in Supporting Range Queries on Encrypted Databases,” Data and Applications Security 2005, LNCS 3654,Springer Berlin, 2005:69-83
[16]Radu Sion, “Query Execution Assure for Outsource Databases,” Proceedings of the 31st VLDB Conference, Trondheim, Norway, 2005
[17]Hakan Hacigumus, Bala Iyer, and Sharad Mehrotra, “Query Optimization in Encrypted Database Systems,” DASFAA 2005, LNCS 3453(2005): 43-55
[18]H. H. Pang and K. L. Tan, “Authenticating query results in edge computing,” in Proceedings. 20th International Conference on Data Engineering, 30 March-2 April 2004, Los Alamitos, CA, USA, 2004, pp. 560-71.
[19]Li Feifei, Hadjieleftheriou Marios, Kollios George, and Reyzin Leonid, “Dynamic authenticated index structures for outsourced databases,” in 2006 ACM SIGMOD International Conference on Management of Data, June 27, 2006 - June 29, 2006, Chicago, IL, United states, 2006, pp. 121-132.
[20]Murat Kantarciouglo and Chris Clifton, “Security Issues in Querying Encrypted Data,” Purdue Computer Science Technical Report 04-013.
[21]Gultekin Ozsoyogulu, David A Singer, Sun S Chang, “Anti-Tamper databases: Querying Encrypted Databases,” Estes Park, Colorado, 2003