UPDATE Query over Encrypted Data Shaukat Ali, Azhar Raut: Saeed Mahfooz
Department of Computer Science, University ofPeshawar, Peshawar, Pakistan
[email protected],
{ azhar.rauf,saeedmahfooz } @upesh.edu.pk
Abstract- Data is a critical asset for every organization.
This paper proposes a novel updating technique which improves the performance of UPDATE query and it has no "false positive hits". For SELECT query if a technique has some "false positive hits" so post processing can be done to remove the extra records, but in case ofUPDATE query there is zero tolerance for "false positive hits". This technique is compatible with all encryption mechanisms. Definition 1: The un-wanted record(s) retrieved during a query is called False Positive Hits. If NJ is the query result in first phase of a query and N2 is the query result
Data of organimtions are normally stored in database, therefore, database security is important. Encryption is one of the strong security layers in database security, but SQL has a limitation that its queries cannot be run directly on encrypted
data.
When
some update
is
needed
in
an
encrypted column of table so the entire column needs to be decrypted before updation process, this degrades system performance. This paper proposes a new technique to update value directly although the conditioned column is in
encrypted form. It does not need to decrypt the entire conditioned
column
for update
process.
This
improves
of post processing query, then false positive hits ( f ) of query can be calculated using the following formula [3].
system performance.
Keywortk---t--Da abase security, Encryption, Perfurmance
I.
f=
INTRODUCTION
Security is one of the hunting areas in database. Database stores critical and important data of business which necessitates database security. There are many layers of database security, encryption is one of them. Encryption is a strong layer of security as it secures data even after it has been hacked by someone. Security of data is considered to be vulnerable when some information can be extracted from it. No information can be retrieved from encrypted data, therefore, it provides security even after penetration of intruder into database [1, 2]. Encryption has a flaw that it reduces the performance of DML(Data Manipulation Language) queries of SQL (Structure Query Language). Encryption degrades performance because the SQL queries cannot be run directly on encrypted data [3]. Security of the data is a challenge because any information leakage can sometime cause a big loss to a business. For example, the accounts information is very critical in the banking sector. Unauthorized access to data of a bank can cause stealing of the accounts information which can result a big loss to the bankers. Most of organizations' data is stored in databases using Database Management Systems that necessitates the security of databases. There are some techniques which address the problem of performance degradation. However, these techniques are ! imited for SELECT query only. For example, hashmg technique [4], [5] bucketization [6], Order Preserving Technique [7]. These techniques do not focus on the situation if update is done on the bases of column which is encrypted. The function of SELECT and UPDATE queries are different in sense that post processing can be done in SELECT query but cannot in UPDATE query.
_N..o!.l_-_N ..2L .,, N2
Definition 2: Conditioned column is that one which is given in the WHERE clause of SQL query.
II.
RELATED WORK
The UPDATE query is considered to be one of the essential transactions of database system. Similarly, at least one invocation of decryption function is needed for an update transaction [8]. Many work has been done in case of SELECT query over encrypted data [4, 7, 9, 10] , but that work cannot be extended to UPDAlE query because it has some "false positive hits". Cipher index method [4] uses hash values for searching over encrypted data column. This technique works for fuzzy match SELECT queries in which the wildcard "%" is used at the end of the string. According to the results taken during their experiments, the probability of conflict of search condition with extra records is from 0.1 to 1 having average of 0.55. Gao Feng and Zhao Danfeng used Cryptograph Index Technology to improve efficiency of query over encrypted data [11]. According to this method, the probability of buckets conflict is from 0.1 to 0.4 with the average of 0.25. If the bucket conflict is ignored and the ratio between buckets and total records in table is 1: 10 still the probability of false positive hits of queries is 0.1. Yong Zhang et al. [10] proposed a bucket index method to speedup the performance of searching over encrypted data In this method, the probability of conflict with unwanted records is from 0.05 to 0.25 having average of 0.15. It means that the probability of extra records to be decrypted is 0.15. The work of Lianzhong Liu and Jingfen Gai [12] has the probability of false positive query hits ranging from 0.1 to 0.7 having average of 0.4. In this work, authors
978-1-61284-941-6/11/$26.00 ©2011 IEEE 279
proposed a separate bucket index method for numeric data and a compression algorithm called 'Bloom filter" is used for character data to reduce the search condition scope. In our proposed technique, there is no "false positive hits" as a query decrypts and retrieves the required values only as per the given search condition. It is clear that other techniques are decrypting unwanted values which is acceptable in case of SELECT query as post processing can be done, but it is unacceptable in case of update query. The "false positi ve hits" also reduces the performance. Here, most of the work is discussed from search or select query. It is because in update query we also searching a record before updating it.
2. 3.
Actual table: This table contains the whole data including the encrypted sensitive column. Additional table: This is an extra table which is used for searching the particular record(s) which need to be updated.
r································1 Additional table
III. RESEARCH PROBLEM AND HYPOTHESIS When someone updates a value in a table then a condition is used in WHERE clause. If the condition is on encrypted data column then the entire column needs to be decrypted and after this the update query can operate on it. The decryption of entire column reduces the query performance. Hypothesis to reduce the problem is as follow: Keeping the encrypted column in a separate table (Additional table) will improve the performance of UPDATE query.
No
Secure_Schema
CI: Checks the encrypted nature of conditioned column in the WHERE clause?
IV. PROPOSED SECURITY TECHNIQUE Security in proposed technique is introduced with the help of an additional table. The other table which contains the whole data along with sensitive encrypted data column is called Actual Table. The additional table contains the encrypted data column of Actual_Table in the plain form and key (Primary key) of Actual_Table in the encrypted form, which hides the relationship between Actual Table and additional table. The order of the rows in Actual_Table and additional table will not be same, rows will be shuffled in additional table. Apart from this, the additional table is stored in secured schema. The secured schema is that one to which only those users are allowed who has clearance to the encrypted data.
C2: Checks the authorization of user to encrypted data? C3: Is any key returned from the query? Fig. I Architecture of Proposed System
The Update mechanism of the proposed technique is explained by the following example. Reference to table 1, suppose a user poses the following query over the Actual_Table: UPDATE Salary FROM Actual Table WHERE
TABLE I ACTUAL-TABLE
Key
Emp_Name
Security#
Salary
1 2 3
Gib
Remand Carol
Encrypted Encrypted Encrypted
1200 1000 6000
. . .
. . .
.....
. . .
The algorithm interprets this query and transforms it as following: UPDATE Salary FROM Actual Table WHERE Key IN(SELECT
TABLE 2 ADDITIONAL TABLE
Key Encrypted Encrypted Encrypted V.
Decrypt_Function (Security#)
1112
Decrypt_Function ( [Additional table] . Key)
Security# 1111 1 1 12 1 1 13
ARCHITECTURE AND WORKING METHODOLOGY OF PROPOSED TECHNIQUE
Following is the architecture of the proposed system. Consider the architecture shown in the figure 1, it consists of three components. 1. User interface: It takes query from user
FROM
[Additional table]
WHERE
[Additional table] .Security#=1112)
In the case of above query, a user wants to update the salary record of that employee whose Security# is equal to 1112. This technique will search Security# in the Additional table, as the WHERE clause contains an encrypted column, subject to the condition if the user has clearance to Secure_Schema. The inner query searches the key(s) in the Additional table of those particular records which satisfY the query's condition criteria. After
280
that, keys are retu r n ed in the WHERE clause to the outer query. The outer query directly updates records based on the (primary) keys. The decryption function is called twice, once for the decryption of keys in the inner query from Additional table and second for decryption of the sensitive values in the outer query from the Actual_Table.
Update Data in Actual_Table directly
VI. ALGORITHM AND FLOWCHART OF PROPOSED TECHNIQUE
Following is the algorithmic steps of the proposed architecture.
1. [User Query] User issue query 2. [Check the Conditioned Column] It{the conditioned column is not encrypted) Goto step 3 Else if (Authorized User) Goto step 4 Else Goto step 5 3. [Update Data] Update data directly in Actual_Table Goto step 5 4. [passing Control to the Secure Schema] [Check for query match] If (no query match) then i. Display ("0 row(s) is updated") ii. Goto step 5 Else [Retrieval of Encrypted Keys] i. Retrieve the corresponding encrypted key(s) ii. Decrypt the key(s) iii. Update values from Actual_Table based on key(s) 5.Exit Fig. 2 Algorithm of proposed technique
VII. TESTING AND RESULTS
Fig. 3 Flowchart of proposed technique
The experiment was conducted on the TPC-E schema of TPC (Transaction Processing Performance Council) [13]. A table name CASH_TRANSACTION was used for testing purposes: the CASH_TRANSACTION table was taken to conduct experiments on Range type queries. Data for testing purposes was generated by the software "EGen" version 1.9.0, which is provided by TPC. The experimental results show that the proposed updation technique is faster than the full column decryption technique in case of exact match query. It is also obvious from Figure 4 that the technique is efficient for range type queries as well. For 2.27% of total data retrieved, the proposed technique gives an improvement of 89.3% over the full column decryption technique. For 15.87% of data retrieved in a query, the performance improvement is 82.9%
Range Type Query 70.0 60.0
_a_-
�
-+- Proposed Techniqu
50.0 40.0 30.0
____
/-
20.0 10.0 0.0
---
-2.3
5.7
9.0
Decrypting the Entire Column and Then Updating
12.5 15.9 19.3 21.5 25.0
Updated records in Precentage
Fig. 4 Experimental result for range type queries
281
Encryption - An Overview of Contemporary Challenges and Design Considerations," SIGMOD, vol. 38, pp. 29 - 34,September
Probability of False positive hits in different techniques 0.60
00.55
o
r---
0.50
+-----1
0.40
+-----1 +-----1
o
0.30
0.20
+----.::nrrs-l
o
00.10 0.10
0.00
I
Technique of Gao Feng(2009)
o
00.40
2009. [3)
Technique of Yong Zhang(2007) Technique of Yong Zhang(2008)
� I
[4)
Technique of U8nzhong liu(2009)
• Proposed Technique
L---L_.L---L-----'
noD
[5)
[6)
Fig. 5 Comparisons of different methods based on "false positive hits"
In our proposed technique, there is no false positive hits as the query decrypts and retrieves the required values only as per the given condition in WHERE clause. It is clear from the Figure 5 that other techniques retrieve unwanted values which is not acceptable in case of UPDATE query although it is acceptable in case of SELECT query. VIII.
CONCLUSION
This paper proposes an efficient technique to update encrypted data column without decrypting the entire column. Novelty of the proposed technique is that it is faster than the existing techniques because it decrypts only the required value and has no "false positive hits". REFERENCES [I)
[7)
[8)
2005.
L. Liu and J. Gai, "A Method of Query over Encrypted Data in Database" in International Conference on Computer Engineering and Technology,2009, pp. 23-27. [10) Z. Yong, L. Wei-xin, and N. Xia-mu, "A Method of Bucket Index over Encrypted Character Data in Database," in Proceedings of the
[9)
Third
E. Shmueli, R. Vaisenberg, Y. Elovici, and C. Glezer, "Database
Conference
on
International
Information
(llH-MSP 2007) -
Volume 01: IEEE Computer Society, 2007. [II) G. Feng and Z. Danfeng, "A Cryptograph Index Technology
Based on Wrong Hit Expectation,"
in IEEE International
Conference on Electronic Computer Technology, 2009, pp. 301305. [12) L. Lianzhong and G. Jingfen, "A Method of Query over Encrypted
Data in Database," in Proceedings of the 2009 International Conference on Computer Engineering and Technology - Volume
Third International Conference on Measuring Technology and [2)
International
Hiding and Multimedia Signal Processing
T. Feng, "The Security Mechanism of Network Database," in Mechatronics Automation, Shangshai, China, 2011, pp. 939-940.
L. Liu and J. Gai, "A method of query over encrypted data in database," in 2009 International Conference on Computer Engineering and Technology,2009, pp. 23-27. Y. Zhang, W. Li, and X. Niu, "A Secure Cipher Index Over Encrypted Character Data In Database " in Seventh International Conference on Machine Learning and CybernetiCS Kunming, 2008, pp. 1111-1116. W. Zheng-Fei Wang, Bai-Le Shi, "Storage and Query over Encrypted Character and Numerical Data in Database," in CIT 2005,2005, pp. 77-81. H. HacigiimiiS, B. R. Iyer, C. Li, and S. Mehrotra, "Executing SQL over Encrypted Data in the Database-Service-Provider Model," in ACM SIGMOD Madison, Wisconsin ACM New York, NY, USA, 2002, pp. 216-227. R Agrawal, J. Kiernan, R Srikant, and Y. Xu, "Order preserving encryption for numeric data," in ACMSIGMOD 2004 Paris, France: ACM New York, NY, USA, 2004,pp. 563 - 574. H. HaCgiimii and S. Mehrotra, "Efficient Key Updates in Encrypted Database Systems," Secure Data Management, pp. 1-15,
01: IEEE Computer Society, 2009. [13) TPC Benchmark Specification, http://www.tpc.org!, 2009.
282
