research-article

Privacy-preserving kNN query processing algorithms via secure two-party computation over encrypted database in cloud computing

Authors:

Hyeong-Jin Kim,

Jae-Woo ChangAuthors Info & Claims

The Journal of Supercomputing, Volume 78, Issue 7

Pages 9245 - 9284

https://doi.org/10.1007/s11227-021-04286-2

Published: 01 May 2022 Publication History

Abstract

Since studies on privacy-preserving database outsourcing have been spotlighted in a cloud computing, databases need to be encrypted before being outsourced to the cloud. Therefore, a couple of privacy-preserving kNN query processing algorithms have been proposed over the encrypted database. However, the existing algorithms are either insecure or inefficient. Therefore, in this paper we propose a privacy-preserving kNN query processing algorithm via secure two-party computation on the encrypted database. Our algorithm preserves both data privacy and query privacy while hiding data access patterns. For this, we propose efficient and secure protocols based on Yao’s garbled circuit. To achieve a high degree of efficiency in query processing, we also propose a parallel kNN query processing algorithm using encrypted random value pool. Through our performance analysis, we verify that our proposed algorithms outperform the existing ones in terms of a query processing cost.

References

[1]

Oh D, Kim I, Kim K, Lee SM, and Ro WW Highly secure mobile devices assisted with trusted cloud computing environments ETRI J 2015 37 2 348-358

[2]

Raja J and Ramakrishnan M Confidentiality-preserving based on attribute encryption using auditable access during encrypted records in cloud location J Supercomput 2020 76 8 6026-6039

[3]

Ahmad A, Ahmad M, Habib MA, Sarwar S, Chaudhry J, Latif MA, and Shahid M Parallel query execution over encrypted data in database-as-a-service (DaaS) J Supercomput 2019 75 4 2269-2288

[4]

Williams P, Sion R, Carbunar B (2008) Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In: Proceedings of the 15th ACM Conference on Computer and Communications Security, pp 139–148

[5]

Cui S, Belguith S, Zhang M, Asghar MR, Russello G (2018) Preserving access pattern privacy in sgx-assisted encrypted search. In: 2018 27th International Conference on Computer Communication and Networks (ICCCN). IEEE, pp 1–9

[6]

Mehmood A, Natgunanathan I, Xiang Y, Hua G, and Guo S Protection of big data privacy IEEE Access 2016 4 1821-1834

[7]

Pingley A, Zhang N, Fu X, Choi HA, Subramaniam S, Zhao W (2011) Protection of query privacy for continuous location based services. In: 2011 Proceedings IEEE INFOCOM. IEEE, pp 1710–1718

[8]

Eom CS, Lee C, Lee W, and Leung C Effective privacy preserving data publishing by vectorization Inf Sci 2020 527 311-328

[9]

Kaiping X, Zhu B, Yang Q, Gai N, Wei D, and Yu N InPPTD: a lightweight incentive-based privacy-preserving truth discovery for crowdsensing systems IEEE Internet Things J 2020 8 6 4305-4316

[10]

Kousika N, Premalatha K (2021) An improved privacy-preserving data mining technique using singular value decomposition with three-dimensional rotation data perturbation. J Supercomput:1–9

[11]

Carbunar B, Yu Y, Shi W, Pearce M, and Vasudevan V Query privacy in wireless sensor networks ACM Trans Sens Netw (TOSN) 2010 6 2 1-34

[12]

Veugen T, Blom F, de Hoogh SJ, and Erkin Z Secure comparison protocols in the semi-honest model IEEE J Sel Top Signal Process 2015 9 7 1217-1228

[13]

Youn TY, Jho NS, and Chang KY Design of additive homomorphic encryption with multiple message spaces for secure and practical storage services over encrypted data J Supercomput 2018 74 8 3620-3638

[14]

Islam MS, Kuzu M, Kantarcioglu M (2012) Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: Ndss, vol 20, p 12

[15]

Wu W, Xian M, Parampalli U, and Lu B February). Efficient privacy-preserving frequent itemset query over semantically secure encrypted cloud database In World Wide Web 2021 24 607-629

[16]

Wu W, Parampalli U, Liu J, and Xian M March). Privacy preserving k-nearest neighbor classification over encrypted database in outsourced cloud environments In World Wide Web 2018 22 101-123

[17]

Dai H, Ji Y, Yang G, Huang H, and Yi X A privacy-preserving multi-keyword ranked search over encrypted data in hybrid clouds In IEEE Access 2019 8 4895-4907

[18]

Wong WK, Cheung DWL, Kao B, Mamoulis N (2009) Secure kNN computation on encrypted databases. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of data, pp 139–152

[19]

Yiu ML, Ghinita G, Jensen CS, and Kalnis P Enabling search services on outsourced private spatial data VLDB J 2010 19 3 363-384

[20]

Hu H, Xu J, Ren C, Choi B (2011) Processing private queries over untrusted data cloud through privacy homomorphism. In: 2011 IEEE 27th International Conference on Data Engineering. IEEE, pp 601–612

[21]

Zhu Y, Xu R, Takagi T (2013) Secure k-NN computation on encrypted cloud data without sharing key with query users. In: Proceedings of the 2013 International Workshop on Security in Cloud Computing, pp 55–60

[22]

Elmehdwi Y, Samanthula BK, Jiang W (2014) Secure k-nearest neighbor query over encrypted data in outsourced environments. In: 2014 IEEE 30th International Conference on Data Engineering. IEEE, pp 664–675

[23]

Zhou L, Zhu Y, and Castiglione A Efficient k-NN query over encrypted data in cloud with limited key-disclosure and offline data owner Comput Secur 2017 69 84-96

[24]

Kim HI, Kim HJ, and Chang JW A secure kNN query processing algorithm using homomorphic encryption on outsourced database Data Knowl Eng 2019 123 101602

[25]

Yao ACC (1986) How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). IEEE, pp 162–167

[26]

Paillier P (1999) Public-key cryptosystems based on composite degree residuosity classes. In: International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, pp 223–238

[27]

Camenisch J, Chandran N, Shoup V (2009) A public key encryption scheme secure against key dependent chosen plaintext and adaptive chosen ciphertext attacks. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, pp. 351–368

[28]

Cambareri V, Mangia M, Pareschi F, Rovatti R, and Setti G On known-plaintext attacks to a compressed sensing-based encryption: a quantitative analysis IEEE Trans Inf Forensics Secur 2015 10 10 2182-2195

[29]

Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57

[30]

Daemen J, Rijmen V (1999) AES proposal: Rijndael

[31]

Yao B, Li F, Xiao X (2013) Secure nearest neighbor revisited. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, pp 733–744

[32]

Hazay C and Lindell Y Efficient secure two-party protocols: Techniques and constructions 2010 Springer

[33]

Tsai WT, Sun X, Balasooriya J (2010) Service-oriented cloud computing architecture. In: 2010 Seventh International Conference on Information Technology: New Generations. IEEE, pp 684–689

[34]

Jadeja Y, Modi K (2012) Cloud computing-concepts, architecture and challenges. In: 2012 International Conference on Computing, Electronics and Electrical Technologies (ICCEET). IEEE, pp 877–880

[35]

Bahrami M, Singhal M (2015) The role of cloud computing architecture in big data. In: Information Granularity, Big Data, and Computational Intelligence. Springer, Cham, pp 275–295

[36]

Beniley JL Multidimensional binary seareh trees used for assoeiative searehing ACM Commun 1975 18 9 509-517

[37]

Robinson JT (1981) The KDB-tree: a search structure for large multidimensional dynamic indexes. In: Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, pp 10–18

[38]

Bugiel S, Nürnberger S, Sadeghi AR, Schneider T (2011) Twin clouds: Secure cloud computing with low latency. In: IFIP International Conference on Communications and Multimedia Security. Springer, Berlin, Heidelberg, pp 32–44

[39]

Liu A, Zhengy K, Liz L, Liu G, Zhao L, Zhou X (2015) Efficient secure similarity computation on encrypted trajectory data. In: 2015 IEEE 31st International Conference on Data Engineering. IEEE, pp 66–77

[40]

Goldreich O (1998) Secure multi-party computation. Manuscript. Preliminary version 78

[41]

Michael Bain (2021) Chess (King-Rook vs. King) Data Set. http://archive.ics.uci.edu/ml/datasets/Chess+%28King-Rook+vs.+King%29. Accessed 21 April 2021

[42]

Ayesha S, Muhammad K, and Talib R Overview and comparative study of dimensionality reduction techniques for high dimensional data Inf Fusion 2020 59 44-58

[43]

Reddy G, Reddy M, Lakshmanna K, Kaluri R, Rajput DS, Srivastava G, and Baker T Analysis of dimensionality reduction techniques on big data IEEE Access 2020 8 54776-54788

Cited By

Li ZWang HZhang SZhang WLu R(2024)SecKNN: FSS-Based Secure Multi-Party KNN Classification Under General Distance FunctionsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.333794019(1326-1341)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2023.3337940
Rahmani PFakhrahmad STaheri M(2022)New attacks on secret sharing-based data outsourcing: toward a resistant schemeThe Journal of Supercomputing10.1007/s11227-022-04467-778:14(15749-15785)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11227-022-04467-7

Index Terms

Privacy-preserving kNN query processing algorithms via secure two-party computation over encrypted database in cloud computing

Index terms have been assigned to the content through auto-classification.

Recommendations

Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...
A secure kNN query processing algorithm using homomorphic encryption on outsourced database
Abstract
With the adoption of cloud computing, database outsourcing has emerged as a new platform. Due to the serious privacy concerns associated with cloud computing, databases must be encrypted before being outsourced to the cloud. Therefore, ...
A Secure and Efficient kNN Classification Algorithm Using Encrypted Index Search and Yao’s Garbled Circuit over Encrypted Databases
Future Data and Security Engineering
Abstract
Database outsourcing has been popular according to the development of cloud computing. Databases need to be encrypted before being outsourced to the cloud so that they can be protected from adversaries. However, the existing kNN classification ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Supercomputing

The Journal of Supercomputing Volume 78, Issue 7

May 2022

1327 pages

ISSN:0920-8542

Issue’s Table of Contents

© The Author(s) 2022.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 May 2022

Accepted: 21 December 2021

Author Tags

Qualifiers

Research-article

Funding Sources

National Research Foundation of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li ZWang HZhang SZhang WLu R(2024)SecKNN: FSS-Based Secure Multi-Party KNN Classification Under General Distance FunctionsIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.333794019(1326-1341)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TIFS.2023.3337940
Rahmani PFakhrahmad STaheri M(2022)New attacks on secret sharing-based data outsourcing: toward a resistant schemeThe Journal of Supercomputing10.1007/s11227-022-04467-778:14(15749-15785)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11227-022-04467-7

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents