{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T06:53:03Z","timestamp":1767855183526,"version":"3.49.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,1,17]],"date-time":"2022-01-17T00:00:00Z","timestamp":1642377600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,17]],"date-time":"2022-01-17T00:00:00Z","timestamp":1642377600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2019R1I1A3A01058375"],"award-info":[{"award-number":["2019R1I1A3A01058375"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:italic>k<\/jats:italic>NN 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 <jats:italic>k<\/jats:italic>NN 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\u2019s garbled circuit. To achieve a high degree of efficiency in query processing, we also propose a parallel <jats:italic>k<\/jats:italic>NN 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.<\/jats:p>","DOI":"10.1007\/s11227-021-04286-2","type":"journal-article","created":{"date-parts":[[2022,1,17]],"date-time":"2022-01-17T12:02:53Z","timestamp":1642420973000},"page":"9245-9284","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Privacy-preserving kNN query processing algorithms via secure two-party computation over encrypted database in cloud computing"],"prefix":"10.1007","volume":"78","author":[{"given":"Hyeong-Jin","family":"Kim","sequence":"first","affiliation":[]},{"given":"Hyunjo","family":"Lee","sequence":"additional","affiliation":[]},{"given":"Yong-Ki","family":"Kim","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0037-6812","authenticated-orcid":false,"given":"Jae-Woo","family":"Chang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,17]]},"reference":[{"issue":"2","key":"4286_CR1","doi-asserted-by":"publisher","first-page":"348","DOI":"10.4218\/etrij.15.0114.0397","volume":"37","author":"D Oh","year":"2015","unstructured":"Oh D, Kim I, Kim K, Lee SM, Ro WW (2015) Highly secure mobile devices assisted with trusted cloud computing environments. ETRI J 37(2):348\u2013358","journal-title":"ETRI J"},{"issue":"8","key":"4286_CR2","doi-asserted-by":"publisher","first-page":"6026","DOI":"10.1007\/s11227-019-03111-1","volume":"76","author":"J Raja","year":"2020","unstructured":"Raja J, Ramakrishnan M (2020) Confidentiality-preserving based on attribute encryption using auditable access during encrypted records in cloud location. J Supercomput 76(8):6026\u20136039","journal-title":"J Supercomput"},{"issue":"4","key":"4286_CR3","doi-asserted-by":"publisher","first-page":"2269","DOI":"10.1007\/s11227-019-02831-8","volume":"75","author":"A Ahmad","year":"2019","unstructured":"Ahmad A, Ahmad M, Habib MA, Sarwar S, Chaudhry J, Latif MA, Shahid M (2019) Parallel query execution over encrypted data in database-as-a-service (DaaS). J Supercomput 75(4):2269\u20132288","journal-title":"J Supercomput"},{"key":"4286_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013148","DOI":"10.1145\/1455770.1455790"},{"key":"4286_CR5","doi-asserted-by":"crossref","unstructured":"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\u20139","DOI":"10.1109\/ICCCN.2018.8487338"},{"key":"4286_CR6","doi-asserted-by":"publisher","first-page":"1821","DOI":"10.1109\/ACCESS.2016.2558446","volume":"4","author":"A Mehmood","year":"2016","unstructured":"Mehmood A, Natgunanathan I, Xiang Y, Hua G, Guo S (2016) Protection of big data privacy. IEEE Access 4:1821\u20131834","journal-title":"IEEE Access"},{"key":"4286_CR7","doi-asserted-by":"crossref","unstructured":"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\u20131718","DOI":"10.1109\/INFCOM.2011.5934968"},{"key":"4286_CR8","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/j.ins.2019.09.035","volume":"527","author":"CS Eom","year":"2020","unstructured":"Eom CS, Lee C, Lee W, Leung C (2020) Effective privacy preserving data publishing by vectorization. Inf Sci 527:311\u2013328","journal-title":"Inf Sci"},{"issue":"6","key":"4286_CR9","first-page":"4305","volume":"8","author":"X Kaiping","year":"2020","unstructured":"Kaiping X, Zhu B, Yang Q, Gai N, Wei D, Yu N (2020) InPPTD: a lightweight incentive-based privacy-preserving truth discovery for crowdsensing systems. IEEE Internet Things J 8(6):4305\u20134316","journal-title":"IEEE Internet Things J"},{"key":"4286_CR10","doi-asserted-by":"crossref","unstructured":"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\u20139","DOI":"10.1007\/s11227-021-03643-5"},{"issue":"2","key":"4286_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1689239.1689244","volume":"6","author":"B Carbunar","year":"2010","unstructured":"Carbunar B, Yu Y, Shi W, Pearce M, Vasudevan V (2010) Query privacy in wireless sensor networks. ACM Trans Sens Netw (TOSN) 6(2):1\u201334","journal-title":"ACM Trans Sens Netw (TOSN)"},{"issue":"7","key":"4286_CR12","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1109\/JSTSP.2015.2429117","volume":"9","author":"T Veugen","year":"2015","unstructured":"Veugen T, Blom F, de Hoogh SJ, Erkin Z (2015) Secure comparison protocols in the semi-honest model. IEEE J Sel Top Signal Process 9(7):1217\u20131228","journal-title":"IEEE J Sel Top Signal Process"},{"issue":"8","key":"4286_CR13","doi-asserted-by":"publisher","first-page":"3620","DOI":"10.1007\/s11227-016-1796-6","volume":"74","author":"TY Youn","year":"2018","unstructured":"Youn TY, Jho NS, Chang KY (2018) Design of additive homomorphic encryption with multiple message spaces for secure and practical storage services over encrypted data. J Supercomput 74(8):3620\u20133638","journal-title":"J Supercomput"},{"key":"4286_CR14","unstructured":"Islam MS, Kuzu M, Kantarcioglu M (2012) Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: Ndss, vol 20, p 12"},{"key":"4286_CR15","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/s11280-021-00863-w","volume":"24","author":"W Wu","year":"2021","unstructured":"Wu W, Xian M, Parampalli U, Lu B (2021) February). Efficient privacy-preserving frequent itemset query over semantically secure encrypted cloud database. In World Wide Web 24:607\u2013629","journal-title":"In World Wide Web"},{"key":"4286_CR16","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s11280-018-0539-4","volume":"22","author":"W Wu","year":"2018","unstructured":"Wu W, Parampalli U, Liu J, Xian M (2018) March). Privacy preserving k-nearest neighbor classification over encrypted database in outsourced cloud environments. In World Wide Web 22:101\u2013123","journal-title":"In World Wide Web"},{"key":"4286_CR17","doi-asserted-by":"publisher","first-page":"4895","DOI":"10.1109\/ACCESS.2019.2963096","volume":"8","author":"H Dai","year":"2019","unstructured":"Dai H, Ji Y, Yang G, Huang H, Yi X (2019) A privacy-preserving multi-keyword ranked search over encrypted data in hybrid clouds. In IEEE Access 8:4895\u20134907","journal-title":"In IEEE Access"},{"key":"4286_CR18","doi-asserted-by":"crossref","unstructured":"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\u2013152","DOI":"10.1145\/1559845.1559862"},{"issue":"3","key":"4286_CR19","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00778-009-0169-7","volume":"19","author":"ML Yiu","year":"2010","unstructured":"Yiu ML, Ghinita G, Jensen CS, Kalnis P (2010) Enabling search services on outsourced private spatial data. VLDB J 19(3):363\u2013384","journal-title":"VLDB J"},{"key":"4286_CR20","doi-asserted-by":"crossref","unstructured":"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\u2013612","DOI":"10.1109\/ICDE.2011.5767862"},{"key":"4286_CR21","doi-asserted-by":"crossref","unstructured":"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\u201360","DOI":"10.1145\/2484402.2484415"},{"key":"4286_CR22","doi-asserted-by":"crossref","unstructured":"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\u2013675","DOI":"10.1109\/ICDE.2014.6816690"},{"key":"4286_CR23","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.cose.2016.11.013","volume":"69","author":"L Zhou","year":"2017","unstructured":"Zhou L, Zhu Y, Castiglione A (2017) Efficient k-NN query over encrypted data in cloud with limited key-disclosure and offline data owner. Comput Secur 69:84\u201396","journal-title":"Comput Secur"},{"key":"4286_CR24","doi-asserted-by":"publisher","first-page":"101602","DOI":"10.1016\/j.datak.2017.07.005","volume":"123","author":"HI Kim","year":"2019","unstructured":"Kim HI, Kim HJ, Chang JW (2019) A secure kNN query processing algorithm using homomorphic encryption on outsourced database. Data Knowl Eng 123:101602","journal-title":"Data Knowl Eng"},{"key":"4286_CR25","doi-asserted-by":"crossref","unstructured":"Yao ACC (1986) How to generate and exchange secrets. In: 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). IEEE, pp 162\u2013167","DOI":"10.1109\/SFCS.1986.25"},{"key":"4286_CR26","doi-asserted-by":"crossref","unstructured":"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\u2013238","DOI":"10.1007\/3-540-48910-X_16"},{"key":"4286_CR27","doi-asserted-by":"crossref","unstructured":"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\u2013368","DOI":"10.1007\/978-3-642-01001-9_20"},{"issue":"10","key":"4286_CR28","doi-asserted-by":"publisher","first-page":"2182","DOI":"10.1109\/TIFS.2015.2450676","volume":"10","author":"V Cambareri","year":"2015","unstructured":"Cambareri V, Mangia M, Pareschi F, Rovatti R, Setti G (2015) On known-plaintext attacks to a compressed sensing-based encryption: a quantitative analysis. IEEE Trans Inf Forensics Secur 10(10):2182\u20132195","journal-title":"IEEE Trans Inf Forensics Secur"},{"key":"4286_CR29","doi-asserted-by":"crossref","unstructured":"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\u201357","DOI":"10.1145\/971697.602266"},{"key":"4286_CR30","unstructured":"Daemen J, Rijmen V (1999) AES proposal: Rijndael"},{"key":"4286_CR31","unstructured":"Yao B, Li F, Xiao X (2013) Secure nearest neighbor revisited. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE). IEEE, pp 733\u2013744"},{"key":"4286_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14303-8","volume-title":"Efficient secure two-party protocols: Techniques and constructions","author":"C Hazay","year":"2010","unstructured":"Hazay C, Lindell Y (2010) Efficient secure two-party protocols: Techniques and constructions. Springer"},{"key":"4286_CR33","doi-asserted-by":"crossref","unstructured":"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\u2013689","DOI":"10.1109\/ITNG.2010.214"},{"key":"4286_CR34","doi-asserted-by":"crossref","unstructured":"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\u2013880","DOI":"10.1109\/ICCEET.2012.6203873"},{"key":"4286_CR35","doi-asserted-by":"crossref","unstructured":"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\u2013295","DOI":"10.1007\/978-3-319-08254-7_13"},{"issue":"9","key":"4286_CR36","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Beniley","year":"1975","unstructured":"Beniley JL (1975) Multidimensional binary seareh trees used for assoeiative searehing. ACM Commun 18(9):509\u2013517","journal-title":"ACM Commun"},{"key":"4286_CR37","doi-asserted-by":"crossref","unstructured":"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\u201318","DOI":"10.1145\/582318.582321"},{"key":"4286_CR38","doi-asserted-by":"crossref","unstructured":"Bugiel S, N\u00fcrnberger 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\u201344","DOI":"10.1007\/978-3-642-24712-5_3"},{"key":"4286_CR39","doi-asserted-by":"crossref","unstructured":"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\u201377","DOI":"10.1109\/ICDE.2015.7113273"},{"key":"4286_CR40","unstructured":"Goldreich O (1998) Secure multi-party computation. Manuscript. Preliminary version 78"},{"key":"4286_CR41","unstructured":"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"},{"key":"4286_CR42","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.inffus.2020.01.005","volume":"59","author":"S Ayesha","year":"2020","unstructured":"Ayesha S, Muhammad K, Talib R (2020) Overview and comparative study of dimensionality reduction techniques for high dimensional data. Inf Fusion 59:44\u201358","journal-title":"Inf Fusion"},{"key":"4286_CR43","doi-asserted-by":"publisher","first-page":"54776","DOI":"10.1109\/ACCESS.2020.2980942","volume":"8","author":"G Reddy","year":"2020","unstructured":"Reddy G, Reddy M, Lakshmanna K, Kaluri R, Rajput DS, Srivastava G, Baker T (2020) Analysis of dimensionality reduction techniques on big data. IEEE Access 8:54776\u201354788","journal-title":"IEEE Access"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-021-04286-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-021-04286-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-021-04286-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T15:22:15Z","timestamp":1650381735000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-021-04286-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,17]]},"references-count":43,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["4286"],"URL":"https:\/\/doi.org\/10.1007\/s11227-021-04286-2","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,17]]},"assertion":[{"value":"21 December 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}