An Effective Statistical Model to Evaluate the Two-phase Query Algorithm in the Encrypted Database with A Secure Index Structure
Keywords:
Statistical model, two-phase query algorithm, database security, secure index structure
Abstract
Database security is essential for protecting sensitive data in the database from unauthorized access, manipulation, or theft. To access the encrypted data, the two-phase query algorithm controls and filters database queries to ensure that only authorized data is accessible. Traditional methods used qualitative analyses to evaluate the effectiveness of the algorithm and were unable to completely judge the degree of credibility. In this paper, a statistical model is proposed that provides quantitative analyses to evaluate the effectiveness of the two-phase query algorithm in the encrypted database with a secure index structure using three major statistical quantities, including completeness, effectiveness, and credibility degrees. From the experimental results conducted in various databases, the proposed model is proven to be efficient and suitable for evaluating the two-phase query algorithm. Moreover, the stability of the statistical quantities is also discussed in different query conditions.
References
[1] H. Hacigum ¨ us¸, B. Iyer, and S. Mehrotra. "Providing database ¨
as a service.", Proceedings 18th International Conference on
Data Engineering, pp. 29-38, 2002.
[2] E. Yuval, R. Waisenberg, E. Shmueli, and E. Gudes. "A
structure preserving database encryption scheme.", Secure
Data Management: VLDB 2004 Workshop, SDM 2004, pp.
28-40, 2004.
[3] E. Shmueli, R. Waisenberg, Y. Elovici, and E. Gudes. "Designing secure indexes for encrypted databases.", Data and
Applications Security XIX: 19th Annual IFIP WG 11.3 Working Conference on Data and Applications Security, pp. 54-68,
2005.
[4] X. Song, D. Wagner, and A. Perrig. "Practical techniques
for searches on encrypted data.", Proceeding 2000 IEEE
symposium on security and privacy, pp. 44-55, 2000.
[5] H. Hacigum ¨ us¸, B. Iyer, C. Li, and S. Mehrotra. "Executing ¨
SQL over encrypted data in the database-service-provider
model.", Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pp. 216-227, 2002.
[6] Z. F. Wang, J. Dai, W. Wang, and B. L. Shi. "Fast query over
encrypted character data in database.", Proceedings of International Conference on Distributed Computing and Internet
Technology, pp. 327-338, 2018.
[7] V. Deshpande, and D. Das. "Efficient searching over encrypted database: methodology and algorithms.", Proceedings
of 2008 International Conference on Machine Learning and
Cybernetics, pp. 1111-1116, 2008
[8] G. Liu, G. Yang, S. Bai, H. Wang, and Y. Xiang. "FASE: a fast
and accurate privacy-preserving multi-keyword top-k retrieval
scheme over encrypted cloud data.", IEEE Transactions on
Services Computing, 15 (2020): 1855-1867.
[9] H. J. Kim, H. Lee, Y. K. Kim, and J. W. Chang. "Privacypreserving k NN query processing algorithms via secure twoparty computation over encrypted database in cloud computing.", The Journal of Supercomputing, 78 (2022): 9245-9284.
[10] Y. Zhang, W. X. Li, and X. M. Niu. "Secure cipher index
over encrypted character data in database.", Proceedings of
2008 International Conference on Machine Learning and
Cybernetics, pp. 1111-1116, 2008.
[11] Z. Wu, G. Xu, Z. Yu, X. Yi, E. Chen, and Y. Zhang.
"Executing SQL queries over encrypted character strings in
the Database-As-Service model.", Knowledge-Based Systems,
35 (2012): 332-348.
[12] Sheng, B., and Q. Li. "Verifiable privacy-preserving range
query in two-tiered sensor networks.", Proceedings of EEE
INFOCOM 2008-The 27th Conference on Computer Communications, pp. 46-50, 2008.
[13] Goh, E. J. "Secure Indexes.", IACR, 1 (2003): 1-18.
[14] U. Kuhn. "Analysis of a database and index encryption ¨
scheme–problems and fixes.", Proceedings of Secure Data
Management: Third VLDB Workshop, pp. 146-159, 2006.
[15] D. Boneh and B. Waters. "Conjunctive, subset, and range
queries on encrypted data.", Proceedings of Theory of Cryptography: 4th Theory of Cryptography Conference, pp. 535-
554, 2007.
[16] H. A. Park, D. H. Lee, J. Zhan, and G. Blosser. "Efficient
keyword index search over encrypted documents of groups.",
Proceedings of 2008 IEEE International Conference on Intelligence and Security Informatics, pp. 225-229, 2008.
[17] M. S¸erban. "Methods to increase search performance for
encrypted databases.", Procedia Economics and Finance, 3
(2012): 1063-1068.
[18] S. Raghavendra, K. Meghana, P. A. Doddabasappa, C. M.
Geeta, R. Buyya, K. R. Venugopal, and L. M. Patnaik.
"Index generation and secure multi-user access control over
an encrypted cloud data.", Procedia Computer Science, 89
(2016): 293-300.
[19] W. Song, B. Wang, Q. Wang, Z. Peng, W. Lou, and Y.
Cui. "A privacy-preserved full-text retrieval algorithm over
encrypted data for cloud storage applications.", Journal of
Parallel and Distributed Computing, 99 (2017): 14-27.
[20] R. Refaie, A. A. Abd El-Aziz, N. Hamza, M. A. Mahmood, and H. Hefny. "A new efficient algorithm for executing queries over encrypted data.", Proceedings of 2015
International Conference on Computing, Communication and
Security, pp. 1-4, 2015.
[21] R. Xu, K. Morozov, Y. Yang, J. Zhou, and T. Takagi.
"Efficient outsourcing of secure k-nearest neighbour query
over encrypted database.", Computers & Security, 69 (2017):
65-83.
[22] G. Singh, A. Kaul, and S. Mehta. "Secure k-NN as a service
over encrypted data in multi-user setting.", Proceedings of
2018 IEEE 11th International Conference on Cloud Computing, pp. 154-161, 2018.
[23] J. Ye, Z. Xu, and Y. Ding. "mage search scheme over
encrypted database.", Future Generation Computer Systems,
87 (2018): 251-258.
as a service.", Proceedings 18th International Conference on
Data Engineering, pp. 29-38, 2002.
[2] E. Yuval, R. Waisenberg, E. Shmueli, and E. Gudes. "A
structure preserving database encryption scheme.", Secure
Data Management: VLDB 2004 Workshop, SDM 2004, pp.
28-40, 2004.
[3] E. Shmueli, R. Waisenberg, Y. Elovici, and E. Gudes. "Designing secure indexes for encrypted databases.", Data and
Applications Security XIX: 19th Annual IFIP WG 11.3 Working Conference on Data and Applications Security, pp. 54-68,
2005.
[4] X. Song, D. Wagner, and A. Perrig. "Practical techniques
for searches on encrypted data.", Proceeding 2000 IEEE
symposium on security and privacy, pp. 44-55, 2000.
[5] H. Hacigum ¨ us¸, B. Iyer, C. Li, and S. Mehrotra. "Executing ¨
SQL over encrypted data in the database-service-provider
model.", Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pp. 216-227, 2002.
[6] Z. F. Wang, J. Dai, W. Wang, and B. L. Shi. "Fast query over
encrypted character data in database.", Proceedings of International Conference on Distributed Computing and Internet
Technology, pp. 327-338, 2018.
[7] V. Deshpande, and D. Das. "Efficient searching over encrypted database: methodology and algorithms.", Proceedings
of 2008 International Conference on Machine Learning and
Cybernetics, pp. 1111-1116, 2008
[8] G. Liu, G. Yang, S. Bai, H. Wang, and Y. Xiang. "FASE: a fast
and accurate privacy-preserving multi-keyword top-k retrieval
scheme over encrypted cloud data.", IEEE Transactions on
Services Computing, 15 (2020): 1855-1867.
[9] H. J. Kim, H. Lee, Y. K. Kim, and J. W. Chang. "Privacypreserving k NN query processing algorithms via secure twoparty computation over encrypted database in cloud computing.", The Journal of Supercomputing, 78 (2022): 9245-9284.
[10] Y. Zhang, W. X. Li, and X. M. Niu. "Secure cipher index
over encrypted character data in database.", Proceedings of
2008 International Conference on Machine Learning and
Cybernetics, pp. 1111-1116, 2008.
[11] Z. Wu, G. Xu, Z. Yu, X. Yi, E. Chen, and Y. Zhang.
"Executing SQL queries over encrypted character strings in
the Database-As-Service model.", Knowledge-Based Systems,
35 (2012): 332-348.
[12] Sheng, B., and Q. Li. "Verifiable privacy-preserving range
query in two-tiered sensor networks.", Proceedings of EEE
INFOCOM 2008-The 27th Conference on Computer Communications, pp. 46-50, 2008.
[13] Goh, E. J. "Secure Indexes.", IACR, 1 (2003): 1-18.
[14] U. Kuhn. "Analysis of a database and index encryption ¨
scheme–problems and fixes.", Proceedings of Secure Data
Management: Third VLDB Workshop, pp. 146-159, 2006.
[15] D. Boneh and B. Waters. "Conjunctive, subset, and range
queries on encrypted data.", Proceedings of Theory of Cryptography: 4th Theory of Cryptography Conference, pp. 535-
554, 2007.
[16] H. A. Park, D. H. Lee, J. Zhan, and G. Blosser. "Efficient
keyword index search over encrypted documents of groups.",
Proceedings of 2008 IEEE International Conference on Intelligence and Security Informatics, pp. 225-229, 2008.
[17] M. S¸erban. "Methods to increase search performance for
encrypted databases.", Procedia Economics and Finance, 3
(2012): 1063-1068.
[18] S. Raghavendra, K. Meghana, P. A. Doddabasappa, C. M.
Geeta, R. Buyya, K. R. Venugopal, and L. M. Patnaik.
"Index generation and secure multi-user access control over
an encrypted cloud data.", Procedia Computer Science, 89
(2016): 293-300.
[19] W. Song, B. Wang, Q. Wang, Z. Peng, W. Lou, and Y.
Cui. "A privacy-preserved full-text retrieval algorithm over
encrypted data for cloud storage applications.", Journal of
Parallel and Distributed Computing, 99 (2017): 14-27.
[20] R. Refaie, A. A. Abd El-Aziz, N. Hamza, M. A. Mahmood, and H. Hefny. "A new efficient algorithm for executing queries over encrypted data.", Proceedings of 2015
International Conference on Computing, Communication and
Security, pp. 1-4, 2015.
[21] R. Xu, K. Morozov, Y. Yang, J. Zhou, and T. Takagi.
"Efficient outsourcing of secure k-nearest neighbour query
over encrypted database.", Computers & Security, 69 (2017):
65-83.
[22] G. Singh, A. Kaul, and S. Mehta. "Secure k-NN as a service
over encrypted data in multi-user setting.", Proceedings of
2018 IEEE 11th International Conference on Cloud Computing, pp. 154-161, 2018.
[23] J. Ye, Z. Xu, and Y. Ding. "mage search scheme over
encrypted database.", Future Generation Computer Systems,
87 (2018): 251-258.
Published
2025-10-11
Issue
Section
Regular Articles
