{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:20:34Z","timestamp":1760239234405,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2020,10,18]],"date-time":"2020-10-18T00:00:00Z","timestamp":1602979200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>With the rapid growth of smart devices and technological advancements in tracking geospatial data, the demand for Location-Based Services (LBS) is facing a constant rise in several domains, including military, healthcare and transportation. It is a natural step to migrate LBS to a cloud environment to achieve on-demand scalability and increased resiliency. Nonetheless, outsourcing sensitive location data to a third-party cloud provider raises a host of privacy concerns as the data owners have reduced visibility and control over the outsourced data. In this paper, we consider outsourced LBS where users want to retrieve map directions without disclosing their location information. Specifically, our paper aims to address the following problem: Given a user\u2019s location s, a target destination t, and a graph G stored in a cloud, can users retrieve the shortest path route from s to t in a privacy-preserving manner? Although there exist a few solutions to this problem, they are either inefficient or insecure. For example, existing solutions either leak intermediate results to untrusted cloud providers or incur significant costs on the end-user. To address this gap, we propose an efficient and secure solution based on homomorphic encryption properties combined with a novel data aggregation technique. We formally show that our solution achieves semantic security guarantees under the semi-honest model. Additionally, we provide complexity analysis and experimental results to demonstrate that the proposed protocol is significantly more efficient than the current state-of-the-art techniques.<\/jats:p>","DOI":"10.3390\/cryptography4040029","type":"journal-article","created":{"date-parts":[[2020,10,18]],"date-time":"2020-10-18T21:26:06Z","timestamp":1603056366000},"page":"29","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["ESPADE: An Efficient and Semantically Secure Shortest Path Discovery for Outsourced Location-Based Services"],"prefix":"10.3390","volume":"4","author":[{"given":"Bharath K.","family":"Samanthula","sequence":"first","affiliation":[{"name":"Department of Computer Science, Montclair State University, 1 Normal Avenue, Montclair, NJ 07043, USA"}]},{"given":"Divya","family":"Karthikeyan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Montclair State University, 1 Normal Avenue, Montclair, NJ 07043, USA"}]},{"given":"Boxiang","family":"Dong","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Montclair State University, 1 Normal Avenue, Montclair, NJ 07043, USA"}]},{"given":"K. Anitha","family":"Kumari","sequence":"additional","affiliation":[{"name":"Department of Information Technology, PSG College of Technology, Coimbatore, Tamil Nadu 641004, India"}]}],"member":"1968","published-online":{"date-parts":[[2020,10,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Bennett, J., Rokas, O., and Chen, L. (2017). Healthcare in the Smart Home: A Study of Past, Present and Future. Sustainability, 9.","DOI":"10.3390\/su9050840"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"678","DOI":"10.1109\/ACCESS.2015.2437951","article-title":"The Internet of Things for Health Care: A Comprehensive Survey","volume":"3","author":"Islam","year":"2015","journal-title":"IEEE Access"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"4418","DOI":"10.1109\/JIOT.2018.2814063","article-title":"Internet of Things for Smart Manufacturing System: Trust Issues in Resource Allocation","volume":"5","author":"Jeong","year":"2018","journal-title":"IEEE Internet Things J."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Fraga-Lamas, P., Fern\u00e1ndez-Caram\u00e9s, T.M., Su\u00e1rez-Albela, M., Castedo, L., and Gonz\u00e1lez-L\u00f3pez, M. (2016). A Review on Internet of Things for Defense and Public Safety. Sensors, 16.","DOI":"10.3390\/s16101644"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1080\/17489725.2018.1508763","article-title":"Location based services: Ongoing evolution and research agenda","volume":"12","author":"Huang","year":"2018","journal-title":"J. Locat. Based Serv."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/1325555.1325568","article-title":"Location-based services","volume":"51","author":"Junglas","year":"2008","journal-title":"Commun. ACM"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/MTAS.2007.335564","article-title":"Control, trust, privacy, and security: Evaluating location-based services","volume":"26","author":"Perusco","year":"2007","journal-title":"IEEE Technol. Soc. Mag."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"4778","DOI":"10.1109\/JIOT.2018.2820039","article-title":"Security and Privacy in Location-Based Services for Vehicular and Mobile Communications: An Overview, Challenges, and Countermeasures","volume":"5","author":"Asuquo","year":"2018","journal-title":"IEEE Internet Things J."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/978-981-10-8639-7_6","article-title":"Investigation of Privacy Issues in Location-Based Services","volume":"Volume 707","author":"Sa","year":"2019","journal-title":"Recent Findings in Intelligent Computing Techniques"},{"key":"ref_10","first-page":"149","article-title":"A Survey on Cloud Computing","volume":"Volume 654","author":"Aggarwal","year":"2018","journal-title":"Big Data Analytics"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Stuedi, P., Mohomed, I., and Terry, D. (2010, January 15\u201318). WhereStore: Location-based data storage for mobile devices interacting with the cloud. Proceedings of the 1st ACM Workshop on Mobile Cloud Computing & Services: Social Networks and Beyond, San Francisco, CA, USA.","DOI":"10.1145\/1810931.1810932"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Ghinita, G., Kalnis, P., Khoshgozaran, A., Shahabi, C., and Tan, K.-L. (2008, January 10\u201312). Private queries in location based services: Anonymizers are not necessary. Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada.","DOI":"10.1145\/1376616.1376631"},{"key":"ref_13","unstructured":"Yi, X., Paulet, R., Bertino, E., and Varadharajan, V. (4, January 31). Practical k nearest neighbor queries with location privacy. Proceedings of the IEEE 30th International Conference on Data Engineering, Chicago, IL, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Samanthula, B.K., Rao, F., Bertino, E., and Yi, X. (2015, January 13\u201315). Privacy-Preserving Protocols for Shortest Path Discovery over Outsourced Encrypted Graph Data. Proceedings of the IEEE International Conference on Information Reuse and Integration, San Francisco, CA, USA.","DOI":"10.1109\/IRI.2015.72"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Blanton, M., Steele, A., and Alisagari, M. (2013, January 7\u201310). Data-oblivious graph algorithms for secure computation and outsourcing. Proceedings of the 8th ACM SIGSAC Symposium on Information, Computer and Communications Security, Hangzhou, China.","DOI":"10.1145\/2484313.2484341"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"2305","DOI":"10.1007\/s11277-017-4299-8","article-title":"Privacy Preserving in Cloud Environment for Obstructed Shortest Path Query","volume":"96","author":"Zhang","year":"2020","journal-title":"Wirel. Pers. Commun."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","article-title":"Public-Key Cryptosystems Based on Composite Degree Residuosity Classes","volume":"Volume 1592","author":"Paillier","year":"1999","journal-title":"Advances in Cryptology\u2014EUROCRYPT"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., and Rackoff, C. (1985, January 6\u20138). The knowledge complexity of interactive proof-systems. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, Providence, RI, USA.","DOI":"10.1145\/22145.22178"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1017\/CBO9780511721656.004","article-title":"General Cryptographic Protocols","volume":"Volume 2","author":"Goldreich","year":"2004","journal-title":"Foundations of Cryptography"},{"key":"ref_20","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, MIT Press."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/978-3-642-24712-5_3","article-title":"Twin Clouds: Secure Cloud Computing with Low Latency","volume":"Volume 7025","author":"Bugiel","year":"2011","journal-title":"Communications and Multimedia Security"},{"key":"ref_22","unstructured":"Wang, B., Li, M., Chow, S.M., and Li, H. (2013, January 21\u201323). Computing encrypted cloud data efficiently under multiple keys. Proceedings of the 2013 IEEE Conference on Communications and Network Security, National Harbor, MD, USA."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1261","DOI":"10.1109\/TKDE.2014.2364027","article-title":"k-Nearest Neighbor Classification over Semantically Secure Encrypted Relational Data","volume":"27","author":"Samanthula","year":"2015","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Samanthula, B.K., Albehairi, S., and Dong, B. (2019, January 8\u201310). A Privacy-Preserving Framework for Collaborative Association Rule Mining in Cloud. Proceedings of the IEEE Cloud Summit, Washington, DC, USA.","DOI":"10.1109\/CloudSummit47114.2019.00025"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/2160158.2160159","article-title":"On the (im)possibility of obfuscating programs","volume":"59","author":"Barak","year":"2012","journal-title":"J. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Lee, K.C.K., Lee, W.-C., Leong, H., and Zheng, B. (2009, January 2\u20136). Navigational path privacy protection: Navigational path privacy protection. Proceedings of the 18th ACM Conference on Information and Knowledge Management, Hong Kong, China.","DOI":"10.1145\/1645953.1646041"},{"key":"ref_27","first-page":"393","article-title":"A Survey of Single-Database Private Information Retrieval: Techniques and Applications","volume":"Volume 4450","author":"Ostrovsky","year":"2007","journal-title":"Public Key Cryptography"},{"key":"ref_28","unstructured":"Kushilevitz, E., and Ostrovsky, R. (1997, January 19\u201322). Replication is not needed: Single database, computationally-private information retrieval. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, FL, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"692","DOI":"10.14778\/2212351.2212352","article-title":"Shortest path computation with no information leakage","volume":"5","author":"Mouratidis","year":"2012","journal-title":"Proc. VLDB Endow."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Mehrotra, S., Sharma, S., Ullman, J.D., Ghosh, D., Gupta, P., and Mishra, A. (2020). Panda: Partitioned Data Security on Outsourced Sensitive and Non-sensitive Data. arXiv.","DOI":"10.1109\/ICDE.2019.00064"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1109\/JIOT.2015.2469605","article-title":"EPLQ: Efficient Privacy-Preserving Location-Based Query over Outsourced Encrypted Data","volume":"3","author":"Li","year":"2015","journal-title":"IEEE Internet Things J."},{"key":"ref_32","unstructured":"Zhu, X., Ayday, E., and Vitenberg, R. (2019). A privacy-preserving framework for outsourcing location-based services to the cloud. IEEE Trans. Dependable Secur. Comput."},{"key":"ref_33","first-page":"35p","article-title":"A Survey on Homomorphic Encryption Schemes: Theory and Implementation","volume":"51","author":"Acar","year":"2018","journal-title":"ACM Comput. Surv."},{"key":"ref_34","unstructured":"Elmehdwi, Y., Samanthula, B.K., and Jiang, W. (April, January 31). Secure k-nearest neighbor query over encrypted data in outsourced environments. Proceedings of the IEEE 30th International Conference on Data Engineering, Chicago, IL, USA."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1017\/CBO9780511721656.002","article-title":"Encryption Schemes","volume":"Volume 2","author":"Goldreich","year":"2004","journal-title":"Foundations of Cryptography"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/3-540-44586-2_9","article-title":"A Generalisation, a Simpli.cation and Some Applications of Paillier\u2019s Probabilistic Public-Key System","volume":"Volume 1992","author":"Jurik","year":"2001","journal-title":"Public Key Cryptography Lecture Notes in Computer Science"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/4\/4\/29\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:23:25Z","timestamp":1760178205000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/4\/4\/29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,18]]},"references-count":36,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["cryptography4040029"],"URL":"https:\/\/doi.org\/10.3390\/cryptography4040029","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2020,10,18]]}}}